C语言数据结构之链表

$前言$

在上一篇博客中我们提到，线性表包括顺序表和链表，顺序表在上篇博客中已经介绍，本篇博客介绍一下另一种线性表——链表。

1.链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

• 链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。

• ⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？

• 最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。

• 在链表⾥，每节“⻋厢”是什么样的呢？

• 与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点” (顺序表申请的空间是连续的，一次性申请下来的)

• 节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

• 图中指针变量 plist 保存的是第⼀个节点的地址，我们称 plist 此时“指向”第⼀个节点，如果我们希望 plist “指向”第⼆个节点时，只需要修改 plist 保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置？

链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：

struct ListNode
{
	int data;              //节点储存的数据
	struct ListNode* next; //指向节点的下一个节点
};
1
2
3
4
5

• 当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。

• 当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。

我们以打印链表数据为例，看看是怎么拿到链表每一个数据的

$注意:$

1.链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2.节点⼀般是从堆上申请的

3.从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

2.链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表。

1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。
2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。

3.无头单向非循环链表的实现

test.c

#include "Simple_List.h"

void menu()
{
	printf("******************************************\n");
	printf("***************   请选择   ***************\n");
	printf("******  1.PushFront     2.PushBack  ******\n");
	printf("******  3.Insert        4.PopFront  ******\n");
	printf("******  5.PopBack       6.Del       ******\n");
	printf("******  7.Modify        8.Print     ******\n");
	printf("******            0.Exit            ******\n");
	printf("******************************************\n");
}

int main()
{
	int pos = 0;
	int input = 0;
	int value = 0;

	ListNode* head = NULL;

	do 
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要头插的值>:");
			scanf("%d", &value);
			Push_Front_List(&head, value);
			break;
		case 2:
			printf("请输入你要尾插的值>:");
			scanf("%d", &value);
			Push_Back_List(&head, value);
			break;
		case 3:
			printf("请输入你要插入的位置和要插入的值>:");
			scanf("%d %d", &pos, &value);
			Insert_List(&head, pos, value);
			break;
		case 4:
			Pop_Front_List(&head);
			break;
		case 5:
			Pop_Back_List(&head);
			break;
		case 6:
			printf("请输入你要删除的值>:");
			scanf("%d", &pos);
			Del_List(&head, pos);
			break;
		case 7:
			printf("请输入你要修改的位置和要修改的值>:");
			scanf("%d %d", &pos, &value);
			Modify_List(head, pos, value);
			break;
		case 8:
			Print_List(head);
			break;
		case 0:
			Destroy(&head);
			printf("链表销毁成功\n");
			break;
		default:
			printf("选择错误，请重新选择\n");
			break;
		}
	} while (input);
	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

Simple_List.c

#include "Simple_List.h"


//打印链表数据
void Print_List(ListNode* phead)
{
	ListNode* cur = phead;

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


//创建新节点
void Buy_Node(ListNode** ptr) //传二级指针是因为只传一级指针的话，我们改变形参不能改变实参的地址
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));

	if (tmp == NULL) //可能开辟空间不成功
	{
		perror("Buy_Node");
		return;
	}

	*ptr = tmp;
}


//头插
void Push_Front_List(ListNode** phead, LDatatype val)
{
	assert(phead); //phead要解引用，不能为空

	ListNode* newnode = NULL; 
	Buy_Node(&newnode); //插入一个新的数据需要先创建一个新节点插入到链表
	newnode->data = val;
	newnode->next = *(phead);
	*phead = newnode; //因为是头插一个节点，所以头指针要指向新的节点
}


//尾插
void Push_Back_List(ListNode** pphead, LDatatype val)
{
	assert(pphead); //phead要解引用，不能为空

	ListNode* newnode = NULL;
	Buy_Node(&newnode);
	newnode->data = val;
	newnode->next = NULL;

	ListNode* tail = *pphead;
	if (*(pphead) == NULL) //当链表为空时，头指针也为空，尾插需要把新节点地址给予头指针
	{
		*(pphead) = newnode;
		return;
	}

	while (tail->next != NULL) //找到最后一个节点，将新节点插入
	{
		tail = tail->next;
	}
	tail->next = newnode;
}


//寻找指定的的节点的地址
void Find_Ptr_List(ListNode** pphead, LDatatype pos,ListNode** pcur,ListNode** pfront)
{
	assert(pphead && pcur && pfront && *pphead); //这些指针需要解引用，不能为空
	
	*pcur = *pfront = *pphead;
	
	while (*pcur != NULL) // 这样的目的是，如果*pcur找到了指定数据的节点，*pfront就是*pcur的上一个节点
	{
		if ((*pcur)->data == pos) //先判断再让*pcur多走一步的原因是：可能头节点就是指定的数据，先走一步会漏掉判断
			break;
		if (*pcur == *pfront) // 让*pcur比*pfront多走一步，即*pcur = (*pfront)->next
			*pcur = (*pcur)->next;
		else
		{
			*pcur = (*pcur)->next;
			*pfront = (*pfront)->next;
		}
	}
}


//在指定数据的节点前插入数据
void Insert_List(ListNode** pphead,LDatatype pos,LDatatype val)
{
	ListNode* newnode = NULL;
	Buy_Node(&newnode);

	ListNode* cur = NULL;
	ListNode* front = NULL;
	Find_Ptr_List(pphead, pos, &cur, &front);

	if (cur == NULL) //说明整个链表已经判断完了，也没有找到指定数据
	{
		printf("找不到该位置\n");
		return;
	}

	if (cur == front) //说明指定数据就是头节点，直接头插
	{
		Push_Front_List(pphead, val);
		return;
	}

	front->next = newnode; //指定数据不是头节点的其他情况
	newnode->data = val;
	newnode->next = cur;
}


//头删
void Pop_Front_List(ListNode** pphead)
{
	assert(pphead && *pphead); //这些指针需要解引用，不能为空

	ListNode* front = *pphead;
	*pphead = (*pphead)->next; //头删后头指针需要指向新的头节点
	free(front);
	front = NULL;
}


//尾删
void Pop_Back_List(ListNode** pphead)
{
	assert(pphead && *pphead); //这些指针需要解引用，不能为空

	ListNode* tail = NULL;
	tail = *pphead;

	ListNode* front = NULL;
	front = *pphead;

	while (tail->next != NULL) 
	{
		if (front == tail) //让tail多走一步，即tail = front->next;
		{
			tail = tail->next;
		}
		else
		{
			tail = tail->next;
			front = front->next;
		}
	}

	if (front == tail) //说明链表只有一个数据，直接执行头删
	{
		Pop_Front_List(pphead);
		return;
	}

	front->next = NULL; //链表不止一个数据的情况，就需要把tail节点去掉
	free(tail); //找不到cur对应的实参所以不用置空，只需要释放空间即可
}


//删除指定数据
void Del_List(ListNode** pphead, LDatatype pos)
{
	assert(pphead); //pphead需要解引用，不能为空

	ListNode* cur = *pphead;
	ListNode* front = *pphead;

	Find_Ptr_List(pphead, pos, &cur, &front);

	if (cur == NULL) //说明链表遍历完了还没有找到指定数据
	{
		printf("找不到该位置\n");
		return;
	}

	if (cur == front) //说明头节点就是指定的数据，直接头删
	{
		Pop_Front_List(pphead);
		return;
	}

	front->next = cur->next; //头节点不是指定的数据的其他情况
	free(cur); //找不到cur对应的实参所以不用置空，只需要释放空间即可
}


//修改指定数据
void Modify_List(ListNode* phead, LDatatype pos, LDatatype val)
{
	assert(phead); //phead需要解引用，不能为空

	while (phead != NULL) //遍历链表寻找指定数据，再修改
	{
		if (phead->data == pos)
		{
			phead->data = val;
			return;
		}
		phead = phead->next;
		
	}

	if (phead == NULL) //遍历完链表还未找到指定数据
		printf("找不到该位置\n");
}


//销毁链表
void Destroy(ListNode** phead)
{
	while((*phead)!=NULL)
	{
		ListNode* cur = *phead; //销毁需要先记录下这个节点，如果直接销毁会找不到后面的节点
		*phead = (*phead)->next;
		free(cur);
		cur = NULL; //这里要销毁cur，而不是*phead，销毁*phead后面节点就找不到了
	}
}
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

Simple_List.h

#include <stdio.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>

typedef int LDatatype;     //链表储存的数据类型

typedef struct ListNode
{
	LDatatype data;        //节点储存的数据
	struct ListNode* next; //指向节点的下一个节点
}ListNode;

void Print_List(ListNode* phead);

void Push_Front_List(ListNode** phead, LDatatype val);

void Push_Back_List(ListNode** pphead, LDatatype val);

void Insert_List(ListNode** pphead, LDatatype pos, LDatatype val);

void Pop_Front_List(ListNode** pphead);

void Pop_Back_List(ListNode** pphead);

void Del_List(ListNode** pphead, LDatatype pos);

void Destroy(ListNode** phead);

void Modify_List(ListNode* phead, LDatatype pos, LDatatype val);
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

4.带头双向循环链表的实现

test.c

#include "Complex_List.h"

void menu()
{
	printf("****************************************\n");
	printf("************     请选择     ************\n");
	printf("******  1.PushFront   2.PushBack  ******\n");
	printf("******  3.Insert      4.PopFront  ******\n");
	printf("******  5.PopBack     6.Erase     ******\n");
	printf("******  7.Print       0.Exit      ******\n");
	printf("****************************************\n");
}

int main()
{
	int input = 0;
	int value = 0;
	int pos = 0;

	ListNode* plist = NULL;
	Init_List(&plist);

	do
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要头插的值>:");
			scanf("%d", &value);
			Push_Front_List(plist, value);
			break;
		case 2:
			printf("请输入你要尾插的值>:");
			scanf("%d", &value);
			Push_Back_List(plist, value);
			break;
		case 3:
			printf("请输入你要插入的位置和要插入的值>:");
			scanf("%d %d", &pos, &value);
			Insert_List(plist, pos, value);
			break;
		case 4:
			Pop_Front_List(plist);
			break;
		case 5:
			Pop_Back_List(plist);
			break;
		case 6:
			printf("请输入你要删除的值>:");
			scanf("%d", &pos);
			Erase_List(plist, pos);
			break;
		case 7:
			Print_List(plist);
			break;
		case 0:
			Destroy_List(&plist);
			printf("销毁链表成功\n");
			break;
		default:
			printf("选择错误，请重新选择\n");
			break;
		}
	} while (input);
	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

Complex_List.c

#include "Complex_List.h"


//创建新节点
ListNode* Buy_Newnode()
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));

	return newnode;
}


//打印链表数据
void Print_List(ListNode* phead)
{
	assert(phead); //phead需要解引用，不能为空

	ListNode* cur = phead->next;

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


//初始化链表
void Init_List(ListNode** pphead) //要改变实参的地址，需要二级指针
{
	(*pphead) = Buy_Newnode();
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);
	(*pphead)->data = 0;
}


//销毁链表
void Destroy_List(ListNode** pphead)
{
	ListNode* phead = (*pphead);
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	*pphead = NULL;
}


//头插
void Push_Front_List(ListNode* phead,LDataType val)
{
	ListNode* newnode = Buy_Newnode();

	if (newnode == NULL) //有可能空间开辟失败
	{
		perror("Fail: Push_Front_List\n");
		return;
	}

	ListNode* headnext = phead->next;
	newnode->prev = phead; //头插是插入哨兵节点后面
	newnode->next = headnext;
	newnode->data = val;
	phead->next = newnode;
	headnext->prev = newnode;
}


//尾插
void Push_Back_List(ListNode* phead, LDataType val)
{
	ListNode* newnode = Buy_Newnode();

	if (newnode == NULL) //有可能开辟空间失败
	{
		perror("Fail: Push_Back_List\n");
		return;
	}

	ListNode* tail = phead->prev;
	newnode->next = phead; //尾删就是删除哨兵节点前一个节点，因为是循环链表
	newnode->prev = tail;
	newnode->data = val;
	phead->prev = newnode;
	tail->next = newnode;
}


//寻找指定数据节点
ListNode* Find_Ptr_List(ListNode* phead, LDataType pos)
{
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == pos)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}


//在指定数据前面插入数据
void Insert_List(ListNode* phead, LDataType pos, LDataType val)
{
	ListNode* tmp = Find_Ptr_List(phead, pos);

	if (tmp == NULL)
	{
		printf("找不到该位置\n");
		return;
	}

	ListNode* dest = tmp;
	ListNode* last = dest->prev;

	ListNode* newnode = Buy_Newnode();

	newnode->prev = last;
	newnode->next = dest;
	newnode->data = val;
	last->next = newnode;
	dest->prev = newnode;
}


//头删
void Pop_Front_List(ListNode* phead)
{
	if (phead->next == phead) //如果哨兵节点的next是它自己，那么就代表链表为空，不进行删除
		return;

	ListNode* head = phead->next; //头删是删除哨兵节点下一个节点
	phead->next = head->next;
	head->next->prev = phead;
	free(head);
}


//尾删
void Pop_Back_List(ListNode* phead)
{
	if (phead->prev == phead) //如果哨兵节点的prev是它自己，那么就代表链表为空，不进行删除
		return;

	ListNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
}


//删除指定数据
void Erase_List(ListNode* phead, LDataType pos)
{
	ListNode* tmp = Find_Ptr_List(phead, pos);

	if (tmp == NULL)
	{
		printf("找不到该位置\n");
		return;
	}

	ListNode* dest = tmp;
	ListNode* last = dest->prev;
	ListNode* next = dest->next;
	last->next = next;
	next->prev = last;
	free(dest);
}
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

Complex_List.h

#include <stdio.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>

typedef int LDataType;     //节点储存的数据类型

typedef struct ListNode
{
	struct ListNode* prev; //指向节点的上一个节点
	struct ListNode* next; //指向节点的下一个节点
	LDataType data;        //节点储存的数据
}ListNode;

void Print_List(ListNode* phead);

void Init_List(ListNode** phead);

void Push_Front_List(ListNode* phead, LDataType val);

void Push_Back_List(ListNode* phead, LDataType val);

void Insert_List(ListNode* phead, LDataType pos, LDataType val);

void Pop_Front_List(ListNode* phead);

void Pop_Back_List(ListNode* phead);

void Erase_List(ListNode* phead, LDataType pos);

void Destroy_List(ListNode** pphead);
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

通过对比代码，我们发现带头双向循环链表的实现要比无头单向非循环链表的实现简单不少，因为带头双向循环链表哨兵位和循环的设定可以很大程度上方便我们的头插尾插，头删尾删等接口。

5.顺序表和链表的对比