数据结构入门指南：带头双向循环链表

目录

文章目录

前言

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 销毁链表

 3. 源码

总结

前言

        链表一共有8种结构，但最常用的就是无头单向链表、和带头双向循环链表。单链表的结构存在着很多的缺陷，但它是许多数据结构的子结构，在刷题中经常见到，而带头双向循环链表弥补了单链表所有的缺陷，可以说是一个完美结构，虽然相对于单链表来说结构更复杂，但它的特性使它的实现逻辑较为简单，今天我就向大家一一介绍。

1.结构与优势

结构：

优势：

  1. 可以实现快速的插入和删除操作：由于链表的特性，插入和删除节点的时间复杂度为O(1)，不需要像数组一样需要移动其他元素。
  2. 可以实现快速的遍历操作：双向链表可以通过前向或后向的指针进行遍历，而不需要像单向链表那样只能从头节点开始遍历。
  3. 可以实现双向遍历：双向链表可以通过前向和后向的指针进行双向遍历，可以方便地从任意一个节点开始向前或向后遍历。
  4. 可以实现循环遍历：由于链表的循环性质，可以通过不断移动指针进行循环遍历，不需要额外的循环条件判断。
  5. 可以实现更多高级功能：带头双向循环链表可以实现更多高级功能，如反转链表、查找倒数第k个节点等。

总结，带头双向循环链表具有灵活性和高效性，适用于需要频繁插入、删除和遍历操作的场景。

2.链表实现      

 2.1 定义链表

        步入正题，带头双向循环链表，首先它是双向的，什么是双向呢？在单链表定义时会有指向下一个节点的指针，而双向链表有两个指针，一个指向下一个节点，一个指向上一个节点，可以实现前后双向遍历。

typedef struct ListNode
{
	int data;
	struct ListNode* next;//指向下一个节点的指针
	struct ListNode* prev;//指向上一个节点的指针
}LN;

 2.2 创建头节点

         和无头单向链表不同，带头双向循环链表它有头节点，所以在开始执行各操作之前，我们先创建一个头节点并初始化。

        创建头节点需要新建一个节点，在其他插入接口中也需要新建节点，那我们就封装一个创建新节点的函数，最后返回新建节点的地址。

LN* BuyListNode(Datatype x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

         和无头单链表不同，这里带有头节点，就需要对头节点进行初始化一下，虽然在创建节点时就已经对节点进行了初始化，但头节点的初始化与新建节点初始化需求不同，所有这里需要单独进行初始化初始化节点时可以使用双指针，也可以直接返回头节点地址。

LN* InItNode()
{
	LN* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

         头节点进行初始化时，只需将两个指针指向自己，然后返回头节点的地址即可。

 2.3 尾插

        建好头节点后要怎么链接节点呢？我们先写一个尾插来体验一下它的便捷。在单链表中想要进行尾插，还需要遍历一遍链表找到尾节点，而带头双向循环链表就不需要，可以通过头节点直接找到尾节点：tail  =  phead -> prev ;头节点的前一个节点就是尾节点。

我们新建一个节点：

         要想插入就需要把尾节点的next改为新节点的地址，新节点的prev改为尾节点tail的地址

        再把新节点的next改为头节点的地址，把头节点的prev改位新节点的地址。

 

 整体逻辑就是这样，具体代码如下：

void PushBack(LN* phead, Datatype x)
{
	assert(phead);
	LN* tail = phead->prev;
	LN* newnode = BuyListNode(x);

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

2.4 输出链表

        为了便于后续的测试，我们先写一个函数用于输出链表数据。输出函数很简单。

void PrintList(LN* phead)
{
	assert(phead);
	LN* cur = phead->next;//有效节点不包含头节点
	printf("phead <->");
	while (cur != phead)
	{
		printf(" %d <->", cur->data);
		cur = cur->next;
	}
}

         这里需要注意的是遍历链表时的循环条件，由于它是循环链表，所有结束条件有所变化。其次是输出数据时不需要输出头节点的数据，头节点的下一个节点才是有效数据。

我们可以来测试一下：

void test1()
{
	LN* plist = InItNode();
	PushBack(plist, 1);
	PushBack(plist, 2);
	PushBack(plist, 3);
	PushBack(plist, 4);
	PushBack(plist, 5);
	PrintList(plist);
}

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

 输出效果如下：

 2.5 尾删

        基本逻辑理解后，可以先自主尝试写一下尾删。思路也是非常的简单，但要注意的是，有效节点为0的情况。把尾节点的前一个节点next改为头节点地址，头节点的prev改为尾节点的前一个节点，最后释放掉尾节点的空间。

void PopBack(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LN* tail = phead->prev;
	LN* tailprev = tail->prev;

	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
}

2.6 头插

        接下来我们进行头插操作，我们使用的是带头的形式，所有这里进行头插时，不像单链表那样需要使用二级指针，我们需要改的是头节点中的内容，所有使用一级指针就可以解决。

         此外头插时一定要注意操作的次序，避免后续操作有误。例如：

        如果不提前保存第一个节点的地址， 就会导致新节点链接后续节点时找节点麻烦或出现错误。

 正确的顺序如下图：

 代码实现：

void PushFront(LN* phead,Datatype x)
{
	assert(phead);
	LN* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

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

}

         当然新手不建议这样写，这样写很容易把人搞晕，我们可以先保存第一个节点的地址，这样就不会搞错。代码如下：

void PushFront(LN* phead,Datatype x)
{
	assert(phead);
	LN* newnode = BuyListNode(x);
	LN* first = phead->next;

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

	newnode->next = first;
	first->prev = newnode;

}

2.7头删

        这里头删也是非常简单，为了避免出错，我们可以额外创建两个指针，记录第一个节点和第二个节点，逻辑较为简单，就不再画逻辑图，代码如下：

void PopFront(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LN* first = phead->next;
	LN* second = first->next;

	free(first);

	phead->next = second;
	second->prev = phead;

}

需要额外注意链表为空的情况。

2.8 节点个数

        统计节点个数很简单，和输出链表数据一样遍历一下链表统计链表个数代码如下：

int Listsize(LN* phead)
{
	assert(phead);
	int sz = 0;
	LN* cur = phead->next;
	while (cur != phead)
	{
		sz++;
		cur = cur->next;
	}
	return sz;
}

         有人可能会想：用头节点统计不也可以吗？还不用额外的去写一个函数。初始时把头节点的data初始化为0，每次插入data++。这种方式严格来说是不可以的，我们在写链表时每个节点不一定存储的是整形，也可能是字符型，虽然也能计数，但如果节点是1000呢？数据就溢出了，所以不建议那样写。

 2.9 查找

        查找也比较简单，不再多说，代码如下：

LN* ListFind(LN* phead, Datatype x)
{
	assert(phead);
	LN* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

 2.10 位置插入

         带头双向循环链表在位置插入时没有像单链表那样有位置前插入，位置后插入。这里的位置插入都是位置前插入，由于它是循环双向的链表，不像单链表那样不可以向前遍历，双向循环链表可以任意插入，所以位置后插入也并没有什么意义，就统一默认位置前插入。

        位置插入操作和上述的插入操作很类似，推荐额外创建一个指针保存节点信息，就可以避免操作时次序不当造成程序错误，代码如下：

void ListInsert(LN* pos, Datatype x)
{
	assert(pos);
	LN* newnode = BuyListNode(x);
	LN* posprev = pos->prev;

	posprev->next = newnode;
	newnode->prev = posprev;

	newnode->next = pos;
	pos->prev = newnode;

}

2.11 位置删除

        位置删除也一样很简单，我们多创建两个指针变量存储节点信息，就可以有效避免次序不当导致程序错误的问题。代码如下：

void PosErase(LN* pos)
{
	assert(pos);
	LN* posprev = pos->prev;
	LN* posnext = pos->next;

	free(pos);

	posprev->next = posnext;
	posnext->prev = posprev;
}

 2.12 销毁链表

        在链表使用完以后就要销毁，销毁也比较简单，代码如下：

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

         这样还需要注意的一点，在销毁链表的这个函数里虽然销毁了头节点，但是在头节点创建之初使用了结构体指针，在后续操作中都是通过这个指针将链表传递给函数，所以最后在调用销毁链表函数之后要将指向头节点的指针置为NULL，避免出现野指针。当然这里也可以使用二级指针在函数里将这个指针置为NULL。

 3. 源码

List.c

#include"List.h"
LN* BuyListNode(Datatype x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
LN* InItNode()
{
	LN* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
void PrintList(LN* phead)
{
	assert(phead);
	LN* cur = phead->next;
	printf("phead <->");
	while (cur != phead)
	{
		printf(" %d <->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void PushBack(LN* phead, Datatype x)
{
	assert(phead);
	LN* tail = phead->prev;
	LN* newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void PopBack(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LN* tail = phead->prev;
	LN* tailprev = tail->prev;

	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
}
void PushFront(LN* phead,Datatype x)
{
	assert(phead);
	/*LN* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

	newnode->prev = phead;
	phead->next = newnode;*/
	LN* newnode = BuyListNode(x);
	LN* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;

}
void PopFront(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LN* first = phead->next;
	LN* second = first->next;

	free(first);

	phead->next = second;
	second->prev = phead;

}
int Listsize(LN* phead)
{
	assert(phead);
	int sz = 0;
	LN* cur = phead->next;
	while (cur != phead)
	{
		sz++;
		cur = cur->next;
	}
	return sz;
}
LN* ListFind(LN* phead, Datatype x)
{
	assert(phead);
	LN* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
void ListInsert(LN* pos, Datatype x)
{
	assert(pos);
	LN* newnode = BuyListNode(x);
	LN* posprev = pos->prev;

	newnode->next = pos;
	pos->prev = newnode;

	newnode->prev = posprev;
	posprev->next = newnode;
}
void PosErase(LN* pos)
{
	assert(pos);
	LN* posprev = pos->prev;
	LN* posnext = pos->next;

	free(pos);

	posprev->next = posnext;
	posnext->prev = posprev;
}
void DestoryList(LN* phead)
{
	assert(phead);
	LN* cur = phead->next;
	while (cur != phead)
	{
		LN* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

 List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int Datatype;
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}LN;

LN* BuyListNode(Datatype x);
LN* InItNode();
void PrintList(LN* phead);
void PushBack(LN* phead,Datatype x);
void PopBack(LN* phead);
void PushFront(LN* phead, Datatype x);
void PopFront(LN* phead);
LN* ListFind(LN* phead, Datatype x);
int Listsize(LN* phead);
void ListInsert(LN* pos, Datatype x);
void PosErase(LN* pos);
void DestoryList(LN* phead);

 test.c

#include"List.h"
void test1()
{
	LN* plist = InItNode();
	PushBack(plist, 1);
	PushBack(plist, 2);
	PushBack(plist, 3);
	PushBack(plist, 4);
	PushBack(plist, 5);
	PushFront(plist, 0);
	PopBack(plist);
	ListInsert(plist, 10);
	LN* pos = ListFind(plist, 10);

	ListInsert(pos, 11);

	PosErase(pos);
	PrintList(plist);
	DestoryList(plist);
	plist = NULL;
}
void test2()
{
	LN* plist = InItNode();
	PushBack(plist, 1);
	PushBack(plist, 2);
	PushBack(plist, 3);
	PushBack(plist, 4);
	PushBack(plist, 5);
	//PushFront(plist, 0);

	PopFront(plist);
	PrintList(plist);
}

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

 

总结

        带头双向循环链表作为一种数据结构，在解决问题时展现了其独特的优势。通过快速的插入和删除操作，以及灵活的双向遍历和循环遍历能力，它为我们提供了一种高效、灵活的数据组织方式。在实际应用中，我们可以充分发挥带头双向循环链表的特性，优化算法设计，提高程序的效率和可维护性。通过深入学习和掌握带头双向循环链表，我们可以更好地解决实际问题，提升自己的编程能力。希望本文能够帮助读者对带头双向循环链表有更深入的理解，并在实践中得到应用。最后，感谢阅读！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/58921.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

NsPack3.x脱壳手记

NsPack3.x脱壳手记

发现是NsPack3.x的壳 使用ESP守恒快速脱壳 F9遇到popfd后下面的jmp就是通往OEP了 打开LordPE准备转储映像, 首先调整下ImageSize, 接着dump full 接着不要退出目前的调试, 打开Scylla修复IAT, 把OEP的VA地址输入到OEP处, 接着按照如下图所示步骤 完成后如下, 但NsPack3.x…
阅读更多...
探索创意之路：稳定扩散AI绘画指南

探索创意之路：稳定扩散AI绘画指南

文章目录 引言第一部分&#xff1a;了解稳定扩散AI绘画1.1 稳定扩散AI绘画简介1.2 稳定扩散AI绘画的优势 第二部分&#xff1a;使用稳定扩散AI绘画2.1 获取稳定扩散AI绘画工具2.2 准备绘画素材和设置参数2.3 进行AI绘画 第三部分&#xff1a;发挥创意&#xff0c;创作精彩绘画3…
阅读更多...
结构体和 Json 相互转换（序列化反序列化）

结构体和 Json 相互转换（序列化反序列化）

关于 JSON 数据 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也 易于机器解析和生成。RESTfull Api 接口中返回的数据都是 json 数据。 Json 的基本格式如下&#xff1a; { "a": "Hello", "b": "…
阅读更多...
【Linux】五种IO模型

【Linux】五种IO模型

文章目录 1. IO基本概念2. 五种IO模型2.1 五个钓鱼的例子2.2 五种IO模型2.2.1 阻塞IO2.2.2 非阻塞IO2.2.3 信号驱动IO2.2.4 IO多路转接2.2.5 异步IO 1. IO基本概念 认识IO IO就是输入和输出&#xff0c;在冯诺依曼体系结构中&#xff0c;将数据从输入设备拷贝到内存就叫输入&am…
阅读更多...
STM32使用HAL库中外设初始化MSP回调机制及中断回调机制详解

STM32使用HAL库中外设初始化MSP回调机制及中断回调机制详解

STM32使用HAL库之Msp回调函数 1.问题提出 在STM32的HAL库使用中&#xff0c;会发现库函数大都被设计成了一对&#xff1a; HAL_PPP/PPPP_Init HAL_PPP/PPPP_MspInit 而且HAL_PPP/PPPP_MspInit函数的defination前面还会有__weak关键字 上面的PPP/PPPP代表常见外设的名称为…
阅读更多...
什么是OCR？OCR技术详解

什么是OCR？OCR技术详解

光学字符识别(Optical Character Recognition)简称为“OCR”。ORC是指对包含文本资料的图像文件进行分析识别处理&#xff0c;获取文字及版面信息的技术。 一般包括以下几个过程&#xff1a; 1.图像输入 针对不同格式的图像&#xff0c;有着不同的存储格式和压缩方式。目前&…
阅读更多...
JMeter 的使用

JMeter 的使用

文章目录 1. JMeter下载2. JMeter的使用2.1 JMeter中文设置2.2 JMeter的使用2.2.1 创建线程组2.2.2 HTTP请求2.2.3 监听器 1. JMeter下载 官网地址 https://jmeter.apache.org/download_jmeter.cgi https://dlcdn.apache.org//jmeter/binaries/apache-jmeter-5.6.2.zip 下载解…
阅读更多...
[JAVAee]锁策略

[JAVAee]锁策略

目录 乐观锁与悲观锁 乐观锁 乐观锁的冲突检测 悲观锁 读锁与写锁 重量级锁与轻量级锁 重量级锁 轻量级锁 自旋锁 公平锁与非公平锁 可重入锁与不可重入锁 乐观锁与悲观锁 乐观锁 在乐观锁中,假设数据并不会发生冲突,在正式提交数据时会对数据进行冲突检测,如果发…
阅读更多...
ARM 常见汇编指令学习 9 - 缓存管理指令 DC 与 IC

ARM 常见汇编指令学习 9 - 缓存管理指令 DC 与 IC

文章目录 ARM64 DC 与 IC 指令 上篇文章&#xff1a;ARM 常见汇编指令学习 8 - dsb sy 指令及 dsb 参数介绍 ARM64 DC 与 IC 指令 AArch64指令集中有两条关于缓存维护&#xff08;cache maintenance&#xff09;的指令&#xff0c;分别是IC和DC。 IC 是用于指令缓存操作&…
阅读更多...
项目经理必读：领导风格对项目成功的关键影响

项目经理必读：领导风格对项目成功的关键影响

引言 项目经理作为一个领导者的角色&#xff0c;他们需要协调各方资源&#xff0c;管理团队&#xff0c;推动项目的进行。为了完成这些任务&#xff0c;项目经理必须具备各种领导风格的灵活性&#xff0c;以应对项目中的各种变数和挑战。在这篇文章中&#xff0c;我们将讨论领…
阅读更多...
SpringBoot 项目创建与运行

SpringBoot 项目创建与运行

一、Spring Boot 1、什么是Spring Boot&#xff1f;为什么要学 Spring Boot Spring 的诞生是为了简化 Java 程序的开发的&#xff0c;而 Spring Boot 的诞生是为了简化 Spring 程序开发的。 Spring Boot 翻译一下就是 Spring 脚手架 盖房子的这个架子就是脚手架&#xff0c;…
阅读更多...
LeetCode 25题：K个一组翻转链表

LeetCode 25题：K个一组翻转链表

题目&#xff1a; 给你链表的头节点 head &#xff0c;每 k 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 k 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍&#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单纯…
阅读更多...
web爬虫第五弹 - JS逆向入门（猿人学第一题）

web爬虫第五弹 - JS逆向入门（猿人学第一题）

0- 前言 爬虫是一门需要实战的学问。 而对于初学者来说&#xff0c;要想学好反爬&#xff0c;js逆向则是敲门砖。今天给大家带来一个js逆向入门实例&#xff0c;接下来我们一步一步来感受下入门的逆向是什么样的。该案例选自猿人学练习题。猿人学第一题 1- 拿到需求 进入页面…
阅读更多...
在登录界面中设置登录框、多选项和按钮(HTML和CSS)

在登录界面中设置登录框、多选项和按钮(HTML和CSS)

登录框&#xff08;Input框&#xff09;的样式&#xff1a; /* 设置输入框的宽度和高度 */ input[type"text"], input[type"password"] {width: 200px;height: 30px; }/* 设置输入框的边框样式、颜色和圆角 */ input[type"text"], input[type&q…
阅读更多...
flutter：占位视图（骨架屏、shimmer）

flutter：占位视图（骨架屏、shimmer）

前言 有时候打开美团&#xff0c;在刚加载数据时会显示一个占位视图&#xff0c;如下&#xff1a; 那么这个是如何实现的呢&#xff1f;我们可以使用shimmer来开发该功能 实现 官方文档 https://pub-web.flutter-io.cn/packages/shimmer 安装 flutter pub add shimmer示例…
阅读更多...
Pytest+Allure+Excel接口自动化测试框架实战

Pytest+Allure+Excel接口自动化测试框架实战

1. Allure 简介 简介 Allure 框架是一个灵活的、轻量级的、支持多语言的测试报告工具&#xff0c;它不仅以 Web 的方式展示了简介的测试结果&#xff0c;而且允许参与开发过程的每个人可以从日常执行的测试中&#xff0c;最大限度地提取有用信息。 Allure 是由 Java 语言开发…
阅读更多...
【laravel+vue2 】医院信息化手术麻醉临床信息管理系统源码

【laravel+vue2 】医院信息化手术麻醉临床信息管理系统源码

近年来&#xff0c;医院信息化成为医院领域的推广重点&#xff0c;HIS、LIS、PACS、EMR等信息系统的相继出现&#xff0c;显著提高了医院业务的运行效率。手术麻醉系统作为医院信息系统的一部分&#xff0c;由监护设备数据采集系统和麻醉信息管理系统两个子系统组成。 一、医院…
阅读更多...
复亚智能打造全新云平台：让无人机任务管理更智能、更简单

复亚智能打造全新云平台：让无人机任务管理更智能、更简单

复亚智能全新升级的MindView云平台&#xff0c;对航线规划、任务管理、自动飞行、数据管理等各个环节开展可视化、数字化、智能化监管&#xff0c;从任务到结果的“看得清”、“管得住”、“查得准”&#xff0c;带来更轻松的操作&#xff0c;改善作业效率、安全保障和用户体验…
阅读更多...
抖音seo矩阵系统源码搭建开发详解

抖音seo矩阵系统源码搭建开发详解

抖音SEO矩阵系统是一个用于提高抖音视频在搜索引擎排名的工具。如果你想开发自己的抖音SEO矩阵系统&#xff0c;以下是详细的步骤&#xff1a; 开发步骤详解&#xff1a; 确定你需要的功能和算法 抖音SEO矩阵系统包含很多功能&#xff0c;比如关键词研究、内容优化、链接建设、…
阅读更多...
SQL基础复习与进阶

SQL基础复习与进阶

SQL进阶 文章目录 SQL进阶关键字复习ALLANYEXISTS 内置函数ROUND&#xff08;四舍五入&#xff09;TRUNCATE&#xff08;截断函数&#xff09;SEILING&#xff08;向上取整&#xff09;FLOOR&#xff08;向下取整&#xff09;ABS&#xff08;获取绝对值&#xff09;RAND&#x…
阅读更多...
最新文章

Copyright @ 2022~2023