数据结构—双向链表

转载自https://blog.csdn.net/weixin_43866583/article/details/127090511?spm=1001.2014.3001.5502

双向链表

双向链表和单向链表相比，最大的不同是指针域中多了一个指向前一个节点的地址域。这样一来，双向链表中的每个节点就保存了前后节点的地址，从而通过地址形成一条链式的存储结构。

双向链表的最大便利之处在于查询链表时不仅可以正向查找也可以反向查找，甚至如果当前查询的位置在链表中间的位置的时候，可以反方向两头查找，提高查找的速度和效率，增加了便利。

双向不循环链表

双向不循环链表是头结点的前一个指针指向头结点自身，尾节点的后一个指针指向为NULL

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
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
#include <stdio.h>
#include <stdlib.h>
 
 
/*** 定义链表操作的位置：开头、中间、结尾 ***/
typedef enum
{
	Head = 1,
	Middle,
	End,
}Location;
 
 
/*** 定义一个链表节点 ******/
// 1.定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;
 
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Prev; 	// 链表节点的上一个节点的指针域
	struct LinkNode_Struct *Next; 	// 链表节点的下一个节点的指针域
}LinkNode_t;
 
 
/*** 定义一个单向链表的头结点 ***/
LinkNode_t AppleInfo_head; //作为单向链表的一个头结点
 
 
// 初始化单向链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = NULL;
	HeadNode->Prev = NULL;
}
 
// 创建一个链表节点并接入到链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Prev_pf,*Next_pf;
	LinkNode_t *xReturn = NULL;
	LinkNode_t *Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));
 
	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}
 
	Prev_pf = Next_pf = HeadNode;
	
	// 第一节点从头结点后面开始插入
	if (HeadNode->Next == NULL && HeadNode->Prev == NULL)
	{
		HeadNode->Next = Node;
		Node->Next = NULL;
		Node->Prev = HeadNode;
		Node->data.hight  = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	else
	{
		while (Next_pf->Next != NULL)
		{
			Next_pf = Next_pf->Next;
		}
		Next_pf->Next = Node;
		Node->Prev = Next_pf;
		Node->Next = NULL;
		Node->data.hight = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	
	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}
 
// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf;
 
	pf = HeadNode;
 
	do
	{
		pf = pf->Next;
		if (pf->data.weight == weight)
		{
			deleteFlag = 1;
			break;
		}		
	}while (pf->Next != NULL);
 
	if (!deleteFlag)
	{
		printf("链表中找不到这个节点！！！\r\n");
	}
	else
	{
		if (pf->Next == NULL)
		{
			pf->Prev->Next = NULL;
		}
		else
		{
			pf->Prev->Next = pf->Next;
			pf->Next->Prev = pf->Prev; 
		}
		
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}
 
// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != NULL);
	printf("链表输出完成。长度为：%d\r\n",length);
}
 
 
// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != NULL);
 
	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
// 查询链表中有几个相同的数据
void search_Same_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0,cnt = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		length++;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("这个节点在链表中的位置：%d\r\n",length);
			cnt++;
		}
	}while (pf->Next != NULL);
 
	if(search_flag)
	{
		printf("链表查找结束。相同数据的节点数量为：%d\r\n",cnt);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
 
void print_debug_info(void)
{
	printf("******** 链表控制台 *****************\r\n");
	printf("*                                  \r\n");
	printf("*  1：创建链表                      \r\n");
	printf("*  2：删除链表                      \r\n");
	printf("*  3：显示整条链表的数据             \r\n");
	printf("*  4：按条件查找链表节点             \r\n");
	printf("*  5：查找链表中有几个相同数据的节点  \r\n");
	printf("*  8：清空显示                      \r\n");
	printf("*  9：结束运行                      \r\n");
	printf("*                                  \r\n");
	printf("************************************\r\n");
}
 
 
int main(int argc, char *argv[]) 
{
	int Num,i,j;
	int Options;
	int weight,height;
	LinkData_t InsetData;
 
	Init_LinkNode(&AppleInfo_head);
 
	
	while (1)
	{
		print_debug_info();
		printf("\r\n请输入需要操作的键值，按回车键确认！\r\n");
		scanf("%d", &Options);
		switch (Options)
		{
			case 1:
				/*** 创建任意长度的链表 **********************************************************/
				printf("请输入需要创建的链表节点的数量,按回车结束！\r\n");
				scanf("%d", &Num);
 
				printf("请输入节点的数据：\r\n");
				for (i = 0; i < Num; i++)
				{
					printf("请输入第 %d 节点的数据,weight = Height = ,输入完毕按回车结束！\r\n",i+1);
					scanf("%d %d", &weight,&height);
					InsetData.weight = weight;
					InsetData.hight  = height;
					printf("weight = %d height = %d\r\n",weight,height);
 
					if(LinkNode_Create(&AppleInfo_head, &InsetData) > NULL)
					{
						printf("节点 %d 创建成功！\r\n\r\n\r\n",i+1);
					}
					else
					{
						printf("节点 %d 创建失败！\r\n\r\n\r\n",i+1);
					}
				}
				printf("\r\n");
				break;
			
			case 2:
				/******* 删除链表中的某个节点 ***************************************************/
				printf("请输入需要删除的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				destroy_LinkNode(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 3:
				printf("链表数据为：\r\n");
				print_LinkNode_Info(&AppleInfo_head);
				printf("\r\n");
				break;
 
			case 4:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 5:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_Same_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 8:
				system("cls");
				break;
 
			case 9:
				printf("退出链表控制台，请再次运行程序！\r\n");
				return;
				break;
			
			default:
				printf("无效的键值，请重新输入！\r\n");
				break;
		}
	}
	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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
#include <stdio.h>
#include <stdlib.h>
 
 
/*** 定义链表操作的位置：开头、中间、结尾 ***/
typedef enum
{
	Head = 1,
	Middle,
	End,
}Location;
 
 
/*** 定义一个链表节点 ******/
// 1.定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;
 
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Prev; 	// 链表节点的上一个节点的指针域
	struct LinkNode_Struct *Next; 	// 链表节点的下一个节点的指针域
}LinkNode_t;
 
 
/*** 定义一个单向链表的头结点 ***/
LinkNode_t AppleInfo_head; //作为单向链表的一个头结点
 
 
// 初始化单向链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = NULL;
	HeadNode->Prev = HeadNode;	// 双向循环链表的头结点的前一个指针指向头结点本身
}
 
// 创建一个链表节点并接入到链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Prev_pf,*Next_pf;
	LinkNode_t *xReturn = NULL;
	LinkNode_t *Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));
 
	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}
 
	Prev_pf = Next_pf = HeadNode;
	
	// 第一节点从头结点后面开始插入
	if (HeadNode->Next == NULL && HeadNode->Prev == HeadNode)
	{
		HeadNode->Next = Node;
		HeadNode->Prev = Node;
		Node->Next = HeadNode;
		Node->Prev = HeadNode;
		Node->data.hight  = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	else
	{
		while (Next_pf->Next != HeadNode)
		{
			Next_pf = Next_pf->Next;
		}
		Next_pf->Next  = Node;
		HeadNode->Prev = Node;
		Node->Prev = Next_pf;
		Node->Next = HeadNode;
		Node->data.hight = InsetData->hight;
		Node->data.weight = InsetData->weight;
		xReturn = Node;
	}
	
	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}
 
// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf;
 
	pf = HeadNode;
 
	do
	{
		pf = pf->Next;
		if (pf->data.weight == weight)
		{
			deleteFlag = 1;
			break;
		}		
	}while (pf->Next != HeadNode);
 
	if (!deleteFlag)
	{
		printf("链表中找不到这个节点！！！\r\n");
	}
	else
	{
		if (pf->Next == HeadNode)
		{
			pf->Prev->Next = HeadNode;
			HeadNode->Prev = pf;
		}
		else
		{
			pf->Prev->Next = pf->Next;
			pf->Next->Prev = pf->Prev; 
		}
		
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}
 
// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != HeadNode);
	printf("链表输出完成。长度为：%d\r\n",length);
}
 
 
// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != HeadNode);
 
	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
// 查询链表中有几个相同的数据
void search_Same_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0,cnt = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		length++;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("这个节点在链表中的位置：%d\r\n",length);
			cnt++;
		}
	}while (pf->Next != HeadNode);
 
	if(search_flag)
	{
		printf("链表查找结束。相同数据的节点数量为：%d\r\n",cnt);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}
 
 
void print_debug_info(void)
{
	printf("******** 链表控制台 *****************\r\n");
	printf("*                                  \r\n");
	printf("*  1：创建链表                      \r\n");
	printf("*  2：删除链表                      \r\n");
	printf("*  3：显示整条链表的数据             \r\n");
	printf("*  4：按条件查找链表节点             \r\n");
	printf("*  5：查找链表中有几个相同数据的节点  \r\n");
	printf("*  8：清空显示                      \r\n");
	printf("*  9：结束运行                      \r\n");
	printf("*                                  \r\n");
	printf("************************************\r\n");
}
 
 
int main(int argc, char *argv[]) 
{
	int Num,i,j;
	int Options;
	int weight,height;
	LinkData_t InsetData;
 
	Init_LinkNode(&AppleInfo_head);
 
	
	while (1)
	{
		print_debug_info();
		printf("\r\n请输入需要操作的键值，按回车键确认！\r\n");
		scanf("%d", &Options);
		switch (Options)
		{
			case 1:
				/*** 创建任意长度的链表 **********************************************************/
				printf("请输入需要创建的链表节点的数量,按回车结束！\r\n");
				scanf("%d", &Num);
 
				printf("请输入节点的数据：\r\n");
				for (i = 0; i < Num; i++)
				{
					printf("请输入第 %d 节点的数据,weight = Height = ,输入完毕按回车结束！\r\n",i+1);
					scanf("%d %d", &weight,&height);
					InsetData.weight = weight;
					InsetData.hight  = height;
					printf("weight = %d height = %d\r\n",weight,height);
 
					if(LinkNode_Create(&AppleInfo_head, &InsetData) > NULL)
					{
						printf("节点 %d 创建成功！\r\n\r\n\r\n",i+1);
					}
					else
					{
						printf("节点 %d 创建失败！\r\n\r\n\r\n",i+1);
					}
				}
				printf("\r\n");
				break;
			
			case 2:
				/******* 删除链表中的某个节点 ***************************************************/
				printf("请输入需要删除的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				destroy_LinkNode(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 3:
				printf("链表数据为：\r\n");
				print_LinkNode_Info(&AppleInfo_head);
				printf("\r\n");
				break;
 
			case 4:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 5:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_Same_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;
 
			case 8:
				system("cls");
				break;
 
			case 9:
				printf("退出链表控制台，请再次运行程序！\r\n");
				return;
				break;
			
			default:
				printf("无效的键值，请重新输入！\r\n");
				break;
		}
	}
	return 0;
}