数据结构与算法(C语言版)P3.2---链表之带头双向循环链表的实现_pta带头节点的双向循环链表操作c语言

1、前言

前面一章详细介绍了链表的概念、结构以及分类。并且实现了无头单向非循环链表。
这一篇主要实现带头双向循环链表的。由于需要串联前面的知识，把上一篇至此：链表之无头单向非循环链表的实现

2、带头双向循环链表的特性和结构

2.1、结构

（1）、每个结点有两个指针域（next，prev），一个数据域（data）。
（2）前面结点的next指针域指向后一个结点的地址，并且后一个结点的prev指针域指向前一个结点的地址。
（3）头结点的prev指针域指向尾节点的地址，并且尾节点的next指针域指向头结点地址。

由以上复杂的结构构成了带头双向循环链表。

2.2、特性

带头双向循环链表：结构复杂，使用简单。一般用在单独存储数据。实际中使用的链表结构，都是带头双向链表，另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

为什么说带头双向循环链表的使用简单呢？
其中有一个原因就是"带头"。
那这里就不得不说链表中带头结点（哨兵位）的好处了。

3、带头结点和不带头结点的区别

链表中带哨兵位和不带哨兵位的主要区别在于对边界条件的处理。下面是它们的一些区别：

哨兵位：

• 带哨兵位的链表在头节点之前插入一个特殊的节点，称为哨兵节点或者虚拟头节点。
• 哨兵节点的值一般为空，它的存在使得链表的操作更加简单，避免了很多边界条件的判断。
• 带哨兵位的链表通常有更统一的代码结构，操作起来更加方便。

边界条件处理：

• 不带哨兵位的链表需要特殊处理空链表和只有一个节点的情况。
• 在不带哨兵位的链表中，需要单独对头节点为空或者只有一个节点的情况进行处理，增加了代码编写和维护的复杂度。

空间开销：

• 带哨兵位的链表相比不带哨兵位的链表会多占用一个节点的空间。

总结来说就是，如果使用带哨兵位的链表，我们在遇见插入和删除结点的操作时不用再特殊考虑一些边界情况。比如：没有头结点，只有一个结点或者有多个结点时的3种情况。

所以说使用带哨兵位可以降低链表的难度。

那下面就来实现带头双向循环链表。

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

主要实现接口功能：

• 哨兵位初始化（ListInit）
• 扩容（BuyListNode）
• 头插（ListPushFront）
• 打印（ListPrint）
• 销毁（ListDestroy）
• 头删（ListPopFront）
• 尾插（ListPushBack）
• 尾删（ListPopBack）
• 查询指定pos位置元素（ListFind）
• 在pos位置之前插入（ListInsert）
• 删除pos位置结点（ListErase）

4.1、定义结构体

#pragma once

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

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

next指针变量用于本结点链接后继节点。
prev指针变量用于本结点链接前继节点。
data变量用于存储数据。

4.2、哨兵位初始化

LNode* ListInit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));

	phead->next = phead;
	phead->prev = phead;
	return phead;
}
1
2
3
4
5
6
7
8

这里的哨兵位初始化，一定要注意，由于带头双向循环链表结构的特殊性，哨兵位的首尾是相连的。所以我们需要将哨兵位的next和prev都指向本身。

4.3、扩容

扩容的思想千篇一律，不在介绍。

LNode* BuyListNode(LTDataType x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

4.4、头插

除了要考虑相邻结点之间的链接，这里还要考虑首结点和尾节点的首尾相连。

void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	LNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}
1
2
3
4
5
6
7
8
9
10
11

4.5、打印

这里打印接口说明一下，和无头单向非循环相比，这里的while循环结束的条件不同。因为带头双向循环链表结点是首尾相连的，所以这里的尾节点不在是NULL了，而phead，所以当cur == phead说明链表遍历结束。

void ListPrint(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

4.6、销毁

while循环条件结束和打印接口的一样，都是cur == phead时链表遍历结束。

void ListDestroy(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12

4.7、以上接口功能测试

实现了头插，打印，销毁，扩容，初始化等接口功能，就可以测试以下基本插入程序了。

#include "list.h"

void TestList1()
{
	LNode* plist = ListInit();

	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);
	ListPushFront(plist, 6);

	ListPrint(plist);

	ListDestroy(plist);
}

int main()
{
	TestList1();
	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

输出：

基础接口功能没问题，继续向下完善。

4.8、头删

void ListPopFront(LNode* phead)
{
	//断言是否只有哨兵位
	assert(phead);
	assert(phead->next != NULL);

	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
}
1
2
3
4
5
6
7
8
9
10
11
12

4.9、尾插

这里需要说明，在以往的无头单向非循环链表中，我们需要依次向后遍历的找尾节点。但是在这里找为节点是很简单的操作。因为带头双向循环链表时首位结点相互链接的。哨兵位的prev指向的就是尾节点。

void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}
1
2
3
4
5
6
7
8
9
10

4.10、尾删

void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
}
1
2
3
4
5
6
7
8
9
10
11

4.11、查询指定pos位置元素，返回结点地址pos

LNode* ListFind(LNode* phead, LTDataType x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur)
	{
		if (x == cur->data)
		{
			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
18

4.12、在pos位置之前插入

核心思想：记录pos前继结点，然后依次链接即可。

void ListInsert(LNode* pos,LTDataType x)
{
	assert(pos);
	LNode* newnode = BuyListNode(x);
	LNode* posPrev = pos->prev;

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

4.13、删除pos位置

核心思想：记录pos的前继、后驱结点，然后依次链接即可。

void ListErase(LNode* pos)
{
	assert(pos);

	LNode* posPrev = pos->prev;
	LNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}
1
2
3
4
5
6
7
8
9
10

那到此为止带头双向循环链表的基础接口就实现完毕了。

其实在进行__头插、头删、尾插、尾删__的时候有个高级的处理方式。就是借助__ListFind、ListInsert、ListErase__接口进行处理。下面我们来具体写代码演示。

5、头插、头删、尾插、尾删的高级实现方式

5.1、头插

核心思想：ListInsert接口本身就是完成指定pos位置之前的插入。如果我们想要在头插种使用，那只需要传参头结点后驱结点的地址即可。在头结点的后驱结点使用ListInsert就是头插。

void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	/*
	LNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
	*/

	//使用ListInsert接口完成头插功能
	ListInsert(phead->next, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.2、头删

void ListPopFront(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	*/

	//使用ListErase接口完成头删功能
	ListErase(phead->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.3、尾插

核心思想：这里有个地方难理解。为什么我们使用ListInsert接口函数进行尾插，需要传参phead？我们不应该传尾节点的地址吗？那是因为带头双向循环链表的首位结点时相连的，因为phead就是尾节点的地址，所以就需要传参phead。

void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);

	/*
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
	*/

	//使用ListInsert接口完成尾插功能
	ListInsert(phead,x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4、尾删

void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
	*/

	//使用ListErase接口完成尾删功能
	ListErase(phead->prev);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

至此带头双向循环链表主要功能已全部实现，下面展示全代码验证其正确性。

6、全代码展示

这里使用三个文件：

• list.h：用于结构体、各种函数接口的声明
• list.c：用于各种函数接口的定义。
• test.c：用于创建链表，实现链表。

6.1、list.h

#pragma once

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

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LNode;


//哨兵位初始化
LNode* ListInit();

//扩容
LNode* BuyListNode(LTDataType x);

//头插
void ListPushFront(LNode* phead, LTDataType x);

//打印
void ListPrint(LNode* phead);

//销毁
void ListDestroy(LNode* phead);

//头删
void ListPopFront(LNode* phead);

//尾插
void ListPushBack(LNode* phead, LTDataType x);

//尾删
void ListPopBack(LNode* phead);

//查询指定pos位置元素，返回结点pos地址
LNode* ListFind(LNode* phead, LTDataType x);

//在pos位置之前插入
void ListInsert(LNode* pos,LTDataType x);

//删除当前pos位置结点
void ListErase(LNode* 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

6.2、list.c

#include "list.h"

//哨兵位初始化
LNode* ListInit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));

	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//扩容
LNode* BuyListNode(LTDataType x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

//头插
void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	/*
	LNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
	*/

	//使用ListInsert接口完成头插功能
	ListInsert(phead->next, x);
}

//打印
void ListPrint(LNode* phead)
{
	assert(phead);

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

//销毁
void ListDestroy(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

//头删
void ListPopFront(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	*/

	//使用ListErase接口完成头删功能
	ListErase(phead->next);
}

//尾插
void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);

	/*
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
	*/

	//使用ListInsert接口完成尾插功能
	ListInsert(phead,x);
}

//尾删
void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
	*/

	//使用ListErase接口完成尾删功能
	ListErase(phead->prev);
}

//查询指定pos位置元素，返回结点pos地址
LNode* ListFind(LNode* phead, LTDataType x)
{
	assert(phead);

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

//在pos位置之前插入
void ListInsert(LNode* pos,LTDataType x)
{
	assert(pos);
	LNode* newnode = BuyListNode(x);
	LNode* posPrev = pos->prev;

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

//删除当前pos位置结点
void ListErase(LNode* pos)
{
	assert(pos);

	LNode* posPrev = pos->prev;
	LNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}
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

6.3、test.c

#include "list.h"

void TestList1()
{
	LNode* plist = ListInit();

	ListPushFront(plist, 11);
	ListPushFront(plist, 22);
	ListPushFront(plist, 33);
	ListPushFront(plist, 44);
	ListPushFront(plist, 55);
	ListPushFront(plist, 66);

	ListPopBack(plist);

	//LNode* pos = ListFind(plist, 4);
	//ListErase(pos);

	ListPrint(plist);

	ListDestroy(plist);
}

int main()
{
	TestList1();
	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