目录

带头结点的双向循环链表

 1.存储定义

2.结点的创建

3.结点的初始化

4.尾插结点

5.尾删结点

6.头插结点

7.头删结点 

8.查找并返回结点

9.在pos结点前插入结点

10.删除pos结点

11.打印链表

 12.销毁链表

13.头插结点2.0版

 14.尾插结点2.0版


前言

我们使用链表时,想要去找到前面的前驱结点的时候,我们发现了受到限制,因为当时的结点只能去找后面的结点。

于是,就到了这里带头结点的双向循环链表

如图

首先给出  双向链表定义:是在单链表每个结点中,再设置一个指向其前驱结点的指针域。

双向循环链表就是最后一个结点的next指向头结点,头结点的前驱指向尾结点。

带头结点的双向循环链表

 1.存储定义

typedef int CLDataType;

typedef  struct ListNode
{
	CLDataType val;
	struct ListNode* next; //存放后面结点的指针
	struct ListNode* pre;  //存放前面结点的指针
}ListNode;

2.结点的创建

结点的创建,刚开始创建头结点我们一般会采用二级指针的方式这里我们采用使用函数返回值的形式来避免野指针问题

//创建链表
ListNode* CreateNode(CLDataType x) 
{
	//这里采用返回值的形式进行创建结点
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL) 
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->pre = NULL;
	newnode->next = NULL;
	return newnode;
}

 如果是刚开始创建的头节点的话:

3.结点的初始化

这个时候就能体现带头结点双向循环链表的好处了

ListNode* InitNode() 
{
	ListNode* phead = CreateNode(-1);
	//让头节点的前驱和后继结点都指向自己
	phead->next = phead;	
	phead->pre = phead;
	return phead;
}

 因为修改了头结点,所以接着使用函数返回值的形式。

注意:初始化时,头结点的前驱和后继指针都指向自己如图

4.尾插结点

之前的单链表尾插需要遍历整个链表去找尾结点,但是,这里是带头结点的双向循环链表,只需去找头结点的前驱结点就找到了尾结点。

//尾插结点
void ListPushBack(ListNode* phead, CLDataType x) 
{
	assert(phead);
	ListNode* newnode = CreateNode(x);
	ListNode* tail = phead->pre;
	
	tail->next = newnode; //之前的尾结点的后继指针指向新结点
	newnode->pre = tail;  //新结点的前驱指向之前的尾结点
	newnode->next = phead; //新结点的后继指针指向头结点
	phead->pre = newnode;  //头结点的前驱指向

 当链表中只有一个头结点的时候,tail指向自己。

 再继续尾插时,仍是这样。

5.尾删结点

 一般都是先找到尾节结点,然后再去找到尾结点的前一个结点Pre。Pre指向头结点,头结点的前驱指向Pre。之后再删去尾节结。

//尾删结点
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //避免只有一个头结点
	ListNode* tail = phead->pre;
	ListNode* Pre = tail->pre; //用来记录尾结点的前一个结点
	Pre->next = phead;
	phead->pre = Pre;
	free(tail);
	tail = NULL;
}

注意:当只有一个头结点的情况时,说明已经没有链表结点。所以不能进行删除。进而这里采用assert( phead->next != phead) 来避免此情况。

6.头插结点

单链表的头插相似,用next指针记录头结点的下一个结点。先让新结点与next指针指向的结点建立连接,再与头结点建立连接

//头插结点
void ListPushFront(ListNode* phead,CLDataType x) 
{
	assert(phead);
	ListNode* newnode = CreateNode(x);
	ListNode* next = phead->next; //记录头结点后的第一个结点

	newnode->next = next;
	next->pre = newnode;

	phead->next = newnode;
	newnode->pre = phead;
}

7.头删结点 

这里需要注意的是避免只有一个头结点的情况下,删除结点,这样使用同尾删结点一样的方法通过断言 assert(phead->next != phead);

//头删结点
void ListPopFront(ListNode* phead) 
{
	assert(phead);
	assert(phead->next != phead);
	phead->next = phead->next->next;
	phead->next->next->pre = phead;
}

8.查找返回结点

这里采用cur指针去遍历链表,找到就返回结点,没有找到就返回空。

//查找返回结点
ListNode* ListFind(ListNode* phead, CLDataType x) 
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead) 
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

9.在pos结点前插入结点

因为是带头结点的双向循环链表,这样就可以直接进行插入

//在pos前面插入结点
void ListInsert(ListNode* pos, CLDataType x) 
{
	assert(pos);
	ListNode* newnode = CreateNode(x);
    //注意顺序
    //先让后驱建立连接
	newnode->next = pos;
	pos->pre->next = newnode;
    //再前驱建立连接
	newnode->pre = pos->pre;
	pos->pre = newnode;
}

10.删除pos结点

 修改pos的前驱和后继

//删除pos位置的结点
void ListErase(ListNode* pos) 
{
	assert(pos);
	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
}

11.打印链表

//打印链表
void ListPrint(ListNode* phead) 
{
	assert(phead);
	ListNode* cur = phead->next;
	printf("phead<==>");
	while (cur != phead) 
	{
		printf("%d<==>", cur->val);
		cur = cur->next;
	}
	printf("n");
}

 12.销毁链表

//销毁链表
void ListDestory(ListNode* phead) 
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

13.头插结点2.0版

这里我们借助 在pos结点前插入结点 的接口

头插结点,那就是把pos结点变为 phead->next 的结点。这样结点的插入模拟了头插结点,从而减少了一写代码工作量

//头插结点2.0
void ListushFront(ListNode* phead, CLDataType x)
{
	assert(phead);
	ListNode* newnode = CreateNode(x);
	ListNode* next = phead->next; //记录头结点后的第一个结点
	ListInsert(next,x); //这里的next相当于pos结点
}

例如  :在 1结点 前插入 结点25

 

 14.尾插结点2.0版

根据带头结点的双向循环链表的特性,再借助前面的 在pos结点前插入结点(ListInsert) 的接口

这时我们会想到的就是 尾插结点不是在尾结点的后面进行插入的吗,而ListInsert是在pos前面进行结点的插入。 这时就采用  在头结点的前进行插入结点,从而达到尾插结点的特性

//尾插结点
void ListPushBack(ListNode* phead, CLDataType x)
{
	assert(phead);
	ListNode* newnode = CreateNode(x);
	ListInsert(phead,x);
}

原文地址:https://blog.csdn.net/qq_72505850/article/details/134468936

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_21558.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注