无头单向非循环链表的实现

2024-04-07 01:36

本文主要是介绍无头单向非循环链表的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.链表的结构

在用代码实现之前,我们要先了解这种链表的逻辑结构和物理结构,

在逻辑上我们能知道这种链表能够通过前一个节点的 next 来存储下一个节点的地址,从而能够找到下一个数据,这就是一种线性结构,我们可以把数据看成是按照一定的顺序存储起来的,虽然他们的空间顺序不一定是他们的逻辑顺序。上面图中的 head 并不是指的链表是有头链表,head不是烧饼位,而是链表头节点,存储第一个数据的空间。我们使用链表时只要知道头节点的位置,就能访问到所有的数据,如果链表为空,则一个节点也没有。

这就是链表的物理结构,通过对节点的 next 中存的地址解引用就能访问到下一个节点,而尾节点的 next 我们设置为空指针。

2.链表的实现

链表的物理结构和逻辑结构我们清楚之后,我们就能找到每个节点的情况,无非就是数据域和指针域,数据域用来存储数据,而指针域用来存储下一个节点的指针,对于每一个节点我们用结构体定义出来就是这样的:

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

而对于后续的链表的操作,我们只需要传头结点的地址就够了,因为链表通过头节点就能访问到所有数据。而链表没有数据时,没有头节点,链表地址就是空指针。所以我们一般首先将plist初始化为NULL,而因为链表没有元素时什么也没有,所以现在要实现的这个单链表是不需要初始化的。

void test1()
{SLTNode* plist = NULL;//对plist进行操作}

下面就是要实现的一些接口

头插

对单链表头插数据十分简单。我们首先要创建一个newnode,因为创建节点的功能我们在后面的各种插入数据中都要用到,所以我们直接写一个函数来完成创建节点的功能

//创建新节点
SLTNode* NewSLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

我们在函数中创建一个新节点,将新节点的的数据初始化为插入的数据,next设置为NULL。然后返回新节点地址。

然后头插数据我们具体要怎么做呢?

看图就很简单了,我们只需要 phead 指向新节点,然后原来的链表链接到新节点的next就完成了。

但是头插是要改变 phead 的,也就是整个链表的头节点地址 plist ,所以在头插函数中我们要传plist 的地址,也就是一个二级指针,记住,要修改什么类型的变量就要传那个类型的指针,plist是SLTNode*类型的指针变量,要修改 plist 就要传plist的地址,在函数参数部分就要用SLTNode** 的指针来接收。

//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x);

传参的时候,可能链表为空,也就是phead(plist)为NULL,但是 plist 是一个变量,他的地址不可能为空,也就是pphead 不能为NULL,如果为空,就说明传参有问题,我们可以用assert断言一下,后续的很多结构都要对一些不可能为空的指针断言检查。链表为空和链表不为空时的操作其实是一样的逻辑和代码,因为phead为NULL的时候,将 phead 连接到newnode的时候,不会对newnode有什么影响,newnode的next还是NULL,也就是它既是头指针也是尾指针。

//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = NewSLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

为了方便测试,我们先写一个打印链表的函数出来。

打印链表

打印函数我们只需要从头结点遍历到NULL就行了。因为打印链表不会出现需要修改头结点的请跨,所以我们传 plist 就够了,同时因为链表可能为空,我们不用对传过来的phead断言。

//打印链表
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur)//当cur为空时就结束{printf("%d->", cur->data);cur = cur->next;}//为了更加直观,在最后面打印一个NULLprintf("NULL\n");}

写完打印函数之后先来测试一下头插的函数

	SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);

头插函数没有问题。

头删

头删函数我们一样看图来分析

我们只需要把phead指向的节点删除,在这之前要修改phead指向第二个元素,要注意先换phead的指向再去free第一个节点,否则就出现野指针的问题了。同时,我们要注意头节点要修改,我们要传二级指针pphead,而且,删除元素的时候链表不能是空链表,所以我们还要对 *pphead也进行断言。

//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//先记录要删除的节点SLTNode* del = *pphead;//调整头结点指针*pphead = (*pphead)->next;//最后释放原来的头节点free(del);
}

然后对函数进行测试,我们一个一个把数据删完

	//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);//头删SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);

测试链表为空再删除一下的情况

assert断言失败报错,说明函数功能是没问题的。因为当链表只有一个节点时,我们先将 phead 的值修改为phead的next,也就是NULL,所以删完之后phead又重新变成了空指针。

尾插

单链表的尾插是一件很麻烦的事情,因为他首先要找到尾节点,而由于他是单向非循环的,所以找尾节点只能遍历。我们用一个 cur 的指针来遍历链表

而cur什么时候停下来呢,尾节点有一个特点,就是他的next为NULL,所以我们的遍历的结束条件就是cur->next!=NULL。但是光这样还不行,尾插的对象可能是一个空链表,也就是cur为NULL,这时候对cur解引用就会出错。所以尾插也要检查链表是否为空,如果为空,也要修改头结点的指针,所以尾插传的也是 pphead (&plist)。而当链表为空时我们可以复用头插的函数来插入数据 。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);if (*pphead == NULL)//如果为空链表{SLTPushFront(pphead, x);}else{SLTNode* newnode = NewSLTNode(x);SLTNode* cur = *pphead;while (cur->next){cur = cur->next;}//找到尾节点将newnode连接到尾节点的nextcur->next = newnode;}
}

然后对尾插进行测试


void test2()
{SLTNode* plist = NULL;//对plist进行操作//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}

尾删

尾删的第一步和尾插一样都是找尾节点,但是又有一点不一样,就是尾删需要用一个指针prev来保存尾节点的前一个节点,因为我们不仅要释放掉最后一个节点,还要对倒数第二个节点的next置为NULL。当然尾删的前提是链表不为空,可以用assert断言,同时,因为删除数据可能会把链表删为空,也就是可能会改变phead,所以也要传二级指针。这里我们要思考一下要不要将只有一个节点的请跨单独拿出来讨论。

当只有一个节点时,cur->next为NULL,所以不会进入循环中,这时候我们就不需要定义一个prev指针了,而是直接释放掉phead,然后要通过二级指针把plist置为NULL。

有了思路代码就很好写了

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* cur = *pphead;if (cur->next == NULL)//只有一个节点的情况{free(cur);*pphead = NULL;}else{SLTNode* prev=NULL;while (cur->next){prev = cur;cur = cur->next;}//循环退出时prev为倒数第二个节点prev->next = NULL;free(cur);}
}

首先我们来测试正常情况下的尾删


void test2()
{SLTNode* plist = NULL;//对plist进行操作//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);}

当链表为空时再次尾删

数据查找

查找函数也没什么可取巧的,我们就是要遍历链表,一一比对数据,如果链表中能找到该数据,则返回节点的指针,如果找不到就返回空指针。

//查找数据,返回节点地址
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* cur = phead;while (cur)//遍历查找{if (cur->data == x){return cur;}cur = cur->next;}//遍历完找不到就返回NULLreturn NULL;
}

而查找函数返回了节点的指针之后,我们就不用再额外写一个修改函数了,因为我们可以直接对pos的data进行操作。

测试一下查找和修改

	SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 1);if (pos != NULL){pos->data = 30;SLTPrint(plist);}else{printf("找不到\n");}

指定位置插入

链表指定位置插入的逻辑是在该位置之前插入,这时候我们就需要遍历查找pos的前一个位置。在这个函数中我们不再讨论 pos 是否为链表中的节点位置,只讨论Find函数的返回值中NULL和节点指针两个方面,如果pos传的是NULL,就报错,这就要求使用者在函数传参使得要注意一点了。同时,因为传的pos有可能是头结点的地址,如果是头节点的地址,我们就用头插的做法来写。

//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(*pphead);assert(pos);SLTNode* newnode = NewSLTNode(x);if (pos == *pphead)//头结点的情况{newnode->next = *pphead;*pphead = newnode;}else{SLTNode* prev = *pphead;while (prev->next != pos)//我们不讨论pos是非节点指针{prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

测试插入,首先测试尾节点

	SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 1);SLTInsert(&plist, pos, 30);SLTPrint(plist);

再测试头节点

指定位置之前插入数据的效率有点低,要遍历一遍,但是我们发现它在指定位置之后插入就很方便,于是我们再来实现一个指定位置之后插入的函数

//指定位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode = NewSLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

测试首尾节点

	SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 4);SLTInsertAfter(&plist, pos, 30);SLTPrint(plist);pos = SLTFind(plist, 1);SLTInsertAfter(&plist, pos, 10);SLTPrint(plist);

指定位置删除

指定位置删除的逻辑与指定位置插入差不多,也是要先找到pos的前一个结点,然后将pos的前一个结点的next修改为pos的next。由于pos也与可能是头节点,所以有可能会修改头节点,要传二级指针。

//指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos)//头删{*pphead = pos->next;free(pos);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

测试头尾的删除

	SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);//SLTNode* pos = SLTFind(plist, 4);//SLTInsertAfter(&plist, pos, 30);//SLTPrint(plist);//pos = SLTFind(plist, 1);//SLTInsertAfter(&plist, pos, 10);//SLTPrint(plist);//SLTNode* pos = SLTFind(plist, 4);SLTErase(&plist, pos);SLTPrint(plist);pos = SLTFind(plist, 1);SLTErase(&plist, pos);SLTPrint(plist);

其实这个函数还有一点点小问题,那就是对pos释放之后没有对函数外面的pos置空,如果要置空的话,就要传pos的指针,又是一个二级指针,但是在我们看来,这是使用者应该做的事。

总结

以上就是单链表的实现,它的优势就是头插头删很方便,效率很高,但是单链表除了头部操作,其他的操作都很不适合,想要做到任意位置的高效的插入删除还是要看后面要学的带头双向循环链表

这篇关于无头单向非循环链表的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881336

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

工厂ERP管理系统实现源码(JAVA)

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本,并实时掌握各环节的运营状况。 在采购管理方面,系统能够处理采购订单、供应商管理和采购入库等流程,确保采购过程的透明和高效。仓库管理方面,实现库存的精准管理,包括入库、出库、盘点等操作,确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、