Data Structures – Single Linked Tables

Neither head nor middle insertion deletion efficiency O(N)
Running out of space, expansion has some consumption (especially off-site expansion)
Expansion logic, there may still be space (e.g. if 100 is full and you want to insert 110 data, expanding to 200 will waste 90 space)

Pros:

Tail plug tail delete fast enough
Random access and modification of subscripts

1.2 Concept and structure of a linked table

Sequential tables only need to know the address of the first element to have aA contiguous piece of physical space and the tail is defined by sizewhile the chained table in thePhysical space is not continuousRatherApply on DemandRelease of individual spaces, inter-spaceInterlinking with pointers. The end of the chain table space is defined with NULL. Data Structures - Single Linked Tables

Note: The address of the node coming out of the malloc is randomized.

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include <stdio.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;



int main()
{
	return 0;
}

From the diagram of a single linked table we know that it is havingmultinode linkageof a node implies that there is a structure in the node, then the node we point to thepointer on a gaugeThat’s what it should be.Structure pointer variable.（struct SListNode* next)

1.3 Printing Functions

on account ofpheadis pointing to the first node, so don’t change it easily, we can create another pointer to traverse the chain table.

void PrintSList(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

I’m sure many of you can’t understand whycur = cur->next; thisnextWhy is it still possible to go ahead and use it when it’s clearly not explicitly pointed to in the code?Actually, it’s in thecurWhen pointing to the first nodecur->nextis to fetch the structure’snextThe value of thenextWhat is stored is the address of the next structure.This makescurto point to the second node. As to whynextBeing able to store the address of the next node is all about what the assembly in the compiler is supposed to do (the computer automatically recognizes the instruction), so we won’t go into that too much.

Next, I’ll take you through a run-through of the simple chained table;

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include <stdio.h>
#include <stdlib.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void PrintSList(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

int main()
{
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	// Note! Here the node coming out of the malloc is a structure, so sizeof has to be substituted for the size of the structure as well.
	// Again, because it is received with a structure pointer, the forced type conversion is also used (SLTNode*).
	n1->data = 10;
	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	n2->data = 20;
	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	n3->data = 30;

	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;

	PrintSList(n1);
	return 0;
}

After seeing the simple chain table then next we have to enter the real full structure of the chain table, the old rules, first create 3 files.

1.4 Space functions

SLTNode* BuySlistNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

When we created the spatial function we later tested it:(There will be a difficulty though, how do we link these nodes together?) Data Structures - Single Linked Tables

Here we go ahead and link and analyze with header plugs:

When our chain table is not empty, theTo head plug you need to usenewnode This new node links plist to the first node pointed to by plist.Start by giving the address of the first node (pointed to by plist) to thenewnodeThis new node’snextat the new node, so that the new node is linked behind the first node, and then give the address of the new node to theplistinstruct sb. to do sth.plistWhat is pointed to is always the new first node. Note! Never swap the order, if the address of the new node newnode is given to plist first, then the original first node can’t be found by plist and becomes a wild pointer. When the chain table is empty，due toplistpoints to a null pointer, then when a new node is inserted, theplistThe pointer becomes the new node (the first node), and what the new node points to is the null pointer（newnode->next=NULL)。 Finally, we conclude that the two lines of code about header insertion newnode->next = plist and plist = newnode fit both cases perfectly, and do not need to be distinguished from each other by conditions.

Final Test:

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include "Slist.h"
#include <stdio.h>
#include <stdlib.h>


void TestSList1()
{
	int n = 0;
	printf("Please enter the length of the chained table:");
	scanf("%d", &n);
	printf("\n Please enter the value of each node in turn: \n");
	SLTNode* plist = NULL;
	for (int i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySlistNode(val);
		newnode->next = plist;
		plist = newnode;
		PrintSList(plist);
	}
	
}


int main()
{
	TestSList1();
	return 0;
}

1.5 The Tail-Plug Function (the most, most troublesome)

End insertion: definitely from the end.malloca new space, then the node it is on stores the inserted number first, then the address of the null pointer. But since it was inserted from the end.Well, we’ll have to find the tail on the original data., inserted from the back of the tail to become the end.

Many YouYouYou will mistakenly write the code as follows: (in fact, this is a big mistake) When we draw a physical diagram to analyze it, we know that if we create a new node and tail stops the loop because it points to a null pointer, but after we execute the last line of code: tail = newnode, tail does point to the new node.But we can see from the figure that the new node is not linked to the previous node! The previous node is still pointing to a null pointer. There are three local variables in this function:phead, newnode, tail. Out of scope all destroyed. Data 4 is not tail-inserted, theThis newly opened node was lost instead.The reason why the node where 4 is located will not be destroyed is because the node ismallocOpened up on the heap, unless you go to thefreeoff, or it would not have been destroyed. That’s why we bother tomallocA node thatIf you mess with the node out of scope inside the function alone it will be destroyed. Also don’t worry about destroying the pead and not being able to find the chain table.pheadIt’s a formal parameter. We still have it out there.pilst(real parameter) also has pointers.

Finally we will test for insertion: (tail plug 1000)

// Tail insertion function
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySlistNode(x);
	SLTNode* tail = phead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}

void TestSList1()
{
	int n = 0;
	printf("Please enter the length of the chained table:");
	scanf("%d", &n);
	printf("\n Please enter the value of each node in turn: \n");
	SLTNode* plist = NULL;
	for (int i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySlistNode(val);
		newnode->next = plist;
		plist = newnode;
		PrintSList(plist);
	}
	SLTPushBack(plist, 1000);
	PrintSList(plist);
	
}

1.5.1 The most critical part of the tail plug!

The front is a chained table tossed together first by various means and then tail-plugged. Now let’s test what happens when there is no chained table (empty chained table) and no nodes are tail-plugged.

//Modified tail insertion function
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySlistNode(x);
	
	if (phead == NULL)
	{
		phead = newnode;
	}
	else
	{
		SLTNode* tail = phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

The insertion fails as a result, why is this?

Let’s analyze a wave together:

When the if condition has finished executing leave the scope thepheadandnewnode variables are destroyed as before. This time is already different from the previous test!In test 1 there is already a chained table，Outside as a real reference plist is already pointing to the first node, in the case of tail-plugging only plist will always point to the first node.So instead, you don’t have to care about the pead that destroys it when it goes out of local scope.In test 1 the role of the head is more to allow the tail to point to the first node without problems, instead of trying to change the value of plist. And now that the chain table is empty in test 2, theThis means that the outside plist’s pointing to it is always a null pointer, and requires a Phead to pass the address of the new node for the outside plist to be able to point to it without problems.However, as soon as the pad leaves the scope, it will be destroyed and can’t play the role of passing the address, what should I do? In fact, the form parameter herepheadand real parametersplistIt’s still essentiallycall by value (computing)，pheadbutplistinitial recognitioninterim copychangepheadThe value of theplistof their purpose, but aren’t they all pointers? How can they not be changed? Next, I’ll show you a small case to understand~

Small cases:

void Swap1(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void Swap2(int** pp1, int** pp2)
{
	int* tmp = **pp1;
	**pp1 = **pp2;
	**pp2 = tmp;
}

int main()
{
	TestSList1();
	int a = 0;
	int b = 1;
	Swap1(&a, &b);
	int* x1 = &a;
	int* x2 = &b;
	Swap1(x1, x2);
	return 0;
}
In the above code, theIf the value of int needs to be changed, then you have to pass int* to receive it. What if the value to be changed is int*? Then you have to use int** to receive it.We are passing x1,x2 two values of type int* in an empty chain table, but receiving them in int*, so how can x1,x2 be changed~

So in order for the outside plist to be able to change, first pass the address of the plist, then use the secondary pointer to receive it~

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
}

int main()
{
	//TestSList1();
	TestSList2();
	//int a = 0;
	//int b = 1;
	//Swap1(&a, &b);
	//int* x1 = &a;
	//int* x2 = &b;
	//Swap1(x1, x2);
	return 0;
}

//Modified tail insertion function
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySlistNode(x);
	
	if (*pphead == NULL)
	{
        //change the pointer to the structure with a secondary pointer
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
        //change structure (next) with structure pointer (tail)
		tail->next = newnode;
	}
}

Now the situation has changed and ourppheadis directed atplist, and*ppheadIt becomes de-quoting the address, that is, going to see theplistThe address stored inside, dereferenced to find theplistThe address stored in it is empty, then thenewnodeaddress is passed in for the purpose of an address-passing call.

why then?tailWhat about not using secondary pointers? Well, first of alltail(a pointer to a structure) points to a structure thattail->nextis a member inside the structure, and for us to make changes to the structure, we use the structure pointer.

The hardest part is over, and I’m sure you’ll be able to master the rest of the content with ease!

1.6 Header Interpolation Functions

After the complicated baptism of the tail-plug function, does that head-plug function still need a secondary pointer? It’s definitely needed. Tail insertion is only necessary to use the secondary pointer when there is an empty linked table.That head plug can require a secondary pointer every time.

The tail plug needs to determine whether the chain table is empty or not, because one side is changing the structure and the other side is changing the structure pointer. The head insertion doesn’t need to determine whether the chain table is empty or not, it’s going to change the structure pointer anyway.

// Header insertion function
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
	SLTNode* newnode = BuySlistNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

Test it:

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	PrintSList(plist);
}

1.7 Tail Deletion Functions

As a question: do I need a secondary pointer for tail deletion?

It is true that we only need to pay attention to change the structure on the line, do not need to use the secondary pointer ~, but single we deleted to only the last node, there is no previous node to empty.So it is necessary to change the plist so that it points to NULL drops ~ so still need to use the secondary pointer Oh.

Haha did you realize that as long as you take this bite of the second level pointer, you’ll be able to say all the good things about the back of it ~ God stops the gods, Buddha stops the Buddhas ~.

in the event thatfreeoff the last space node, then its previous node becomes a wild pointer since the space of the stored address has been lost, then the pointer to the stored address becomes a wild pointer.So we need to make the address stored in the node in front of the tail a null pointer to make sure it is the tail deleted to become the new tail. Data Structures - Single Linked Tables

//End-deletion function
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead);
    // The purpose of the assertion here is because pphead points to the address of the plist, which always has something to point to.
    // Either points to NULL or to a chained table, so pphead cannot be null.
	// Empty
	assert(*pphead);
	// a node
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// a node以上
	else
	{
		SLTNode* tailpre = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailpre = tail;
			tail = tail->next;
		}
		free(tail);
		tailpre->next = NULL;
	}
}

There’s also a hard-to-read write-up: choose your own ~

//End-deletion function
void SLTPopBack(SLTNode** pphead)
{
	// Empty
	assert(*pphead);
	// a node
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// a node以上
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{

			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
	
	
		
	
}

The usual test:

void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);

	SLTPopBack(&plist);
	PrintSList(plist);

	SLTPopBack(&plist);
	PrintSList(plist);


}

1.8 Header Deletion Functions

The basic logic is to save the next nodenewheadand thenfreedrop the first node and finally letplist-orientednewhead.

//Header deletion function
void SLTPopFront(SLTNode** pphead)
{
    assert(pphead);
	// Empty
	assert(*pphead);
	//Non-empty
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
	
}

Test it:

void TestSList4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);

	SLTPopFront(&plist);
	PrintSList(plist);

	SLTPopFront(&plist);
	PrintSList(plist);

	SLTPopFront(&plist);
	PrintSList(plist);

}

1.9 Find Functions

// Find function
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

The lookup function can also serve to modify values

1.10 Insert x function before pos

First assert violently to avoid the case where the chain table is empty.Second, when we want to insert before the first node of the chain table, we can use the reuse of the header insertion function. So what do we need to pass into the header function at this point? From the figure, we can see that we end up with a header plug that modifies the followingplistpointing, so it is necessary to set theplistThe address of the person is passed on, and theppheadhappen to be pointing atplistaddress, so here you can pass thepphead。

As for insertion in other locations we can only findposThe previous pointer. Here we just need to pay attention to the deleted node before and after the node connected to the line. In fact, this is the same operation as specifying an insertion, which is done via theprevandposto make the connection. Just change whatever you want after that, instead don’t worry about the order here.

//insert x before pos
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySlistNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}

}

Test it:

void TestSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsert(&plist, pos, 40);
	}
	PrintSList(plist);

}

1.12 Inserting the x function after pos

Since it is not possible to implement header insertion in this function (it is not possible to change the plist), there is no need to pass a header pointer for this function to receive. Data Structures - Single Linked Tables

The function only needs one thing to be noted, don’t start by adding a new function to thepos—>nextdeposit (e.g. in a bank account)newnodeaddress, which would lose the originald3address, resulting in thenewnode—>nextPointing to yourself creates a deadly cycle.

// Insert x after pos
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySlistNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

Test it:

void TestSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsertAfter(pos, 3);
	}
	PrintSList(plist);

}

1.13 Delete Pos Position Function

There are two things to note about this function:

Need to record pointer before pos
Header deletion needs to be handled separately, by directly reusing the header deletion function (which would then need to receive the plist to change where it points)

//Delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		{
			while (prev->next != pos)
			{
				prev = prev->next;
			}
			prev->next = pos->next;
			free(pos);
		}
	}
}

Test it.

void TestSList7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTErase(&plist,pos);
        pos = NULL;
        // Remember to empty the pos when you're done with it, otherwise it'll keep pointing to the original position.
	}
	PrintSList(plist);

}

1.14 Delete the last position of pos function

//Delete the last position of pos
void SLTInsertErase(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//If pos points to the tail node, it's meaningless
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}

Test it:


void TestSList8()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTEraseAfter(pos);
		pos = NULL;
	}
	PrintSList(plist);

}

1.15 Mini-Tests

As shown in the figure, there is no way for us to find the header pointer without giving theposThe pointer in front of it doesn’t work as a link.posThe role of the latter node.

We can putd2value is given to the precedingd1Then letpos->next-orientedd2The address of the node following the address, and thenfreeoffd2Just fine, but this has the drawback that when theposWhen pointing to the tail node, there is no value after it to swap with.

III. Full code

#pragma once
//Slist.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


//Printing Functions
void PrintSList(SLTNode* phead);

//space functions
SLTNode* BuySlistNode(SLTDataType x);

// Tail insertion function
void  SLTPushBack(SLTNode** pphead, SLTDataType x);

// Header insertion function
void  SLTPushFront(SLTNode** pphead, SLTDataType x);

//End-deletion function
void  SLTPopBack(SLTNode** pphead);

//Header deletion function
void  SLTPopFront(SLTNode** pphead);

// Find function
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//insert x before pos
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

// Insert x after pos
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//Delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos);

//Delete the last position of pos
void SLTEraseAfter(SLTNode* pos);

———————————————————————————————————————————

#define _CRT_SECURE_NO_WARNINGS 1
//Slist.c
#include "Slist.h"

//Printing Functions
void PrintSList(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//space functions
SLTNode* BuySlistNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

coda function (math.)
//SLTNode* SLTPushBack(SLTNode* phead, SLTDataType x)
//{
//	SLTNode* newnode = BuySlistNode(x);
//	SLTNode* tail = phead;
//	while (tail->next != NULL)
//	{
//		tail = tail->next;
//	}
//	tail->next = newnode;
//}

//修改后的coda function (math.)
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySlistNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

// Header insertion function
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySlistNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//End-deletion function
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
		// The purpose of the assertion here is because pphead points to the address of the plist, which always has something to point to.
		// Either points to NULL or to a chained table, so pphead cannot be null.
	// Empty
	assert(*pphead);
	// a node
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// a node以上
	else
	{
		SLTNode* tailpre = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tailpre = tail;
			tail = tail->next;
		}
		free(tail);
		tailpre->next = NULL;
	}
}

truncation function (math.)
//SLTNode* SLTPopBack(SLTNode** pphead)
//{
//	// Empty
//	assert(*pphead);
//	// a node
//	if ((*pphead)->next != NULL)
//	{
//		free(*pphead);
//		*pphead = NULL;
//	}
//	// a node以上
//	else
//	{
//		SLTNode* tail = *pphead;
//		while (tail->next->next)
//		{
//
//			tail = tail->next;
//		}
//		free(tail->next);
//		tail->next = NULL;
//	}
//	


//Header deletion function
void  SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	// Empty
	assert(*pphead);
	//Non-empty
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;

}

// Find function
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//insert x before pos
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySlistNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}

}

Delete x after pos
//void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
//{
//	assert(pos);
//	SLTNode* after = pos->next;
//	while (after->data != x)
//	{
//		after = after->next;
//	}
//	pos->next = after->next;
//	free(after);
//	pos->next = after;
//	
//}

// Insert x after pos
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySlistNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

//Delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		{
			while (prev->next != pos)
			{
				prev = prev->next;
			}
			prev->next = pos->next;
			free(pos);
		}
	}
}

//Delete the last position of pos
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//If pos points to the tail node, it's meaningless
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}

——————————————————————————————————————————

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include "Slist.h"
#include <stdio.h>
#include <stdlib.h>


void TestSList1()
{
	int n = 0;
	printf("Please enter the length of the chained table:");
	scanf("%d", &n);
	printf("\n Please enter the value of each node in turn: \n");
	SLTNode* plist = NULL;
	for (int i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySlistNode(val);
		newnode->next = plist;
		plist = newnode;
		PrintSList(plist);
	}
	SLTPushBack(plist, 1000);
	PrintSList(plist);
	
}

//void Swap1(int* p1, int* p2)
//{
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//}
//
//void Swap2(int** p1, int** p2)
//{
//	int* tmp = **p1;
//	**p1 = **p2;
//	**p2 = tmp;
//}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	PrintSList(plist);
}
void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);

	SLTPopBack(&plist);
	PrintSList(plist);

	SLTPopBack(&plist);
	PrintSList(plist);


}
void TestSList4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);

	SLTPopFront(&plist);
	PrintSList(plist);

	SLTPopFront(&plist);
	PrintSList(plist);

	SLTPopFront(&plist);
	PrintSList(plist);

}

void TestSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsert(&plist, pos, 40);
	}
	PrintSList(plist);

}

void TestSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsertAfter(pos, 3);
	}
	PrintSList(plist);

}
void TestSList7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTErase(&plist,pos);
		pos = NULL;
	}
	PrintSList(plist);

}


void TestSList8()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	PrintSList(plist);
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTEraseAfter(pos);
		pos = NULL;
	}
	PrintSList(plist);

}

int main()
{
	//TestSList1();
	//TestSList2();
	TestSList8();
	//int a = 0;
	//int b = 1;
	//Swap1(&a, &b);
	//int* x1 = &a;
	//int* x2 = &b;
	//Swap1(x1, x2);
	return 0;
}

IV. Concluding remarks

Although the single chained table to use up quite dwarfs haha, but we usually oj question most of the single chained table as an example, it is because of their own defects to facilitate the question well ~ single chained table will also be on the back of the hash map to understand to play a supporting role in the effect. Finally, thank you for watching, friends can learn new knowledge is the amount of honor, look forward to our next meeting~!

Data Structures – Single Linked Tables

II. Chained table representation and implementation (single linked tables)

1.1 Advantages and disadvantages of sequential tables

1.2 Concept and structure of a linked table

1.3 Printing Functions

1.4 Space functions

1.5 The Tail-Plug Function (the most, most troublesome)

1.5.1 The most critical part of the tail plug!

1.6 Header Interpolation Functions

1.7 Tail Deletion Functions

1.8 Header Deletion Functions

1.9 Find Functions

1.10 Insert x function before pos

1.12 Inserting the x function after pos

1.13 Delete Pos Position Function

1.14 Delete the last position of pos function

1.15 Mini-Tests

III. Full code

IV. Concluding remarks

Recommended Today

vivado Error Summary 1 — WARING:[Labtools 27-3361] the debug hub core was not detected make sure the clock