单链表详解(由浅入深，含有源代码，带你玩转单链表和二级指针)

单链表–开始发车💨

🔰 一.单连表的基本构造

💢引言

如下图，通过下面这个图我们可以看出，单链表由每个个节点组成，每个节点包含两个域：数据域和指针域。数据域存储数据，指针域将每个节点链接起来。所以第一步我先将节点的结构定义出来。

🕐 1.节点结构的定义

typedef int ElemData;  //ElemData的数据类型根据存储数据类型而定

typedef struct SListNode
{
	ElemData data;
	struct SListNode* next;
}SLTNode;

1
2
3
4
5
6
7
8

🕑2.创建节点

💢引言

节点的结构定义好了之后，我们需要创建一个个节点，那我们能不能像下面这样的方式创建一个个节点呢？
void TextSList1() { SLTNode n1; SLTNode n2; SLTNode n3; }答案是肯定不行的，你这样创建的变量n1、n2和n3存储在栈帧上，一旦出了TextSList1()这个自定义函数，这三个节点就被销毁了，到时候你想要调用这三个节点是不可能的。我们创建的节点必须是在程序结束后才能销毁或者是我们自己来销毁，这个时候需要用到malloc这个函数在堆上为节点申请空间，节点的创建具体的代码请看下面。

SLTNode* BuySListNode(ElemData x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));//用malloc函数在堆上申请空间
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
1
2
3
4
5
6
7

🕒3.打印函数

链表创建好了之后，以及后续对单链表一些基本功能的编写，都需要检测一下这些功能和单链表的创建是否存在Bug和漏洞，当然你也可以进行调试，但是我们第一步都是进行打印，根据打印的数据也找不到问题所在，再进一步进行调试。

void SListPrint(SLTNode* Plist)
{

	SLTNode* cur = Plist;
	while (cur != NULL)
	{
		//printf("[%d|%p]->", cur->data, cur->next);  //打印数据和地址
		printf("%d->", cur->data);    //只打印数据
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

🕓4.先创建一个简单链表玩玩

前面我们已经创建了节点，但是我们并不知道这样创建是否合理，能不能打印，那就让我们先创建一个简单的链表来玩一玩吧，检测一下这个节点创建函数行不行。

逻辑图

SLTNode* BuySListNode(ElemData x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

SLTNode* CreatSListNode(int n)
{
	SLTNode* Phead, * Ptail;   //头尾指针
	Phead = Ptail = NULL;
	for (int i = 0;i < n;i++)
	{
		SLTNode* newNode = BuySListNode(i);
		if (Phead == NULL)
		{
			Phead = Ptail = newNode;
		}
		else
		{
			Ptail->next = newNode;
			Ptail = newNode;
		}
	}
	return Phead;
}
void TextSList1()
{
	SLTNode* Plist = CreatSListNode(5);
	SListPrint(Plist);
}
int main()
{
     TextSList1();
     return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

运行结果图

根据运行结果图我们可以看出，前面节点的创建是没有问题的。

🔰二.单链表的基本功能

🕔1.尾插

这里尾插我们采用的是调用二级指针来实现的，当然你也可以采用一级去实现尾插，但是你每次必须用一个指针去接收尾插之后链表的头节点的地址，否则就会出现一个Bug漏洞；比如当你手上的链表为空链表时，进行尾插，你用尾插函数改变尾插函数中的头指针的值，并不会影响传过来的头指针里面的值，相当于你这个尾插函数形同虚设，有和没有没啥区别，因为形参的改变不会影响实参。

错误的代码

//错误示范，这个代码存在一个Bug，当PPlist=NULL时，无法正常插入
void SListPushBack(SLTNode* PPlist, ElemData x)
{
	SLTNode* newNode = BuySListNode(x);
	if (PPlist == NULL)
	{
		  PPlist = newNode;
	}
	else
	{
			SLTNode * PPtail;
			PPtail = PPlist;
		while (PPtail->next != NULL)
		{
			PPtail = PPtail->next;
		}
	}
	PPtail->next = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

错误代码的测试

void SListPushBack(SLTNode* PPlist, ElemData x)
{
	SLTNode* newNode = BuySListNode(x);
	if (PPlist == NULL)
	{
		  PPlist = newNode;
	}
	else
	{
			SLTNode * PPtail;
			PPtail = PPlist;
		while (PPtail->next != NULL)
		{
			PPtail = PPtail->next;
		}
	}
	PPtail->next = newNode;
}
void TextSList2()
{
	
	SLTNode* Plist =NULL;  

	SListPushBack(Plist, 1);
	SListPushBack(Plist, 2);
	SListPushBack(Plist, 3);
	SListPushBack(Plist, 4);
	SListPushBack(Plist, 5);

	SListPrint(Plist);
}
int main()
{
     TextSList2();
     return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

运行结果图

从运行结果图我们可以知道，当单链表为空时，这段代码并不能实现尾插功能。

逻辑图解释

正确的代码

void SListPushBack(SLTNode** PPlist, ElemData x)
{
	
		SLTNode* newNode = BuySListNode(x);
	if (*PPlist == NULL)
	{
		*PPlist = newNode;
	}
	else
	{
		SLTNode* PPtail;
		PPtail = *PPlist;
		while (PPtail->next != NULL)
		{
			PPtail = PPtail->next;
		}
		PPtail->next = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

功能的测试

void SListPushBack(SLTNode** PPlist, ElemData x)
{
	
		SLTNode* newNode = BuySListNode(x);
	if (*PPlist == NULL)
	{
		*PPlist = newNode;
	}
	else
	{
		SLTNode* PPtail;
		PPtail = *PPlist;
		while (PPtail->next != NULL)
		{
			PPtail = PPtail->next;
		}
		PPtail->next = newNode;
	}
}

void TextSList3()
{

	SLTNode* Plist = NULL;   //用这个节点可以写一篇博客

	SListPushBack(&Plist, 1);
	SListPushBack(&Plist, 2);
	SListPushBack(&Plist, 3);
	SListPushBack(&Plist, 4);
	SListPushBack(&Plist, 5);

	SListPrint(Plist);
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

运行结果图

🕕2.尾删

采用二级指针

代码接口

void SListPopBack(SLTNode** PPlist)
{
	assert(*PPlist);   //断言，当链表为空时不再进行尾删
	if ((*PPlist)->next == NULL)
	{
		free(*PPlist);
		(*PPlist) = NULL;
	}
	else
	{
		SLTNode* ptail;
		ptail = *PPlist;
		while (ptail->next->next != NULL)
		{
			ptail = ptail->next;
		}
		SLTNode* q = ptail->next;
		free(q);
		ptail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

图解带你弄懂二级指针的调用
不管是一级指针还是二级指针，它们也都是变量有自己的变量名、存储空间的大小、存储的内容、地址和类型。>

功能测试

void SListPopBack(SLTNode** PPlist)
{
	assert(*PPlist);
	if ((*PPlist)->next == NULL)
	{
		free(*PPlist);
		(*PPlist) = NULL;
	}
	else
	{
		SLTNode* ptail;
		ptail = *PPlist;
		while (ptail->next->next != NULL)
		{
			ptail = ptail->next;
		}
		SLTNode* q = ptail->next;
		free(q);
		ptail->next = NULL;
	}
}

void TextSList4()
{

	SLTNode* Plist = NULL;   
	
	SListPushBack(&Plist, 1);
	SListPushBack(&Plist, 2);
	SListPushBack(&Plist, 3);
	SListPushBack(&Plist, 4);
	SListPushBack(&Plist, 5);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
}
int main()
{
    TextSList4();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

运行结果图

🕖 3.头插

采用二级指针

逻辑图

代码接口

void SListPushFront(SLTNode** PPlist, ElemData x)
{
	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == NULL)
	{
		*PPlist = newNode;
	}
	else
	{
		newNode->next = *PPlist;
		*PPlist = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

功能测试

void SListPushFront(SLTNode** PPlist, ElemData x)
{
	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == NULL)
	{
		*PPlist = newNode;
	}
	else
	{
		newNode->next = *PPlist;
		*PPlist = newNode;
	}
}
void TextSList5()
{

	SLTNode* Plist = CreatSListNode(5); 
	SListPushFront(&Plist, 6);
	SListPrint(Plist);
}
int main()
{
    TextSList5();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

运行结果图

🕗4.头删

采用二级指针

逻辑图

代码接口

void SListPopFront(SLTNode** PPlist)
{
	assert(*PPlist);
	SLTNode* Phead = *PPlist;
	*PPlist = (*PPlist)->next;
	free(Phead);
}
1
2
3
4
5
6
7

功能测试

void SListPopFront(SLTNode** PPlist)
{
	assert(*PPlist);
	SLTNode* Phead = *PPlist;
	*PPlist = (*PPlist)->next;
	free(Phead);
}

void TextSList6()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);
}
int main()
{
   TextSList6();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

运行结果图

🕘 5.值查找

代码接口

SLTNode* SListDataFind(SLTNode* plist, ElemData x)
{

	SLTNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

功能测试

SLTNode* SListDataFind(SLTNode* plist, ElemData x)
{

	SLTNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

void TextSList7()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SLTNode* pos = SListDataFind(Plist, 3);
	if (pos!=NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
		printf("没找到\n");
	}

	pos = SListDataFind(Plist, 5);
	if(pos != NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
	printf("没找到\n");
	}
}
int main()
{
  TextSList7();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

运行结果图

🕙6.位置查找

代码接口

SLTNode* SListLocadeFind(SLTNode* plist, int pos)
{

	assert(pos >= 0);
	int i = 0;
	SLTNode* cur = plist;
	while (cur != NULL && i < pos)
	{
		cur = cur->next;
		i++;
	}
	if (cur == NULL)
		 return NULL;
	else
		return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

功能测试

SLTNode* SListLocadeFind(SLTNode* plist, int pos)
{

	assert(pos >= 0);
	int i = 0;
	SLTNode* cur = plist;
	while (cur != NULL && i < pos)
	{
		cur = cur->next;
		i++;
	}
	if (cur == NULL)
		 return NULL;
	else
		return cur;
}
void TextSList8()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);
	SLTNode* pos = SListLocadeFind(Plist, 3);
	if (pos!=NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
		printf("没找到\n");
	}
	pos = SListLocadeFind(Plist, 5);
	if(pos != NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
	printf("没找到\n");
	}
}
int main()
{
  TextSList8();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

运行结果图

###🕚 7.在pos位置的后面插入一个新节点

代码接口

void SListInsertAfter(SLTNode* pos, ElemData x)
{
	assert(pos);
	SLTNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

1
2
3
4
5
6
7
8

🕚8.删除pos位置后面一个节点

代码接口

oid SListErasetAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* q = pos->next;
		pos->next = q->next;
		free(q);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7和8功能测试

void SListInsertAfter(SLTNode* pos, ElemData x)
{
	assert(pos);   //断言
	SLTNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
void TextSList9()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SLTNode* pos = SListLocadeFind(Plist, 0);
	  if (pos != NULL)
		printf("%d\n", pos->data);

	 
		SListInsertAfter(pos, 8);
	    SListPrint(Plist);
	    SListErasetAfter(pos);
	    SListPrint(Plist);
}
int main()
{
      TextSList9();
      return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

运行结果图

🕚9.在pos位置前面插入一个新节点

采用二级指针

代码接口

void SListInsert(SLTNode** PPlist, SLTNode* pos, ElemData x)
{
	assert(pos);
	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == pos)
	{

		//SListPushFront(PPlist,  x);    //也可以调用我们的头插函数
		newNode->next = *PPlist;
		*PPlist = newNode;
	}
	else
	{
		SLTNode* Phead = *PPlist;
		while (Phead->next != pos)
		{
			Phead = Phead->next;
		}
		newNode->next = Phead->next;
		Phead->next = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🕝10.删除pos位置的节点

采用二级指针

代码接口

void SListErase(SLTNode** PPlist, SLTNode* pos)
{
	assert(pos);
	SLTNode* Ptail = *PPlist;
	if (*PPlist == pos)
	{

		//SListPopFront(PPlist);   //也可以调用头删函数
		*PPlist = (*PPlist)->next;
		free(*PPlist);
	}
	else
	{
		while (Ptail->next != pos)
		{
			Ptail = Ptail->next;
		}
		
		Ptail->next = Ptail->next->next;
		free(pos);
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

9和10功能测试

void SListInsert(SLTNode** PPlist, SLTNode* pos, ElemData x)
{
	assert(pos);
	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == pos)
	{

		//SListPushFront(PPlist,  x);    //也可以调用我们的头插函数
		newNode->next = *PPlist;
		*PPlist = newNode;
	}
	else
	{
		SLTNode* Phead = *PPlist;
		while (Phead->next != pos)
		{
			Phead = Phead->next;
		}
		newNode->next = Phead->next;
		Phead->next = newNode;
	}
}

void SListErase(SLTNode** PPlist, SLTNode* pos)
{
	assert(pos);
	if (*PPlist == pos)
	{

		//SListPopFront(PPlist);   //也可以调用头删函数
		*PPlist = (*PPlist)->next;
		free(*PPlist);
	}
	else
	{
	    SLTNode* Ptail = *PPlist;
		while (Ptail->next != pos)
		{
			Ptail = Ptail->next;
		}
		
		Ptail->next = Ptail->next->next;
		free(pos);
	}
	
}
void TextSList10()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SLTNode* pos = SListLocadeFind(Plist, 0);
	SListInsert(&Plist, pos, 80);
	SListPrint(Plist);

	 pos = SListDataFind(Plist, 3);
	 SListInsert(&Plist, pos, 700);
	 SListPrint(Plist);

	 pos = SListDataFind(Plist, 3);
	 SListErase(&Plist, pos);
	 SListPrint(Plist);

	 pos = SListLocadeFind(Plist, 0);
	 SListErase(&Plist, pos);
	 SListPrint(Plist);

	 pos = SListLocadeFind(Plist, 0);
	 SListErase(&Plist, pos);
	 SListPrint(Plist);

	 pos = SListLocadeFind(Plist, 0);
	 SListErase(&Plist, pos);
	 SListPrint(Plist);

	 pos = SListLocadeFind(Plist, 0);
	 SListErase(&Plist, pos);
	 SListPrint(Plist);

	 pos = SListLocadeFind(Plist, 0);
	 SListErase(&Plist, pos);
	 SListPrint(Plist);

}
int main()
{
    TextSList10();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

运行结果图

🔰三.源码

💥 1.头文件SList.h

#pragma once
#include 
#include 

typedef int ElemData;  //ElemData的数据类型根据存储数据类型而定

typedef struct SListNode
{
	ElemData data;
	struct SListNode* next;
}SLTNode;

//动态申请一个节点
SLTNode* BuySListNode(ElemData x);

//创建一个链表玩玩
SLTNode* CreatSListNode(int n);

//打印函数
void SListPrint(SLTNode* Plist);

//尾插
//void SListPushBack(SLTNode* PPlist, ElemData x);
void SListPushBack(SLTNode** PPlist, ElemData x);
//尾删
void SListPopBack(SLTNode** PPlist);

//头插
void SListPushFront(SLTNode** PPlist, ElemData x);
//头删
void SListPopFront(SLTNode** PPlist);

//值查找
SLTNode* SListDataFind(SLTNode* plist, ElemData x);
//位置查找
SLTNode* SListLocadeFind(SLTNode* plist, int pos);


//中间插入
//插入到后面
//存在Bug,当实参为NULL时，无法正常插入
void SListInsertAfter(SLTNode* pos, ElemData x);
//中间删除
//删除后面的一个数
//存在Bug,当只存在一个节点，无法正常删除
void SListErasetAfter(SLTNode* pos);

//在pos之前插入
void SListInsert(SLTNode** PPlist, SLTNode* pos, ElemData x);
//删除pos位置
void SListErase(SLTNode** PPlist, SLTNode* pos);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

💥2.接口文件SList.c

#include "SList.h"

SLTNode* BuySListNode(ElemData x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

SLTNode* CreatSListNode(int n)
{
	SLTNode* Phead, * Ptail;   //头尾指针
	Phead = Ptail = NULL;
	for (int i = 0;i < n;i++)
	{
		SLTNode* newNode = BuySListNode(i);
		if (Phead == NULL)
		{
			Phead = Ptail = newNode;
		}
		else
		{
			Ptail->next = newNode;
			Ptail = newNode;
		}
	}
	return Phead;
}


void SListPrint(SLTNode* Plist)
{

	SLTNode* cur = Plist;
	while (cur != NULL)
	{
		//printf("[%d|%p]->", cur->data, cur->next);
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}


//错误示范，这个代码存在一个Bug，当PPlist=NULL时，无法正常插入
//void SListPushBack(SLTNode* PPlist, ElemData x)
//{
//	SLTNode * PPtail;
//	PPtail = PPlist;
//	SLTNode* newNode = BuySListNode(x);
//	if (PPlist == NULL)
//	{
//		 PPtail = newNode;
//		return;
//	}
//	else
//	{
//		while (PPtail->next != NULL)
//		{
//			PPtail = PPtail->next;
//		}
//	}
//	PPtail->next = newNode;
//	return;
//}

void SListPushBack(SLTNode** PPlist, ElemData x)
{

	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == NULL)
	{
		*PPlist = newNode;
	}
	else
	{
		SLTNode* PPtail;
		PPtail = *PPlist;
		while (PPtail->next != NULL)
		{
			PPtail = PPtail->next;
		}
		PPtail->next = newNode;
	}
}

void SListPopBack(SLTNode** PPlist)
{
	assert(*PPlist);
	if ((*PPlist)->next == NULL)
	{
		free(*PPlist);
		(*PPlist) = NULL;
	}
	else
	{
		SLTNode* ptail;
		ptail = *PPlist;
		while (ptail->next->next != NULL)
		{
			ptail = ptail->next;
		}
		SLTNode* q = ptail->next;
		free(q);
		ptail->next = NULL;
	}
}


void SListPushFront(SLTNode** PPlist, ElemData x)
{
	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == NULL)
	{
		*PPlist = newNode;
	}
	else
	{
		newNode->next = *PPlist;
		*PPlist = newNode;
	}
}

void SListPopFront(SLTNode** PPlist)
{
	assert(*PPlist);
	SLTNode* Phead = *PPlist;
	*PPlist = (*PPlist)->next;
	free(Phead);
}

SLTNode* SListDataFind(SLTNode* plist, ElemData x)
{

	SLTNode* cur = plist;
	//while (cur->next != NULL);
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

SLTNode* SListLocadeFind(SLTNode* plist, int pos)
{

	assert(pos >= 0);
	int i = 0;
	SLTNode* cur = plist;
	while (cur != NULL && i < pos)
	{
		cur = cur->next;
		i++;
	}
	if (cur == NULL)
		return NULL;
	else
		return cur;
}


void SListInsertAfter(SLTNode* pos, ElemData x)
{
	assert(pos);
	SLTNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

void SListErasetAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* q = pos->next;
		pos->next = q->next;
		free(q);
	}
}

void SListInsert(SLTNode** PPlist, SLTNode* pos, ElemData x)
{
	assert(pos);
	SLTNode* newNode = BuySListNode(x);
	if (*PPlist == pos)
	{

		//SListPushFront(PPlist,  x);    //调用我们的头插函数
		newNode->next = *PPlist;
		*PPlist = newNode;
	}
	else
	{
		SLTNode* Phead = *PPlist;
		while (Phead->next != pos)
		{
			Phead = Phead->next;
		}
		newNode->next = Phead->next;
		Phead->next = newNode;
	}
}

void SListErase(SLTNode** PPlist, SLTNode* pos)
{
	assert(pos);
	if (*PPlist == pos)
	{

		//SListPopFront(PPlist);   调用头删函数
		*PPlist = (*PPlist)->next;
		free(pos);
	}
	else
	{
		SLTNode* Ptail = *PPlist;
		while (Ptail->next != pos)
		{
			Ptail = Ptail->next;
		}
		Ptail->next = Ptail->next->next;
		free(pos);
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237

💥3.测试文件test.c

#include "SList.h"

void TextSList1()
{
	SLTNode* Plist = CreatSListNode(5);
	SListPrint(Plist);
}

void TextSList3()
{

	SLTNode* Plist = NULL;   

	SListPushBack(&Plist, 1);
	SListPushBack(&Plist, 2);
	SListPushBack(&Plist, 3);
	SListPushBack(&Plist, 4);
	SListPushBack(&Plist, 5);

	SListPrint(Plist);
}

void TextSList4()
{

	SLTNode* Plist = NULL;

	SListPushBack(&Plist, 1);
	SListPushBack(&Plist, 2);
	SListPushBack(&Plist, 3);
	SListPushBack(&Plist, 4);
	SListPushBack(&Plist, 5);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
	SListPopBack(&Plist);
	SListPrint(Plist);
}

void TextSList5()
{

	SLTNode* Plist = CreatSListNode(5);
	SListPushFront(&Plist, 6);
	SListPrint(Plist);
}

void TextSList6()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);

	SListPopFront(&Plist);
	SListPrint(Plist);
}

void TextSList7()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SLTNode* pos = SListDataFind(Plist, 3);
	if (pos != NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
		printf("没找到\n");
	}

	pos = SListDataFind(Plist, 5);
	if (pos != NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
		printf("没找到\n");
	}
}

void TextSList8()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);
	SLTNode* pos = SListLocadeFind(Plist, 3);
	if (pos != NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
		printf("没找到\n");
	}
	pos = SListLocadeFind(Plist, 5);
	if (pos != NULL)
	{
		printf("找到了\n");
		printf("%d\n", pos->data);
	}
	else
	{
		printf("没找到\n");
	}
}

void TextSList9()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SLTNode* pos = SListLocadeFind(Plist, 0);
	if (pos != NULL)
		printf("%d\n", pos->data);


	SListInsertAfter(pos, 8);
	SListPrint(Plist);
	SListErasetAfter(pos);
	SListPrint(Plist);

}

void TextSList10()
{
	SLTNode* Plist = NULL;
	SListPushFront(&Plist, 1);
	SListPushFront(&Plist, 2);
	SListPushFront(&Plist, 3);
	SListPushFront(&Plist, 4);
	SListPrint(Plist);

	SLTNode* pos = SListLocadeFind(Plist, 0);
	SListInsert(&Plist, pos, 80);
	SListPrint(Plist);

	pos = SListDataFind(Plist, 3);
	SListInsert(&Plist, pos, 700);
	SListPrint(Plist);

	pos = SListDataFind(Plist, 3);
	SListErase(&Plist, pos);
	SListPrint(Plist);

	pos = SListLocadeFind(Plist, 0);
	SListErase(&Plist, pos);
	SListPrint(Plist);

	pos = SListLocadeFind(Plist, 0);
	SListErase(&Plist, pos);
	SListPrint(Plist);

	pos = SListLocadeFind(Plist, 0);
	SListErase(&Plist, pos);
	SListPrint(Plist);

	pos = SListLocadeFind(Plist, 0);
	SListErase(&Plist, pos);
	SListPrint(Plist);

	pos = SListLocadeFind(Plist, 0);
	SListErase(&Plist, pos);
	SListPrint(Plist);

}

int main()
{
	//TextSList1();      //创建简单链表测试
	//TextSList3();     //尾插测试
	//TextSList4();    //尾删测试
	//TextSList5();    //头插测试
	//TextSList6();  //头删测试
	//TextSList7();     //值查找测试
	//TextSList8();     //地址查找测试
	//TextSList9();     //在pos后面插入和删除pos后面节点测试
	TextSList10();      //在pos之前插入和删除pos位置测试
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214