【数据结构】链表 （4000+字超级详细 图文结合）C语言

**ઇଓ **欢迎来阅读子豪的文章，大家有什么宝贵的意见或建议可以在留言区留言

**☾ ⋆ **如果你喜欢我的文章，欢迎 点赞 关注 收藏

**ღღ **我的码云仓库：补集王子 (YZH_skr) - Gitee.com

*❣***ฅ **不要偷偷拿走我的小火车哦~嘿嘿

顺序表对比

以前学习了的顺序表

优点

动态物理空间下标连续存放访问

缺点

1，空间不够，要扩容，扩容有一定的内存消耗，其次一般扩容是扩二倍，会存在一定的空间浪费

2.头部或中间插入效率低（要挪动数据）

改善方案： 链表

1.按需申请释放空间

2.头部或者中间插入删除就不需要挪动数据（新增然后去掉原来的）

跟这个小火车类似

单链表链表很重要

链表笔试面试题基本都是单链表结构，单链表会成为以后更复杂数据结构子结构（哈希桶，图）

下图中，每个方框代表一个结点，箭头代表链接next关系

1的next存2的地址，2的next存3的地址，以此类推

习惯

一般需要遍历的时候就设置cur（指向当前位置）指针

单独弄个指针，不让原来的指针动（cur ）

循环一直更新cur直到遇到NULL

while (cur != NULL)
    {
        cur = cur->next;
    }

难点：

cur = cur->next 指针 = 指针里的next所指向的值 （更新指针）

基础链表操作

打印

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

开辟新结点

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

链表增删查改

其实只需要懂下面两张图就能轻松理解增删查改的步骤了

尾插

void SListPushBack(SLTNode** pphead, SLTdataType x)    // 尾插    只要改了第一个结点就得用二级指针 传地址
{
    SLTNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        // 找尾节点
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

现在只有头结点的地址（phead）

尾巴要不空就是最后一个

判断 while (tail->next!=NULL)

把新的地值給最后一个然后把自己变为空

这里出现问题 plist是实参 phead 是形参 形参改变是对实参无影响的 原函数plist还是空

所以在可能会改变头接点的情况下，都要传址调用

链表是多个节点通过结构体的next指针实现逻辑结构的链接次序的，我们通常表示链表是用一个指针进行表示的，这个指针指向的就是链表的头结点。通过这个头结点地址，我们可以实现对链表的遍历等其它操作。
以尾插为例，这里我们在链表的最后一个节点的后面插入一个节点，我们并不影响plist和phead的指向 这个时候一级指针就可以实现

但如果我现在是空链表想插入一个节点，我这里就需要改变plist的指向，但是如果是传值的话，我们只能修改实参的拷贝phead的指向，而不能真正操作修改plist的指向。我们调用完尾插的函数之后，我们的plist还是指向null，这块就有问题了

指针的地址就是二级指针

pphead是存的plist的地址 想改plist就要对pphead解引用

头插

void SListPushFront(SLTNode** pphead, SLTdataType x)
{
    assert(*pphead);

    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

若头为空，亦是如此插

头删

void SListPopFront(SLTNode** pphead)
{
    assert(*pphead != NULL);
    //if (*pphead == NULL)
    //    return;

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

必须要先存一下头结点信息，不然free掉了就找不到下一个指针了

传二级问题

要改变plist（头结点），就要传plist的地址，需要传二级指针

处理空指针 或者 删成空指针还在删的问题

指针检查（断言debug版本才有 release会忽略）

尾删

void SListPopBack(SLTNode** pphead)
{
    assert(*pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //SLTNode* tailPrev = NULL;
        //SLTNode* tail = *pphead;
        //while (tail->next != NULL)
        //{
        //    tailPrev = tail;
        //    tail = tail->next;
        //}
        //free(tail);
        //tailPrev->next = NULL;

        SLTNode* tail = *pphead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

直接找尾删掉不行

这样倒数第二个就成了野指针

把尾部的前一个给他记录一下，设置一个prev指针指向cur的前一个结点

tail走一下prev走一下

** 删到只有一个结点的时候要单独考虑一下**

if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }

查找（返回此结点）

SLTNode* SListFind(SLTNode* phead, SLTdataType x)
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->data == x)
            return cur;

        cur = cur->next;
    }
    return NULL;
}

pos位置插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTdataType x)
{
    assert(pos);
    assert(pphead);

    // 头插
    if (pos == *pphead)
    {
        SListPushFront(pphead, x);
    }
    else
    {
        SLTNode* prev = *pphead;    //记录前面一个结点
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        SLTNode* newnode = BuySListNode(x);    //插入
        prev->next = newnode;
        newnode->next = pos;
    }
}

删除pos位置结点

// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);

    if (*pphead == pos)
    {
        SListPopFront(pphead);    // 只有一个就头删
    }
    else
    {
        SLTNode* prev = *pphead;    //记录前面一个结点
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        prev->next = pos->next;        //删除

        free(pos);                    //释放指针
        pos = NULL;
    }
}

插入pos后

要注意顺序 ，要先指向后一个再，让pos的next指向newnode (删除)

还有一种就是用一个指针标识他，就不在乎链接顺序

// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTdataType x)
{
    assert(pos);

    //SLTNode* newnode = BuySListNode(x);    先指向下一个
    //newnode->next = pos->next;            再链接 删除原来那根线
    //pos->next = newnode;                    不能反

    // 不在乎链接顺序
    SLTNode* newnode = BuySListNode(x);
    SLTNode* next = pos->next;    // 记录下一个结点
    // pos newnode next
    pos->next = newnode; 
    newnode->next = next;
}

删除pos后的结点

// 删除pos后面的接点
void SListEraseAfter(SLTNode* pos)
{
    assert(pos);

    if (pos->next == NULL)
        return;

    SLTNode* del = pos->next;
    //pos->next = pos->next->next;
    pos->next = del->next;

    free(del);
    del = NULL;
}

总结

一：指针检查

当要对指针进行修改操作时应该考虑空指针野指针问题应该对指针进行检查

1. 温柔的检查（if判断）

if (*pphead == NULL)

    return;

2. 暴力的检查（断言）

assert ( *pphead)

二：释放结点（free）

当结点不用了，（next线断了应该进行释放）

free（cur）;

cur指向空间的内容已经被释放了 但是可以对cur重新赋值 改变cur的指向

所以对指针先free，再赋值

总之学习还是得多画图，凭空想象很困难

数据结构链表这一块知识内容毋庸置疑非常重要

学习起来肯定有一定的难度，但是不要怕

第一遍不会就看第二遍，软磨硬泡必须给他拿下！

如果你喜欢我的文章，别忘了 素质三连：关注，收藏，点赞！