0
0

C——单链表

一.前言

我们在前面已经了解了链表中的双向链表，而我们在介绍链表分类的时候就说过常用的链表只有两种——双向带头循环链表和单向不带头不循环链表。下来我来介绍另一种常用的链表——单向不带头不循环链表也叫做单链表。不清楚链表分类的以及不了解双向链表的可以看我之前的博客C——双向链表-CSDN博客。

二.单链表的结构

我们已经了解了单链表的全称叫做单向不带头不循环链表，我们怎么理解这链表前面的修饰词呢？其实，单链表就像是一节节连接起来的火车车厢一样。但是这节车厢只可以向后走，并且火车的车头和车尾是不能连接在一起的。

我们照着这张图再来分析单链表的结构：单向的意思就是只能沿着D->A->C->E->Z->X->W这个方向走，那不带头的意思就是没有头节点即哨兵位，我们在讲双向链表的时候提到了哨兵位，他只是一个没有有效数据的头节点。不循环的意思我们也可以对照这双向链表来看，双向链表的尾节点可以找到头节点，头节点也可以找到尾节点，这就是循环；而单链表的尾节点指向的不是头节点而是NULL，头节点也不能找到尾节点。

那么单链表的节点到底是什么样的呢？

我们再来与双向链表的节点进行对比一下：

单链表节点只有两个成员，分别是数据和指向下一个节点的指针，而双向链表的节点有三个成员，分别是数据，指向前一个节点的指针和指向下一个节点的指针。

综上所述：单链表是一个只能指向下一个节点的链表，而且没有头节点，并且是不循环的。

三.实现单链表

与双向链表的实现相似，实现单链表也需要很多的函数及头文件，所以我们将所有的函数声明和头文件都放到singlelist.h中，函数的实现都放入singlelist.c中。

3.1单链表节点的结构

//链表节点
struct SingleList
{
    int val;
    struct SingleList* next;
};

我们这样写虽然可以完成链表的基本结构，但是难道我们链表只能存储整形嘛？如果我们创建了很多个整型节点，但是有一天我们想利用链表存储字符型或者浮点型数据，那么我们就得一个一个的去修改，费时费力；还有就是这个节点的名称很长，在后面的代码中会重复出现，也很浪费时间。所以我们可以利用typedef关键词，对节点重命名，以及对int重命名。

//节点数据类型
typedef int SingleListdatatype;

//链表节点
typedef struct SingleListNode
{
    SingleListdatatype val;
    struct SingleListNode* next;
}SLNode;

这样我们在多次使用该类型的时候就不需要再写那么长一串了，以后再修改储存的数据类型的时候也就不用一个一个节点的修改了，只需将定义的节点数据类型中的数据类型修改即可。

3.2单链表节点的创建

我们在创建节点的时候实际上就是创建一个结构体变量，我们可以利用动态内存管理为我们的每一个节点动态开辟一块内存空间。

//节点的创建
SLNode* BuyNode(SingleListdatatype x)
{
    SLNode* node = (SLNode*)malloc(sizeof(SLNode));
    if (node == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    node->val = x;
    node->next = NULL;
    return node;
}

我们来测试一下节点创建函数是否正确：

我们利用此测试代码来调试发现，我们创建了4个节点，通过调试也确实观察到了这四个节点，并且它们储蓄的数据就是我们传的数据，指向下一个节点的指针也是NULL。与我们想要实现的结果相同。

那我们现在将这四个节点连接起来：

void test1()
{
    SLNode* plist = NULL;
    SLNode* plist1 = BuyNode(1);
    SLNode* plist2 = BuyNode(2);
    SLNode* plist3 = BuyNode(3);
    SLNode* plist4 = BuyNode(4);

    plist1->next = plist2;
    plist2->next = plist3;
    plist3->next = plist4;
}

int main()
{
    test1();
    return 0;
}

我们再来调试一下：

我们看到将所有节点连接起来之后，我们就可以利用第一个节点找到后面的节点。

3.3链表的打印

//链表的打印
void SLNodePrint(SLNode* plist)
{
    while (plist)//plist != NULL
    {
        printf("%d->", plist->val);
        plist = plist->next;
    }
    printf("NULL\n");
}

我们再来测试一下该函数：

也是没有出现问题，说明我们链表的打印已经完成了。

3.4尾插

我们现在创建的节点需要我们手动将其连接起来，我们可以利用尾插方法，将新创建的节点直接连接到前一个节点上。 

//尾插
void SLNodepushback(SLNode** plist, SingleListdatatype x)
{
    assert(plist);

    SLNode* newnode = BuyNode(x);//新节点

    if (*plist == NULL)
    {
        //空链表
        *plist = newnode;
    }
    else
    {
        //非空链表
        //遍历原链表，找到尾节点
        SLNode* pcur = *plist;
        while (pcur->next)//(*plist)->next != NULL
        {
            pcur = pcur->next;
        }
        pcur->next = newnode;
    }
}

我们测试下尾插方法：

我们尾插了四次，通过打印方法，将链表打印出来，说明我们的尾插方法也没有问题。但是有些人可能会有疑问：为什么这里传的是二级指针 而不传一级指针？

因为我们是通过一个结构体类型的指针来维护我们的链表，而我们传一级指针的话相当于值传递，而对于值传递来说，形参改变是不影响实参的。简单来说，就说你在函数内部将形参节点的next指针改变了，但是却不影响实参的值。达不到我们的目的。所以要想形参的改变影响实参的话，我们就得地址传递，就得传一级指针的地址，也就是二级指针

3.5头插

头插从名字就可以听出来是把一个新节点插到链表的头部，我们利用图来分析如何进行头插：

//头插
void SLpushfront(SLNode** plist, SingleListdatatype x)
{
    assert(plist);

    SLNode* newnode = BuyNode(x);
    newnode->next = *plist;
    *plist = newnode;
}

我们测试头插方法：

根据打印结果来看，头插的方法也没有任何问题。

3.6尾删

尾删就是删除链表中的尾节点，那么前提就是该链表不能为空，如果都是空链表了，怎么执行删除操作呢？我们画图来分析一下：

//尾删
void SLpopback(SLNode** plist)
{
    assert(plist && *plist);//*plist != NULL防止链表为空

    SLNode* pcur = *plist;//记录倒数第二个节点
    SLNode* del = *plist;//记录尾节点
    while (del->next)
    {
        pcur = del;
        del = del->next;
    }
    pcur->next = NULL;
    free(del);
    del = NULL;
}

我们测试之后发现出了错误，这是为什么呢？

我们进行四次尾删，最后一次删除会将1删除掉，此时应该只打印NULL，这里打印了随机值。这是为什么呢？ 

//尾删
void SLpopback(SLNode** plist)
{
    assert(plist && *plist);//*plist != NULL防止链表为空

    if (!((*plist)->next))//(*plist)->next == NULL
    {
        //链表只有一个节点
        free(*plist);
        *plist = NULL;
    }
    else
    {
        //链表有多个节点
        SLNode* pcur = *plist;//记录倒数第二个节点
        SLNode* del = *plist;//记录尾节点
        while (del->next)
        {
            pcur = del;
            del = del->next;
        }
        pcur->next = NULL;
        free(del);
        del = NULL;
    }
}

我们现在再来测试一下修改后的尾删代码：

我们看到，现在就没有问题了。

3.7头删

我们实现了尾删，现在来实现头删。头删的前提与尾删的前提相同：链表不能为空。头删实际上就是删除链表中的第一个节点，我们画图分析如何实现头删：

//头删
void SLpopfront(SLNode** plist)
{
    assert(plist && *plist);//链表不能为空

    SLNode* next = (*plist)->next;
    free(*plist);
    *plist = next;
}

我们来测试头删方法：

没有问题~

那如果我们多删一次呢？

我们看到，第五次删除的时候这时候已经是空链表了，我们再看提示的错误信息，说是断言出错了，这就说明了链表为空了。

3.8查找数据

查找数据非常简单，我们只需要遍历链表，将要查找的数据与链表中的数据进行对比，如果找到了则返回该数据对应节点的地址；如果没找到则返回NULL。

//查找
SLNode* SLFind(SLNode* plist, SingleListdatatype x)
{
    assert(plist);

    SLNode* pcur = plist;
    while (pcur)
    {
        if (pcur->val == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

测试查找：

结果没毛病，老铁OK了！

3.9在指定位置之前插入数据

我们要在指定位置的前面插入数据，所以我们必须得找到该指定位置，这就需要调用我们的查找方法了。我们来画图分析一下：

//在指定位置之前插入数据
void SLposfront(SLNode** plist, SLNode* pos, SingleListdatatype x)
{
    assert(plist && *plist);//链表不能为空，否则找不到指定位置

    if (pos == *plist)
    {
        //pos节点就是第一个节点
        //调用头插方法
        SLpushfront(plist,x);
    }
    else
    {
        //pos节点不是第一个节点
        SLNode* newnode = BuyNode(x);
        SLNode* pcur = *plist;
        SLNode* prev = *plist;
        while (pcur)
        {
            if (pcur->val == pos->val)
            {
                break;
            }
            prev = pcur;
            pcur = pcur->next;
        }
        // prev newnode pcur/pos
        prev->next = newnode;
        newnode->next = pcur;
    }
}

我们测试该代码：

我们测试了三种位置的插入，无论是第一个节点之前还是中间节点之前或者是尾节点之前都没有问题。

3.10在指定位置之后插入数据

在指定位置之后插入数据与在指定位置之前插入数据有相同点但也有不同点，我们继续来画图分析：

//在指定位置之后插入数据
void SLposback(SLNode* pos, SingleListdatatype x)
{
    assert(pos);
    SLNode* newnode = BuyNode(x);
    //pos newnode pos->next
    newnode->next = pos->next;
    pos->next = newnode;
}

我们对其进行测试来看：

3.11删除pos节点

我们现在来删除指定节点，前提肯定是链表不能为空。我们接着来画图分析：

//删除pos节点
void slpoppos(SLNode** plist, SLNode* pos)
{
    assert(plist && *plist);
    assert(pos);

    if (*plist == pos)
    {
        //pos是头节点，调用头删方法
        SLpopfront(plist);
    }
    else
    {
        SLNode* prev = *plist;
        while (prev->next != pos)
        {
            //找到pos的前一个节点
            prev = prev->next;
        }
        //prev pos pos->next
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

测试该代码： 老铁没毛病！

3.12删除pos节点之后的节点

删除pos节点之后的节点我们要改变指向的指针就只有一个了，那就是pos->next指针。要让它指向pos->next->next。我们画图分析：

//删除pos节点后一个节点
void slpopposback(SLNode* pos)
{
    assert(pos && pos->next);//pos->next != NULL避免pos是尾节点

    SLNode* Next = pos->next;
    pos->next = pos->next->next;
    free(Next);
    Next = NULL;
}

测试代码：

那如果我们的pos节点就是尾节点程序会发生什么呢？

我们看到，上面提醒我们断言出错，说明此时pos节点为尾节点。

3.13销毁链表

//销毁链表
void DestorySL(SLNode** plist)
{
    assert(plist && *plist);
    SLNode* Next = (*plist)->next;
    while (Next)
    {
        free(*plist);
        *plist = Next;
        Next = Next->next;
    }
    free(*plist);
    *plist = NULL;
}

我们通过调试来判断我们的销毁方法:没有问题！

到这里，我们单链表的所有方法都已经完成了。下面附上完整代码：

四.完整代码

1.singlelist.h

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

//节点数据类型
typedef int SingleListdatatype;

//链表节点
typedef struct SingleListNode
{
    SingleListdatatype val;
    struct SingleListNode* next;
}SLNode;

//节点的创建
SLNode* BuyNode(SingleListdatatype x);

//链表的打印
void SLNodePrint(SLNode* plist);

//尾插
void SLNodepushback(SLNode** plist, SingleListdatatype x);

//头插
void SLpushfront(SLNode** plist, SingleListdatatype x);

//尾删
void SLpopback(SLNode** plist);

//头删
void SLpopfront(SLNode** plist);

//查找
SLNode* SLFind(SLNode* plist, SingleListdatatype x);

//在指定位置之前插入数据
void SLposfront(SLNode** plist, SLNode* pos,SingleListdatatype x);

//在指定位置之后插入数据
void SLposback(SLNode* pos, SingleListdatatype x);

//删除pos节点
void slpoppos(SLNode** plist, SLNode* pos);

//删除pos节点后一个节点
void slpopposback(SLNode* pos);

//销毁链表
void DestorySL(SLNode** plist);

2.singlelist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleList.h"

//节点的创建
SLNode* BuyNode(SingleListdatatype x)
{
    SLNode* node = (SLNode*)malloc(sizeof(SLNode));
    if (node == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    node->val = x;
    node->next = NULL;
    return node;
}

//链表的打印
void SLNodePrint(SLNode* plist)
{
    while (plist)//plist != NULL
    {
        printf("%d->", plist->val);
        plist = plist->next;
    }
    printf("NULL\n");
}

//尾插
void SLNodepushback(SLNode** plist, SingleListdatatype x)
{
    assert(plist);

    SLNode* newnode = BuyNode(x);//新节点

    if (*plist == NULL)
    {
        //空链表
        *plist = newnode;
    }
    else
    {
        //非空链表
        //遍历原链表，找到尾节点
        SLNode* pcur = *plist;
        while (pcur->next)//(*plist)->next != NULL
        {
            pcur = pcur->next;
        }
        pcur->next = newnode;
    }
}

//头插
void SLpushfront(SLNode** plist, SingleListdatatype x)
{
    assert(plist);

    SLNode* newnode = BuyNode(x);
    newnode->next = *plist;
    *plist = newnode;
}

//尾删
void SLpopback(SLNode** plist)
{
    assert(plist && *plist);//*plist != NULL防止链表为空

    if (!((*plist)->next))//(*plist)->next == NULL
    {
        //链表只有一个节点
        free(*plist);
        *plist = NULL;
    }
    else
    {
        //链表有多个节点
        SLNode* pcur = *plist;//记录倒数第二个节点
        SLNode* del = *plist;//记录尾节点
        while (del->next)
        {
            pcur = del;
            del = del->next;
        }
        pcur->next = NULL;
        free(del);
        del = NULL;
    }
}

//头删
void SLpopfront(SLNode** plist)
{
    assert(plist && *plist);//链表不能为空

    SLNode* next = (*plist)->next;
    free(*plist);
    *plist = next;
}

//查找
SLNode* SLFind(SLNode* plist, SingleListdatatype x)
{
    assert(plist);

    SLNode* pcur = plist;
    while (pcur)
    {
        if (pcur->val == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

//在指定位置之前插入数据
void SLposfront(SLNode** plist, SLNode* pos, SingleListdatatype x)
{
    assert(plist && *plist);//链表不能为空，否则找不到指定位置
    assert(pos);

    if (pos == *plist)
    {
        //pos节点就是第一个节点
        //调用头插方法
        SLpushfront(plist,x);
    }
    else
    {
        //pos节点不是第一个节点
        SLNode* newnode = BuyNode(x);
        SLNode* pcur = *plist;
        SLNode* prev = *plist;
        while (pcur)
        {
            if (pcur->val == pos->val)
            {
                break;
            }
            prev = pcur;
            pcur = pcur->next;
        }
        // prev newnode pcur/pos
        prev->next = newnode;
        newnode->next = pcur;
    }
}

//在指定位置之后插入数据
void SLposback(SLNode* pos, SingleListdatatype x)
{
    assert(pos);
    SLNode* newnode = BuyNode(x);
    //pos newnode pos->next
    newnode->next = pos->next;
    pos->next = newnode;
}

//删除pos节点
void slpoppos(SLNode** plist, SLNode* pos)
{
    assert(plist && *plist);
    assert(pos);

    if (*plist == pos)
    {
        //pos是头节点，调用头删方法
        SLpopfront(plist);
    }
    else
    {
        SLNode* prev = *plist;
        while (prev->next != pos)
        {
            //找到pos的前一个节点
            prev = prev->next;
        }
        //prev pos pos->next
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

//删除pos节点后一个节点
void slpopposback(SLNode* pos)
{
    assert(pos && pos->next);//pos->next != NULL避免pos是尾节点

    SLNode* Next = pos->next;
    pos->next = pos->next->next;
    free(Next);
    Next = NULL;
}

//销毁链表
void DestorySL(SLNode** plist)
{
    assert(plist && *plist);
    SLNode* Next = (*plist)->next;
    while (Next)
    {
        free(*plist);
        *plist = Next;
        Next = Next->next;
    }
    free(*plist);
    *plist = NULL;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleList.h"

//void test1()
//{
//    SLNode* plist1 = BuyNode(1);
//    SLNode* plist2 = BuyNode(2);
//    SLNode* plist3 = BuyNode(3);
//    SLNode* plist4 = BuyNode(4);
//
//    plist1->next = plist2;
//    plist2->next = plist3;
//    plist3->next = plist4;
//
//    SLNodePrint(plist1);
//}

void test2()
{
    SLNode* plist = NULL;
    //测试尾插
    SLNodepushback(&plist, 1);
    SLNodepushback(&plist, 2);
    SLNodepushback(&plist, 3);
    SLNodepushback(&plist, 4);
    SLNodePrint(plist);

    //测试销毁链表
    DestorySL(&plist);

    //测试删除pos节点的下一个节点
    //SLNode* find = SLFind(plist, 4);
    //slpopposback(find);
    //SLNodePrint(plist);

    //测试删除pos节点
    //SLNode* find = SLFind(plist, 4);
    //slpoppos(&plist,find);
    //SLNodePrint(plist);

    //测试在指定位置之后插入数据
    //SLNode* find = SLFind(plist, 1);
    //SLposback(find,66);
    //SLNodePrint(plist);

    //测试在指定位置之前插入数据
    //SLNode* find = SLFind(plist, 4);
    //SLposfront(&plist,find,100);
    //SLNodePrint(plist);

    //测试查找
    //SLNode* find = SLFind(plist,99);
    //if (find == NULL)
    //{
    //    printf("找不到!");
    //}
    //else
    //{
    //    printf("找到了!");
    //}

    //测试头删
    //SLpopfront(&plist);
    //SLNodePrint(plist);//2 3 4
    //SLpopfront(&plist);
    //SLNodePrint(plist);//3 4
    //SLpopfront(&plist);
    //SLNodePrint(plist);//4
    //SLpopfront(&plist);
    //SLNodePrint(plist);//NULL
    //SLpopfront(&plist);
    //SLNodePrint(plist);

    //测试尾删
    //SLpopback(&plist);
    //SLNodePrint(plist);//1 2 3
    //SLpopback(&plist);
    //SLNodePrint(plist);//1 2
    //SLpopback(&plist);
    //SLNodePrint(plist);//1
    //SLpopback(&plist);
    //SLNodePrint(plist);//NULL

    //测试头插
    //SLpushfront(&plist,100);
    //SLNodePrint(plist);
    //SLpushfront(&plist,99);
    //SLNodePrint(plist);
}

int main()
{
    //test1();
    test2();
    return 0;
}

完！

标签： c语言 开发语言 数据结构
本文转载自: https://blog.csdn.net/xsc2004zyj/article/details/138670837
版权归原作者 用手码出世界 所有， 如有侵权，请联系我们删除。
登录后发布评论

“C——单链表”的评论:

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

java+vue计算机毕设茶叶产品质量安全可追溯系统【源码+程序+论文+开题】

Postman：Postman API测试：Postman数据驱动测试实践

解决：IntelliJ IDEA 项目中代码文件不能运行的问题(即：J 标文件的问题)

Docker：安装 MongoDB 的详细指南

Git - 两种方式撤销已提交到远端仓库的记录并删除提交记录

Kafka 原理

Flink Memory Management原理与代码实例讲解

文章导航