0
0

数据结构—单链表、双向循环链表的实现【C语言】

“要从容地着手去做一件事，但一旦开始，就要坚持到底。”——比阿斯

✏️前言

数据结构—顺序表的实现【C语言】_虾料的博客-CSDN博客https://blog.csdn.net/Che__dan/article/details/125698803?spm=1001.2014.3001.5501

    上一期，咱们已经熟悉了**顺序表的实现**（点击上方**链接**👆）。但它是有**缺点的**，就是**插入**和**删除**需要移动大量的元素，导致这一问题的原因是顺序表具有很强的邻居关系，元素之间没有空隙，无法快速插入元素，而删除元素后，中间就留有空隙，自然要弥补。为了解决这一问题，链表就诞生了。这一期，我们将会掌握各种链表的实现。开始之前，**请先深呼吸，静心食用**🍉。

✏️链表的概念及结构

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

    前面说了，链表可以解决顺序表的缺点，就是让所有的元素都不考虑相邻的位置，只需让每个元素知道它下一个元素的位置在哪里，这样所有的元素都可以通过遍历找到。为了表示每个数据元素**aᵢ**与其直接后续数据元素**aᵢ₊₁**之间的逻辑关系**，**除了储存本身的信息之外还需存储一个指示其 直接后继的信息。储存数据的区域叫**数据域**，存储后继位置的区域叫**指针域**，这两部分信息加起来就叫**结点（如下图）**。
  • 逻辑结构：

     其中**“Data”**用来存储数据元素，而**“Next”**用来存储后一个**“Data”**的地址。最后一个结点的指针域为空。

✏️链表的分类

   链表细分来看的话有以下几种：
  • 单向链表（带头、不带头两种）

  • 双向链表

  • 循坏链表

  • 双向循环链表

    对于头结点，是为了**更加方便地对链表进行操作**而设立的。头结点的数据域可以不存储任何数据（可以存储此链表的名字或长度），就当它是一个标记。

    **ps:**当然双向、循环等链表也分带头和不带头，由于篇幅所限……(好吧，实在是编不下去了，其实我是懒得画图😁，不过带不带头差别不大)。

✏️链表的实现

    虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
  • 无头+单向+非循环链表

  • 带头+双向+循环链表

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

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

📍无头+单向+非循环链表的实现

  • 结构（结点的实现）：

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;//注意不能将struct SListNode*改为SLTNode。

}SLTNode;

   这里的指针**

struct SListNode*

**如何理解呢？就看成next指针被赋予了指向该结构体类型的能力（这里next是指针不是结构体，不是套娃哦）。

需要实现的功能：

（SList.h）

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

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;//注意不能将struct SListNode*改为SLTNode。

}SLTNode;

//创建结点
SLTNode* BuySListNode(SLTDataType x);

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//尾删
void SListPopBack(SLTNode** pphead);
//头删
void SListPopFront(SLTNode** pphead);

//查找（修改）
SLTNode* SListFind(SLTNode* pphead, SLTDataType x);

//pos之后的位置插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//pos之后的位置删除
void SListEraseAfter(SLTNode* pos);

  • 创建结点(初始化结点)

      我们有了结点的类型“

SLTNode

”，接下来就需要生产结点，后面的插入操作就需要调用此函数。

//创建结点
SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}

   **assert的作用**就是判断进入函数的指针是否为空指针，如果是空指针就结束当前程序运行。（此函数的头文件是“assert.h”）

    “assert(x)”  x为真，就能通过。

  • 尾插

      创建一个新结点，链表的最后一个结点连接新结点。


//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode= BuySListNode(x);

    //当外面的头指针为空时
    if (*pphead==NULL)
    {
        *pphead= newnode;
    }
    else
    {
        SLTNode* tail = *pphead;//保证头指针不变，通过tail来寻找最后一个结点的位置；
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

    这里的形参**为什么是双指针**呢？原因：外面没有结点时，头指针赋为空，续而进入函数后，需要改变外面指针的内容，而改变实参要传它地址，然实参为指针，当然就要传二级了（下同）。

  • 头插

e28535dff1f1a712016c0ea1799909f8.jpeg

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

  • 尾删

      **找到**链表的**倒数第二个结点**，并利用这个结点对最后一个结点进行删除。至于**为什么**非要用倒数第二个结点：**不知道倒数第二个结点的位置**情况下**，**如果删除了最后一个结点，那倒数第二个结点指针域怎么置空呢？**（其实加上头结点就会避免这种情况，具体的后面循环链表中可以体现）**


//尾删
void SListPopBack(SLTNode** pphead)
{
    assert(*pphead);
    
    //只有一个结点的情况
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

  • 头删

      不带头结点的链表头删较简单，把头指针向后移，并销毁前一个结点。

//头删
void SListPopFront(SLTNode** pphead)
{
    assert(*pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

  • 查找（修改）

      遍历链表，找到你输入的值，并返回它的位置。

//查找（修改）
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
    SLTNode* cur = pphead;
    while (cur)
    {
        if (cur->data == x)
            return cur;

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

  • pos之后的位置插入

//pos之后的位置插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    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* cur = pos->next;
    pos->next = cur->next;

    free(cur);
    cur = NULL;
}

📍带头+双向+循环链表的实现

  • 结构（结点的实现）

      带头双向循坏链表的每个结点不仅要存储数据和后续结点，**还要储存前继结点**，于是乎就需要**两个指针域（如图）**。


typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
}LTNode;

需要实现的功能：

（List.h）

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
}LTNode;

//创建空间
LTNode* BuyListNode(LTDataType x);
// 创建返回链表的头结点
LTNode* ListInit();

// 双向链表尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(LTNode* phead);

// 双向链表头插
void ListPushFront(LTNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(LTNode* phead);

// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(LTNode* pos);

//打印
void ListPrint(LTNode* phead);
//求链表的长度
int Listsize(LTNode* phead);
//销毁链表
void ListDestory(LTNode* phead);

  • 创建结点(初始化结点)

//创建空间
LTNode* BuyListNode(LTDataType x)
{
    LTNode* node=(LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)//检查空间是否创建成功
    {
        perror("malloc:");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

  • 创建返回链表的头结点

       此链表是有头结点的，咱们需要单独写个函数，但问题是刚开始的时候，**头结点**的**前后指针指向谁呢？其实就指向头结点本身，以便后续的插入。（这里在头指针里存-1）**


// 创建返回链表的头结点.
LTNode* ListInit()
{
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;

    return phead;
}

  • 双向循环链表尾插

       循环链表的**最后一个结点要与头结点相互链接。**

** **下图为头结点后第一个结点的尾插。

58a3757dbb4a5e10c80fa1e444a4d762.jpeg

// 双向循环链表尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;最后一个结点

    tail->next = newnode;
    newnode->prev = tail;
    phead->prev = newnode;
    newnode->next = phead;
}

  • 双向循环链表尾删

       其实找到最后两个结点

27dd427070c9ffc965d70daca9169aa2.jpeg

// 双向循环链表尾删
void ListPopBack(LTNode* phead)
{
    assert(phead->next != phead);//只有头结点的情况就最出程序
    assert(phead);
    LTNode* tail = phead->prev;//最后一个结点
    LTNode* tailPrev = tail->prev;//倒数第二个结点
    free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}

  • 双向循环链表头插

4c3b0304c62ace3dab099f1fbdbfbfd4.jpeg

// 双向循环链表头插
void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* next = phead->next;//头结点后的结点
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;

}
  • ---### 双向循环链表头删

3395c414e69141045abc97fe75378bef.jpeg

// 双向循环链表头删
void ListPopFront(LTNode* phead)
{
    assert("phead");
    assert(phead->next != phead);

    LTNode* cur = phead->next;
    phead->next = cur->next;
    cur->next->prev = phead;
    free(cur);
}

  • 双向循坏链表在pos的前面进行插入

e2f98a1179ff6f34df725a3540bfdeb6.jpeg

// 双向循坏链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x)
{
    assert("pos");
    LTNode* newnode = BuyListNode(x);
    LTNode* cur = pos->prev;//pos前一个结点

    cur->next = newnode;
    newnode->prev = cur;
    newnode->next = pos;
    pos->prev = newnode;

}

  • 双向循环链表删除pos位置的结点

       找到pos的前后结点，相链接，再free掉pos就OK啦！

// 双向循环链表删除pos位置的结点
void ListErase(LTNode* pos)
{
    assert("pos");
    LTNode* prev = pos->prev;//pos前一个结点
    LTNode* next = pos->next;//pos后一个结点

    prev->next = next;
    next->prev = prev;
    free(pos);
}

     **注意：其实“在pos位置的插入、删除”也以用于头插、头删、尾插、尾删，非常万能。**

  • 求链表的长度

       这个遍历一遍就行了，但要**注意循坏结束条件**。

//求链表的长度
int Listsize(LTNode* phead)
{
    assert(phead);
    int size = 0;
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

  • 销毁链表

//销毁链表
void ListDestory(LTNode* phead)
{
    assert(phead);
    int size = 0;
    LTNode* cur = phead->next;
    while (cur != phead)//只剩头结点时结束
    {
        LTNode* next = cur->next;
        ListErase(cur);//删除该结点
        cur = next;
    }
    free(phead);
}

✏️结语

     只要掌握了无头单向链表、带头双向循环链表，在链表这一块就差不多了，所以**点赞收藏吧！**😘
标签： 链表 数据结构 c语言
本文转载自: https://blog.csdn.net/Che__dan/article/details/125921322
版权归原作者 虾料 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构&mdash;单链表、双向循环链表的实现【C语言】”的评论:

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

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

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

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

单元测试数据库回滚问题

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

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

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

文章导航