数据结构(单链表)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
前沿
在前面总结的顺序表的时候最后也说出了他的一些缺点例如头插/中间插的时候的时间复杂度是O(n)这个效率并不高而如何提高效率的实现呢这里我们可以通过单链表来简单的提高这个效率。
思维导图
目录
一、链表的概念
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位置上的删除
测试结果
到这里单链表的大概已经全部完成啦
总结
^ - ^单链表只是解决了顺序表的一部分缺点但并没有全部解决例如在尾插或者尾删的时候仍然需要一个结构体指针来遍历寻找。而能实现彻底解决的方法是循环带头双向链表在后面的日子里我会努力完成
最后 孩子码文不易如果觉得文章有帮助的话可以点个关注哈哈哈哈哈。