C语言实现数据结构——双向带头结点的循环链表_双向结点

本人数据结构编写规则

① 在函数中判断结构体指针是否为空时采用assert函数，而不是用if语句判断。
② 函数的命名规则遵循：操作+结构类型名 的规则。例如 InitSqList 与DestroySqList。
③ 严蔚敏老师一书中很多运用了C++的语法，而我们是用C语言来实现，因此编写规则与书上会有很多不同，但是思路是一样的。例如用malloc代替new，free代替delete，引用与指针的区别等。
④ 本文没有采用bool变量以及自定义的Status作为返回值来判断是否操作成功。

正文

单链表的结点中只有一个指向直接后继的指针域，因此只能顺着指针单向遍历以寻找其他结点。因为单链表在尾插和尾删这种场景下的效率也是不尽人意的，因为要遍历整个链表，时间复杂度即使O(N)，双向循环链表这种数据结构由此而生。

本篇介绍的是带头结点的双向循环链表。

函数声明

DubCirNode* InitDubCirList(); 		初始化，返回头结点的地址
DubCirNode* CreateNewnodeDubCirList(DubCirDataType i);	新建结点
void BackInsertDubCirList(DubCirNode* phead, DubCirDataType i);
void BackDeleteDubCirList(DubCirNode* phead);尾插与尾删

void FrontInsertDubCirList(DubCirNode* phead, DubCirDataType i);
void FrontDeleteDubCirList(DubCirNode* phead);头插与头删

DubCirNode* SearchDubCirList(DubCirNode* phead, DubCirDataType i);
void PrintDubCirList(DubCirNode* phead);打印

void InsertBeforeDubCirList(DubCirNode* pos, DubCirDataType i);
在pos地址处结点之前插入
void DeleteAtDubCirList(DubCirNode* pos); 删除pos地址处结点
void ModifyAtDubCirList(DubCirNode* pos, DubCirDataType i);
修改pos地址处结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结构体定义

typedef int DubCirDataType;
typedef struct DCL
{
	DubCirDataType data;
	struct DCL* pre;
	struct DCL* next;
}DubCirNode;
1
2
3
4
5
6
7

相比于单链表，结构体的定义多出一个pre指针，即指向直接前驱的指针域。在单链表中我们可以不选择初始化，但是这里为了满足链表循环的特性，我们选择对链表进行初始化。

初始化与新建结点函数

DubCirNode* CreateNewnodeDubCirList(DubCirDataType i)
{
	DubCirNode* newnode = (DubCirNode*)malloc(sizeof(DubCirNode));
	if (newnode != NULL)
	{
		newnode->pre = NULL;
		newnode->next = NULL;
		newnode->data = i;
	}
	else
	{
		printf("开辟新结点失败！");
		exit(-1);
	}
	return newnode;
}
DubCirNode* InitDubCirList()
{
	DubCirNode* newnode = CreateNewnodeDubCirList(10086);
	newnode->next = newnode;	头结点随便存个数据就行
	newnode->pre = newnode;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

让前后指针都指向头结点本身，而不是像单链表时那样指向NULL。初始化函数选择返回新建结点的地址，便可以在初始化的时候不传二级指针。也可以新建结点后传二级指针后再进行修改。因为修改指针的指向需要传二级指针。

头插函数

void FrontInsertDubCirList(DubCirNode* phead, DubCirDataType i)
{
	assert(phead);
	DubCirNode* newnode = CreateNewnodeDubCirList(i);
	newnode->pre = phead;        1
	newnode->next = phead->next; 2
	newnode->next->pre = newnode;3
	phead->next = newnode;		 4
}
1
2
3
4
5
6
7
8
9

头插函数相比单链表多了对pre指针的处理。

void FrontDeleteDubCirList(DubCirNode* phead)
{
	assert(phead);
	DubCirNode* cur = phead->next;
	cur->next->pre = phead;		1
	phead->next = cur->next;	2
	free(cur);
	cur = NULL;
}
1
2
3
4
5
6
7
8
9

尾插

void BackInsertDubCirList(DubCirNode* phead, DubCirDataType i)
{
	assert(phead);
	DubCirNode* tail = phead->pre;
	DubCirNode* newnode = CreateNewnodeDubCirList(i);

	tail->next = newnode;	1
	newnode->pre = tail;	2

	newnode->next = phead;	3
	phead->pre = newnode;	4

}
1
2
3
4
5
6
7
8
9
10
11
12
13

尾插函数就不用通过tail遍历整个链表来找到尾结点，直接找到phead的pre既是尾结点。

尾删

void BackDeleteDubCirList(DubCirNode* phead)
{
	assert(phead);
	if (phead->next == phead)
	{
		printf("链表为空，删除失败\n");
		return;
	}
	DubCirNode* tail = phead->pre;
	DubCirNode* pretail = tail->pre;
	pretail->next = tail->next;	1
	phead->pre = pretail;		2
	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在pos前插入结点

void InsertBeforeDubCirList(DubCirNode* pos, DubCirDataType i)
{
	assert(pos);
	DubCirNode* newnode = CreateNewnodeDubCirList(i);
	DubCirNode* prepos = pos->pre;
	newnode->next = pos;	1
	newnode->pre = prepos;	2
	prepos->next = newnode;	3
	pos->pre = newnode;		4
}
1
2
3
4
5
6
7
8
9
10

删除pos位置的结点

void DeleteAtDubCirList(DubCirNode* pos)
{
	assert(pos);
	DubCirNode* prepos = pos->pre;
	DubCirNode* nextpos = pos->next;
	prepos->next = nextpos;
	nextpos->pre = prepos;
	free(pos);
	pos = NULL;
}
1
2
3
4
5
6
7
8
9
10

这里我们可以对最后两个增删函数进行复用，复用到头尾的增删函数里。
例如：

InsertBeforeDubCirList(phead->next, i);
在phead的下一个结点前插入，即是头插
DeleteAtDubCirList(phead->next);
删除phead的下一个结点，即是头删
InsertBeforeDubCirList(phead, i);
在phead的前一个结点插入，即是尾插
DeleteAtDubCirList(phead->pre);
删除phead的前一个结点，即是尾删
1
2
3
4
5
6
7
8

编写这些函数的时候有一个明显的优点，不用考虑边界的条件，因为这个链表从始至终都是循环的，即不存在错误访问到空指针的情况。

头结点的注意事项

头结点一般不用于存储数据，有一种说法是用头结点的数据域来存储整个链表中元素的个数，但这是考虑有所欠缺的，因为要考虑到数据的类型，例如存储浮点数，或者是char类型，当链表元素超过128个就会出现问题，甚至元素的个数可以是指针类型，所以头结点一般不存储有意义的数据，随便存个数字例如10086用于区分头结点就行。

结语

双向带头循环链表是非常有用且高效的数据结构。其解决了单链表只能单向遍历、尾部操作时间复杂度高的缺点，在遍历的时候更加方便。但是这种结构同样存在缺陷，需要记录前缀结点，增加了内存的开销。