当前位置:首页 » 《随便一记》 » 正文

【数据结构】带头双向循环链表_Suk_god的博客

0 人参与  2022年04月09日 09:44  分类 : 《随便一记》  评论

点击全文阅读


文章目录

  • 双向链表的结构
  • 基础操作
    • 数据结构
    • 创建结点
    • 创建头结点
    • 双向链表的销毁
    • 双向链表的打印
    • 双链表的尾插
    • 双向链表的尾删
    • 双链表的头插
    • 双链表的头删
    • 双向链表的查找
    • 双向链表在pos的前面进行插入
    • 双向链表删除pos位置的节点
    • 改写相关函数
      • 尾插
      • 尾删
      • 头插
      • 头删
  • 完整代码
  • 总结

双向链表的结构

1.双向循环链表的每一个结点都包括以下部分:
在这里插入图片描述
2.头结点中的data域没有实际意义

3.双向循环链表
例如:
在这里插入图片描述

基础操作

数据结构

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

创建结点

由于链表是动态开辟空间,所以每次插入元素是都需要从堆上申请空间。
具体操作细节如下:

//创建一个节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == newNode)
	{
		return NULL;
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

创建头结点

对于头结点来说,创建头结点时与其他结点略有不同,它的data域没有实际意义。

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	//头结点的data域无实际意义
	ListNode* head = BuyListNode(0);
	head->next = head;
	head->prev = head;
	return head;
}

双向链表的销毁

由于链表的每一个结点都是从堆上动态开辟的,所以在使用完毕后必须要手动的释放,否则就会产生内存泄漏。
具体细节分析见下图:
在这里插入图片描述
注意传参问题。其他的都是一些常规操作!
具体实现代码如下:

// 双向链表销毁
void ListDestory(ListNode** pHead)
{
	assert(pHead);
	
	ListNode* delNode = (*pHead)->next;
	while (delNode != *pHead)
	{
		(*pHead)->next = delNode->next;
		delNode->next->prev = (*pHead);
		free(delNode);
		delNode = (*pHead)->next;
	}
	//最终剩下头结点没有释放
	free(*pHead);
	*pHead = NULL;
}

双向链表的打印

循环遍历整个链表,同时输出每个节点的data域内容。
注意:循环终止条件的确定
由于是循环双链表 ,所以当输出结点与头结点相等时就已经完成一趟的遍历。

// 双向链表打印
void ListPrint(ListNode* pHead)
{
		

	if (pHead == pHead->next)
	{
		printf("空链表,无结点!\n");
		return;
	}
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}

	printf("\n");
}

双链表的尾插

在链表的末尾插入一个结点,要经历以下步骤:
1.创建新节点
2.找到原链表的最后一个结点
3.改变链表相关指针的指向,使得新结点成为链表的最后一个结点
前两步可以很容易的实现。我们具体分析一下第三步:
在这里插入图片描述
可以看到,在双向循环链表中尾插一个结点,需要改变四个指针的指向,并且具有一定的先后顺序。
接下来看具体实现代码

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* newNode = BuyListNode(x);
	newNode->next = pHead;
	newNode->prev = pHead->prev;
	pHead->prev->next = newNode;
	pHead->prev = newNode;
}

双向链表的尾删

想要删掉末尾结点,需要有以下操作步骤:
1.找到末尾结点

2.由于末尾结点将要被删除,所以应当改变相关指针,使得原链表的倒数第二个结点成为新链表的末尾结点。

3.释放要删除结点的内存空间。

对于双向循环链表来说,1,3两步都很容易实现,我们具体分析一下步骤2
通过改变指针的指向,从而将倒数第二个结点(下图的结点3)作为新链表的末尾结点。
在这里插入图片描述
完整操作见代码

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);

	if (pHead ==  pHead->next)
	{
		printf("链表为空,无法删除!\n");
		return;
	}

	ListNode* delNode = pHead->prev;
	pHead->prev = delNode->prev;
	delNode->prev->next = pHead;
	free(delNode);
	delNode = NULL;
}

双链表的头插

想要头插一个结点,需要进行如下几步操作:
1.为要插入的结点申请空间

2.找到原链表的第一个结点

3.调整相关指针指向,让新结点的prev与头结点相连,新结点的next与原链表的首结点相连

着重分析步骤3:
要想插入一个结点,我们就要对原链表中的相关指针进行修改,从而将新结点加进去。具体实现过程见下图
在这里插入图片描述
下面是总体实现的代码

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newNode = BuyListNode(x);

	newNode->next = pHead->next;
	newNode->prev = pHead;
	pHead->next->prev = newNode;
	pHead->next = newNode;
}

双链表的头删

步骤:
1.找到第一个结点、

2.修改指针,使得第二个结点与头结点相连

3.释放原来的结点(步骤1找到的结点)

主要分析步骤2的实现过程:
在这里插入图片描述
完整实现代码如下

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	if (pHead == pHead->next)
	{
		printf("没有结点,无法删除!\n");
		return;
	}
	ListNode* delNode = pHead->next;

	pHead->next = delNode->next;
	delNode->next->prev = pHead;
	free(delNode);
	delNode = NULL;
}

双向链表的查找

主体思想与链表的输出一致,循环遍历链表,在遍历的过程中判断每一个结点的data域与目标值是否相等,若相等,则返回该结点的地址,退出循环。如果遍历链表一遍后仍然没有找到,难么就返回NULL值。
这个就不画图分析了,直接上代码

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//循环遍历比较data域,注意循环的控制条件
	ListNode* cur  = pHead->next;
	while (pHead != cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

双向链表在pos的前面进行插入

步骤:
1.为插入的结点开辟空间
2.修改相关指针,插入链表
具体过程如下图所示
在这里插入图片描述
上图分析的比较详细,直接上实现代码

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newNode = BuyListNode(x);
	newNode->next = pos;
	newNode->prev = pos->prev;
	pos->prev->next = newNode;
	pos->prev = newNode;
}

双向链表删除pos位置的节点

要删除一个结点,那么我们要将它的前一个节点与后一个结点建立关系后,再将要删除结点直接释放掉就可以。就如下图展示的这样
在这里插入图片描述
操作都比较简单,就直接上代码了

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

改写相关函数

仔细观察上述代码,我们可以发现,其实对链表进行尾插、尾删、头插、头删都可以看做是对链表任意位置的插入与删除操作。所以我们可以根据任意位置的插入与删除函数对前面的尾插、尾删、头插、头删函数进行改写!

尾插

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//改写
	ListInsert(pHead,x);

}

尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);

	if (pHead ==  pHead->next)
	{
		printf("链表为空,无法删除!\n");
		return;
	}
	ListErase(pHead->prev);
}

头插

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead->next, x);

}

头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	if (pHead == pHead->next)
	{
		printf("没有结点,无法删除!\n");
		return;
	}
	ListErase(pHead->next);

}

完整代码

详情请点击 我的Git

总结

对于带头结点的双向循环链表来说,它的特点比较明显:
1.头结点将链表的首尾结点紧密的联系起来,增加了寻找结点的效率

2.链表内部前后结点也更为灵活,可以随意访问,在执行插入、删除等操作时,效率很高,只需要改变对应指针的指向就能实现。

3.支持任意位置时间复杂度为O(1)的插入和删除,不需要扩容、不存在空间浪费。

各位看官们三连支持一波啊·~~~


点击全文阅读


本文链接:http://zhangshiyu.com/post/37582.html

结点  链表  双向  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1