C语言进阶——数据结构之链表(续)

前言

hello,大家好呀,我是Humble,本篇博客承接之前的C语言进阶——数据结构之链表

的内容(没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~),上次我们重点说了链表中的单链表,即不带头单向不循环链表

还说到了链表的分类虽然有8种,但实际上最常用的还是单链表和双向链表(带头双向循环链表)

所以今天我们就来讲讲双向链表的实现吧~

双向链表的结构

下面是双向链表的一个图示:

双向链表,全称为带头双向循环链表

双向与循环这2个概念很好理解,所以我们下面看一下什么是带头

这个“带头”跟之前我们说的“头节点”是两个概念,

实际前面在说单链表时有称呼并不严谨,但是为了大家更好的理解就直接称为单链表的头节点

 带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨 的

哨兵位”存在的意义: 遍历循环链表避免死循环

对于双向链表的节点,我们这样定义:
 

typedef int LTDataType;
typedef struct ListNode 
{
    LTDataType data;
    struct ListNode* next; //指针保存下一个节点的地址
    struct ListNode* prev; //指针保存前一个节点的地址
    
}LTNode;

双向链表的实现

下面我们来实现一下双向链表的各个功能

其实当我们掌握了单链表的各个操作后,我们会发现其实双向链表虽然在结构上看着比单链表复杂不少,但在实现上并不难~

我们首先在VS上创建一个List的工程,再分别创建List.h头文件,List.c源文件以及Test.c测试文件,在这之上,我们依次去实现双向链表的各个功能~

初始化 LTInit

首先是初始化,因为双向链表多了一个头节点,即哨兵位,所以我们需要对其初始化~

代码如下:

LTNode* LTInit() //对哨兵位初始化~
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    if (phead == NULL) 
    {
	 perror("malloc fail!");
	 exit(1);
    }
   phead->data = -1;
   phead->next =phead->prev =phead;

	return phead;

}

下面来测试一下~
 

void ListTest() 
{

	LTNode* plist = LTInit();

}

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

	

这里我们通过调试来观察一下初始化是否成功:

另外,因为我们后面还要多次用到申请节点空间,所以我们单独封装一个函数LTBuyNode,

这样后面再使用只需要调用它就可以了

LTNode* LTBuyNode(LTDataType x) //申请新节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL) 
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

同时,关于上面初始化的代码我们也可以进行简化:

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);

	return phead;
}

尾插LTPushBack

好,有了这样一个链表,下面我们实现一下尾插LTPushBack

代码如下:
 

//尾插
void LTPushBack(LTNode* phead, LTDataType x) 
{
	assert(phead);	//phead不能为空
	LTNode* newnode = LTBuyNode(x);

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

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

同样,我们在Test.c文件中进行测试

void ListTest() 
{
	LTNode* plist = LTInit();

	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
}





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

	

调试后,,结果如下:

这样尾插的功能就实现了~

不过,我们后续如果一直用调试的方式去观察未免有些麻烦,所以这里我们也封装一个打印的函数

//打印
void LTPrint(LTNode* phead)
{
	//phead不能为空
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	
}

有了打印函数,我们再测试尾插,只要运行代码就可以了

结果如下:

头插LTPushFront

接下来,我们来实现一下头插LTPushFront

关于头插,有一个需要注意的点,头插要插在第一个、有效节点之前,而不是在哨兵位之前

头插代码如下:
 

//头插
void LTPushFront(LTNode* phead, LTDataType x) 
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

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

老规矩,写完后,我们来测试一下:

void ListTest() 
{
	LTNode* plist = LTInit();

	//头插
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

}

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

尾删 LTPopBack

写删除操作时要注意:当链表为空时(只有一个哨兵位节点),要assert断言

代码如下:

void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表为空:只有一个哨兵位节点
	assert(phead->next != phead);

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

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

	free(del);
	del = NULL;


}

下面是测试代码以及结果:

void ListTest() 
{
	LTNode* plist = LTInit();

	
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	


     //尾删
    LTPopBack(plist);
    LTPrint(plist);
    printf("\n");

    LTPopBack(plist);
    LTPrint(plist);
    printf("\n");

    LTPopBack(plist);
    LTPrint(plist);

}



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

头删LTPopFront

接下来我们来实现头部删除LTPopFront

直接上代码:

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* del = phead->next;
	LTNode* next = del->next;

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

	free(del);
	del = NULL;
}

下面来测试:
 

void ListTest() 
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	

	//头删
	LTPopFront(plist);
	LTPrint(plist);
	printf("\n");

	LTPopFront(plist);
	LTPrint(plist);
	printf("\n");

	LTPopFront(plist);
	LTPrint(plist);
	printf("\n");
}

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

运行结果如下:

查找LTFind

在前面我们已经实现了插入的4种操作,下面我们看一下查找

代码如下:

LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x) 
			return pcur;
		
		pcur = pcur->next;
	}
	return NULL;

}

来测试一下吧~

void ListTest() 
{
	LTNode* plist = LTInit();
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);

	LTNode* findRet = LTFind(plist, 3);

	if (findRet == NULL) 
	    printf("未找到!\n");
	
	else 
		printf("找到了!\n");
}



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

在指定位置之后插入数据LTInsert

插入代码如下:

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) 
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);

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

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

测试代码如下:
 

void ListTest()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4); //4->3->2->1->

	LTNode* findRet = LTFind(plist, 3);

	LTInsert(findRet,66); //预期结果为 //4->3->66->2->1->
	LTPrint(plist);

}



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

运行结果:

删除pos位置的数据LTErase

删除代码如下:

//删除pos位置的数据
void LTErase(LTNode * pos) 
{
	assert(pos);

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

}

下面我们来进行测试~

void ListTest()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4); //4->3->2->1->

	LTNode* findRet = LTFind(plist, 3);

	LTErase(findRet);
	LTPrint(plist); //预期结果为:4->2->1->
}


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

链表的销毁LTDestroy

最后我们看一下双向链表的销毁LTDestroy

注意:我们这里的函数要传的是地址,也就是要用到二级指针,因为这里我们直接要对链表的哨兵位做修改,要与前面的代码相区分哦~

销毁的代码如下:

void LTDesTroy(LTNode** pphead) 
{
	assert(pphead);
	//哨兵位不能为空
	assert(*pphead);

	LTNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//链表中只有一个哨兵位
	free(*pphead);
	*pphead = NULL;
}

至于销毁操作的调试,大家可以自行测试,这里就不再赘述了

到此,我们就把双向链表的操作给讲完了

事实上学会了单链表和双向链表的操作,即使将来遇到链表的其他6种类型也可以游刃有余,很快上手并解决问题的,所以建议大家还是要好好掌握单链表和双向链表的操作~

结语

好了,今天关于链表的分享就到这里了,如果对大家有帮助就太好啦~

在学习编程的道路上Humble与各位同行,加油吧各位!

最后,希望大家点个免费的赞或者关注吧(感谢感谢),也欢迎大家订阅我的专栏

让我们在接下来的时间里一起成长,一起进步吧!

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

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

相关文章

2023年智能可穿戴行业市场分析(电商数据查询分析):智能手表销额增长21%,手环明显下滑

近年来,随着技术的进步,智能可穿戴设备在社交网络、医疗保健、导航等诸多领域有着非常广泛的应用,这为大众生活带来了诸多便利。 当前的可穿戴产品形态纷繁多样,主要包括智能手表、智能眼镜、智能手环、健康穿戴和体感控制等等&am…

Java框架篇面试题

📕作者简介: 过去日记,致力于Java、GoLang,Rust等多种编程语言,热爱技术,喜欢游戏的博主。 📗本文收录于java面试题系列,大家有兴趣的可以看一看 📘相关专栏Rust初阶教程、go语言基…

【江科大】STM32:I2C通信外设(硬件)

在将2C通信外设之前,我们先捋一捋,串口的相关特点来和2C进行一个对北比。 首先: 1,大部分单片机,设计的PCB板均带有串口通信的引脚(也就是通信基本都借助硬件收发器来实现) 2.对于串口的异步时序&#xff0…

什么样的宣传才能对消费者起效?

品牌离不开宣传,宣传又直接面向消费者,然后面对铺天盖地的宣传,除了从业人员,相信大部分用户都会有抵触心理,今天媒介盒子就来和大家聊聊,什么样的宣传能够提高消费者的接受度,让宣传不白宣传。…

elementui 表单 resetFields 方法不生效问题解决

问题 调用 elementui 官方提供的表单重置方法 resetFields 方法重置表单不生效,相信很多小伙伴都遇到过这个问题。 解决方法 检查代码看每个表单项的 prop 与 v-model 绑定的属性值命名是否相同,不相同的话就会导致 resetFields 方法不生效的问题&am…

AI技术的崛起:软件工程师的新篇章

随着人工智能(AI)技术的迅猛发展与普及,各行各业都受到了前所未有的冲击与变革。 对于软件工程师而言,AI技术的崛起既带来了挑战,也带来了前所未有的机遇。本文将探讨AI技术对软件工程师的影响,以及如何应…

vue2面试题:什么是双向数据绑定

vue2面试题:什么是双向数据绑定 回答思路:1.什么是双向绑定-->2.双向数据绑定的原理-->3.如何实现双向数据绑定1.什么是双向绑定2.双向数据绑定的原理3.如何实现双向数据绑定来一个构造函数:执行初始化,对data执行响应化处理…

Linux: make/Makefile 相关的知识

背景: 会不会写makefile,从一个侧面说明了一个人是否具备完成大型工程的能力一个工程中的源文件不计数,其按类型、功能、模块分别放在若干个目录中,makefile定义了一系列的 规则来指定,哪些文件需要先编译&#xff0c…

ubuntu22.04安装filebeat报错解决

1、查看报错 journalctl -u filebeat 或者 filebeat -c /etc/filebeat/filebeat.yml找到报错信息 runtime/cgo: pthread_create failed: Operation not permitted 2、解决报错 在filebeat.yml配置文件添加如下配置,重启filebeat seccomp:default_action: allow…

ansible 常用模块

目录 1.ping模块 2.command模块 3. shell模块 4.copy模块 5.file模块 6.fetch模块 7.cron模块 8.yum模块 9.service模块 10.user模块 11.group模块 12.script 模块 13.setup模块 14. get_url模块 15.stat模块 16.unarchive模块 1.ping模块 使用ansible db1 -m pin…

【数学建模】综合评价方法

文章目录 综合评价的基本理论和数据预处理综合评价的基本概念综合评价体系的构建综合指标的预处理方法评价指标预处理示例 常用的综合评价数学模型线性加权综合评价模型TOPSIS法灰色关联度分析熵值法秩和比(RSR)法综合评价示例 综合评价的基本理论和数据…

NODE笔记 2 使用node操作飞书多维表格

前面简单介绍了node与简单的应用,本文通过结合飞书官方文档 使用node对飞书多维表格进行简单的操作(获取token 查询多维表格recordid,删除多行数据,新增数据) 文章目录 前言 前两篇文章对node做了简单的介绍&#xff…

Android-System fastboot 介绍和使用

一、fastboot简介 在android手机中,fastboot是一种比recovery更底层的刷机模式。 实际操作中:fastboot是一种线刷,就是使用USB连接手机的一种刷机模式。相对于某些系统来说,线刷比卡刷更可靠,安全。recovery是一种卡刷…

node 第二十三天 mongoDB shell 命令 CRUD 增删改查 基础

什么是 mongoDB shell 命令 mongoDB shell 命令就是在cmd窗口或者powershell窗口与mongoDB交互的命令, 以下简称mongosh 对应我们上一天安装的 mongosh 工具 有什么用 mongosh 对一般的开发者可能意义不大, 因为在开发过程中我们会基于某一款语言来使用mongoDB, 比如在node端我…

【Java程序员面试专栏 专业技能篇】计算机网络核心面试指引

关于计算机网络部分的核心知识进行一网打尽,包括计算机的网络模型,各个层的一些重点概念,通过一篇文章串联面试重点,并且帮助加强日常基础知识的理解,全局思维导图如下所示 分层基本概念 计算机网络模型的分层及具体作用 计算机网络有哪些分层模型 可以按照应用层到物…

单调栈经典例题

import java.util.Scanner;public class Main{public static void main(String[] args) {//单调递增栈,栈中的所有元素严格单调递增//比如1 6 5 4 9 8 7 10 11 56不会出现在答案里//因为被4给拦截住了//遍历到4的时候可以把56都出栈//89也不会出现,被7拦住了//遍历到…

【漏洞复现】SpringBlade export-user接口SQL注入漏洞

文章目录 前言声明一、SpringBlade系统简介二、漏洞描述三、影响版本四、漏洞复现五、修复建议 前言 SpringBlade 是一个由商业级项目升级优化而来的微服务架构 采用Spring Boot 2.7 、Spring Cloud 2021 等核心技术构建,完全遵循阿里巴巴编码规范。提供基于React和…

2024年美赛数学建模思路 - 案例:退火算法

文章目录 1 退火算法原理1.1 物理背景1.2 背后的数学模型 2 退火算法实现2.1 算法流程2.2算法实现 建模资料 ## 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 退火算法原理 1.1 物理背景 在热力学上&a…

文献速递:人工智能医学影像分割---基于合成MRI辅助的深度注意力全卷积网络的CT前列腺分割

文献速递:人工智能医学影像分割—基于合成MRI辅助的深度注意力全卷积网络的CT前列腺分割**** 01文献速递介绍 Prostate cancer is the most common cancer and the second leading cause of cancer death among men in the United States.1 Depending on the risk…

TA百人计划学习笔记 3.2混合模式及剔除

资料 源视频 【技术美术百人计划】图形 3.2 混合模式及剔除_哔哩哔哩_bilibili ppt https://github.com/sunkai174634/PhotoShopBlendModeUnityShader 实例 notargs.com混合模式 unity 官方文档 ShaderLab:混合 - Unity 手册 是什么 从渲染流程解释 从效果上解释 Bl…