【数据结构】单链表超详细解析 | 从零开始步步解读 | 画图理解

举报
柠檬叶子C 发表于 2022/04/17 00:08:58 2022/04/17
【摘要】 ​ ​前言：本章节将对链表的概念进行介绍，着重讲解单顺序表。对常用的接口函数进行一个个讲解，并进行解析，单链表表讲解部分将从零实现常见单链表接口函数。我会尽量加快数据结构的更新速度，还希望大家多多三连支持！🔗 C语言教学专栏：《维生素C语言》一、链表介绍0x00 链表的概念​📚 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数组元素的逻辑顺序是通过链表中的指针链接次序实现的。0...

​

 ​


前言：

本章节将对链表的概念进行介绍，着重讲解单顺序表。对常用的接口函数进行一个个讲解，并进行解析，单链表表讲解部分将从零实现常见单链表接口函数。我会尽量加快数据结构的更新速度，还希望大家多多三连支持！

🔗 C语言教学专栏：《维生素C语言》


一、链表介绍

0x00 链表的概念

​

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


0x01 顺序表和链表的优缺点

❓ 为什么线性表和链表各自存在？

💡 因为他们各有优点，他们是互补的，并不是有他没我，有我没他的。


✅ 顺序表的优点：

​

     ① 支持随机访问，有些算法需要结构随机访问，比如二分查找和优化的快排等。

     ② 数据是按顺序存放的，空间利用率高。

     ③ 通过下标直接访问，存取速度高效。

❌ 顺序表的缺陷：

     ① 空间不够了就需要扩容，扩容是存在消耗的。

     ② 头部或者中间位置的插入或删除，需要挪动，挪动数据时也是存在消耗的。

     ③ 避免频繁扩容，一次一般都是按倍数去扩容（2倍适中），可能存在一定空间的浪费现象。


0x02 顺序表的优缺点

✅ 链表的优点：

​

     ① 按需申请空间，不用就释放空间（ 链表可以更合理地使用空间）。

     ② 头部或者中间位置的插入和删除，不需要挪动数据。

     ③ 不存在空间浪费。

❌ 链表的缺陷：

     ① 每一个数据，都要存一个指针去链接后面的数据节点。

     ② 不支持随机访问（用下标直接访问第 i 个），必须得走 O(N) 。

Tips：单链表的缺陷还是很多的，单纯单链表的增删查找的意义不大，但是很多OJ题考察的都是单链表。单链表多用于更复杂的数据结构的子结构，如哈希桶，邻接表等。所以真正存储数据还是得靠双向链表。


0x03 链表的结构

​

① 逻辑结构：便于更形象方便地理解而想象出来的（比如这个箭头其实不存在）。

​

② 物理结构：在内存中是实实在在如何存储。

​


二、单链表的定义

0x00 定义单链表

​

typedef int SLNodeDataType;        // SLNodeDataType == int

typedef struct SingleListNode {
    SLNodeDataType data;           // 用来存放节点的数据 int data
    struct SingleListNode* next;   // 指向后继节点的指针
} SLNode;                          // 重命名为SLNode 便于利用该结构体

🔑 解读：在顺序表章节讲过，为了方便后续使用我们将类型 typedef 一下。首先创建结构体，因为叫单链表，所以我们将它取为 SingleListNode。结构体有两个变量，data 是用来存放节点的数据的变量，而 next 是用来指向后继节点指针的变量。我们详细来说说结构体指针 next，它的类型是 struct SingleListNode* 也就是自己本身，从而实现 "套娃" 的效果，这么一来它就拥有了 "链接" 的资本（既可以存数据，又可以存下一个节点的地址，简直是一直用一直爽啊）。为了方便后续地使用，我们再把这个结构体重命名成 SLNode（非常合理的简写，SingleListNode）。


0x01 接口函数

📚 这是需要实现几个接口函数：

SLNode* CreateNewNode(SLNodeDataType x);
void SListPrint(SLNode* pHead);
void SListPushBack(SLNode** pHead, SLNodeDataType x);
void SListPushFront(SLNode** ppHead, SLNodeDataType x);
void SListPopBack(SLNode** pHead);
void SListPopFront(SLNode** pHead);
SLNode* SListFind(SLNode* pHead, SLNodeDataType x);
void SListInsert(SLNode** ppHead, SLNode* pos, SLNodeDataType x);
//void SListInsert(SLNode* pHead, int pos, SLNodeDataType x);
void SListEarse(SLNode** ppHead, SLNode* pos);
void SListDestroy(SLNode** ppHead);
void SListInsertAfter(SLNode* pos, SLNodeDataType x);
void SListEraseAfter (SLNode* pos);


三、详解接口函数的实现

0x00 打印（SListPrint）

💬 SList.h

#pragma once
#include <stdio.h>

typedef int SLNodeDataType;        // SLNodeDataType == int

typedef struct SingleListNode {
    SLNodeDataType data;           // 用来存放节点的数据 int data
    struct SingleListNode* next;   // 指向后继节点的指针
} SLNode;                          // 重命名为SLNode 便于利用该结构体

void SListPrint(SLNode* pHead);

🔑 解读：用结构体指针 *pHead 接收， 这里 *pHead 就表示头结点，我下面会详细说一下。

💬 SList.c

#include "SList.h"

/* 打印 */
void SListPrint (
    SLNode* pHead //pHead为形参，是pList的一份临时拷贝（取名为pHead方便区分）
    )
{
    SLNode* cur = pHead; //工具人
    while (cur != NULL)  //cursor不为空时进入循环
    {
        printf("%d -> ", cur->data); //打印data中的内容
        cur = cur->next; //令cursor指向后继节点
    }
    printf("NULL\n");
}

🔑 解读：我们想实现单链表的打印，我们就需要遍历整个链表。首先创建一个结构体指针 cur 来存放 pHead ，然后通过 cur 来把整个链表走一遍。只要 cur 不为 NULL，就说明还没有走完，就进入循环，循环体内打印出当前 cur->data 的内容，就实现了打印节点中的内容，随后将 cur 赋值成 cur->next ，使得 cur 指向它后面的节点。当 cur 为 NULL 时说明已经走完了，则跳出循环。最后我们再打印一个 "NULL" 把链表的尾部表示出来（便于调试观看）。


💬 Test.c

这里我们还没写什么东西，就不写测试用例了。 （其实是作者想偷懒 ） 


0x01 尾插（SListPushBack）

💬 SList.h

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

typedef int SLNodeDataType;        // SLNodeDataType == int

typedef struct SingleListNode {
    SLNodeDataType data;           // 用来存放节点的数据 int data
    struct SingleListNode* next;   // 指向后继节点的指针
} SLNode;                          // 重命名为SLNode 便于利用该结构体

void SListPrint(SLNode* pHead);
void SListPushBack(SLNode** pHead, SLNodeDataType x);

🔑 解读：创建一个新节点，我们就需要动态开辟内存，所以我们要引入 #include <stdlib.h> 这个头文件。SListPushBack 函数参数为 SLNode** pHead，这里用 "二级指针" 接收，因为传入的就是一个结构体指针的地址（&pList），它本身就是一个指针了，所以这里我们就需要用指针的指针（即二级指针）来接收它。因为形参是实参的一份临时拷贝。至于这里为什么传入 &pList 呢？因为形参只是实参的一份临时拷贝，为了能够改变外部，所以我们要采用址传递（即传入结构体指针 pList 的地址并用二级指针接收）。


💬 SList.c

/* 尾插 */
void SListPushBack (
    SLNode** ppHead,  //头结点，二级指针
    SLNodeDataType x  //传入的数据
    )
{
    //创建新节点
    SLNode* new_node = (SLNode*)malloc(sizeof(SLNode));
    // 检查是否扩容失败
    if (new_code == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    //放置
    new_code->data = x;  //要传入的数据
    new_code->next = NULL;  //next默认置为空

    //如果链表是空的
    if (*ppHead == NULL)
    {
        //直接插入即可
        *ppHead = new_node;
    }
    else
    {
        //找到尾结点
        SLNode* end = *ppHead;
        while (end->next != NULL)
        {
            end = end->next; //令end指向后继节点
        }
        //插入
        end->next = new_node;
    }
}

🔑 解读：

Step1：首先我们需要创建新的节点，定义一个新的结构体指针变量 new_node 作为新节点。这里我们 malloc 一块能放得下 SLNode 的空间就够了。这里我们检查下扩容是否失败，现在计算机存储今非昔比，已经到了几乎不可能出现扩容失败的情况了。但我还是喜欢检查一下，我们在动态内存开辟章节就建议大家养成这个习惯了，它毕竟是个好习惯。随后我们就可以往 new_node 里面放置内容了， new_node->data 中存放我们要传入的数据，因为创建新节点时我们也不确定下面到底有没有数据，所以 new_node->next 置为 NULL，创建新节点需要做的事情就这么多。

Step2：当新节点创建完毕后，我们就可以开始写尾插了。如果链表没有数据的话我们就可以直接插入，岂不美哉？所以我们先判断链表是否为空，这里记得对 *ppHead 解引用。如果链表是空的，我们就直接把 new_code 赋给 *ppHead 即可完成插入。如果链表是有数据的，我们要实现尾部插入，我们就要找到尾节点。这里我们创建一个寻尾指针 SLNode* end 作为工具人，来替代 *ppHead 去找尾节点。思路也很简单，如果 end 的下一个节点不为空，就进入循环，令 end 指向后继节点。这样 end 就成功找到了尾节点，最后 end->next 就是尾节点了，我们把 new_code 赋给 end->next 即可完成插入。


💬 Test.c

写到这里，我们就可以来测试下我们之前写的东西了：

#include "SList.h"

void TestSList1()
{
	SLNode* pList = NULL;
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);

	SListPrint(pList);
}

int main()
{
	TestSList1();

	return 0;
}

🔑 解读：

① 打印解析： 

​


 ② 尾插解析：​


0x02 创建新节点（CreateNewNode）

⚡ 考虑到创建新节点要经常用，为了方便复用，我们把它写成函数（CreateNewNode）：

/* 创建新节点 */
SLNode* CreateNewNode (
    SLNodeDataType x  //传入的数据
    )
{
    //创建，开辟空间
    SLNode* new_node = (SLNode*)malloc(sizeof(SLNode));
    //malloc检查
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    //放置
    new_node->data = x; //存传入的数据
    new_node->next = NULL; //next默认置空

    return new_node; //递交新节点
}

💬 SList.c：更新一下刚才尾插的写法

/* 尾插 */
void SListPushBack (
    SLNode** ppHead,  //头结点，二级指针
    SLNodeDataType x  //传入的数据
    )
{
    //创建新节点
    SLNode* new_node = CreateNewNode(x);
    //如果链表是空的
    if (*ppHead == NULL)
    {
        //直接插入即可
        *ppHead = new_node;
    }
    else
    {
        //找到尾结点
        SLNode* end = *ppHead;
        while (end->next != NULL)
        {
            end = end->next; //令end指向后继节点
        }
        //插入
        end->next = new_node;
    }
}


0x03 头插（SListPushFront）

💬 SList.h

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

typedef int SLNodeDataType;        // SLNodeDataType == int

typedef struct SingleListNode {
    SLNodeDataType data;           // 用来存放节点的数据 int data
    struct SingleListNode* next;   // 指向后继节点的指针
} SLNode;                          // 重命名为SLNode 便于利用该结构体

void SListPrint(SLNode* pHead);
void SListPushBack(SLNode** pHead, SLNodeDataType x);
void SListPushFront(SLNode** ppHead, SLNodeDataType x);

🔑 解读：这里仍然要使用二级指针。


💬 SList.c

/* 头插 */
void SListPushFront (
    SLNode** ppHead, //头结点
    SLNodeDataType x //传入的数据
    )
{
    //创建新节点
    SLNode* new_node = CreateNewNode(x);
    //先让新节点的next指向头结点
    new_node->next = *ppHead;
    //更新头结点
    *ppHead = new_node;
}

🔑 解读：

Step1：头插就很简单了，思路就是让新节点的 next 指向头结点，然后再让新节点做头结点即可。首先创建新节点，直接套用我们刚才创建的 CreateNewNode 函数即可。

Step2：创建完毕后，让新结点 new_node->next 存好头结点 *ppHead ，这样在物理上就实现了 "链接" 。最后我们再更新下头结点就可以了，把 new_node 赋给 *ppHead 。现在 new_node 就变成了新的头结点了，也就实现了头插的效果。


💬 Test.c：

#include "SList.h"

void TestSList1()
{
	SLNode* pList = NULL;
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);

	SListPrint(pList);

	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);

	SListPrint(pList);
}

int main()
{
	TestSList1();

	return 0;
}

🚩 运行结果如下：

​


0x04 尾删（SListPopBack）

💬 SList.h

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

typedef int SLNodeDataType;        // SLNodeDataType == int

typedef struct SingleListNode {
    SLNodeDataType data;           // 用来存放节点的数据 int data
    struct SingleListNode* next;   // 指向后继节点的指针
} SLNode;                          // 重命名为SLNode 便于利用该结构体

void SListPrint(SLNode* pHead);
void SListPushBack(SLNode** pHead, SLNodeDataType x);
void SListPushFront(SLNode** ppHead, SLNodeDataType x);
void SListPopBack(SLNode** pHead);

🔑 解读：尾删我们需要注意的是防止没有东西可删除，所以我们需要预防出现为空的情况。这里本人更倾向的是 assert 断言暴力解决的方法，和在顺序表章节中一样。使用断言就需要引入头文件 #include <assert.h> 。

​


💬 SList.c

① 方法1：prev 前驱指针

void SListPopBack (
    SLNode** ppHead  //头结点
    )
{
    //防止结点为空
    assert(*ppHead != NULL);

    //如果只有一个结点
    if ((*ppHead)->next == NULL)
    {
        free(*ppHead);
        *ppHead = NULL;
    }
    else //两个及两个以上结点
    {
        //找到尾部
        SLNode* prev = NULL; //前驱指针
        SLNode* end = *ppHead;
        while (end->next != NULL)
        {
            prev = end; //保存现有end
            end = end->next;  //令end指向后继节点
        }
        // 删除
        free(end);
        end = NULL;
        prev->next = NULL;
    }
}

🔑 解读：

Step1：首先 assert 断言防止链表没有节点。

Step2：开始判断，分为两种情况。第一种情况是只有一个结点，第二种情况是有两个及两个以上的节点，我们首先来看第一种情况。第一种情况时，我们就可以直接删除，使用 free 释放空间完空间后再把它置成空（动态内存开辟章节详细讲过为什么要这么做）。【维生素C语言】第十三章 - 动态内存管理

​  

 Step3：第二种情况时，因为是尾删所以我们理所当然要找到尾部的节点。为了防止最后没法触及上一个节点从而没办法把它置空，所以这里在创建寻尾指针 end 的同时，还要创建一个前驱指针 prev 以用来实时保存 end 的值，让 end 去送死。只要 end->next 不是 NULL 时就进入循环，首先保存 end 的值，然后令 end 指向后继节点。当 end->next 为 NULL 时，free 释放空间并置空，此时这个尾部节点就被删除了，但是上一个节点还存着这个已经删除的节点地址。这时，我们的前驱指针 prev 就能派上用场了，将 prev -> next 置为 NULL 就可以解决问题。这就是前驱指针的作用。


② 方法2：next->next 保守解决

/* 尾删 */
void SListPopBack (
    SLNode** ppHead  //头结点
    )
{
    //防止结点为空
    assert(*ppHead != NULL);

    //如果只有一个结点
    if ((*ppHead)->next == NULL)
    {
        free(*ppHead);
        *ppHead = NULL;
    }
    else //两个及两个以上结点
    {  
        SLNode* end = *ppHead;
        while (end->next->next)
        {
            end = end->next;
        }
        free(end->next);
        end->next = NULL;
    }
}

🔑 解读：

Step1 & Step2 同上。

Step3：我们也可以不使用前驱指针来实现。利用链表的性质进行更深一层的解引用也可以解决最后没法触及上一个节点从而无法将其置空的问题。首先创建寻尾指针 end，循环判断条件让 end 保留在 "安全位置" 不让他去送死了，也就是 end->next->next ，从而做到提前发现为空的情况，从而让 end 能够保留下来用来置空。当 end->next->next 为空时跳出循环，free 释放掉 end->next ，最后将 end->next 置为空。


💬 List.c：

① 把头插的4个数据逐个删除并打印：

#include "SList.h"

void TestSList2()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);

	SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	//SListPopBack(&pList);
}

int main()
{
	//TestSList1();
	TestSList2();

	return 0;
}

🚩 运行结果如下：

​


② 测试断言效果：

#include "SList.h"

void TestSList2()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);

	SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);

	SListPopBack(&pList);
    SListPrint(pList);
}

int main()
{
	//TestSList1();
	TestSList2();

	return 0;
}

🚩 运行结果如下：

​



0x05 头删（SListPopFront ）

💬 SList.h

void SListPopFront(SLNode** pHead);


💬 SList.c

/* 头删 */
void SListPopFront (
    SLNode** ppHead  //头节点
    )
{
    //防止节点为空
    assert(*ppHead != NULL); 
    //直接free会导致你找不到下一个节点了，所以我们需要处理一下：
    SLNode* save_next = (*ppHead)->next; //保存头节点的下一个节点
    //删除
    free(*ppHead); //释放头节点
    *ppHead = save_next; //更新头节点（刚才我们保存的）
}

🔑 解读：

Step1：首先防止节点为空。

Step2：头删我们要注意的是不能直接 free 掉，因为直接删的话就会导致找不到下一个节点了。创建 save_next 指针，用来保存我们要删除的头结点 *phead 指向的下一个结点的地址。保存好了之后我们就可以大胆的删除了，直接把头结点 free 掉即可。

Step3：更新头结点，将我们刚才保存的 save_next 赋值给 *pphead


💬 List.c

#include "SList.h"

void TestSList3()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);
	SListPrint(pList);

	SListPopFront(&pList);
	SListPrint(pList);

	SListPopFront(&pList);
	SListPrint(pList);

	SListPopFront(&pList);
	SListPrint(pList);

	SListPopFront(&pList);
	SListPrint(pList);

	//SListPopFront(&pList);
	//SListPrint(pList);
}


int main()
{
	//TestSList1();
	//TestSList2();
	TestSList3();

	return 0;
}

🚩 运行结果如下：

​



0x06 查找（SListFind）

💬 SList.h

SLNode* SListFind(SLNode* pHead, SLNodeDataType x);

🔑 解读：查找用不上二级指针，因为不需要修改链表的内容。函数返回结果为 SLNode* 


💬 SList.c

/* 查找 */
SLNode* SListFind (
    SLNode* pHead, 
    SLNodeDataType x
    )
{
    //查找就是遍历整个节点
    SLNode* cur = pHead;
    while (cur != NULL)
    {
        if (cur->data == x) // 找到了
            return cur;
        else // 继续找
            cur = cur->next;
    }
    // 没找到
    return NULL; 
}

🔑 解读：查找和打印函数一样，很简单，只需要创建一个 cur 遍历链表就可以了。如果 cur->data 和传入的 x，即需要查找的值相同就返回 cur，cur 是带有值和地址的。如果整个链表都走完了还没有找到相同的值，就返回 NULL 。


💬 List.c：查找多个节点

#include "SList.h"

void TestSList4()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 4);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 4);
	SListPrint(pList);

	// 找
	SLNode* pos = SListFind(pList, 2);
	int i = 1;
	while (pos)
	{
		printf("第%d个pos节点:%p->%d\n", i++, pos, pos->data);
		pos = SListFind(pos->next, 2);
	}
}

int main()
{
	//TestSList1();
	//TestSList2();
	//TestSList3();
	TestSList4();

	return 0;
}

🚩 运行结果如下：

​


0x07 指定位置前插（SListInsert）

* 一般默认是在pos位置之前去插入一个节点

💬 SList.h

void SListInsert(SLNode** ppHead, SLNode* pos, SLNodeDataType x);

🔑 解读：因为我们要对链表动手，所以这里我们又要传指针的地址，用二级指针接收了。pos 是要插入的位置，带有值和地址。


💬 SList.c

/* 在pos位置之前去插入一个节点 */
void SListInsert (
    SLNode** ppHead, 
    SLNode* pos, 
    SLNodeDataType x
    )
{
    //创建新结点
    SLNode* new_node = CreateNewNode(x);
    if (*ppHead == pos)
    {
        //头插
        new_node->next = *ppHead;
        *ppHead = new_node;
    }
    else
    {
        //找到pos的前一个位置
        SLNode* posPrev = *ppHead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }

        /* 
         * 插入：让posPrev连上new_node, new_node连上pos
         * 
         * ... (posPrev)->            (pos)->(pos->next)
         *                     ↓
         * ... (posPrev)->[new_node]->(pos)->(pos->next)
         * 
         */

        //插入
        posPrev->next = new_node;
        new_node->next = pos;
    }
}

🔑 解读：

Step1：首先创建新节点。分为两种情况，第一种情况是直接头插，第二种情况就是要找 pos 的前面一个结点的位置。我们首先看第一种情况，如果 *ppHead == pos 就直接头插就行了，先让新节点的 next 指向头结点，然后再更新头结点就行。这里你也可以直接调用 SListPushFront，但是头插代码就2行，所以这里就直接写了。

Step2：第二种情况，我们定义一个结构体指针 posPrev 用来找 pos 的前一个位置，如果 posPrev-> next 还不是 pos 就进入循环，让 posPrev 往下走，直到 posPrev->next 为 pos，也就找到 pos 前一个位置了。

Step3：找到 pos 前一个位置后就可以插入了，直接把 new_node 交给 posPrev->next ，此时 new_node 默认指向 NULL，还要把 pos 交给 new_node->next 。



💬 List.c：

① 第二种情况：

#include "SList.h"

void TestSList5()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);
	SListPrint(pList);
	
	SLNode* pos = SListFind(pList, 3);
	if (pos)
	{
		SListInsert(&pList, pos, 30);
	}
	SListPrint(pList);
}
int main()
{
	//TestSList1();
	//TestSList2();
	//TestSList3();
	//TestSList4();
	TestSList5();

	return 0;
}

🚩 运行结果如下：

​


① 第一种情况（需要头插的情况）：

#include "SList.h"

void TestSList5()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);
	SListPrint(pList);
	
    //需要头插的情况
	SLNode* pos = SListFind(pList, 4);
	if (pos)
	{
		SListInsert(&pList, pos, 40);
	}
	SListPrint(pList);

}
int main()
{
	//TestSList1();
	//TestSList2();
	//TestSList3();
	//TestSList4();
	TestSList5();

	return 0;
}

🚩 运行结果如下：

​



0x08 删除指定位置节点（SListEarse）

💬 SList.h

void SListEarse(SLNode** ppHead, SLNode* pos);

💬 SList.c

/* 删除pos位置的节点 */
void SListEarse(
    SLNode** ppHead,
    SLNode* pos
)
{
    //防止没有节点的情况
    assert(*ppHead != NULL);
    assert(pos);
    //只有一个节点的情况
    if (*ppHead == pos)
    {
        //直接头删
        SListPopFront(ppHead);
    }
    //二个或两个以上节点的情况
    else
    {
        // 找到pos前面的一个结点
        SLNode* posPrev = *ppHead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next; //把前面和后面数据链接起来
        free(pos);
        //pos = NULL;
    }
}

🔑 解读：

Step1：防止节点为空。因为我们要删除 pos 位置的值，所以还要防止传入的 pos 为空。

Step2：还是分为两种情况，一种是有节点的情况，即头删的情况，我们直接调用 SListPopFront 即可。

Step3：第二种情况，我们定义一个结构体指针 Posprev 用来找 pos 。在删除之前我们要把 pos 前面和后面的数据链接起来，Posprev->next = pos->next ，最后再 free 掉 pos 即可。值得一提的是，这里的 pos 可以不置空。


💬 List.c：删除 3

#include "SList.h"

void TestSList6()
{
	SLNode* pList = NULL;
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 3);
	SListPushFront(&pList, 4);
	SListPrint(pList);

	SLNode* pos = SListFind(pList, 3);
	if (pos)
	{
		SListEarse(&pList, pos);
	}
	SListPrint(pList);

}

int main()
{
	//TestSList1();
	//TestSList2();
	//TestSList3();
	//TestSList4();
	//TestSList5();
	TestSList6();

	return 0;
}

🚩 运行结果如下：

​


0x09 销毁（SListDestroy）

💬 SList.h

void SListDestroy(SLNode** ppHead);

💬 SList.c

/* 销毁 */
void SListDestroy (
    SLNode** ppHead
    )
{
    assert(ppHead);

    SLNode* cur = *ppHead;
    while (cur != NULL) {
        SLNode* next = cur->next;
        free(cur);
        cur = next;
    }

    *ppHead = NULL;
}

🔑 解读：销毁得有东西才能销毁，所以断言 ppHead 不为空。通过 cur 逐个走一遍，为了防止删了一个下一个结点就找不到了，每次进入循环都先创建一个 next 指针来保存 cur->next，然后再 free 掉。全部结束后再把 *ppHead 置为空，就完成销毁了。


0x0A 指定位置后插（SListInsertAfter）

💬 SList.h

void SListInsertAfter(SLNode* pos, SLNodeDataType x);

💬 SList.c

/* 在pos位置之后去插入一个节点 */
void SListInsertAfter (
    SLNode* pos,
    SLNodeDataType x
    )
{
    assert(pos);
    SLNode* new_node = CreateNewNode(x);
    new_node->next = pos->next;
    pos->next = new_node;
}

🔑 解读：在 pos 后面插入就很简单了，因为不需要找 pos 前面的结点，没有什么好讲的。


0x0B 删除指定位置之后的节点（SListEraseAfter）

💬 SList.h

void SListEraseAfter (SLNode* pos);

💬 SList.c

/* 删除pos之后的一个节点 */
void SListEraseAfter (
    SLNode* pos
    )
{
	assert(pos);
	assert(pos->next);

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


四、完整代码

💬 SList.h

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

typedef int SLNodeDataType;        // SLNodeDataType == int

typedef struct SingleListNode {
    SLNodeDataType data;           // 用来存放节点的数据 int data
    struct SingleListNode* next;   // 指向后继节点的指针
} SLNode;                          // 重命名为SLNode 便于利用该结构体

void SListPrint(SLNode* pHead);
void SListPushBack(SLNode** pHead, SLNodeDataType x);
void SListPushFront(SLNode** ppHead, SLNodeDataType x);
void SListPopBack(SLNode** pHead);
void SListPopFront(SLNode** pHead);

SLNode* SListFind(SLNode* pHead, SLNodeDataType x);
void SListInsert(SLNode** ppHead, SLNode* pos, SLNodeDataType x);
//void SListInsert(SLNode* pHead, int pos, SLNodeDataType x);
void SListEarse(SLNode** ppHead, SLNode* pos);
void SListDestroy(SLNode** ppHead);
void SListInsertAfter(SLNode* pos, SLNodeDataType x);
void SListEraseAfter (SLNode* pos);


💬 SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

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

/* 创建新节点 */
SLNode* CreateNewNode(SLNodeDataType x) {
    //创建，开辟空间
    SLNode* new_node = (SLNode*)malloc(sizeof(SLNode));
    //malloc检查
    if (new_node == NULL) {
        printf("malloc failed!\n");
        exit(-1);
    }
    //放置
    new_node->data = x; //存传入的数据
    new_node->next = NULL; //next默认置空

    return new_node; //递交新节点
}

/* 尾插 */
void SListPushBack(SLNode** ppHead, SLNodeDataType x) {
    //创建新节点
    SLNode* new_node = CreateNewNode(x);
    //如果链表是空的
    if (*ppHead == NULL) {
        //直接插入即可
        *ppHead = new_node;
    }
    else {
        //找到尾结点
        SLNode* end = *ppHead;
        while (end->next != NULL) {
            end = end->next; //令end指向后继节点
        }
        //插入
        end->next = new_node;
    }
}

/* 头插 */
void SListPushFront(SLNode** ppHead, SLNodeDataType x) {
    //创建新节点
    SLNode* new_node = CreateNewNode(x);
    //先让新节点的next指向头结点
    new_node->next = *ppHead;
    //更新头结点
    *ppHead = new_node;
}

/* 尾删 */
void SListPopBack(SLNode** ppHead) {
    //防止结点为空
    assert(*ppHead != NULL);

    //如果只有一个结点
    if ((*ppHead)->next == NULL) {
        free(*ppHead);
        *ppHead = NULL;
    }
    else {  //两个及两个以上结点
        /*
        //找到尾部
        SLNode* prev = NULL; //前驱指针
        SLNode* end = *ppHead;
        while (end->next != NULL)
        {
            prev = end; //保存现有end
            end = end->next;  //令end指向后继节点
        }
        // 删除
        free(end);
        end = NULL;
        prev->next = NULL;
        */

        SLNode* end = *ppHead;
        while (end->next->next) {
            end = end->next;
        }
        free(end->next);
        end->next = NULL;
    }
}

/* 头删 */
void SListPopFront(SLNode** ppHead) {
    //防止节点为空
    assert(*ppHead != NULL);
    //直接free会导致你找不到下一个节点了，所以我们需要处理一下：
    SLNode* save_next = (*ppHead)->next; //保存头节点的下一个节点
    //删除
    free(*ppHead); //释放头节点
    *ppHead = save_next; //更新头节点（刚才我们保存的）
}

/* 查找 */
SLNode* SListFind(SLNode* pHead, SLNodeDataType x) {
    //查找就是遍历整个节点
    SLNode* cur = pHead;
    while (cur != NULL) {
        if (cur->data == x) // 找到了
            return cur;
        else // 继续找
            cur = cur->next;
    }
    // 没找到
    return NULL;
}

/* 在pos位置之前去插入一个节点 */
void SListInsert(SLNode** ppHead,SLNode* pos,SLNodeDataType x) {
    //创建新结点
    SLNode* new_node = CreateNewNode(x);
    if (*ppHead == pos) {
        //头插
        new_node->next = *ppHead;
        *ppHead = new_node;
    }
    else {
        //找到pos的前一个位置
        SLNode* posPrev = *ppHead;
        while (posPrev->next != pos) {
            posPrev = posPrev->next;
        }

        /*
         * 插入：让posPrev连上new_node, new_node连上pos
         *
         * ... (posPrev)->            (pos)->(pos->next)
         *                     ↓
         * ... (posPrev)->[new_node]->(pos)->(pos->next)
         *
         */

         //插入
        posPrev->next = new_node;
        new_node->next = pos;
    }
}

/* 删除pos位置的节点 */
void SListEarse(SLNode** ppHead, SLNode* pos) {
    //防止没有节点的情况
    assert(*ppHead != NULL);
    assert(pos);
    //只有一个节点的情况
    if (*ppHead == pos) {
        //直接头删
        SListPopFront(ppHead);
    }
    else {   //二个或两个以上节点的情况
        // 找到pos前面的一个结点
        SLNode* posPrev = *ppHead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next; //把前面和后面数据链接起来
        free(pos);
        //pos = NULL;
    }
}

/* 销毁 */
void SListDestroy(SLNode** ppHead) {
    assert(ppHead);

    SLNode* cur = *ppHead;
    while (cur != NULL) {
        SLNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *ppHead = NULL;
}

/* 在pos位置之后去插入一个节点 */
void SListInsertAfter(SLNode* pos,SLNodeDataType x) {
    assert(pos);
    SLNode* new_node = CreateNewNode(x);
    new_node->next = pos->next;
    pos->next = new_node;
}

/* 删除pos之后的一个节点 */
void SListEraseAfter(SLNode* pos) {
    assert(pos);
    assert(pos->next);

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


参考资料：

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

比特科技. 数据结构v5[EB/OL]. 2021[21]. .

📌 作者：王亦优

📃 更新： 2021.11.3

❌ 勘误： 无

📜 声明： 由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！

本章完。

​

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构 面向对象编程
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入