0
0

[数据结构]单链表(从0-＞1)

前言

*********************************************************作者：小蜗牛向前冲*

****************************名言：我可以接收失败，但我不能接收放弃

如果觉的博主的文章还不错的话，还。请************************************************************************************************************************点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

在前面我们学习了，顺序表(一个连续存储的物理单元，是用数组实现)实现了对数据的增删查改，我们本期将来学习单链表（也实现对数据的增删查改），既然都是对数据增删查改，为什么我们不用顺序表而要弄出个个单链表呢？这就不得不提顺序表的缺陷。

一 顺序表的不足之处

对于顺序表的不足，我们主要从时间复杂度和内存的浪费上考虑。

  1. 中间/头部的插入删除，时间复杂度为O(N)

  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

二 链表

概念：

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

** 1 链表的分类**

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向或者双向

带头或者不带头

** 循环或者非循环**

1.** 无头单向非循环链表：结构简单，一般不会单独用来存数据**。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

  1. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

下面我们主要研究无头单向非循环链表。

2 单链表

单链表结构简单，但是又是非常重要的，从图中我们可以看出。

1 从逻辑是单链表是连续的，但是在物理层面是非连续的

2 链表的节点，一般都是从堆区申请的

为了更好的理解单链表，我们将他的功能一一实现。

三 单链表的实现

1 创建三个文件

1 SList.h

在该文件中我们完成，单表的类型定义，接口函数的声明，引用的头文件。

2 SList.c

完成单链表表接口函数的实现

3 Test.c

主函数，测试顺序表各接口的功能

2 SList.h

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

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

typedef int SLTDataType;//定义节点中数据类型

typedef struct SListNode
{
    SLTDataType data;//指向节点中的数据
    struct SListNode* next;//指向下个节点的指针
}SListNode;//注意这里重命名不能在结构体中中生效

//打印单链表
void SListPrint(SListNode* phead);
//申请新节点
SListNode* BuySLTNode(SLTDataType x);
//单链表销毁
void SListDestory(SListNode** pphead);
//单链表头插
void SListPushFort(SListNode** pphead, SLTDataType x);
//单链表头删
void SListPopFort(SListNode** pphead);
//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//单链表尾删除
void SListPopBack(SListNode** pphead);
//单链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
//在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//在pos后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);

这里和顺序表一样就是要定义函数实现单链表的功能。

这里我们重点关注，结构体的定义

typedef int SLTDataType;//定义节点中数据类型

typedef struct SListNode
{
    SLTDataType data;//指向节点中的数据
    struct SListNode* next;//指向下个节点的指针
}SListNode;//注意这里重命名不能在结构体中中生效

一个节点中主要包括存储的数据和**指向下个节点的指针 **

3 SList.c

#define  _CRT_SECURE_NO_WARNINGS

#include"SList.h"

//打印单链表
void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;//保存单链表头的地址
    while (cur)
    {
        printf("%d->", cur->data);//打印链表数据
        cur = cur->next;//保存指向下个节点的地址
    }
    printf("NULL\n");//链表最后指向空
}

//申请新节点
SListNode* BuySLTNode(SLTDataType x)
{
    SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//为新节点的数据申请空间
    if (NewNode==NULL)
    {
        perror("malloc fail");//申请失败报错
        exit(-1);
    }
    NewNode->data = x;//将为新节点插入数据
    NewNode->next = NULL;//将节点指向下个位置的地址置空
    return NewNode;
}

//链表销毁
void SListDestory(SListNode** pphead)
{
    assert(pphead);//断言(plist地址肯定不为空)
    SListNode* cur = *pphead;//保存好链表头的地址
    while (cur)
    {
        SListNode* next = cur->next;//将指向一个链的地址记录下来
        free(cur);//释放头的空间
        cur = next;//指向一个链
    }
    *pphead = NULL;//销毁完毕，单链表内容为空
}

//单链表头插
void SListPushFort(SListNode** pphead,SLTDataType x)
{
    assert(pphead);//断言(plist地址肯定不为空)
    SListNode* NewNode = BuySLTNode(x);//申请一个节点
    NewNode->next = *pphead;
    *pphead = NewNode;
}

//单链表头删
void SListPopFort(SListNode** pphead)
{
    assert(pphead);//断言(plist地址肯定不为空)
    //温柔的检测
    if (*pphead == NULL)//链表为空就不删除
    {
        return;
    }
    //暴力检测
    //assert(*pphead!=NULL);
    SListNode* del = *pphead;//将要删除地址给del
    *pphead = (*pphead)->next;//plist指向下个链表的头
    free(del);//释放要删除的空间
    del = NULL;
}

//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
    assert(pphead);//断言
    SListNode* NewNode = BuySLTNode(x);//申请一个节点
    //1链表为空
    //2联邦不为空
    if (*pphead == NULL)
    {
        *pphead = NewNode;
    }
    else
    {
        SListNode* tail = *pphead;//记录链表头的地址
        //找尾
        while (tail->next != NULL)
        {
            tail = tail->next;//不断的指向下个链
        }
        tail->next = NewNode;//尾插入数据
    }
}

//单链表尾删除
void SListPopBack(SListNode** pphead)
{
    assert(pphead);//断言(plist地址肯定不为空)
//温柔的检测
    if (*pphead == NULL)//链表为空就不删除
    {
        return;
    }
    if ((*pphead)->next == NULL)//一个节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else//多个节点
    {
        SListNode* tail = *pphead;//记录链表头的地址
        SListNode* prev = NULL;//置空

        //找尾
        while (tail->next != NULL)
        {
            prev = tail;//保存上个节点的地址
            tail = tail->next;//不断的指向下个节点
        }
        prev->next = NULL;//将上个节点的位置置空
        free(tail);//释放
        tail = NULL;
    }
}

//单链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
    SListNode* cur = phead;//标记头节点
    //遍历链表
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;//找到返回标记点
        }
        cur = cur->next;
    }
    return NULL;//没找到返回NULL
}

//在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
    assert(pphead);//断言
    assert(pos);
    if (pos == *pphead)//第一个节点就是pos
    {
        SListPushFort(pphead, x);//直接头插
    }
    else//第一个节点不为pos
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;//不断指向下个节点
            // 暴力检查，pos不在链表中.prev为空，还没有找到pos，说明pos传错了
            assert(prev);
        }
        SListNode* NewNode = BuySLTNode(x);//申请新的节点
        prev->next = NewNode;//上个节点的next指向新节点
        NewNode->next = pos;//新节点指向pos;
    }
}

//在pos后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
    assert(pos);//断言
    //直接插入就行了
    SListNode* NewNode = BuySLTNode(x);//申请新的节点
    NewNode->next = pos->next;//指向pos后的节点
    pos->next = NewNode;//节点pos指向新节点
}

在这里我们主要完成对单链表增删查改函数接口的实现。

我们考虑到要观察储存在单链表中的数据，所以我们首先要实现一个打印单链表的函数。

打印单链表

//打印单链表
void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;//保存单链表头的地址
    while (cur)
    {
        printf("%d->", cur->data);//打印链表数据
        cur = cur->next;//保存指向下个节点的地址
    }
    printf("NULL\n");//链表最后指向空
}

这里我们只要不断的通过cur找到的节点下个数据即可，还要注意中单链表打印完毕后，不要忘记在最后一行打印NULL表示链表到此为止。

在实现单链表的其他功能的前提是我们需要有一个节点。

申请节点

//申请新节点
SListNode* BuySLTNode(SLTDataType x)
{
    SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//为新节点的数据申请空间
    if (NewNode==NULL)
    {
        perror("malloc fail");//申请失败报错
        exit(-1);
    }
    NewNode->data = x;//将为新节点插入数据
    NewNode->next = NULL;//将节点指向下个位置的地址置空
    return NewNode;
}

在这个节点中就一个数据和一个空指针。

有时候当我们不要这个单链表时，我们可以写函数接口来销毁他。

链表销毁

//链表销毁
void SListDestory(SListNode** pphead)
{
    assert(pphead);//断言(plist地址肯定不为空)
    SListNode* cur = *pphead;//保存好链表头的地址
    while (cur)
    {
        SListNode* next = cur->next;//将指向一个链的地址记录下来
        free(cur);//释放头的空间
        cur = next;//指向一个链
    }
    *pphead = NULL;//销毁完毕，单链表内容为空
}

在这里我们只要注意通过free不断释放节点申请的空间即可，顺便提一句，当我们要修改一级指针的值，通常我们要用到二级指针。在测试中我们给SListDestory传的是&plist(plist是一个一级指针)，所以要用二级指针来接收。

下面我们来实现一个简单的头插

单链表的头插

//单链表头插
void SListPushFort(SListNode** pphead,SLTDataType x)
{
    assert(pphead);//断言(plist地址肯定不为空)
    SListNode* NewNode = BuySLTNode(x);//申请一个节点
    NewNode->next = *pphead;
    *pphead = NewNode;
}

这里我们注意节点之间的链接。

有了头插我们中来个头删除吧。

单链表的头删除

//单链表头删
void SListPopFort(SListNode** pphead)
{
    assert(pphead);//断言(plist地址肯定不为空)
    //温柔的检测
    if (*pphead == NULL)//链表为空就不删除
    {
        return;
    }
    //暴力检测
    //assert(*pphead!=NULL);
    SListNode* del = *pphead;//将要删除地址给del
    *pphead = (*pphead)->next;//plist指向下个链表的头
    free(del);//释放要删除的空间
    del = NULL;
}

这里我们要判断链表是否为空，为空就不删除，不为空直接释放头节点就可以，但这里我们注意重新指向下个节点。

写道这里我们还没有测试我们之前写的功能，下面我们测试一下。

** 测试很重要(不要全部写完在来测试)**

单链表的尾插

//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
    assert(pphead);//断言
    SListNode* NewNode = BuySLTNode(x);//申请一个节点
    //1链表为空
    //2联邦不为空
    if (*pphead == NULL)
    {
        *pphead = NewNode;
    }
    else
    {
        SListNode* tail = *pphead;//记录链表头的地址
        //找尾
        while (tail->next != NULL)
        {
            tail = tail->next;//不断的指向下个链
        }
        tail->next = NewNode;//尾插入数据
    }
}

对于单链表的尾插，我们要分为二种情况：

1 链表为空

为空的直接把新节点赋值给*pphead（plist）即可

2 链表不为空

首先我们要找链表的尾，其次才是插入数据

单链表的尾删

/单链表尾删除
void SListPopBack(SListNode** pphead)
{
    assert(pphead);//断言(plist地址肯定不为空)
//温柔的检测
    if (*pphead == NULL)//链表为空就不删除
    {
        return;
    }
    if ((*pphead)->next == NULL)//一个节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else//多个节点
    {
        SListNode* tail = *pphead;//记录链表头的地址
        SListNode* prev = NULL;//置空

        //找尾
        while (tail->next != NULL)
        {
            prev = tail;//保存上个节点的地址
            tail = tail->next;//不断的指向下个节点
        }
        prev->next = NULL;//将上个节点的位置置空
        free(tail);//释放
        tail = NULL;
    }
}

单链表的尾删的话条件更加复杂一点，我们要考虑链表为空就不删除，链表中为一个节点(不要尾)和链表中多个节点(要找尾)。

下面我们继续测试函数的功能

有了增删，那么我们还要写查和改。

单链表查找

//单链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
    SListNode* cur = phead;//标记头节点
    //遍历链表
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;//找到返回标记点
        }
        cur = cur->next;
    }
    return NULL;//没找到返回NULL
}

单链表的查的话主要是，遍历链表，找我们查找数据，返回指向该数据的指针就可。

其实查找的功能主要是方便我们能找道pos的地址从而实现对他的前插和后插。

在pos之前插入

//在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
    assert(pphead);//断言
    assert(pos);
    if (pos == *pphead)//第一个节点就是pos
    {
        SListPushFort(pphead, x);//直接头插
    }
    else//第一个节点不为pos
    {
        SListNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;//不断指向下个节点
            // 暴力检查，pos不在链表中.prev为空，还没有找到pos，说明pos传错了
            assert(prev);
        }
        SListNode* NewNode = BuySLTNode(x);//申请新的节点
        prev->next = NewNode;//上个节点的next指向新节点
        NewNode->next = pos;//新节点指向pos;
    }
}

在对pos之前插入我们要考虑许多，首先pos是不能为空的，其实当第一个节点就是pos时,我们直接头插入就可以了，最后当第一个节点不为pos时，就要在判断链表中是pos是否存在。

在pos后插入

//在pos后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
    assert(pos);//断言
    //直接插入就行了
    SListNode* NewNode = BuySLTNode(x);//申请新的节点
    NewNode->next = pos->next;//指向pos后的节点
    pos->next = NewNode;//节点pos指向新节点
}

对于pos后插就简单了，我们直接插入就好。

继续测试

对于修改pos值就不多说了，我们有pos的指针直接改就是了。

单链表就基本功能就都实现了，大家一定要动手多多尝试。

标签： 数据结构
本文转载自: https://blog.csdn.net/qq_61552595/article/details/126417370
版权归原作者 小蜗牛~向前冲 所有， 如有侵权，请联系我们删除。
登录后发布评论

“[数据结构]单链表(从0-＞1)”的评论:

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

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

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

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

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

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

git-- github的使用

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

文章导航