0
0

[ 数据结构_C实现 ] 无头单向非循环链表的简单实现(单链表)

1. 链表

1.1 链表的概念及结构

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

个人理解为：链表有两种结构，为逻辑结构和物理结构。

逻辑结构：链表是链式结构在逻辑上是连续的，它们之间用指针连接起来，上一个节点的next存储下一个节点的地址，一次类推，最后一个节点的next指向NULL。我们可以类比为一列火车(如图1-1)，依次链接起来的(如图1-2)。

物理结构：链式结构在逻辑上连续但是在物理结构上不一定连续，也就是说这些结点在内存中不一定是连续存储的。两次申请的空间可能连续可能不连续。

注意：现实中的节点一般都是从堆上申请出来的，从堆上申请的空间，是按照一定的策略分配的，两次申请的空间可能连续可能不连续（如图1-3）。

1.2链表的分类

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

1、单向或者双向

2、带头或者不带头

3、循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构:无头单向非循环链表(本篇文章所实现）和带头双循环链表。

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

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

1.3接口

//不会改变链表的头指针，传一级指针
//打印
void SListPrint(SLTNode* plist);

//可能会改变链表的头指针，传二级指针
//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x);
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);
//头删
void SListPopFront(SLTNode** pplist);
//尾删
void SListPopBack(SLTNode** pplist);

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

//在pos位置之前插入
void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos);

//删除pos后面的值
void SListEraseAfter(SLTNode** pplist, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pplist);

本篇文章我们将实现以上这些接口。

2. 接口实现

2.1 节点的创建

struct SListNode
{
    SLTDataType data;
    struct SListNode* next; //指向下一个指针(结构体类型)
};

data表示该节点的值，next表示指向下一个指针(仍然是结构体类型，是一个结构体指针)。

2.2 打印链表

void SListPrint(SLTNode* plist);

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

2.3 创建新节点

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

新节点包括数据data，next我们默认置NULL

2.4 尾插

void SListPushBack(SLTNode** pplist, SLTDataType x);

void SListPushBack(SLTNode** pplist, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    //找尾节点的指针
    //*pplist = plist
    if (*pplist == NULL)
    {
        *pplist = newnode; //形参的改变不会影响实参
    }
    else
    {
        //找尾
        SLTNode* tail = *pplist;//tail是局部变量
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        //尾节点链接新节点
        tail->next = newnode;
    }
}

尾插的核心是寻找尾结点，寻找的关键要点是尾结点的next指针指向空，因为我们只需要判断尾指针的下一个指针是否为空则可以找到尾。

注意：

我们学过函数知道，形参的改变不影响实参，要改变实参就要传地址，用指针接收，因此我们改变的是结构体指针的地址，我们需要二级指针来接收。

2.5 头插

//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);

void SListPushFront(SLTNode** pplist, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pplist;
    *pplist = newnode; //形参的改变不会影响实参
}

头插相对来说比较简单。得到新节点后，让新节点的next指向头结点，头结点再被改为newnode即可。

2.6 尾删

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

//尾删
void SListPopBack(SLTNode** pplist)
{
    assert(pplist);

    //1.空
    if (*pplist == NULL)
    {
        return;
    }
    //2.一个结点
    else if ((*pplist)->next == NULL)
    {
        free(*pplist);
        *pplist = NULL;
    }
    else
    {
        //3.多个结点
        SLTNode* prev = NULL;
        SLTNode* tail = *pplist;
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;

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

尾删需要考虑链表的节点个数，分为空链表，一个节点，多个几点这三类。

1、如果为空链表，直接return。

2、如果有一个节点，我们直接讲这个节点free释放，再将头结点置空即可。

3、如果有多个节点，我们首先还是要找尾，但是这次我们不仅要找尾，还要找尾结点的上一个节点，因此我们可以有两种方法来解决

第一种方法：

创建两个临时结构体指针，一个找尾，一个找尾的上一个节点，找到后只需要free掉尾结点，再将上一个节点的next指位NULL

第二种方法：

只需创建一个临时结构体指针，我们通过next的next找尾，next找尾的上一个节点，也可实现尾删。

2.7 头删

void SListPopFront(SLTNode** pplist);

void SListPopFront(SLTNode** pplist)
{
    assert(pplist);
    //1.空
    if (*pplist == NULL)
    {
        return;
    }
    //2.非空  单节点与多节点可合并
    else
    {
        SLTNode* head = (*pplist)->next;
        free(*pplist);
        *pplist = head;
    }
}

头删也要分为两种情况，链表为空和非空

1、链表为空，直接return。

2、链表不为空，我们找到第二个节点，释放掉第一个节点，再将第二个节点的地址给头结点即可。

2.8 查找

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

查找是比较简单的，只需要注意的是，查找返回的是具体数值的地址，若为空，则返回NULL。

2.9 在pos位置之前插入

void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x);

//在pos位置之前插入
void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
    assert(pplist);
    assert(pos);
    //1.头插 pos是第一个节点
    if (pos == *pplist)
    {
        SListPushFront(pplist, x);
    }
    //2. pos不是第一个节点
    else
    {
        SLTNode* prev = *pplist;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        SLTNode* newnode = BuySListNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

在写之前一定要判断该链表和该位置是否为空，如果都不存在链表和该位置，插值也是无稽之谈。

这是我们也要分为pos位第一个位置和pos不是第一个位置两种情况：

1、如果pos在第一个位置，相当于头插的作用，我们只需要调用头插接口即可。

2、如果pos不在第一个位置，我们先找到pos位置的上一个节点prev，prev的next保存newnode的地址，newnode的next保存pos位置的地址即可。

2.10 在pos位置之后插入

void SListInsertAfter(SLTNode* pos, SLTDataType x);

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    //存一份pos下一位的地址
    SLTNode* next = pos->next;
    SLTNode* newnode = BuySListNode(x);
    pos->next = newnode;
    newnode->next = next;
}

首先仍然需要对pos位置进行断言

接下来这一步非常关键，我们必须要创建一个next指针来保存pos的next指针的地址，因为只有pos位置才能访问到pos的next指针，创建newnode后，只需要将pos的next保存newnode的地址，再让newnode的next保存刚刚创建的next的指针的地址即可。

2.11 删除pos位置

void SListErase(SLTNode** pplist, SLTNode* pos);

//删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos)
{
    assert(pplist);
    assert(pos);
    //1.pos是第一个 相当于头删
    if (*pplist == pos)
    {
        SListPopFront(pplist);
    }
    //2.
    else
    {
        SLTNode* prev = *pplist;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }

}

删除操作一定要对链表进行断言

这里我们依然要分为pos位置是第一个节点和pos位置不是第一个节点两种情况：

1、pos位置是第一个节点，相当于头删，调用头删接口即可

2、pos位置不是第一个节点，我们需要找到pos位置的前一个节点prev，然后将prev的next保存pos的next的地址，再将pos位置free，再置空即可。

2.12 删除pos后面的值

void SListEraseAfter(SLTNode** pplist, SLTNode* pos);

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

这个比较简单，只需要创建临时指针next保存pos的next地址，再让pos的next保存next的next的地址，再释放掉next即可。

3.菜单

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void menu()
{
    printf("************************************\n");
    printf("*****      1.尾插              *****\n");
    printf("*****      2.头插              *****\n");
    printf("*****      3.尾删              *****\n");
    printf("*****      4.头删              *****\n");
    printf("*****      5.查找 x            *****\n");
    printf("*****      6.在pos位置之前插入  *****\n");
    printf("*****      7.在pos位置之后插入  *****\n");
    printf("*****      8.删除pos位置的元素  *****\n");
    printf("*****      9.删除pos之后的元素  *****\n");
    printf("*****     10.打印单链表         *****\n");
    printf("*****     -1.退出              *****\n");
    printf("************************************\n");
}

int main()
{
    SLTNode* plist = NULL;
    int option = -1;
    menu();
    do
    {
        printf("请输入选项:> ");
        scanf("%d", &option);
        if (option == 1)
        {
            int x = 0;
            printf("请输入你要尾插的数字:>");
            scanf("%d", &x);
            SListPushBack(&plist, x);
        }
        else if (option == 2)
        {
            int x = 0;
            printf("请输入你要头插的数字:>");
            scanf("%d", &x);
            SListPushFront(&plist, x);
        }
        else if (option == 3)
        {
            SListPopBack(&plist);
        }
        else if (option == 4)
        {
            SListPopFront(&plist);
        }
        else if (option == 5)
        {
            int x = 0;
            printf("请输入你要查找的值x:>");
            scanf("%d", &x);
            SLTNode* cur = SListFind(plist, x);
            if (cur != NULL)
            {
                printf("存在数字%d\n",x);
            }
            else
            {
                printf("未找到数字%d", x);
            }
        }
        else if (option == 6)
        {
            int x = 0;
            int y = 0;
            printf("请分别输入pos值x和pos前所插入的值y:>");
            scanf("%d %d", &x,&y);
            SLTNode* pos = SListFind(plist, x);
            if (pos != NULL)
            {
                SListInsertBefore(&plist, pos, y);
            }
            else
            {
                printf("该链表不存在%d\n",x);
            }

        }
        else if (option == 7)
        {
            int x = 0;
            int y = 0;
            printf("请分别输入pos值x和pos后所插入的值y:>");
            scanf("%d %d", &x, &y);
            SLTNode* pos = SListFind(plist, x);
            if (pos != NULL)
            {
                SListInsertAfter(pos, y);
            }
            else
            {
                printf("该链表不存在%d\n",x);
            }

        }
        else if (option == 8)
        {
            int x = 0;
            printf("请输入要删除pos位置的值:>");
            scanf("%d", &x);
            SLTNode* pos = SListFind(plist, x);
            SListErase(&plist, pos);
        }
        else if (option == 9)
        {
            int x = 0;
            printf("请输入要删除pos位置之后的值:>");
            scanf("%d", &x);
            SLTNode* pos = SListFind(plist, x);
            SListEraseAfter(&plist, pos);
        }
        else if (option == 10)
        {
            SListPrint(plist);
        }
    } while (option != -1);
    SListDestroy(&plist);
    return 0;
}

完整代码在我的Gitte：2022_03_10 链表/2022_03_10 链表 · 李兴宇/数据结构 - 码云 - 开源中国 (gitee.com)

（本篇完）

标签： 数据结构 c语言 链表
本文转载自: https://blog.csdn.net/qq_58325487/article/details/123495494
版权归原作者 小白又菜 所有， 如有侵权，请联系我们删除。
登录后发布评论

“[ 数据结构_C实现 ] 无头单向非循环链表的简单实现(单链表)”的评论:

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

单元测试、功能测试、验收测试和集成测试有什么区别？ [关闭]

【C#】Visual Studio代码格式化方法

cri-dockerd 安装和配置指南

学习笔记--VSC++DX UI的创建管理

Spark 广播变量（Broadcast Variable）原理及源码分析

Vue开发者工具扩展（Edge安装）

构建现代化 CMDB 前端平台

文章导航