首页 > 其他分享 >数据结构--双向循环链表

数据结构--双向循环链表

时间：2024-12-26 22:28:11浏览次数：6  
标签：prev Listnode cur -- pos next 链表 phead 数据结构

之前我们写过了单链表的博文了，我们发现这是不是找头找尾有点麻烦啊。这里让我们来引入是双向带头的循环的链表。

双向循环链表

至此，正文开始：

首先让我们来区分什么几种类型：

类型

单向链表，双向链表，带头/不带头，循环/不循环

1.单向链表

2.双向链表：

 3.带头/不带头

4.循环/非循环：

带头循环/不带头不循环

区别：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

好了，有了上面图的认识，下面我们主要讲的是带头循环的双向链表。

创建结构体：

因为我们要的是双向循环链表，由上面的图片知道，我们需要知道头节点的前一个，尾节点的下一个这样的一些指针，所以我们才创建了一个结构体的prev指针和next指针，

剩下的在之前的文章已经讲过原因了，这里就不再多讲。

typedef int SLDatatype;
typedef struct Listnode
{
	struct Listnode* next;
	struct Listnode* prev;
	SLDatatype data;
}Listnode;

创建新节点

由于后面向插入的代码中都要用到2，所以我们在这里先创建一个函数，来使后面不那么杂糅

Listnode* BuyListnode(SLDatatype x)
{
	//扩容
	Listnode* node=( Listnode*) malloc(sizeof( Listnode));
	//判断
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

这里为什么是这个呢？
你看创建新节点，而它也是要双向的，
因为它只有一个，它的下一个和前一个是不是就是它本身，即空
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

 解释：上面当中的exit（-1）

在C语言中， exit(-1)  是用于终止程序执行并返回一个状态码给操作系统的语句。

 exit  函数定义在  stdlib.h  头文件中，它接受一个整数参数作为程序的退出状态码。通常约定， 0  表示程序正常结束，而非零值（这里是  -1 ）一般表示程序出现了错误或异常情况而终止。例如：

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

int main() {
    printf("程序准备异常终止\n");
    exit(-1);
    // 这行代码不会执行，因为exit会直接结束程序
    printf("这行不会输出");
    return 0;
}

上述代码运行时会输出 程序准备异常终止  后就终止了，后面的 printf  语句不会被执行，同时返回 -1  这个状态码给操作系统告知其是异常结束。

其他的就跟顺序表，单链表中的大差不差。

初始化

初始化，即给链表创建一个头节点。

Listnode* ListInit()
{
	Listnode* phead = BuyListnode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

 

 解答：

上面的BuyListnode（-1）为啥是赋值-1呢？

答：因为我们的头节点不存储有效数据。

 打印部分

void ListPrint(Listnode* phead)
{
	assert(phead);
因为是带头的，而打印时不需要打印头的，所以是next
	Listnode* cur = phead->next;
	printf("<=head=>");
	while (cur !=phead)
	{
		printf("%d=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

释放部分 

//释放
void  ListDestory(Listnode* phead)
{
	assert(phead);
	Listnode* cur = phead;
	while (cur)
	{
		Listnode* temp = cur->next;
		free(cur);
		cur = temp;
	}

}

判断是否空


bool Empty(Listnode* phead)
{
	assert(phead);
	if (phead->next==phead)
	{
		return true;
	}
	else
	{
		return false;
	}
}

尾插部分：

//尾插
void ListPushBack(Listnode* phead,SLDatatype x)
{
	assert(phead);
	Listnode* newnode = BuyListnode(x);
	Listnode* tail = phead->prev;
	
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

分析：

 这里就非常能体现这个的优势了

比如下面：

已经知道了phead了不是吗。

然后，因为它是循环的，

phead的前一个（prev）就是tail了，这样就直接能找到尾了。这是不是就非常简便了是不是！

接着，我们就跟着下图插入就非常简便了。

tail的next指向新节点

新节点前一个是指向tail

新节点的next指向头节点。

头节点的前一个是指向新节点。

就完成了！！！！

 头插部分：

//头插
void ListPushFront(Listnode* phead, SLDatatype x)
{
	assert(phead);
	Listnode* newnode = BuyListnode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

}

解答：

因为我们弄了带头的哨兵。

所以直接在phead的下一个插入即是尾插了。

其他的跟尾插的思路差不多。

 尾删部分

//尾删
void ListPopBack(Listnode* phead)
{
	assert(phead);
	Listnode* tail = phead->prev;
	Listnode* tailprev = tail->prev;
	
	phead->prev = tailprev;
	tailprev->next = phead;
	free(tail);
	tail = NULL;
}

分析：

先找到尾，这在上面已经说过方法了。

再定义一个prev，即tail的前一个

然后将原本头指向尾改成指向prev

原本尾tail指向头phead的改成prev指向头

最后，再释放d3，就完成了。

 中间随意位置插入

void ListInsert(Listnode* pos, SLDatatype x)
{
	assert(pos);
	Listnode* prev = pos->prev;
	Listnode* newnode = BuyListnode(x);
	
    
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

分析：

先定义一个pos位置

找到pos位置后，再定义pos前一个指针，即pos->prerv

再插入就行了（按照上面的插入过程一样）

下面的图虽然有点吧准确（数太少了），但是基本原理是一样的

 中间随意位置删除

void ListErase(Listnode* pos)
{
	assert(pos);
	Listnode* prev = pos->prev;
	Listnode* Next = pos->next;
	prev->next = Next;
	Next->prev = prev;
	free(pos);
	//等用的人弄空
	//pos = NULL;
}

分析：

也是先找到pos位置，

定义pos的前一个数指针。和pos的后一个数指针

再将，pos的前一个数指针，指向，pos的后一个数指针  

最后，把pos指针释放掉。

查找部分 

Listnode* Find(Listnode* phead, SLDatatype x)
{
	assert(phead);
	Listnode* cur = phead->next;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

跟单链表差不多，也挺容易理解的。这里就不过多去讲了。

总代码

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"


Listnode* BuyListnode(SLDatatype x)
{
	//扩容
	Listnode* node=( Listnode*) malloc(sizeof( Listnode));
	//判断
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}


Listnode* ListInit()
{
	Listnode* phead = BuyListnode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
void ListPrint(Listnode* phead)
{
	assert(phead);
	Listnode* cur = phead->next;
	printf("<=head=>");
	while (cur !=phead)
	{
		printf("%d=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//释放
void  ListDestory(Listnode* phead)
{
	assert(phead);
	Listnode* cur = phead;
	while (cur)
	{
		Listnode* temp = cur->next;
		free(cur);
		cur = temp;
	}

}

//判断空
bool Empty(Listnode* phead)
{
	assert(phead);
	if (phead->next==phead)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//尾插
void ListPushBack(Listnode* phead,SLDatatype x)
{
	assert(phead);
	Listnode* newnode = BuyListnode(x);
	Listnode* tail = phead->prev;
	
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//头插
void ListPushFront(Listnode* phead, SLDatatype x)
{
	assert(phead);
	Listnode* newnode = BuyListnode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

}
//尾删
void ListPopBack(Listnode* phead)
{
	assert(phead);
	Listnode* tail = phead->prev;
	Listnode* tailprev = tail->prev;
	
	phead->prev = tailprev;
	tailprev->next = phead;
	free(tail);
	tail = NULL;
}
void ListInsert(Listnode* pos, SLDatatype x)
{
	assert(pos);
	Listnode* prev = pos->prev;
	Listnode* newnode = BuyListnode(x);
	
    
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}


void ListErase(Listnode* pos)
{
	assert(pos);
	Listnode* prev = pos->prev;
	Listnode* Next = pos->next;
	prev->next = Next;
	Next->prev = prev;
	free(pos);
	//等用的人弄空
	//pos = NULL;
}

Listnode* Find(Listnode* phead, SLDatatype x)
{
	assert(phead);
	Listnode* cur = phead->next;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

头文件LIst.h 

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;
typedef struct Listnode
{
	struct Listnode* next;
	struct Listnode* prev;
	SLDatatype data;
}Listnode;


//创建新节点
Listnode* BuyListnode(SLDatatype x);
//销毁
void  ListDestory(Listnode* phead);
//初始化
Listnode* ListInit();
//打印
void ListPrint(Listnode* phead);
//判断空
bool Empty(Listnode* phead);


//尾插
void ListPushBack(Listnode* phead,SLDatatype x);
//头插
void  ListPushFront(Listnode* phead, SLDatatype x);
//尾删
void ListPopBack(Listnode* phead);
//插中间随意位置
void ListInsert(Listnode* pos, SLDatatype x);
//删中间随意位置
void ListErase(Listnode* pos);
//寻找
Listnode* Find(Listnode* phead, SLDatatype x);

 测试代码test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include  "list.h"

Test1()
{
	Listnode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	/*ListPushFront(plist, 5);
	ListPushFront(plist, 6);*/
	//ListPopBack(plist);
	Listnode*pos= Find(plist, 3);
	// ListInsert(pos,3);
	ListErase(pos);
	ListPrint(plist);
}
int main()
{
	Test1();

	return 0;
}

最后，鸡汤部分：

 你准备独自远行，忍受孤独和孤独，忍受身心的压迫，让汗水化为泪水，但你的脚步从未停止。干得好，即使不能获得桂冠，只要坚持下去，一定会得到最后的掌声。

加油，赶路人！

标签：prev,Listnode,cur,--,pos,next,链表,phead,数据结构
From： https://blog.csdn.net/go_bai/article/details/144649187

相关文章

  • 集智书童 | MITA-YOLO: 一种改进的间接视觉 YOLOv8方法用于目标检测，很酷！
    本文来源公众号“集智书童”，仅用于学术分享，侵权删，干货满满。原文链接：MITA-YOLO:一种改进的间接视觉YOLOv8方法用于目标检测！火势可能导致文化遗产建筑遭受严重破坏，因此及时的火警检测至关重要。传统的密集布线和钻孔可能对这些结构造成损害，因此减少摄像头的数量以最小化这......
  • 极市平台 | 超越YOLO11和D-FINE！DEIM：最强实时目标检测算法
    本文来源公众号“极市平台”，仅用于学术分享，侵权删，干货满满。原文链接：超越YOLO11和D-FINE！DEIM：最强实时目标检测算法极市导读本文介绍了一种改进的DETR目标检测框架DEIM，通过增加正样本数量和优化匹配质量的损失函数，显著加快了DETR模型的收敛速度，并在多个数据集上提升了性能，成......
  • 江大白 | 基于AI，低空经济的无人机检测识别研究综述（建议收藏！）
    本文来源公众号“江大白”，仅用于学术分享，侵权删，干货满满。原文链接：基于AI，低空经济的无人机检测识别研究综述导读近年来，无人机产业和应用发展迅速，深度学习在无人机检测与识别中的应用也取得了显著进展。本文对基于深度学习的无人机检测与识别技术进行了详细综述，包括视觉、音......
  • （二）Event Recoder在嵌入式开发领域应用
    目录一、EventRecoder在嵌入式开领域的发展二、简介三、应用3.1调试与故障诊断3.1.1替代串口调试3.1.2系统运行状态监测3.1.3中间件及操作系统调试3.2性能分析与优化3.2.1代码执行时间测量3.2.2资源使用情况分析3.3系统验证与测试3.3.1功能验证3.3.2稳定性测试......
  • （一）认识Event Recoder
    目录一、不同领域EventRecoder的含义1.汽车领域2.嵌入式软件开发领域3.WebSphere4.航空领域二、结束语一、不同领域EventRecoder的含义1.汽车领域功能与作用        汽车EDR主要用于记录车辆在行驶过程中尤其是事故发生前后的关键数据，如碰撞前几秒内......
  • （三）在Keil工程中创建Event Recoder
    添加EventRecoder的步骤1.创建Keil工程2.打开“ManageRun-TimeEnvironment” 3.在“ManageRun-TimeEnvironment”中添加EventRecoder4.实现printf重定向        由于使能了printf重定向，工程里面一定不要再做重定向了，比如fpuc，fgetc。另外当前选择了......
  • 用Detr训练自定义数据
    前面记录了Detr及其改进DeformableDetr。这一篇记录一下用Detr训练自己的数据集。先看下Detr附录中给出的大体源码，整体非常清晰。接下来记录大体实现过程一、数据准备借助labelme对数据进行标注然后将标注数据转换成COCO格式，得到以下几个文件其中JPEGImages存放所有图片，V......
  • 【岗位招聘】基础设施管理
    参考：某银行职位描述：1.负责网络、主机、虚拟化平台、云平台、操作系统、中间件、数据库系统整体规划、架构设计和建设实施;2.制定和落实网络、主机、虚拟化平台、云平台、操作系统、中间件、数据库系统相关管理制度规范;3.负责网络、主机、虚拟化平台、云平台、操作系统、中......
  • P1552 [APIO2012] 派遣
    P1552[APIO2012]派遣题目背景在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。题目描述在这个帮派里，有一名忍者被称之为Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级......
  • 数据结构（哈希表（下）方法讲解）
    前言：在前一部分中，我们探讨了哈希表的基本原理、设计思想、优势与挑战，并了解了它在实际项目中的应用场景。哈希表作为一种高效的数据结构，在查找、插入和删除等操作上具有显著优势，但要真正掌握它的使用，深入理解其操作方法是至关重要的。本部分将专注于哈希表的方法讲解。哈希......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99