数据结构之链表（带头双向循环链表）

摘星

发布于 2023-04-28 09:25:49

1720

发布于 2023-04-28 09:25:49

文章被收录于专栏：C/C++学习C/C++学习

前言

在了解了单链表之后，想必大家对于链表已经有了很多的了解，同时对于比单链表更有趣的带头双向循环链表也有了很大的兴趣。因此今天要带大家了解的是链表中的带头双向循环链表。

一、带头双向循环链表

结合图片可以了解到，这种链表有头结点（哨兵位），每个节点带有两个指针，一个指向前一个节点，另一个指向后一个节点，这样就可以将前后节点都联系起来。虽然它的结构看上去有点复杂，但实际上的实现和使用都很简单，具体如何我们往下接着看。

二、双向链表

1.双向链表的声明

typedef int LTDataType;
typedef struct ListNode//链表的节点
{
	LTDataType date;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

2.双向链表的接口

//创建链表的头结点（返回头结点的地址）
ListNode* ListCreate();
//打印链表
void ListPrint(ListNode* plist);
//链表的销毁
void ListDestory(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
//链表的尾删
void ListPopBack(ListNode* plist);
//链表的头插
void ListPushFront(ListNode* plist, LTDataType x);
//链表的头删
void ListPopFront(ListNode* plist);
//链表的查找(如果找到了就返回下标，没找到就报错)
ListNode* ListFind(ListNode* plist, LTDataType x);
//在pos前面插入数据
void ListInsert(ListNode* pos, LTDataType x);
//双向链表删除pos位置处的节点
void ListErase(ListNode* pos);

3.接口的实现

创建返回链表的头结点

//创建返回链表的头结点
ListNode* ListCreate()//头结点（哨兵位）
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->next = p;
	p->prev = p;
	return p;
}

这里有一个要注意点：我之前看的一些书上，对于头结点的date也进行了赋值，主要用于记录链表的长度（结点个数），但是实际上这种做法是不可取的。原因如下：链表节点的数据类型不确定；如果类型为char，那它所存储的最大值是127，如果链表节点个数超过了127就会产生错误；当然，即便是int类型，如果数据数量过多也会产生问题所以，我们所定义的链表的头结点不进行赋值。

创建一个新节点

ListNode* ListBuyNewNode(LTDataType x)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	if (!p)
	{
		perror("malloc fail");//如果扩容失败，会报警告，告诉使用者扩容失败
	}
	p->next = p;
	p->prev = p;
	p->date = x;
	return p;
}

打印链表

void ListPrint(ListNode* plist)
{
	ListNode* p = plist;
	while (p->next != plist)//因为是循环链表，所以当p->next==plist为真时，p指向末尾节点（注意：不能用p-<next==NULL进行判断,会死循环）
	{
		printf("%d->", p->next->date);
		p = p->next;
	}
	printf("NULL\n");//如果链表为空则打印NULL
}

链表的销毁

void ListDestory(ListNode* plist)
{
	ListNode* tail = plist;
	while (plist->next != plist)
	{
		tail = plist->prev;
		plist->prev = tail->prev;
		plist->prev->next = plist;
		free(tail);
	}
	free(plist);
}

尾插

void ListPushBack(ListNode* plist, LTDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	ListNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	plist->prev = newnode;
	newnode->next = plist;
}

尾删

void ListPopBack(ListNode* plist)
{
	ListNode* tail = plist;
	assert(plist->next != plist);//避免链表中没有数据仍在删除造成越界
	tail = plist->prev;
	plist->prev = tail->prev;
	plist->prev->next = plist;
	free(tail);
}

头插

void ListPushFront(ListNode* plist, LTDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->prev = plist;
	newnode->next = plist->next;
	plist->next->prev = newnode;
	plist->next = newnode;
}

头删

void ListPopFront(ListNode* plist)
{
	assert(plist->next != plist);
	ListNode* begin = plist->next;
	plist->next = begin->next;
	begin->next->prev = plist;
	free(begin);
}

在链表中进行查找

(如果找到了就返回下标，没找到就返回NULL)

ListNode* ListFind(ListNode* plist, LTDataType x)
{
	ListNode* pos = plist->next;
	while (pos != plist)
	{
		if (pos->date == x)
			return pos;
		pos = pos->next;
	}
	exit(-1);//
}

查找也可以充当修改。

在pos前面插入数据

void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	pos->prev = newnode;
}

链表删除pos位置处的节点

void ListErase(ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

4.主函数（测试）

void test1()//测试尾插
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	// 双向链表尾插
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
void test2()//测试尾删
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	ListPushBack(plist, 10);
	//链表的尾删
	ListPopBack(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
	/*ListPopBack(plist);//再删除就会报错
	ListPrint(plist);*/
	//链表的销毁
	ListDestory(plist);
}
void test3()//测试头插
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
void test4()//测试头删
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPrint(plist);
	/*ListPopFront(plist);//再删除就报错
	ListPrint(plist);*/
	//链表的销毁
	ListDestory(plist);
}
void test5()//测试查找
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	ListNode*pos = ListFind(plist, 38);
	if (pos)
	{
		printf("找到了\n");
	}
	//链表的销毁
	ListDestory(plist);
}
void test6()//测试在pos位置之前插入一个节点
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	ListNode*pos = ListFind(plist, 22);
	ListInsert(pos,80);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
void test7()//测试删除pos位置的数据
{
	//创建返回链表的头结点
	ListNode* plist = ListCreate();
	ListPushFront(plist, 20);
	ListPushFront(plist, 21);
	ListPushFront(plist, 25);
	ListPushFront(plist, 24);
	ListPushFront(plist, 22);
	ListPrint(plist);
	ListNode*pos = ListFind(plist, 22);
	ListErase(pos);
	ListPrint(plist);
	//链表的销毁
	ListDestory(plist);
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	test7();
	return 0;
}

总结

以上就是今天要讲的内容，本文主要介绍了带头双向循环链表，对带头双向循环链表的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路自行实现带头双向循环链表。本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构