欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

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

最编程 2024-06-11 12:25:47
...

前言

之前已经介绍过数据结构链表中的单链表，现在我们一起来学习双链表。 那什么又是双链表呢？ 在学习双链表之前我们来看看链表的分类。

1. 链表的分类

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

链表
链表

1.1 链表说明

1.单向或者双向

单向
单向

2.带头或者不带头

不带头
不带头
带头
带头

3.循环或者不循环

不循环
不循环
带头循环
带头循环

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

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

2. 双向循环链表

2.1 双向循环链表的结构

带头循环双链表
带头循环双链表

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。 “哨兵位”存在的意义：遍历循环链表避免死循环。

2.2 双向循环链表的实现

我们在上面的图中看见，每个节点有三部分内容：第一部分就是保存的数据data，第二部分就是保存下一个节点地址的next指针， 第三部分就是保存前一个节点地址的prev指针。 在初始状态时，双向链表为空，这里的空指的是只有一个哨兵位，而哨兵位节点是不能被操作的，即哨兵位不能被改变。

哨兵位
哨兵位

要用C语言先定义一个包含哨兵位的双向循环链表。我们发现此时哨兵位节点的下一个节点指向的还是哨兵位，哨兵位的前一个指针指向的还是哨兵位。

代码语言：javascript
复制 
typedef struct ListNode {
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

向之前的单链表一样，用双向循环链表来实现增删改查。下面我们一起来学习一下吧。

3. 用代码实现双向循环链表

同之前的单链表一样我们用三个文件来实现， List.h用来实现函数声明，List.c用来实现相关函数，test.c用来测试代码。

3.1 双向循环链表的初始化

3.1.1 初始化分析

而在实现双向循环链表初始化时不需要传入参数，调用该方法之后给我们返回一个头结点。

为了更加方面知道哨兵位的位置，在初始化时给它的数据赋值为-1。 我们实现节点有三部分内容：数据 前驱指针 后继指针。

哨兵位
哨兵位

而在上面我们就提到哨兵位节点的下一个节点指向的还是哨兵位，哨兵位的前一个指针指向的还是哨兵位。

3.1.2 初始化代码
代码语言：javascript
复制 
LTNode* LTInit() 
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL) {
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->prev = phead;
	return phead;
}

3.2 双向循环链表的尾插

3.2.1 尾插分析
尾插
尾插

尾插就是在节点之后插入新节点，值得注意的是，在双向循环链表中要实现尾插就是在哨兵位的前面插入节点。 因为涉及到新节点的申请，那先讲讲如何申请一个新的节点。

3.2.2 节点的申请

我们用malloc向内存申请一个大小为sizeof(LTNode)的空间，用来存放我们所要插入的数据x。而它的node->next和node->prev在插入前都置为NULL。

代码语言：javascript
复制 
LTNode* ListBuyNode(LTDataType x)
 {
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	node->data = x;
	node->next = node->prev = NULL;
	return node;
}
3.2.3 尾插的代码

在进行尾插时要先处理插入节点node的前驱和后继指针，让node->prev = phead->prev，和node->next = phead;再处理phead->prev(之前的尾结点) 和 phead，让phead->prev->next = node，和phead->prev = node。

下面我们用代码来实现一下：

代码语言：javascript
复制 
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* node = ListBuyNode(x);
	node->prev = phead->prev;
	node->next = phead;
	phead->prev->next = node;
	phead->prev = node;
}

在test.c中插入1，2，3，4

结果
结果

3.3 双向循环链表的头插

3.3.1 头插分析
头插
头插

同尾插一样，再插入之前要先申请一个节点用来存放新插入的数据，就不再多赘述。

头插要处理node的prev和next，让node->prev = phead，和node->next = phead->next;再处理phead和 phead->next，让phead->next->prev = node，和phead->next = node。

3.3.2 头插代码
代码语言：javascript
复制 
void LTPushFront(LTNode* phead, LTDataType x) 
{
	assert(phead);
	LTNode* node = ListBuyNode(x);
	node->prev = phead;
	node->next = phead->next;
	phead->next->prev = node;
	phead->next = node;
}

在尾插入的基础上插入5，6，7

头插
头插

3.4 双向循环链表的尾删

3.4.1 尾删分析
尾删
尾删

我们用del来表示要删除的节点，要实现尾巴删除，就要先确定删除节点的位置，而我们知道这是在双向循环链表中，哨兵位的前一个节点就是del,所以就先定义del = phead->prev。 先处理del的prev节点，让它的下一个节点指向哨兵位del->prev->next = phead，再处理phead，让它的前一个节点指向del的前一个节点就是phead->prev = del->prev。 最后再释放del,将del置为NULL。

3.4.2 尾删代码
代码语言：javascript
复制 
void LTPopBack(LTNode* phead) 
{
	assert(phead);
    assert(phead->next != phead);
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
    free(del);
	del = NULL;
}

在上面的基础上尾删4次的结果

尾删除
尾删除

3.5 双向循环链表的头删

3.5.1 头删分析
头删
头删

同尾删一样，也用del来表示要删除的节点。 也是要先找到del的位置，而它的位置就是哨兵位的下一个节点，也就是phead->next。 然后同样先处理del的下一个节点，让它的prev指向哨兵位，就是del->next->prev = phead；再处理哨兵位的下一个节点，让它等于del的下一个节点，就是phead->next = del->next。 同上面语言先把del释放，再置为NULL。

3.5.2头删代码
代码语言：javascript
复制 
void LTPopFront(LTNode* phead)
 {
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;

	//phead del->next
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

在头插的基础上，实行头删5次，结果如下：

头删
头删

3.6 双向循环链表指定位置之后插入

3.6.1 指定位置之后插入分析
插入
插入

要在指定位置之后插入数据，我们要先找到这个位置，用pos来记录这个地址。 而插入的数据的节点我们同样用node来记录。 首先处理node的prev和next，让node的下一个节点指向pos的下一个节点，就是node->next = pos->next；然后让node的prev指向pos，就是node->prev = pos。 再处理pos的next和 pos->next的prev，让pos的next指向node，就是pos->next = node;在让pos->next的prev指向node,也就是node->next->prev = node。

3.6.2 指定位置之后插入代码
代码语言：javascript
复制 
void LTInsert(LTNode* pos, LTDataType x) 
{
	assert(pos);
	LTNode* node = ListBuyNode(x);
	node->next = pos->next;
	node->prev = pos;
	pos->next = node;
	node->next->prev = node;
}

在1的位置之后插入11

插入
插入

3.7 双向循环链表删除指定节点

3.7.1 删除指定节点分析
删除
删除

同样我们要先找到这个位置，用pos来记录这个地址。 先处理pos->next的prev,让pos->next->prev = pos->prev; 再处理pos->prev的next，让pos->prev->next = pos->next; 最后同样是释放pos，将pos置为NULL。

3.7.2 删除指定节点代码
代码语言：javascript
复制 
void LTErase(LTNode* pos)
 {
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

在尾插的基础是删除数据为1的节点，结果如下：

删除
删除

3.8 双向循环链表的销毁

3.8.1 销毁分析
销毁
销毁

定义一个cur指针用来存除了哨兵位以后的位置，让它初始化为cur = phead->next; 使用while循环时，再定义一个指针next，让它始终为next = cur->next，这样释放cur以后，cur就能继续向后遍历。 而除了循环之后，哨兵位还没有释放，此时我们需要在循环外释放哨兵位，然后将它置为NULL。

3.8.2 销毁代码
代码语言：javascript
复制 
void LTDestroy(LTNode* phead) {
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//除了循环之后，哨兵位还没有释放
	free(phead);
	phead = NULL;
}

同样在尾插的基础上，实现 双向循环链表的销毁，结果显示：

结果
结果

4. 附代码

4.1 List.h

代码语言：javascript
复制 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义双向链表节点的结构
typedef int LTDataType;

typedef struct ListNode {
	LTDataType data;//val == data
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

void LTPrint(LTNode* phead);

//链表的初始化以及销毁
//void LTInit(LTNode** pphead);//前提：我们要传入一个头结点
LTNode* LTInit();//不需要传入参数，调用该方法之后给我们返回一个头结点

//实际这里更倾向于传递一级指针，因为要保持接口一致性
void LTDestroy(LTNode* phead);
//void LTDestroy(LTNode** pphead);


//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
//插入删除操作
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

4.2 List.c

代码语言：javascript
复制 
#include"List.h"
//前提：我们要传入一个头结点
//void LTInit(LTNode** pphead) {
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	if (*pphead == NULL) {
//		perror("malloc error");
//		return;
//	}
//	//节点有三部分内容：数据 前驱指针 后继指针
//	(*pphead)->data = -1;//哨兵位
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}
//不需要传入参数，调用该方法之后给我们返回一个头结点
LTNode* LTInit() {
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL) {
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->prev = phead;
	return phead;
}
LTNode* ListBuyNode(LTDataType x) {
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	node->data = x;
	node->next = node->prev = NULL;
	return node;
}
//插入操作
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* node = ListBuyNode(x);

	//先处理新节点node的前驱和后继指针
	node->prev = phead->prev;
	node->next = phead;

	//再处理phead->prev(之前的尾结点) 和  phead
	phead->prev->next = node;
	phead->prev = node;
}
void LTPrint(LTNode* phead) {
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void LTPushFront(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* node = ListBuyNode(x);
	//node节点的 prev next
	node->prev = phead;
	node->next = phead->next;

	//处理phead  phead->next
	phead->next->prev = node;
	phead->next = node;
}
void LTPopBack(LTNode* phead) {
	assert(phead);
	//链表不能为空链表：链表中只有一个哨兵位节点
	assert(phead->next != phead);

	LTNode* del = phead->prev;
	//先处理del的prev节点
	del->prev->next = phead;
	//处理phead
	phead->prev = del->prev;

	free(del);
	del = NULL;
}
void LTPopFront(LTNode* phead) {
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;

	//phead del->next
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {
	assert(pos);
	LTNode* node = ListBuyNode(x);
	//node的prev 和 next
	node->next = pos->next;
	node->prev = pos;

	//pos的next 和 pos->next的prev
	pos->next = node;
	node->next->prev = node;
}
void LTErase(LTNode* pos) {
	assert(pos);
	//pos->prev:next  pos  pos->next:prev
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void LTDestroy(LTNode* phead) {
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//除了循环之后，哨兵位还没有释放
	free(phead);
	phead = NULL;
}
//void LTDestroy(LTNode** pphead) {
//	assert(pphead && *pphead);
//	LTNode* cur = (*pphead)->next;
//	while ( cur!=*pphead )
//	{
//		LTNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//}

4.3 test.c

代码语言：javascript
复制 
#include"List.h"

void ListTest() {
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);// 1 2 3 4

	//LTPushFront(plist, 5);
	//LTPushFront(plist, 6);
	//LTPushFront(plist, 7);
	//LTPrint(plist);//7 6 5 1 2 3 4

	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	/*LTPopFront(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);*/

	测试指定位置之后插入
	//LTNode* find = LTFind(plist, 1);
	///*LTInsert(find, 11);*/
	//LTErase(find);
	//LTPrint(plist);
	LTDestroy(&plist);
	/*LTDestroy(plist);*/
	//传一级指针的时候需要手动将plist置为空
	plist = NULL;
	LTPrint(plist);
}

int main()
{
	ListTest();
	return 0;
}

上一篇： HashMap

下一篇： Python 高级 - 插入列表头

推荐阅读