数据结构(单链表)
创始人
2024-01-28 15:43:07
0

    前沿:

       在前面总结的顺序表的时候,最后也说出了他的一些缺点,例如头插/中间插的时候的时间复杂度是O(n),这个效率并不高,而如何提高效率的实现呢,这里我们可以通过单链表来简单的提高这个效率。

  思维导图:

目录

 一、链表的概念:

1.1概念:

 二、链表的结构:

2.1结构:

三、单链表的实现:

3.1链表的初始化:

 3.2链表申请一个节点:

3.3链表的头插:

 3.4链表的的打印:

3.5链表的尾插:

 3.6链表的头删:

3.7链表的尾删:

 3.8链表的销毁:

3.9链表的查找和修改:

​3.10链表的pos插入:

3.11链表在pos位置上的删除:

总结 :


 一、链表的概念:

1.1概念:

      链表是一种物理存储存结构上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

 二、链表的结构:

2.1结构:

2.1.1 单向、双向

2.1.2 带头、不带头

2.1.3循环、不循环

这都是链表的不同结构,今天我们要写的比较简单,是单链表的实现。

三、单链表的实现:

3.1链表的初始化:

   3.1.1链表的初始化很简单的只需要让头指针为零就可以啦! 

但其实我们大可不必这么麻烦直接让plist的地址为NULL就可以

 3.2链表申请一个节点:

3.2.2链表进行插入时都要创建一个一个结构体,为了方便我们直接通过一个函数来创建方便我们进行插入。

3.3链表的头插:

3. 3.1链表头插代码实现前,我们先记住一句话,改谁就传谁的地址,因为函数传参传的是形参,形参的改变不会影响实参的大小,要想改变实参的大小我们需要传入实参的地址。(不理解的可以看我的函数栈帧的创建销毁^_^https://blog.csdn.net/m0_63177573/article/details/127750960)这里我们需要改变头节指向的头节,而头节本身就是个地址,所以这里我们需要用到二级指针。

 3.4链表的的打印:

3.4.1链表的打印我只需要我们创建一个结构体指针对我们的的数一一遍历即可。

这里我们就可以先对插入进行测试一下 

这里我就展示一个的测试,其他的测试,我们要每完成一个功能就进行测试一下。

3.5链表的尾插:

3.5.1链表的尾插 有两种情况,第一种是第一个节点为NULL,第二种是不为NULL。两种情况不一样我们要分情况写。

打印结果: 

 3.6链表的头删:

3.6.1创建函数前我们都要先想是改变结构体指针呢还是结构体成员呢,头删很显然是改变结构体指针,所以需要用二级指针。

打印结果 :

3.7链表的尾删:

(^_^)v   首相我们还是要考虑是改变结构体指针还是结构体,这里我们分两种情况,当只是一个节点的时候,我们则需要改变结构体指针,需要把节点释放,同时设为NULL,故需要二级指针,当多个节点的时候,只需要改变结构体成员。 

 

打印结果

 3.8链表的销毁:

3.8.1链表在使用完之后一定要进行销毁,否则将会出现内存的泄漏。

3.9链表的查找和修改:

3.9.1 链表可以在查找中进行修改 。代码还是比较简单的。^ _ ^

测试结果:

3.10链表的pos插入:

       3.10.1链表的pos插入有两种方式,一种是节点插在前面,另一种把节点插在后面。

^_^pos前插入:

结果为: 

^_^pos后插入: 

 3.11链表在pos位置上的删除:

测试结果: 

到这里单链表的大概已经全部完成啦!

总结 :

       ^ - ^单链表只是解决了顺序表的一部分缺点,但并没有全部解决,例如在尾插或者尾删的时候,仍然需要一个结构体指针来遍历寻找。而能实现彻底解决的方法是循环带头双向链表,在后面的日子里,我会努力完成💪

 最后 孩子码文不易,如果觉得文章有帮助的话,可以点个关注哈哈哈哈哈。

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...