0
0

数据结构“入门”—单链表（C语言实现）

1:前言

🍎单链表是顺序表的进一步拓展，学好单链表同时也为我们后面学好双向链表打好基础，那单链表相对于顺序表来说有哪些优点，既然单链表比顺序表更加完善我们又为何要引入顺序表概念呢？

下面我们详谈一下顺序表相对于单链表的优缺点。

优点：

** **顺序表是连续的一段物理空间，更加方便下标的随机访问。

缺点：

  1. 插入数据，空间不足时要扩容，扩容会导致性能的消耗。
  2. 头部或者中间位置插入或者删除数据时，需要挪动数据，效率较低。
  3. 空间不能现创现用，顺序表的扩容是以双倍增长，开辟的部分空间会产生浪费，同时频繁的扩容也会导致性能的消耗。

🐂： 顺序表不能按需申请和释放空间。而为了弥补顺序表这一缺陷，做到需要存入一个数据就申请一块空间，删除一个数据就释放一块空间。链表结构由此诞生。

2:单链表基本概念

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

链表的每个结点都储存一个数据和下一个结点的地址，正是储存的地址将一个个元素联系起来，这和我们生活中的火车有点类似。

⚠：​​​​​1 从上图我们能够看出，链式结构在逻辑上是连续的，但在物理上不一定连续。

    2 现实中的结点(可想象成火车的一节车厢)一般都是从堆上申请出来的。

    3 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续也可能不连续。

接下来我们还是会用三个文件来创建一个单链表。

2:单链表的实现

2-1 ：单链表的创建

Slist.h文件


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

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;//储存下一个结点的地址。
}SListNode;

2-2 ：创建一个结点

Slist.h文件

//创建一个节点
SListNode* BuySListNode(SLTDataType x);

Slist.c文件

//创建一个节点
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    return newnode;
}

2-3 ：打印链表

Slist.h文件

//打印链表
void SListPrint(SListNode* phead);

Slist.c文件

//打印链表
void SListPrint(SListNode* phead)
{
    SListNode *cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

2-4 ：销毁单链表

Slist.h文件

//销毁单链表
void SListDestroy(SListNode** pphead);

Slist.c文件

//销毁单链表
void SListDestroy(SListNode** pphead)
{
    assert(pphead);

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

3:增删查改

3-1：插入数据

尾插

思路：

🍎：如果链表本身是空链表，则把新开的结点给phead，需要注意的是形参是实参的临时拷贝，形参的改变不影响实参，这里要改变slist，phead是slist的一份临时拷贝，phead的改变不影响slist，所以要传slist的地址，而slist本身就是指针，所以要传指针的地址，那么就要用二级指针来接收。

🍎：如果链表不是空链表，此时我们就需要创建一个指针变量tail来遍历链表，找到链表的最后一个结点，然后把新创建的结点插入进去。

Slist.h文件

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

Slist.c文件：

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
    assert(pphead);

    SListNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //找尾
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

Test.c文件

void TestSList1()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
}

头插

思路：

🍎头插相对于尾插更简单一点，只需要把新创建的结点放入链表头部，需要注意的是头插和尾插一样，需要传二级指针。

Slist.h文件

//头插
void SListPushFront(SListNode** pphead, SLTDataType x);

Slist.c文件：

//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
    assert(pphead);

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

Test.c文件

** 在pos之前插入**

思路：

🍎：pos不在头结点 。pos是结点的地址，我们通过SListFind函数找到pos。同时我们还需要找到pos前一个结点的地址，只有这样我们才能将链表的结点依次链接起来，我们可以创建一个指针变量prev，然后遍历链表，当prev->next==pos时prev就是pos前一个结点的地址，然后我们创建一个新的结点，实现结点的插入。

🍎：pos在头结点。如果pos是在头结点那么此时就相当于头插，仅用调用头插函数。

Slist.h文件

//在pos之前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x);

Slist.c文件：

//在pos之前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    //1 pos是第一个节点
    //2 pos不是第一个节点
    if (pos == *pphead)
    {
        SListPushFront(pphead, x);//pos是第一个节点调用头插。
    }
    else
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        SListNode* newnode = BuySListNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

Test.c文件

void TestSList6()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListInsertBefore(&slist, pos, 30);
    }
    SListPrint(slist);
}

在pos之后插入

思路：

🍎：在pos之后插入相较于在pos之前插入来说更加的方便，因为在pos之后插入不用寻找pos上一个结点，不用遍历。

Slist.h文件

//在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);

Slist.c文件：

/在pos之后插入(相对于pos之前插入优势：不用寻找pos上一个节点，不用遍历。
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
    assert(pos);
    
    法一
    //SListNode* next = pos->next;
    //SListNode* newnode = BuySListNode(x);

    //pos->next = newnode;
    //newnode->next = next;

    //法二
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

Test.c文件

void TestSList6()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListInsertBefore(&slist, pos, 30);
    }
    SListPrint(slist);
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListInsertAfter(pos, 10);
    }
    SListPrint(slist);
}

3-2：删除数据

尾删

思路：

🍎：尾删和尾插一样，都是要寻找最后一个结点，所以我们还是定义一个指针变量tail遍历链表，当tail->next==NULL时我们就找到了尾，但是当我们free最后一个结点后我们已无法找到倒数第二个结点，因为当我们尾删后倒数第二个结点的next必须置为空，所以我们还需要创建一个指针变量prev，尾删后将prev->next置为空。此种情况只是常规情况，当链表为空或者只有一个结点时我们还需要进行讨论。

Slist.h文件

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

Slist.c文件：


//尾删
void SListPopBack(SListNode** pphead)
{
    assert(pphead);
    //0 空链表
    //1 只有一个节点
    //2 多个节点
    if (*pphead == NULL) // assert(*pphead != NULL);
    {
        return;
    }
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
    //法一
        SListNode* prev = NULL;
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;//不置也无所谓，它是局部变量，出函数销毁。

        prev->next = NULL;

        //法二
        /*SListNode* tail = *pphead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;*/
    }
}

Test.c文件

void TestSList3()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPrint(slist);
}

头删

思路：

🍎：当链表为空时不用删除直接返回空链表，非空链表我们可以创建一个指针变量next来保存第二个结点的地址，即为第一个结点的next，然后free第一个结点，将next赋值给*pphead

Slist.h文件

//头删
void SListPopFront(SListNode** pphead);

Slist.c文件：

//头删
void SListPopFront(SListNode** pphead)
{
    assert(pphead);

    //1 空
    //2 非空
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode* next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}

Test.c文件

void TestSList4()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
    SListPopFront(&slist);
    SListPopFront(&slist);
    SListPrint(slist);
}

删除pos处数据

思路：

🍎：当pos为第一个结点时，我们只需要调用头删，当pos不是最后一个结点我们需要创建一个指针变量prev指向pos的前一个结点，然后将prev->next置成pos的下一个结点，再把pos free掉。

Slist.h文件

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos);

Slist.c文件：

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
    assert(pphead);
    assert(pos);
    if (*pphead == pos)
    {
        SListPopFront(pphead);
    }
    else
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

Test.c文件

void TestSList7()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListErase(&slist, pos);
    }
    SListPrint(slist);
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListErase(&slist, pos);
    }
    SListPrint(slist);
}

删除pos后一位数据

思路：

🍎：删除pos后一位数据相对来说比较简单，因为我们不需要考虑pos前面的地址，不需要遍历。

Slist.h文件

//删除pos位置后面的值
void SListEraseAfter(SListNode* pos);

Slist.c文件：

//删除pos位置后面的值
void SListEraseAfter(SListNode* pos)
{
    assert(pos);

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

Test.c文件

void TestSList7()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListErase(&slist, pos);
    }
    SListPrint(slist);
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListEraseAfter(pos);
    }
    SListPrint(slist);
}

3-3：查＋改数据

思路：

🍎：查找结点非常简单只需要遍历链表即可，而改数据又是建立查找的基础之上。

Slist.h文件

//查找＋修改
SListNode* SListFind(SListNode* phead, SLTDataType x)

Slist.c文件：

//查找＋修改
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }

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

Test.c文件

void TestSList5()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        printf("找到了:%p\n", pos);
        //修改
        pos->data *= 10;
    }
    SListPrint(slist);
}

4:总代码

SList.h文件

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;//储存下一个结点的地址。
}SListNode;

//打印链表
void SListPrint(SListNode* phead);

//创建一个结点
SListNode* BuySListNode(SLTDataType x);

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

//头插
void SListPushFront(SListNode** pphead, SLTDataType x);

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

//头删
void SListPopFront(SListNode** pphead);

//查找＋修改
SListNode* SListFind(SListNode* phead, SLTDataType x);

//在pos之前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x);

//在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos);

//删除pos位置后面的值
void SListEraseAfter(SListNode* pos);

//销毁单链表
void SListDestroy(SListNode** pphead);

SList.c文件

#include"SList.h"

//打印链表
void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

//创建一个节点
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    return newnode;
}

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
    assert(pphead);
    SListNode* newnode = BuySListNode(x);
    if (*pphead==NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //找尾
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
} 

//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
    assert(pphead);

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

//尾删
void SListPopBack(SListNode** pphead)
{
    assert(pphead);
    //0 空链表
    //1 只有一个节点
    //2 多个节点
    if (*pphead == NULL) // assert(*pphead != NULL);
    {
        return;
    }
    else if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        //错误写法
    /*SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    free(tail);
    tail = NULL;*/
    //法一
        SListNode* prev = NULL;
        SListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;//不置也无所谓，它是局部变量，出函数销毁。

        prev->next = NULL;

        //法二
        /*SListNode* tail = *pphead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;*/
    }
}

//头删
void SListPopFront(SListNode** pphead)
{
    assert(pphead);

    //1 空
    //2 非空
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        SListNode* next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}

//查找＋修改
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }

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

//在pos之前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    //1 pos是第一个结点
    //2 pos不是第一个结点
    if (pos == *pphead)
    {
        SListPushFront(pphead, x);
    }
    else
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        SListNode* newnode = BuySListNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

//在pos之后插入(相对于pos之前插入优势：不用寻找pos上一个节点，不用遍历。
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
    assert(pos);
    //法一
    /*SListNode* next = pos->next;
    SListNode* newnode = BuySListNode(x);

    pos->next = newnode;
    newnode->next = next;*/
    //法二
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
    assert(pphead);
    assert(pos);
    if (*pphead == pos)
    {
        SListPopFront(pphead);
    }
    else
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

//删除pos位置后面的值
void SListEraseAfter(SListNode* pos)
{
    assert(pos);

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

//销毁单链表
void SListDestroy(SListNode** pphead)
{
    assert(pphead);
    
    SListNode* cur = *pphead;
    while (cur)
    {
        SListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

Test.c文件

#include"SList.h"

void TestSList1()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
}

void TestSList2()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
    SListPushFront(&slist, 10);
    SListPrint(slist);
    SListPushFront(&slist, 20);
    SListPrint(slist);
}
void TestSList3()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
    SListPopBack(&slist);
    SListPopBack(&slist);
    SListPrint(slist);
}

void TestSList4()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }
    SListPrint(slist);
    SListPopFront(&slist);
    SListPopFront(&slist);
    SListPrint(slist);
}

void TestSList5()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        printf("找到了:%p\n", pos);
        //修改
        pos->data *= 10;
    }
    SListPrint(slist);
}

void TestSList6()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListInsertBefore(&slist, pos, 30);
    }
    SListPrint(slist);
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListInsertAfter(pos, 10);
    }
    SListPrint(slist);
}

void TestSList7()
{
    SListNode* slist = NULL;//空链表
    for (int i = 0; i < 4; i++)
    {
        SListPushBack(&slist, i);
    }

    SListPrint(slist);
    SListNode* pos = SListFind(slist, 3);
    if (pos)
    {
        SListErase(&slist, pos);
    }
    SListPrint(slist);
    pos = SListFind(slist, 1);
    if (pos)
    {
        SListEraseAfter(pos);
    }
    SListPrint(slist);
}

int main()
{
    /*TestSList1();
    TestSList2();
    TestSList3();
    TestSList4();
    TestSList5();
    TestSList6();*/
    TestSList7();
    return 0;
}
标签： 数据结构 链表 c语言
本文转载自: https://blog.csdn.net/weixin_60718941/article/details/123738166
版权归原作者 Fan~Fan 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构&ldquo;入门&rdquo;&mdash;单链表（C语言实现）”的评论:

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

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航