数据结构初阶 链表的补充

数据结构初阶 链表的补充

一. 主要介绍

本篇博客将会着重介绍四个接口函数

1. 查找指定位置的链表
2. 在指定位置插入数据
3. 在指定位置删除数据
4. 销毁链表

二. 查找指定位置的链表

我们这里首先画出一个单链表的逻辑图

我们假设 里面的值是确定的 是 5 3 4 3 1

那么我们就有图如下所示

我们首先来看普通情况 （找值为3的位置）

首先我们的pos指针被head赋值 指向单链表的第一个位置

看看它的值是否是我们要找的值

如果不是就找下一个

直到我们的pos指针指向空为止

这里因为有多个可能的pos值

我们返回了第一个找到的值之后 继续找下一个值 找到空为止

如果我们找不到的话 就什么都不做

代码表示如下

voidSListFindpos(SL* pphead, SLType x){structSLlist* pos;
    pos = pphead;int i =1;while(pos){if(pos->date == x){printf("找到了第%d个节点：%p->%d\n", i++, pos, x);}
        pos = pos->next;}}

演示效果如下

三. 在指定位置插入数据（前）

我们在使用这个接口函数之前 首先要将前面的Find函数修改一下

让它返回指向pos位置的指针

修改之后接口代码如下

structSLlist*SListFindpos(SL* pphead, SLType x){structSLlist* pos;
    pos = pphead;int i =1;while(pos){if(pos->date == x){return pos;}
        pos = pos->next;}}

之后我们来看图

我们想要在pos面前插入一个数据 那么我们就需要得到两个信息

一个是指向pos位置的指针

一个是pos指针的位置

很显然我们知道pos指针的位置 但是pos前面的位置怎么找呢？

没办法 这就来到了单链表的缺陷之一

只能够向后查找

如果这个时候我们想要得到pos数据的位置只能一步步遍历

上代码

voidSListInsertPos(SL** pphead, SL* pos ,SLType x){
    SL* newnode =(SL*)malloc(sizeof(SL));
    newnode->date = x;
    newnode->next =NULL;

    SL* prev =*pphead;while(prev->next!=pos){
        prev = prev->next;}
    prev->next = newnode;
    newnode->next = pos;}

显示效果如下

我们想想看 假如说Find找不到值 我们就让它返回一个空指针

如果说要我们在空的位置插入数据 这不就是难为人嘛

直接给它断言一下

我们来试着找一个不存在的值

这里回直接断言报错

四. 在指定的位置插入数据（后）

还是一样 咱们先考虑普遍数据

这里就很简单了 我们只需要将pos指向的下一位指向新创建的数据

另外将原来的pos next赋值给新数据

代码表示如下

voidSListInsert2Pos(SL** pphead, SL* pos, SLType x){assert(pos);
    SL* newnode =(SL*)malloc(sizeof(SL));
    newnode->date = x;

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

我们可以发现 pos位置后面插入数据比前面插入数据简单多了

代码演示结果如下

五. 删除指定位置的数据

还是一样 我们先看图

这个看上去很简单

我们只需要做两步就可以

第一 释放将pos上面一个节点的指针指向pos下一个节点的指针

（同样的 需要查找pos前面一个节点的位置 ）

第二 释放pos位置开辟出来的空间 避免内存泄漏

我们现在来看看特殊情况 如果说pos返回的NULL指针 还是一样的断言报错

代码表示如下

voidSListDelPos(SL** pphead, SL* pos){assert(pos);
    SL* prev =*pphead;while(prev->next != pos){
        prev = prev->next;}

    prev->next = pos->next;free(pos);
    pos =NULL;}

表示结果如下

六. 删除单链表

还是老样子 我们直接画图

这里特别要注意一点！ 我们删除单链表并不是只是把头指针指空就结束了
这样会造成很严重的内存泄漏问题！

但是这样子的话我们一个指针就做不了了

如果说我们将一个指针先释放 它就指不到后面了

如果说我们先指向后面 那么它就找不到前面的数据了

所以说这里我们需要两个指针

我们注意到pos指向空指针的时候 pre刚好指向最后一个释放

下面我们开始写代码

voidSListDestory(SL** pphead){assert(*pphead);
    SL* prev =NULL;
    SL* pos =*pphead;while(pos){
        prev = pos;
        pos = pos->next;free(prev);}
    prev =NULL;*pphead =NULL;}

演示效果如下

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏

希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正

大家下期再见