0
0

今天小胡杨手绘28张图只为教会你单链表

欢迎光临

**个人主页：欢迎大家光临——>**沙漠下的胡杨

** 各位大帅哥，大漂亮**

如果觉得文章对自己有帮助

可以一键三连支持博主

** 你的每一分关心都是我坚持的动力**

** **

☄： 本期重点 ：数据结构篇单链表实现

** 希望大家每天都心情愉悦的学习工作。**

目录

什么是单链表呢？

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

**类似于向一条链串联起来的一样。 **

链表的实际地址的存放

链表我们一般的图示为下面的样子：

** 实际上我们要看链表的实际地址存放：**

代码如下：

    SLTNode* d1 = (SLTNode*)malloc(sizeof(SLTNode));
    assert(d1);
    SLTNode* d2 = (SLTNode*)malloc(sizeof(SLTNode));
    assert(d2);
    SLTNode* d3 = (SLTNode*)malloc(sizeof(SLTNode));
    assert(d3);

    d1->data = 1;
    d2->data = 2;
    d3->data = 3;
    

    d1->next = d2;
    d2->next = d3;
    d3->next = NULL;
    
    SListPrint(d1);

这是单链表的实际存放的地址

创建链表

首先我们要先创建链表，用结构体创建这就不在多说啦，关于这个头文件定义结构体细节处理都在代码中了。 结构体有不明白的请移步☞结构体详解

#pragma once//防止头文件重复包含

#define  _CRT_SECURE_NO_WARNINGS//防止scanf函数报错

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//断言头文件

typedef int SLTDataType;//把int重命名

typedef struct SListNode//结构体重命名
{
    SLTDataType data;
    struct SListNode *next;//这个不可以使用重命名后的名字
}SLTNode;

申请结点

我们有链表了，但是我们还没有链表的组成成员呀！所以我们要申请结点，什么时候需要申请结点呢？那肯定是选择插入就会需要结点啊，所以我们不妨写函数是就直接申请结点，并附上数据，指针我们可以默认指向为NULL。

看下代码：

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode *)malloc(sizeof(SLTNode));
    assert(newnode);
    newnode->next = NULL;
    newnode->data = x;

    return newnode;
}

我们可以直接要把要赋给的值传给函数，然后开辟一个结点的空间，进行断言，判断是否申请到了空间，接着把要赋给的值给data，把结点指针的指向NULL。

链表的尾插

首先我们先想一下传什么参数呢？

首先是要插入的值，那么是传链表的地址，还是直接传链表呢？如果链表为NULL呢？

我们先看一个示意图：

我们已经有啦一个结点，并且已经放好值了，那么怎么操作呢？我们只需要把d3中的next的NULL指向新开辟的结点，是不是就可以啦！接着看图：

变为这个样子就可以啦。****（最重要的是plist没有改变）

可是如果我们的链表没有元素呢？****接着看图：

** 此时的plist是为NULL，那我们直接吧plist指向 d 的地址就好呀，并且只有一个 d 刚好d的下一个结点为NULL。**（注意：plist已经由空指针变为了指向新节点 d 了）

看下代码（很多人都会错误的示范）：

void SListPushBack(SLTNode *pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);

    if (pphead == NULL)
    {
        pphead = newnode;
    }
    else
    {
        SLTNode* cur = pphead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}

这样写的话有没有一点点的不妥呢？

我们调试下，发现plist没有变，链表没有插入，接着看图：

我们得出了一个结论：

不是传指针，就可以改变这个指针的指向的，我们应该传二级指针的形式，然后解引用，达到改变plist地址的效果，所以我们链表所有的插入 和 删除函数都传二级指针，传二级指针时，我们使用头结点只要解引用就好了。

所以正确的代码为：

void SListPushBack(SLTNode **pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);

    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* cur = *pphead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}

其他的都没有改变，只是把用链表头的地方，改为解引用链表头。

链表的头插

头插我们依然要考虑这个问题就是 plist 是否改变呢？

这是肯定的，头插就是换个头呀！就是链表的头被改变了，所以我们要传地址。

我们接着看个图来理解下：

** 这是刚开始的情况，我们要把 plist 的地址放入新结点，并且把plist改为新结点的地址。**

下面我们接着看图示：

我们是没有plist，但是我们有 pphead，直接解引用就是头结点。

需要注意的点：

必须要先进行步骤一，再进行步骤二，否则，我们的头结点就被覆盖了，然后就找不到以后的节点啦，所以我们一定要先执行步骤一，在执行步骤二。

下图是先执行步骤二，在执行步骤一的后果（死循环）：

下面是正确的代码：

void SListPushFrond(SLTNode **pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

链表的头删：

链表的头删很简单，我们还是传递二级指针，因为如果就一个结点，删除后变为了NULL，此时链表的指向还是发生了变换。

看下面图示：

** 我们只需要把原来头结点的指向第二个结点，然后把原来头结点free掉就可以啦。**

需要注意的是：

我们要先创建一个结点指针，保存第二个结点的地址

然后我们要释放原来的头指针（*pphead）

*接着把保存第二个结点的地址赋值给 pphead，让它成为新的链表的头指针。

如果刚好是一个结点，也是可以的，因为*pphead的下个结点为NULL

*我们先把NULL存起来，然后把 pphead 这个结点 free掉

再把NULL放到*pphead中，就变为NULL了，符合条件。

下面是代码：

void SListPopFrond(SLTNode **pphead)
{
    assert(pphead);
    
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

链表的尾删

链表的尾删我们要考虑的就要多点，如果有一个结点，和有多个结点分开分析

还是先看图：

如果是这种情况，就直接free掉，然后置为NULL就好了。

** 这种情况就要把d3这个结点 free掉，然后把 d2 结点的指向NULL就好了。**

那我们怎么找到 d2 呢？接着看图：

** 这就是我们写代码的实际逻辑啦，下面是代码，代码中的注释部分是第二种办法，通过访问两次下一个指针的指向：**

void SListPopBack(SLTNode **pphead)
{
    assert(*pphead);

    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //SLTNode *cur = *pphead;
        //while (cur->next->next != NULL)
        //{
        //    cur = cur->next;
        //}
        //free(cur->next);
        //cur->next = NULL;
        SLTNode *tail = *pphead;
        SLTNode *tailprev = NULL;
        while (tail->next != NULL)
        {
            tailprev = tail;//失误三
            tail = tail->next;
        }
        free(tail);
        tailprev->next = NULL;
    }
}

查找链表元素：

查找就很简单了，我们直接暴力查找就好啦：

看下代码：

SLTNode* SListFind(SLTNode *pphead, SLTDataType x)
{
    SLTNode* cur = pphead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }

    return NULL;
}

需要注意的地方：

首先，我们要先保存头指针，不要改变头指针。

其次，我们要考虑代码的健壮性，并且配合其他的函数接口使用，所以我们返回值设定为结点指针。如果找不到，我们就返回NULL。

修改链表元素

修改就可以配合查找一起使用也很简单，直接看代码吧：

我们可以通过查找到的下标，进行修改，没啥说的。

void SListModify(SLTNode *pos, SLTDataType x)
{
    assert(pos);

    pos->data = x;
}

在链表任意位置后插

在链表任意位置后插入，首先我们应该找该位置，然后进行插入。

先看图：

这个插入位置我们已知，然后我们只需要改变指向就可以啦，接着看图：

我们要注意的是先进行步骤一，在进行步骤二，顺序一定不能反，否则就和头插一样死循环了。

下面是具体的代码：

void SListInsertAfter(SLTNode *pos, SLTDataType x)
{
    assert(pos);

    SLTNode* newnode = BuySListNode(x);//注意下面代码的位置
    newnode->next = pos->next;
    pos->next = newnode;
}

在链表任意位置前插

在链表任意位置后插，这个比较复杂啦。下面看图一点点的分析：

首先如果只有一个结点，那就相当于头插了

和头插一样，不在赘述啦~

如果有多个结点，就复杂啦~ 我们先看图吧：

我们怎么知道这个位置前一个的结点值呢？方法其实和尾删一样，使用一个变量遍历，循环结束的条件变为 p1->next != 这个位置 。

看下图：

最后看下代码：

void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{
    assert(pos);

    if (pos == *pphead)
    {
        SListPushFrond(pphead, x);
    }
    else
    {
        SLTNode *prve = *pphead;
        while (prve->next != pos)
        {
            prve = prve->next;
        }
        SLTNode* newnode = BuySListNode(x);
        newnode->next = pos;
        prve->next = newnode;
    }
}

在链表任意位置后删

删除任意位置比较简单，我们只需要注意一点，

就是链表元素为1时，就没有后续啦，就不能删除啦。

还是看下图吧：

只有一个结点，不能删除后面的元素，其他的，直接覆盖，然后free掉pos位置的结点

我们直接看代码吧：

void SListEraseAfter(SLTNode *pos)
{
    assert(pos);
    SLTNode *next = pos->next;
    if (next)
    {
        pos->next = next->next;
        free(next);
        next = NULL;
    }
}

删除链表的任意位置

这个又点麻烦，我们一点点分析：

首先如果这个位置在链表的头上，那么我们就是头删，

还是看图：

** 如果在其他位置删除，和任意位置前插一样，我们要创建一个指针结点，进行遍历，循环结束的条件是 p1->next != pos,然后把断裂的链表链接就好啦。**

接着看图吧：

下面是代码：

void SListErase(SLTNode **pphead, SLTNode *pos)
{
    assert(pphead);
    assert(pos);

    if (*pphead == pos)
    {
        SListPopFrond(pphead);
    }
    else
    {
        SLTNode *prve = *pphead;
        while (prve->next != pos)
        {
            prve = prve->next;
        }
        prve->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

链表的打印

打印可以不用传链表地址，我们不会修改链表内容，还有一点就是创建临时变量来遍历。

看代码吧：

void SListPrint(SLTNode* pphead)
{
    SLTNode* cur = pphead;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

链表空间释放

这个没说的，还是要传链表的地址，因为我们要把链表置为NULL

直接看代码吧：

void SListDestroy(SLTNode **pphead)
{
    assert(pphead);

    SLTNode *cur = *pphead;
    while (cur)
    {
        SLTNode *next = cur->next;
        free(cur);
        cur = next;
    }

    *pphead = NULL;
}

关于整体的代码头文件篇：

#pragma once

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

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

void SListPrint(SLTNode* pphead);//打印

SLTNode* BuySListNode(SLTDataType x);//申请新节点

void SListPushBack(SLTNode **pphead, SLTDataType x);//尾插

void SListPushFrond(SLTNode **pphead, SLTDataType x);//头插

void SListPopFrond(SLTNode **pphead);//头删

void SListPopBack(SLTNode **pphead);//尾删

SLTNode* SListFind(SLTNode *pphead, SLTDataType x);//查找

void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x);//任意位置前插

void SListInsertAfter(SLTNode *pos, SLTDataType x);//任意位置后插

void SListErase(SLTNode **pphead, SLTNode *pos);//删除任意位置

void SListEraseAfter(SLTNode *pos);//任意位置后删

void SListDestroy(SLTNode **pphead);//释放链表

void SListModify(SLTNode *pos, SLTDataType x);//修改链表

关于整体代码源文件：

#include "SList.h"

void SListPrint(SLTNode* pphead)
{
    SLTNode* cur = pphead;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode *)malloc(sizeof(SLTNode));
    assert(newnode);
    newnode->next = NULL;
    newnode->data = x;

    return newnode;
}


void SListPushBack(SLTNode **pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);

    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* cur = *pphead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}

void SListPushFrond(SLTNode **pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

void SListPopBack(SLTNode **pphead)
{
    assert(*pphead);

    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //方法二
        //SLTNode *cur = *pphead;
        //while (cur->next->next != NULL)
        //{
        //    cur = cur->next;
        //}
        //free(cur->next);
        //cur->next = NULL;
        SLTNode *tail = *pphead;
        SLTNode *tailprev = NULL;
        while (tail->next != NULL)
        {
            tailprev = tail;
            tail = tail->next;
        }
        free(tail);
        tailprev->next = NULL;
    }
}


void SListPopFrond(SLTNode **pphead)
{
    assert(pphead);
    
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}


SLTNode* SListFind(SLTNode *pphead, SLTDataType x)
{
    SLTNode* cur = pphead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }

    return NULL;
}

void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{
    assert(pos);

    if (pos == *pphead)
    {
        SListPushFrond(pphead, x);
    }
    else
    {
        SLTNode *prve = *pphead;
        while (prve->next != pos)
        {
            prve = prve->next;
        }
        SLTNode* newnode = BuySListNode(x);
        newnode->next = pos;
        prve->next = newnode;
    }
}

void SListInsertAfter(SLTNode *pos, SLTDataType x)
{
    assert(pos);

    SLTNode* newnode = BuySListNode(x);//注意下面代码的位置
    newnode->next = pos->next;
    pos->next = newnode;
}

void SListErase(SLTNode **pphead, SLTNode *pos)
{
    assert(pphead);
    assert(pos);

    if (*pphead == pos)
    {
        SListPopFrond(pphead);
    }
    else
    {
        SLTNode *prve = *pphead;
        while (prve->next != pos)
        {
            prve = prve->next;
        }
        prve->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SListEraseAfter(SLTNode *pos)
{
    assert(pos);
    SLTNode *next = pos->next;
    if (next)
    {
        pos->next = next->next;
        free(next);
        next = NULL;
    }
}

void SListDestroy(SLTNode **pphead)
{
    assert(pphead);

    SLTNode *cur = *pphead;
    while (cur)
    {
        SLTNode *next = cur->next;
        free(cur);
        cur = next;
    }

    *pphead = NULL;
}

void SListModify(SLTNode *pos, SLTDataType x)
{
    assert(pos);

    pos->data = x;
}

———————————————————————————————————————————

关于链表的简单实现就讲解到这里啦，

码字不容易，希望各位不要吝啬你们的三联哦~

标签： 数据结构
本文转载自: https://blog.csdn.net/m0_64770095/article/details/124448915
版权归原作者 沙漠下的胡杨 所有， 如有侵权，请联系我们删除。
登录后发布评论

“今天小胡杨手绘28张图只为教会你单链表”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

安全见闻（9）二进制安全

C++20 STL CookBook2 更强大的编译时 + 安全比较 + spaceship比较符

Linux：login shell和non-login shell以及其配置文件

使用git命令实现对gitee仓库的下载、更新、上传、上传更新操作。

network-magic：网络管理员必备的开源网络管理工具

git-- github的使用

结合Gitee、PicGo和Typora构建一个免费的个人笔记工具

文章导航