【C语言】数据结构——带头双链表实例探究

2023-12-30 18:26:43

💗个人主页💗
?个人专栏——数据结构学习?
💫点击关注🤩一起学习C语言💯💫

导读：

我们在前面学习了单链表和顺序表。
今天我们来学习双向循环链表。
在经过前面的一系列学习，我们已经掌握很多知识，相信今天的内容也是很容易理解的。
关注博主或是订阅专栏，掌握第一消息。

1. 双链表结构特征

今天我们要学的是双向带头循环列表。
双向循环链表是一个链表的数据结构，每个节点包含两个指针，分别指向前一个节点和后一个节点。与普通的链表不同的是，双向循环链表的尾节点的后继节点指向头节点，头节点的前驱节点指向尾节点，形成一个闭环。
在这里插入图片描述
双向循环链表的特点是可以从任意一个节点开始遍历整个链表。

由于每个节点都可以直接访问前一个节点和后一个节点，所以在双向循环链表中插入和删除节点的操作更加方便和高效。
在插入和删除节点时，只需要修改相邻节点的指针即可，不需要像普通链表那样需要遍历找到前一个节点。

2. 实现双向循环链表

我们需要创建两个 C文件: study.c 和 SList.c，以及一个头文件： SList.h。
头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

2.1 定义结构体

typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

若struct SeqList {}这样来定义结构体的话。在申请SeqList 的变量时，需要这样写，struct SList n;
若用typedef，可以这样写，typedef struct SList{}SL; 。在申请变量时就可以这样写，SL n;
区别就在于使用时，是否可以省去struct这个关键字。

定义两个指针next和prev，分别指向该节点的下一个节点和前一个节点，data记录该节点存放的值。

typedef int LTDataType;

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

2.2 创造节点

因为链表的插入都需要新创建一个节点，为了方便后续的使用以及避免代码的重复出现，我们直接定义函数，后续直接调用即可。

LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

malloc开辟一块空间，存入想要插入的值，前后指针闲置为空，后面调用后再去改变，返回该节点的指针。

2.3 双向链表初始化

先把哨兵位创建出来，前后指针都先指向自己，该节点不存储任何实际的数据，只是作为链表的起始点。

LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);

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

2.4 双向链表打印

方便我们后面测试代码是否出错。

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("哨兵位<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5 双向链表尾插

首先，需要找到链表的尾节点（即头节点的前驱节点）。
然后将新节点插入到尾节点的后面，即新节点的前驱指向尾节点，新节点的后继指向头节点（即原先的尾节点的后继节点），头节点的前驱指向新节点，头节点的后继指向新节点。
最后，将新节点作为尾节点。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;//尾节点
	LTNode* newnode = CreateLTNode(x);//新建一个节点

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

我们用尾插插入1，2，3，4来进行测试。

void TestLT1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

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

在这里插入图片描述
最开始的时候链表只有一个哨兵位，它的前后指针都是指向自己，所以找尾节点找到的就是哨兵位。

第一个数据的插入：

第二个数据的插入：

在这里插入图片描述

2.6 双向链表尾删

要实现带头双向循环链表的尾删操作，可以按照以下步骤：

首先判断链表是否为空，如果为空，则直接返回。

如果链表不为空，找到链表中的最后一个节点的前一个节点，即尾节点的前一个节点。

将尾节点的前一个节点的next指针指向头节点，即将尾节点从链表中移除。

释放尾节点的内存空间。

更新链表的尾指针，即将尾指针指向尾节点的前一个节点。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next);

	LTNode* tail = phead->prev;//最后一个节点
	LTNode* tailprev = tail->prev;//倒数第二个节点
	phead->prev = tailprev;
	tailprev->next = phead;
	free(tail);
	tail = NULL;
}

测试：

void TestLT1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

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

在这里插入图片描述

2.7 双向链表头插

头插法是指将新的节点插入链表的头部，而不是尾部。
在带头双向链表中，首先创建一个新的节点，并将其next指针指向原来的头节点，然后将原来的头节点的prev指针指向新的节点即可。

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);//增加新节点
	LTNode* next = phead->next;//记录原先的第一个节点
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

测试：

void TestLT2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	LTPushFront(plist, 77);
	LTPushFront(plist, 66);
	LTPushFront(plist, 55);
	LTPrint(plist);
}
int main()
{
	TestLT2();
	return 0;
}

在这里插入图片描述

2.8 双向链表头删

带头双向链表的头删操作可以通过以下步骤实现：

如果链表为空，直接返回。
将头节点的下一个节点指针保存在一个临时变量中。
将头节点的下一个节点的前驱节点指针指向空。
将临时变量指向的节点的前驱节点指针指向空。
将头节点指向临时变量指向的节点。
释放临时变量指向的节点的内存空间。

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTNode* del = phead->next;//第一个节点
	LTNode* next = del->next;//第二个节点
	phead->next = next;
	next->prev = phead;
	free(del);
	del = NULL;
}

测试：

void TestLT2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	LTPushFront(plist, 77);
	LTPushFront(plist, 66);
	LTPushFront(plist, 55);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
}
int main()
{
	TestLT2();
	return 0;
}

在这里插入图片描述

2.9 双向链表查找

在带头双向链表中查找一个特定的元素可以按照以下步骤进行：

如果链表为空，则返回空指针或者空值，表示找不到目标元素。
通过指针访问链表的第一个节点，即头节点的下一个节点。
从第一个节点开始，依次遍历链表的每一个节点，直到找到目标元素或者遍历到链表的末尾。
4 如果找到目标元素，返回该节点的指针或者该节点的值，表示找到了目标元素。
如果遍历到链表的末尾都没有找到目标元素，则返回空指针或者空值，表示找不到目标元素。

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;
}

2.10 双向链表任意位置插入

我们利用查找函数，插入到找到的数前面。

判断链表里是否有这位数。
创建一个新节点。
改变pos位置前一个节点、pos节点和新节点的前后驱指针。

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = CreateLTNode(x);//增加新节点
	LTNode* cur = pos->prev;//pos前一个节点
	cur->next = newnode;
	newnode->prev = cur;
	pos->prev = newnode;
	newnode->next = pos;
}

测试：

//任意位置插入测试
void TestLT5()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	if (LTFind(plist, 2))
	{
		LTNode* pos = LTFind(plist, 2);
		LTInsert(pos, 999);
		LTPrint(plist);
	}
	else
	{
		printf("fail\n");
	}
}
int main()
{
	TestLT5();
	return 0;
}

在这里插入图片描述

2.11 双向链表任意位置删除

仍然是利用查找函数，删除find函数返回的节点。

判断是否存在这个数。
把该节点的前一个节点和后一个节点相关联。
释放该节点。

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* before = pos->prev;//pos前一个节点
	LTNode* next = pos->next;//pos后一个节点
	before->next = next;
	next->prev = before;
	free(pos);
	pos = NULL;
}

测试：

//任意位置删除测试
void TestLT6()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	if (LTFind(plist, 2))
	{
		LTNode* pos = LTFind(plist, 2);
		LTErase(pos);
	}
	LTPrint(plist);
}
int main()
{
	TestLT6();
	return 0;
}

在这里插入图片描述

2.12 双链表销毁

动态内存开辟空间，使用完之后需要进行销毁。

void LTDestory(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

2.13 利用任插、任删完成头尾插入和头尾删除

因为我们是带头双向链表，所以我们利用哨兵位就可以轻松找到链表的头尾结点。
所有我们只需要把哨兵位的位置做为参数，就可以轻易完成。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTErase(phead->prev);
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead->next, x);

}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTErase(phead->next);
}

测试：

//任意位置插入删除（头尾增删调用）
void TestLT4()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

	LTPopFront(plist);

	LTPrint(plist);
	LTDestory(plist);
}
int main()
{
	TestLT4();
	return 0;
}

在这里插入图片描述

文章来源:https://blog.csdn.net/qq_64818885/article/details/135305475
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！

【C语言】数据结构——带头双链表实例探究

目录

导读：

1. 双链表结构特征

2. 实现双向循环链表

2.1 定义结构体

2.2 创造节点

2.3 双向链表初始化

2.4 双向链表打印

2.5 双向链表尾插

2.6 双向链表尾删

2.7 双向链表头插

2.8 双向链表头删

2.9 双向链表查找

2.10 双向链表任意位置插入

2.11 双向链表任意位置删除

2.12 双链表销毁

2.13 利用任插、任删完成头尾插入和头尾删除