温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C语言如何实现带头双向循环链表

发布时间:2022-03-28 09:45:19 来源:亿速云 阅读:158 作者:小新 栏目:开发技术

这篇文章主要介绍了C语言如何实现带头双向循环链表,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

前言

C语言如何实现带头双向循环链表

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

1. 创建结构体

注意:typedef起作用是在第7行哦。所以第5,6还需要写struct ListNode类型。

typedef int LNDataType;

typedef struct ListNode
{
	  struct ListNode* prev;
 	  struct ListNode* next;
      LNDataType val;
}LN;

2.malloc新节点

注意:需判断新开辟的节点是否为空。

//申请一个新节点
LN* BuynewNode(LNDataType x)
{
	LN* newNode = (LN*)malloc(sizeof(LN));
	if (newNode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->val = x;
	return newNode;
}

3.创建哨兵位节点

注意:这里因为需要改变plist指针的内容,也就是改变plist指针的指向,所以需要传递plist的地址。

一句话就是:需要改变谁的内容,就传谁的地址

这里有一点非常巧非常妙,就是phead的后继和前驱都是指向自己(phead),这里是模仿C++STL库里的哨兵位节点。

只能佩服想出来这些东西的大神。这样设计哨兵位节点的话,后续尾插,尾删,都特别的巧妙。

C语言如何实现带头双向循环链表

C语言如何实现带头双向循环链表

test.c

	LN* plist = NULL;
	ListNodeInit(&plist);

List.h

//初始化节点
void ListNodeInit(LN** pphead)
{
	LN* newNode = BuynewNode(0);
	*pphead = newNode;
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}

4.尾插

注意:需要断言的原因是因为,即使链表没有一个节点,那链表至少还有个头,所以phead肯定不为空。

这里没有传地址的原因是因为,你不需要改变plist的指向,你改变的是plist指向的结构体里面的值。

多个节点尾插的情况如图。

C语言如何实现带头双向循环链表

一个节点的尾插。

C语言如何实现带头双向循环链表

//尾插
void ListNodePushBack(LN* phead, LNDataType x)
{
	assert(phead);
	LN* newNode = BuynewNode(x);
	LN* tail = phead->prev;
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;
}

5.打印

注意:因为带个头,所以cur从第二个位置开始。

//打印
void ListNodePrint(LN* phead)
{
	LN* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

6.尾删

注意不能删掉头结点,free掉头结点的话会造成野指针,再次访问时会造成非法访问。
所以要用assert断言不为首节点。

//尾删
void ListNodePopBack(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LN* tail = phead->prev;
	LN* tailPrev = tail->prev;
	free(tail);
	tail = NULL;
	phead->prev = tailPrev;
	tailPrev->next = phead;
}

7.头插

最好用next记录下一个节点。这样方便,思路清晰

//头插
void ListNodePushFront(LN* phead, LNDataType x)
{
	assert(phead);
	LN* newNode = BuynewNode(x);
	LN* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = next;
	next->prev = newNode;
}

8.在指定位置pos的前面进行插入

一般情况

C语言如何实现带头双向循环链表

只有一个节点时。

C语言如何实现带头双向循环链表

两种情况都适用以下代码。

//指定位置前插入,极限是头插
void ListNodeInsert(LN* pos, LNDataType x)
{
	if (pos == NULL)
	{
		printf("没有找到这个数\n");
		return;
	}
	LN* newNode = BuynewNode(x);
	LN* tailPrev = pos->prev;
	tailPrev->next = newNode;
	newNode->prev = tailPrev;
	newNode->next = pos;
	pos->prev = newNode;
}

9. 删除指定位置pos节点

正常情况

C语言如何实现带头双向循环链表

极限尾删

C语言如何实现带头双向循环链表

两种情况都适用以下代码。

//指定位置删除
void ListNodeErease(LN* phead, LN* pos)
{
	if (pos == phead || pos == NULL)
	{
		printf("pos指向头,或为空\n");
		return;
	}
	LN* posPrev = pos->prev;
	LN* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

10.销毁链表

注意:这里相当于malloc用完之后的free。否则会造成内存泄漏。
cur可以置空,但用处不大,因为cur是形参,形参是实参的一份临时拷贝,形参置空并不能改变实参。外部的实参还是依旧能非法访问到cur所指向的空间。

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

感谢你能够认真阅读完这篇文章,希望小编分享的“C语言如何实现带头双向循环链表”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI