(带表头)双循环链表的C语言实现(详细)_一个循环链表,拆成两个带有头指针的链表

---

双向循环链表的概述

双循环链表：其实很简单，就是循环链表和双链表的组合。双链表表示每个结点既有前驱也有后继，循环链表表示链表的尾结点不指向NULL，而是和头结点连接。

如图所示：

---

包含相关声明的头文件

将双循环链表包含的相关头文件，函数声明，结构体定义，宏定义等放到一个叫double_circular_linked_list.h的头文件中。
想要使用双循环链表，只需要包含头文件double_circular_linked_list.h。

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

typedef int ElemType;					// 可以创建任何数据类型的链表，只需要修改这一行代码

struct DuCNode;							// 先定义结点的结构体，但是不创建模板
typedef struct DuCNode* Position;		// 定义双循环链表结点地址
typedef struct DuCNode* DuCircList;		// 定义双循环链表的头指针

// 双循环链表结点定义
typedef struct DuCNode {
	ElemType element;
	Position prior;
	Position next;
}DuCNode;

void Init(DuCircList* ppHead);
bool IsEmpty(const DuCircList head);
Position CreateNode(const ElemType elem);
Position GetElem(const DuCircList head, int pos);
Position GetElemPrevious(const DuCircList head, int pos);
void InsertElem(DuCircList head, int pos, ElemType elem);
void PushFront(DuCircList head, ElemType elem);
void PushBack(DuCircList head, ElemType elem);
ElemType DeleteElem(DuCircList head, int pos);
ElemType PopFront(DuCircList head);
ElemType PopBack(DuCircList head);
void ModifyElem(const DuCircList head, int pos, ElemType elem);
int GetLength(const DuCircList head);
void Clear(DuCircList head);
void Destroy(DuCircList* ppHead);

Position LocateElem(const DuCircList head, ElemType elem);
int LocatePos(const DuCircList head, ElemType elem);
void RemoveElem(DuCircList head, ElemType elem);
bool InputInteger(int* num);
void HeadInsert(DuCircList* head);
void TailInsert(DuCircList* head);
void Print(const DuCircList head);
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

---

双循环链表的基本通用操作

1.初始化双循环链表

有头结点的链表，初始化需要创建头结点。头结点的prior域和next域都指向自己。

void Init(DuCircList* ppHead)
{
	// 通过malloc函数新建一个头结点，并让头指针指向头结点
	*ppHead = (DuCircList)malloc(sizeof(DuCNode));
	// 如果分配空间失败，直接终止程序,并调用abort函数，显示相关提示信息
	assert(*ppHead != NULL);
	// 让头结点的prior域和next域都指向自己，形成双向的环
	(*ppHead)->prior = *ppHead;
	(*ppHead)->next = *ppHead;
}
1
2
3
4
5
6
7
8
9
10

2.双循环链表是否为空

bool IsEmpty(const DuCircList head)
{
	return head->next == head && head->prior == head;
}
1
2
3
4

3.创建一个新结点

// 所有插入操作都需要创建新结点，所以我将它专门设计为一个函数，增加代码通用性
Position CreateNode(const ElemType elem)
{
	Position newNode = (Position)malloc(sizeof(DuCNode));
	// 如果创建新结点失败，就打印提示信息，并终止程序
	if (newNode == NULL)
	{
		puts("The creation of a new node failed!");
		exit(EXIT_FAILURE);
	}
	newNode->element = elem;		// 将传入的数据赋值给新结点的数据域
	// 暂时将新结点的prior和next指针域赋值为NULL
	newNode->prior = NULL;
	newNode->next = NULL;
	return newNode;					// 返回新结点的地址
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.查找指定位置上的元素

/*
 * 查找双循环链表指定位置元素的地址，如果pos为0，则返回头结点的地址
 * 如果指定位置超出范围，就打印提示信息，并终止程序
 */
Position GetElem(const DuCircList head, int pos)
{
	// 左边的非法范围异常处理
	if (pos < 0)
	{
		puts("The position is out of range!");
		exit(EXIT_FAILURE);
	}
	
	int count = 0;			// count初始值为0
	Position cur = head;
	//cur初始为头结点，cur每移动一次，count加1，当count==pos，说明找到指定位置的元素了
	while (count < pos)
	{
		cur = cur->next;
		count++;
		// 如果再次找到头结点，说明pos越右侧边界了，就做异常处理
		if (cur == head)
		{
			puts("The position is out of range!");
			exit(EXIT_FAILURE);
		}
	}
	return cur;		// 如果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

5.查找指定位置的前驱元

GetElemPrevious函数在删除操作中使用，可以让删除操作的代码非常优雅

/*
 * 查找双循环链表指定位置元素的前驱元素的地址，pos的范围为[1,length]
 * 如果pos为1，就返回头结点
 * 如果指定位置超出范围，就打印提示信息，并终止程序
 */
Position GetElemPrevious(const DuCircList head, int pos)
{
	// 先做对空表删除元素的异常处理
	if (IsEmpty(head))
	{
		puts("The double circular linked list is empty!");
		exit(EXIT_FAILURE);
	}
	// 左边越界的异常处理
	if (pos <= 0)
	{
		puts("The position is out of range!");
		exit(EXIT_FAILURE);
	}
	Position prec = head;
	int count = 0;
	// 注意，要找的是当前位置的直接前驱，所以是pos-1
	while (count < pos - 1)
	{
		prec = prec->next;
		count++;
		// 如果找到尾结点，说明右边越界了，需要做异常处理
		if (prec->next == head)
		{
			puts("The position is out of range!");
			exit(EXIT_FAILURE);
		}
	}
	return prec;
}
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

6.在指定位置插入元素

/*
 * 有头结点的插入操作非常简单
 * GetElem会返回插入结点需要的前驱结点，并且做pos的范围检测,pos的合法范围为[1,length+1]
 * 注意插入结点的连接操作是双向的，连接前驱和后继结点共需要4行代码
 */
void InsertElem(DuCircList head, int pos, ElemType elem)
{
	Position newNode = CreateNode(elem);
	Position prec = GetElem(head, pos - 1);		// 找到指定位置的前驱结点
	//先把新结点连接上链表
	newNode->next = prec->next;
	newNode->prior = prec;
	// 再让新结点的前驱和后继结点连接上新结点
	prec->next->prior = newNode;				// 这行代码和下面一行千万不能调换
	prec->next = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7.在头部插入元素

// 在表头插入数据元素，也就是在头结点直接后继位置插入新结点
void PushFront(DuCircList head, ElemType elem)
{
	Position newNode = CreateNode(elem);
	//先把新结点连接上链表，位置在头结点直接后继
	newNode->next = head->next;
	newNode->prior = head;
	// 再让新结点的前驱和后继结点连接上新结点
	head->next->prior = newNode;
	head->next = newNode;
}
1
2
3
4
5
6
7
8
9
10
11

8.在尾部插入元素

// 在表尾插入数据元素，也就是在头结点直接前驱位置插入新结点
void PushBack(DuCircList head, ElemType elem)
{
	Position newNode = CreateNode(elem);
	//先把新结点连接上链表，位置在头结点直接前驱
	newNode->next = head;
	newNode->prior = head->prior;
	// 再让新结点的前驱和后继结点连接上新结点
	head->prior->next = newNode;
	head->prior = newNode;
}
1
2
3
4
5
6
7
8
9
10
11

9.删除指定位置上的元素

利用返回指定位置的前驱元函数GetElemPrevious，可以让代码变得非常优雅。

// 删除双循环链表指定位置上的元素，并返回该元素的值,位置范围为:[1,length]
ElemType DeleteElem(DuCircList head, int pos)
{
	Position prec = GetElemPrevious(head, pos);
	Position cur = prec->next;
	ElemType deleteElem = cur->element;
	// 删除的核心逻辑
	cur->next->prior = prec;
	prec->next = cur->next;
	free(cur);
	return deleteElem;
}
1
2
3
4
5
6
7
8
9
10
11
12

10.在头部删除元素

// 在双循环链表头部删除元素，等价于删除第一个数据结点(头结点的直接后继结点)
ElemType PopFront(DuCircList head)
{
	// 先做对空表删除元素的异常处理
	if (IsEmpty(head))
	{
		puts("The double circular linked list is empty!");
		exit(EXIT_FAILURE);
	}

	Position cur = head->next;
	ElemType deleteElem = cur->element;
	// 头删核心逻辑
	head->next = cur->next;
	cur->next->prior = head;
	free(cur);
	
	return deleteElem;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

11.在尾部删除元素

// 在双循环链表尾部删除元素，等价于删除头结点的直接前驱结点
ElemType PopBack(DuCircList head)
{
	// 先做对空表删除元素的异常处理
	if (IsEmpty(head))
	{
		puts("The double circular linked list is empty!");
		exit(EXIT_FAILURE);
	}

	Position cur = head->prior;
	ElemType deleteElem = cur->element;
	// 尾删核心逻辑
	cur->prior->next = head;
	head->prior = cur->prior;
	free(cur);

	return deleteElem;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

12.修改指定位置上元素的值

GetElem函数的设计主要为了兼容插入函数，所以pos为0时，是不会报异常的。
但是修改元素的值，是需要对pos为0做异常处理。
而且，GetElem函数对于空表是不报异常的，因为插入可以对空表进行插入。
所以，修改函数也需要单独做空表异常处理。

// 修改指定位置上元素的值，pos的合法范围为:[1,length]
void ModifyElem(DuCircList head, int pos, ElemType elem)
{
	// 做空表异常处理
	if (IsEmpty(head))
	{
		puts("The double circular linked list is empty!");
		exit(EXIT_FAILURE);
	}
	// 后面的GetElem函数不会做pos=0的非法范围检查，需要单独处理
	if (pos == 0)
	{
		puts("The position is out of range!");
		exit(EXIT_FAILURE);
	}
	Position cur = GetElem(head, pos);
	cur->element = elem;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

13.计算双循环链表长度

// 计算链表长度，如果是空表就返回0
int GetLength(const DuCircList head)
{
	int length = 0;
	Position cur = head;
	while (cur != head->prior)
	{
		cur = cur->next;
		length++;
	}
	return length;
}
1
2
3
4
5
6
7
8
9
10
11
12

14.清空双循环链表

// 清空链表的所有数据结点(不包含头结点)
void Clear(DuCircList head)
{
	Position cur = head->next;
	while (cur != head)
	{
		Position succ = cur->next;
		free(cur);
		cur = succ;
	}
	// 清空所有数据结点后，让头结点的prior和next域都指向自己
	head->next = head;
	head->prior = head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

15.摧毁双循环链表

// 摧毁链表(包括头结点)
void Destroy(DuCircList* ppHead)
{
	Position rear = (*ppHead)->prior;
	Position cur;
	while (*ppHead != rear)
	{
		cur = *ppHead;				// cur指向当前被释放的结点
		// 让表头指向下一个结点，因为上一个结点即将被释放
		(*ppHead) = (*ppHead)->next;
		free(cur);
	}
	free(*ppHead);
	*ppHead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

非通用操作(只适用于整型链表)

1.查找和指定值相同的第一个结点

// 返回和指定值相同的第一个结点的地址，如果没找到，就做异常处理
Position LocateElem(const DuCircList head, ElemType elem)
{
	// 做空表异常处理
	if (IsEmpty(head))
	{
		puts("The double circular linked list is empty!");
		exit(EXIT_FAILURE);
	}

	Position cur = head->next;		// 从第一个数据结点开始找
	while (cur != head )			// 如果找到头结点，说明没找到
	{
		// 如果找到第一个值相同的结点，就直接返回该结点地址
		if (cur->element == elem)
			return cur;
		cur = cur->next;
	}
	// 如果跳出循环，说明没找到，就做异常处理
	puts("The value is not in the list!");
	exit(EXIT_FAILURE);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.返回和指定值相同的第一个结点的序号

// 返回和指定值相同的第一个结点的序号，如果没找到，就返回序号0
int LocatePos(const DuCircList head, ElemType elem)
{
	// 做空表异常处理
	if (IsEmpty(head))
	{
		puts("The double circular linked list is empty!");
		exit(EXIT_FAILURE);
	}

	int pos = 1;
	Position cur = head->next;		// 从第一个数据结点开始找
	while (cur->element != elem)			
	{
		// 如果找到最后一个结点都没找到相同值，就返回0
		if (cur == head->prior)
			return 0;
		cur = cur->next;
		pos++;
	}
	return pos;					
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.移除和指定值相同的第一个结点

/*
 * 移除和指定值相同的第一个结点
 * LocateElem函数已经做了找不到指定值和空表的异常处理
 */
void RemoveElem(DuCircList head, ElemType elem)
{
	Position cur = LocateElem(head, elem);
	cur->prior->next = cur->next;
	cur->next->prior = cur->prior;
	free(cur);
}
1
2
3
4
5
6
7
8
9
10
11

4.自制输入函数（为了头插和尾插方便）

/*
 * 由于头插和尾插都需要连续输入多次数字，而scanf函数不能完美完成这项功能
 * 所以我另写了一个函数专用于将输入的整数存入指定整型变量
 * 如果输入的是整数，就返回true，如果输入非数字字符，就返回false，并且清空缓冲区
 */
bool InputInteger(int* num)
{
	int ok;					// ok用于存储scanf函数成功读入的整数个数
	// 输入num的值，如果合法，ok为1，否则ok不为1
	ok = scanf("%d", num);
	// 如果输入的字符非法，利用下面代码去掉缓冲区里多余的字符
	if (ok != 1)
	{
		while (getchar() != '\n')
			continue;
	}
	// 如果输入的是整数，就返回true，如果输入非法字符，就返回false
	return ok == 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.头插法建立整型双循环链表

/*
 * 使用头插法建立双循环链表，输入数据会依次插入链表的头部
 * 所以，输入数据的顺序和链表中的数据顺序会相反
 */
void HeadInsert(DuCircList* head)
{
	Init(head);			// 先初始化链表
	int num;
	puts("Input a series of integers(enter q to quit):");
	// 可以利用InputInger函数每次输入一个整数给num,如果输入q就结束循环
	while (InputInteger(&num))
	{
		Position newNode = CreateNode(num);
		newNode->next = (*head)->next;
		newNode->prior = *head;
		(*head)->next->prior = newNode;
		(*head)->next = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6.尾插法建立整型双循环链表

/*
 * 使用尾插法建立双循环链表，输入数据会依次插入链表的尾部
 * 所以，输入数据的顺序和链表中的数据顺序相同
 */
void TailInsert(DuCircList* head)
{
	Init(head);			// 先初始化链表
	int num;
	puts("Input a series of integers(enter q to quit):");
	// 可以利用InputInger函数每次输入一个整数给num,如果输入q就结束循环
	while (InputInteger(&num))
	{
		Position newNode = CreateNode(num);
		newNode->next = (*head);
		newNode->prior = (*head)->prior;
		(*head)->prior->next = newNode;
		(*head)->prior = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7.打印整型双循环链表

/*
 * 依次打印链表的元素，最后一个元素连接head
 * 比如1<->2<->3<->head，<->表明是双链表，最后的<->head表明双链表是一个环
 * 如果链表为空，就直接打印head，表示只有头结点
 */
void Print(const DuCircList head)
{
	Position cur = head->next;
	while (cur != head)
	{
		printf("%d<->", cur->element);
		cur = cur->next;
	}
	puts("head");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15