一. 为什么使用链表
1.1顺序结构的缺点
在我们的顺序表结构中 有以下这么几个缺陷
1 空间不够了 需要扩容 扩容是有消耗的
2 头部或者中间位置的插入删 除 需要挪动 挪动数据也是有消耗的
3 避免频繁扩容 依次一般都是按倍数去扩 容易造成空间浪费
我们来举几个例子来论证上面三点
首先 空间不够需要扩容 这个大家没有疑问的吧
其次 头部和中间位置插入数据的时候 因为顺序表是连续存储的
所以说想要插入前面的位置的时候 后面的数据就必须要向后挪动
最后 我们如果说 不按照倍数来扩容的话 可能会更加频繁的扩容
会造成时间和效率上的浪费
按照以空间换时间的思路 还是按倍数 扩容这种解决方法更加优秀一点
1.2 链表的诞生及优点
为了解决以上顺序表的缺点 我们设计出了链表
链表的优点有
1 按需申请空间 不用了就释放空间（更合理的使用空间）
2 头部中间插入删除数据 不需要挪动数据
但是链表其实也是有缺点的
1 每一个数据 都要存一个指针去链接后面的数据节点
2 不支持随机访问
（这里简单解释下随机访问 其实就是能够通过下标直接访问第i个 然而顺序表就支持随机访问 ）
这里画个图简单对比下两种数据结构
所以说 这里我们就能得出一个结论
顺序表和链表并不是对立的关系 而是互补的关系
二. 链表的接口函数实现
2.1 类型定义
还是和顺序表那一节一样 咱们先来定义类型
structSLlist{int x;structSList* next;};
首先因为咱们这个链表储存的类型可能不是整型类型的数据
为了防止以后改来改去 我们首先先使用typedef定义一个类型
如果我们以后想要储存其他类型的数据 只需要改变一行就可以了
代码表示如下
typedefint SLType;
typedefstructSLlist{
SLType x;structSList* next;}SL;
创建一个结构体变量
SL a1;
2.2 遍历（打印）
首先直接上代码
voidSListPrint(SL* phead){
SL* cur = phead;while(cur!=NULL){printf("%d-> ", cur->date);
cur = cur->next;}}
我们这里画图给大家解释一下
phead是一个指针 它指向着第一个链表数据
第一它可以访问结构体中的date数据 可以对这个数据进行
打印 修改等操作
第二 它可以访问结构体中的next指针 而这个指针指向第二个数据
它可以通过这个指针修改自身指向的位置 从而找到链表第二
个数据
2.3 尾插数据
首先我们要尾插数据 我们首先要找到尾在哪里
我们观察图可以发现 尾部的数据跟其他的数据有一个明显的
区别就是它最后的指针指向NULL
我们可以写出以下代码
voidSListPushBack(SL* phead, SLType x){
SL* newnode =(SL*)malloc(sizeof(SL));
newnode->date = x;
newnode->next =NULL;//找到尾节点
SL* tail = phead;while(tail->date!=NULL){
tail = tail->next;}
tail->next = newnode;}
但是呢 只写下这段代码的话 可能会出现一些bug
如果一开始一个数据都没有phead指向空呢？
这样子的话 下面这一段代码是不是就会出问题了
// 空指针无法指向nextwhile(tail->date!=NULL){
tail = tail->next;}
tail->next = newnode;
所以说呢 我们还要判断下phead是不是空指针
如果是空指针 我们还要先给它赋值
加上这一行代码
if(phead==NULL){
phead = newnode;}
但是我们想想 这样子真的能成功嘛？
我们可以来实验一下
调试以下代码
voidtest1(){SListPushBack(PList,1);SListPrint(PList);}intmain(){test1();return0;}
我们可以发现 虽然说phead指针指向的位置改变了 但是说PList指向的位置没有变
这就是形参和实参的区别 想要具体了解的同学可以看看这两篇博客
函数栈帧上
函数栈帧下
所以说呢 我们要想改变PList的值 我们必须要将它的地址传进去
这样子我们就需要用二级指针来接受
我们改变以上代码和传参方式
voidSListPushBack(SL** pphead, SLType x){
SL* newnode =(SL*)malloc(sizeof(SL));
newnode->date = x;
newnode->next =NULL;if(*pphead==NULL){*pphead = newnode;}//找到尾节点else{
SL* tail =*pphead;while(tail->date !=NULL){
tail = tail->next;}
tail->next = newnode;}}
然后打印试试
我们发现就可以完美运行
2.4 头插
这里我们只需要改变两个数据
一个是新链表的next
一个是phead指向的位置
voidSListPushFront(SL** pphead, SLType x){
SL* newnode =(SL*)malloc(sizeof(SL));
newnode->date = x;
newnode->next =NULL;if(*pphead ==NULL){*pphead = newnode;}else{
newnode->next =*pphead;*pphead = newnode;}}
这里需要注意的是 其实不需要加if判断也可以
这里为了增加代码的可读性我就写上
2.5 尾删
我们要做到尾删的话首先要找到最后一个数据存储的空间 然后将它释放掉
类似这样子操作
但是呢 这样子就会出现一个问题
前面一个数据的next还是指向这一片空间 这就形成了经典的野指针问题
为此我们就必须要使用一个指针储存tail的上一个值
这样子在tail找到最后一个数据的时候 pre就能够找到倒数第二个数据的位置
代码表示如下
voidSListPopBack(SL** pphead, SLType x){
SL* pre =NULL;
SL* tail =*pphead;while(tail->next){
pre = tail;
tail = tail->next;}free(tail);
tail =NULL;
pre->next =NULL;}
结果表示如下
voidtest1(){SListPushBack(&PList,1);SListPushBack(&PList,2);SListPushBack(&PList,3);SListPushBack(&PList,4);SListPushBack(&PList,5);SListPushFront(&PList,1);SListPushFront(&PList,2);SListPushFront(&PList,3);SListPushFront(&PList,4);SListPushFront(&PList,5);SListPrint(PList);printf("\n");SListPopBack(&PList);SListPopBack(&PList);SListPopBack(&PList);SListPrint(PList);}intmain(){test1();return0;}
当然这种方法也是有问题的 如果说只有一个节点 这是偶tail指向的next本来就是空
而这个时候pre再对空指针进行解引用 （也是一个明显的野指针错误）
所以说我们要分类讨论
代码表示如下
voidSListPopBack(SL** pphead, SLType x){assert(*pphead);if((*pphead)->next==NULL){free(*pphead);*pphead =NULL;}else{
SL* pre =NULL;
SL* tail =*pphead;while(tail->next){
pre = tail;
tail = tail->next;}free(tail);
tail =NULL;
pre->next =NULL;}}
报错显示如下
2.6 头删
对比来说头删就简单很多了
我们也来分类讨论
当然这里23情况其实对于头删来说是一样的
代码表示如下
voidSListPopFront(SL** pphead){assert(*pphead);
SL* next =(*pphead)->next;free(*pphead);*pphead = next;}
结果如下
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏
希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
版权归原作者 xiaomengxing_ 所有， 如有侵权，请联系我们删除。