深圳幻海软件技术有限公司 欢迎您！
更多

数据结构 | 单链表

2023-04-15

节点 tail slt
…🌳🌲🌱本文已收录至：数据结构|C语言更多知识尽在此专栏中!文章目录🌳前言🌳正文🌲链表打印与销毁🪴打印🪴销毁🌲尾部插入与删除🪴节点申请🪴尾插🪴尾删🌲头部插入与删除🪴头插🪴头删🌲节点查找与修改🪴查找🪴修改🌲任意位置插入与删除🪴简单版🌱插入🌱删除🪴困难版🌱

…

🌳🌲🌱本文已收录至：数据结构 | C语言
更多知识尽在此专栏中!

文章目录

  • 🌳前言
  • 🌳正文
    • 🌲链表打印与销毁
      • 🪴打印
      • 🪴销毁
    • 🌲尾部插入与删除
      • 🪴节点申请
      • 🪴尾插
      • 🪴尾删
    • 🌲头部插入与删除
      • 🪴头插
      • 🪴头删
    • 🌲节点查找与修改
      • 🪴查找
      • 🪴修改
    • 🌲任意位置插入与删除
      • 🪴简单版
        • 🌱插入
        • 🌱删除
      • 🪴困难版
        • 🌱插入
        • 🌱删除
    • 🌲源码区
      • 🪴功能声明头文件部分
      • 🪴功能实现源文件部分
      • 🪴主函数调用源文件部分
    • 🌲相关OJ试题推荐
  • 🌳总结

🌳前言

单链表 是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表 中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置) ，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据

这是百度百科对于 单链表 的解释，通俗来说，单链表 就是一种数据结构，它包含了一个 数据域 data 和一个 指针域 next ，最大的特点就是 链式存储 。链表有很多种，其中 单链表 是最基本、最简单的一种结构，很多OJ题都会利用 单链表 出题，后面的部分高阶数据结构也会用到 单链表 ，因此学好 单链表 很重要。除了 单链表 外，还有 双向带头循环链表 (后面会介绍)等链表类型，先来进入 单链表 的学习吧！

🌳正文

🌲链表打印与销毁

🪴打印

单链表 创建时是一个结构体类型的指针，一开始指向空，只有在经过插入数据后才会有自己的指向 ，因此我们可以根据这一特点，遍历 整个 单链表 ，并输出其中的 数据域 data。

void SLTPrint(const SLT** pphead)//单链表的打印
{
assert(pphead);//不需要断言 *pphead ，因为存在空链表打印的情况，是合法的

printf("\n\n当前链表为: ");
const SLT* cur = *pphead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//cur要向后移动
}

printf("NULL\n\n\n");//链表最后为空
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

🪴销毁

销毁 单链表 也需要将其 遍历 一遍，因为链表中的元素不是连续存放的，只能逐个节点销毁 ，销毁思想为：利用 *pphead 遍历整个 单链表 ，保存头节点 *pphead 的下一个节点信息至 cur，释放原头节点，更新头节点信息(把 cur 的值赋给头节点 *pphead )如此重复，直到释放完所有节点即可。

//不带哨兵位的单链表不需要初始化
void SLTDestroy(SLT** pphead)//单链表的销毁
{
assert(pphead);//一二级指针都不能为空

//空表不走销毁程序，但不能报错
if (*pphead)
{
while (*pphead)
{
SLT* cur = (*pphead)->next;//记录头的下一个位置
free(*pphead);
*pphead = cur;//向后移动，不断销毁
}
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

🌲尾部插入与删除

🪴节点申请

单链表 是由一个一个独立存在的节点组成的结构，当涉及插入操作时，向内存申请节点，涉及删除操作时，就要把对应的节点销毁

static SLT* buyNode(const SLTDataType x)//买节点
{
SLT* newnode = (SLT*)malloc(sizeof(SLT));
assert(newnode);//防止申请失败的情况

newnode->data = x;
newnode->next = NULL;

return newnode;//返回买好的节点
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

🪴尾插

单链表 尾插是比较费劲的，因为得先通过头节点指针向后 遍历 找到尾节点，然后将尾节点与新节点之间建立链接关系，其中还得分情况尾插

  • 链表为空，直接把新节点赋给头节点
  • 不为空，就需要找到尾节点，建立链接关系

关于 单链表 中函数用二级指针的问题：
插入或删除时，如果是第一次操作，需要对头节点本身造成改变，且头节点是一个 一级指针 ，因此需要通过 二级指针 的方式来在函数中改变头节点的值。至于后续的操作，都只是改变了结构体中的 next 值，因此使用 一级指针 就够了，但是为了函数设计时的普适性，单链表 中的函数参数都设计成了 二级指针 的形式。

void SLTPushBack(SLT** pphead, const SLTDataType x)//尾插
{
assert(pphead);

SLT* newnode = buyNode(x);
SLT* tail = *pphead;
//尾插分情况，链表为空，直接赋值，不为空，找到尾，再链接
if (tail == NULL)
{
*pphead = tail = newnode;//直接赋值
}
else
{
while (tail->next != NULL)
{
tail = tail->next;//找到尾节点
}
tail->next = newnode;//链接
}

//SLTInsert(pphead, NULL, x);//可以复用任意位置前插
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

🪴尾删

尾删操作与尾插基本一致，同样是需要找到尾节点，不过每次 tail 指针在向后移动前，会先使用一个 prev 指针保存 tail 的信息，当 tail 为尾节点时，释放 tail ，并将 prev->next 置空，此时的 prev 就是新的尾节点，因为原理都差不多，这里就不用动图展示了，值得注意的是尾删也分两种情况

  • 只有一个节点，此时直接释放头节点(尾节点)，链表置空
  • 存在多个节点，需要先找到尾节点与尾节点的上一个节点，确定新的尾
  • 并不是所有情况都能删除，比如表空的情况，是不能执行操作的，可以用断言处理


void SLTPopBack(SLT** pphead)//尾删
{
assert(pphead);
assert(*pphead);//如果链表为空，是删不了的

SLT* tail = *pphead;
SLT* prev = NULL;
while (tail->next)
{
prev = tail;//保存上一个节点信息
tail = tail->next;//找到尾节点
}

free(tail);

//分情况，如果prev是空，说明删除的尾节点同时也是头节点
if (prev)
prev->next = tail = NULL;//把尾节点的上一个节点指向空
else
*pphead = NULL;//此时直接把prev置空

/*SLT* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
SLTErase(pphead, tail);*///可以复用任意位置删除
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

🌲头部插入与删除

🪴头插

对于头部操作来说，单链表 是很轻松的，比如 单链表 头插的本质就是将 新节点 newnode 与 头节点 *pphead 链接，然后更新头节点信息就行了，即 *pphead = newnode ，三行代码就解决了。

void SLTPushFront(SLT** pphead, const SLTDataType x)//头插
{
assert(pphead);

SLT* newhead = buyNode(x);
newhead->next = *pphead;//直接链接
*pphead = newhead;//更新头节点信息
//代码简洁之道

//SLTInsert(pphead, *pphead, x);//可以复用任意位置前插
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

🪴头删

头删也是比较简单的，先用 cur 指向头节点，先保存 头节点 cur 的下一个节点信息至 节点 newhead，释放 原头节点 cur，更新 newhead 为链表的新头，即 *pphead = newnode 当然涉及删除的操作，都需要进行表空检查，如果链表为空，是不能执行删除的。

void SLTPopFront(SLT** pphead)//头删
{
assert(pphead);
assert(*pphead);//头删同样存在空不能删的情况

//先找到头的下一个节点，然后赋值新头
SLT* cur = *pphead;//指向头节点
SLT* newhead = cur->next;//保存头节点的下一个节点信息

free(cur);
cur = NULL;

*pphead = newhead;//赋值新头

//SLTErase(pphead, *pphead);//可以复用任意位置删除
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

🌲节点查找与修改

🪴查找

查找函数很简单，遍历+比较 就行了，找到目标元素值后，返回相关节点信息，其实查找这个函数主要是为了配合后面任意插入删除函数的 ，所以比较简单。

SLT* SLTFind(const SLT** pphead, const SLTDataType x)//查找值为x的节点(第一次出现)
{
assert(pphead);

SLT* cur = (SLT*)*pphead;//指向头节点
while (cur)
{
if (cur->data == x)
return cur;//找到了，返回相关节点信息
cur = cur->next;
}

return NULL;//没有找到的情况
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

🪴修改

修改函数是在查找函数基础上进行的：当我们输入元素值交给查找函数，找到目标节点后返回其节点信息，然后直接通过返回的节点改变 data 值就行了，在调用查找函数的前提下，一行代码就解决了。

void SLTModify(SLT* node, const SLTDataType val)//修改 node 节点处的值
{
    //注意：在调用函数时，可以通过链式访问，将查找函数的返回值作为形参一传入就行了
assert(node);//断言，如果节点node是空指针，是不能做修改的
node->data = val;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

🌲任意位置插入与删除

🪴简单版

简单版是在任意位置后插入元素，删除任意位置后的节点，根据 单链表 的特性，对后面节点进行操作是比较简单，无非就是改变链接关系。但是这种对后操作存在缺陷：不适合实现头插、头删

🌱插入

插入(后插)主要分两步

  • 获取信息
  • 改变链接关系

获取信息：有三个关键信息：被插入节点 cur、待插入节点 newnode 和 cur 的下一个节点 tail

改变链接关系：很简单，cur->next = newnode，后插嘛，先把待插入节点链接到 cur 后面，然后再把 newnode 和 tail 链接起来就行了

这里的 nodeAfter 是需要通过查找函数找出来的，它是一个 一级指针

//这两个有缺陷，不能对头节点进行操作，但实现起来比较简单
void SLTInsertAfter(SLT* nodeAfter, const SLTDataType x)//任意插，后插法
{
assert(nodeAfter);

SLT* cur = nodeAfter;
SLT* newnode = buyNode(x);
SLT* tail = cur->next;//先保存被插入节点的下一个节点信息

//更改链接关系，后插完成
cur->next = newnode;
newnode->next = tail;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

🌱删除

删除思路，和头删差不多

  • 找到待插入节点 cur
  • 找到 cur 的下一个节点 tail
  • 找到 tail 的下一个节点 newtail

接下来就很简单了，释放 tail 节点，更改链接关系，当然断言是少不了

void SLTEraseAfter(SLT* nodeAfter)//任意删，删除后面节点
{
assert(nodeAfter);
assert(nodeAfter->next);//如果目标节点的下一个为空，是后删不了的

SLT* cur = nodeAfter;
SLT* tail = cur->next;//待删除的节点
SLT* newtail = tail->next;//新尾

free(tail);
tail = NULL;

cur->next = newtail;//更改链接关系
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

🪴困难版

困难版就比较麻烦了，因为它要实现的是任意位置前插元素、删除任意位置的节点，单链表 的最大缺点是不能回退，这就意味着即使我们得到了待删除节点，也是很难求出它的上一个节点的 ，对于这种尴尬情况，只能老老实实从头节点处开始向后 遍历 寻找，直到找到待删除节点的上一个节点。

🌱插入

其实这个也没有多困难，无非就是比上一种多个参数，然后多了一步遍历操作而已，内核思想任然不变

  • 获取信息
  • 更改链接关系

//这两个实现起来比较麻烦，但是很全能
void SLTInsert(SLT** pphead, SLT* node, const SLTDataType x)//任意插，前插法
{
assert(pphead);

SLT* newnode = buyNode(x);
SLT* cur = *pphead;
SLT* prev = NULL;
while (cur != node)
{
prev = cur;//要找到目标节点的上一个节点
cur = cur->next;
}

//判断一下，是否为空表插入
//走的是尾插的那一套思想
if (prev)
{
prev->next = newnode;
newnode->next = node;
}
else
{
newnode->next = node;
*pphead = newnode;//空表需要更新头节点信息
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

🌱删除

删除是一样的逻辑，不过多了一个 tail 而已，指向的位置是 node 的下一个节点，其余步骤跟插入基本一致，之后也是一样的更改链接关系，一样需要判断是否为空表，如果为空表需要更新头节点信息。

其实现在看来，困难版的插入删除，就像是尾部插入删除的升级版，有些麻烦，但很可靠，困难版的任意位置插入删除可以完全替代头尾插入删除，也就是说写这一对函数就够了。

void SLTErase(SLT** pphead, SLT* node)//任意删，删除当前节点
{
assert(pphead);
assert(node);//不必检查*pphead的合法性，查验node就行了

SLT* cur = *pphead;//走的是尾删的那一套思想
SLT* prev = NULL;
SLT* tail = node->next;
while (cur != node)
{
prev = cur;
cur = cur->next;
}

free(node);
//跟尾插一样，需要判断一下
if (prev)
prev->next = tail;
else
*pphead = tail;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

🌲源码区

代码放一起看，会更好理解一些~

🪴功能声明头文件部分

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

typedef int SLTDataType;//单链表的数据类型

typedef struct SListNode
{
SLTDataType data;//数据域
struct SListNode* next;//指针域
}SLT;//重命名为 SLT

void SLTDestroy(SLT** pphead);//单链表的销毁
void SLTPrint(const SLT** pphead);//单链表的打印

void SLTPushBack(SLT** pphead, const SLTDataType x);//尾插
void SLTPopBack(SLT** pphead);//尾删

void SLTPushFront(SLT** pphead, const SLTDataType x);//头插
void SLTPopFront(SLT** pphead);//头删

//这两个有缺陷，不能对头节点进行操作，但实现起来比较简单
void SLTInsertAfter(SLT* nodeAfter, const SLTDataType x);//任意插，后插法
void SLTEraseAfter(SLT* nodeAfter);//任意删，删除后面节点

//这两个实现起来比较麻烦，但是很全能
void SLTInsert(SLT** pphead, SLT* node, const SLTDataType x);//任意插，前插法
void SLTErase(SLT** pphead, SLT* node);//任意删，删除当前节点

SLT* SLTFind(const SLT** pphead, const SLTDataType x);//查找值为x的节点(第一次出现)

void SLTModify(SLT* node, const SLTDataType val);//修改 node 节点处的值

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

🪴功能实现源文件部分

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

//不带哨兵位的单链表不需要初始化
void SLTDestroy(SLT** pphead)//单链表的销毁
{
assert(pphead);//一二级指针都不能为空

//空表不走销毁程序，但不能报错
if (*pphead)
{
while (*pphead)
{
SLT* cur = (*pphead)->next;//记录头的下一个位置
free(*pphead);
*pphead = cur;//向后移动，不断销毁
}
}
}

void SLTPrint(const SLT** pphead)//单链表的打印
{
assert(pphead);//不需要断言 *pphead ，因为存在空链表打印的情况，是合法的

printf("\n\n当前链表为: ");
const SLT* cur = *pphead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//cur要向后移动
}

printf("NULL\n\n\n");//链表最后为空
}

static SLT* buyNode(const SLTDataType x)//买节点
{
SLT* newnode = (SLT*)malloc(sizeof(SLT));
assert(newnode);//防止申请失败的情况

newnode->data = x;
newnode->next = NULL;

return newnode;//返回买好的节点
}

void SLTPushBack(SLT** pphead, const SLTDataType x)//尾插
{
assert(pphead);

SLT* newnode = buyNode(x);
SLT* tail = *pphead;
//尾插分情况，链表为空，直接赋值，不为空，找到尾，再链接
if (tail == NULL)
{
*pphead = tail = newnode;//直接赋值
}
else
{
while (tail->next != NULL)
{
tail = tail->next;//找到尾节点
}
tail->next = newnode;//链接
}

//SLTInsert(pphead, NULL, x);//可以复用任意位置前插
}

void SLTPopBack(SLT** pphead)//尾删
{
assert(pphead);
assert(*pphead);//如果链表为空，是删不了的

SLT* tail = *pphead;
SLT* prev = NULL;
while (tail->next)
{
prev = tail;//保存上一个节点信息
tail = tail->next;//找到尾节点
}

free(tail);

//分情况，如果prev是空，说明删除的尾节点同时也是头节点
if (prev)
prev->next = tail = NULL;//把尾节点的上一个节点指向空
else
*pphead = NULL;//此时直接把prev置空

/*SLT* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
SLTErase(pphead, tail);*///可以复用任意位置删除
}

void SLTPushFront(SLT** pphead, const SLTDataType x)//头插
{
assert(pphead);

SLT* newhead = buyNode(x);
newhead->next = *pphead;//直接链接
*pphead = newhead;//更新头节点信息
//代码简洁之道

//SLTInsert(pphead, *pphead, x);//可以复用任意位置前插
}

void SLTPopFront(SLT** pphead)//头删
{
assert(pphead);
assert(*pphead);//头删同样存在空不能删的情况

//先找到头的下一个节点，然后赋值新头
SLT* cur = *pphead;//指向头节点
SLT* newhead = cur->next;//保存头节点的下一个节点信息

free(cur);
cur = NULL;

*pphead = newhead;//赋值新头

//SLTErase(pphead, *pphead);//可以复用任意位置删除
}

//这两个有缺陷，不能对头节点进行操作，但实现起来比较简单
void SLTInsertAfter(SLT* nodeAfter, const SLTDataType x)//任意插，后插法
{
assert(nodeAfter);

SLT* cur = nodeAfter;
SLT* newnode = buyNode(x);
SLT* tail = cur->next;//先保存被插入节点的下一个节点信息

//更改链接关系，后插完成
cur->next = newnode;
newnode->next = tail;
}

void SLTEraseAfter(SLT* nodeAfter)//任意删，删除后面节点
{
assert(nodeAfter);
assert(nodeAfter->next);//如果目标节点的下一个为空，是后删不了的

SLT* cur = nodeAfter;
SLT* tail = cur->next;//待删除的节点
SLT* newtail = tail->next;//新尾

free(tail);
tail = NULL;

cur->next = newtail;//更改链接关系
}

//这两个实现起来比较麻烦，但是很全能
void SLTInsert(SLT** pphead, SLT* node, const SLTDataType x)//任意插，前插法
{
assert(pphead);

SLT* newnode = buyNode(x);
SLT* cur = *pphead;
SLT* prev = NULL;
while (cur != node)
{
prev = cur;//要找到目标节点的上一个节点
cur = cur->next;
}

//判断一下，是否为空表插入
//走的是尾插的那一套思想
if (prev)
{
prev->next = newnode;
newnode->next = node;
}
else
{
newnode->next = node;
*pphead = newnode;//空表需要更新头节点信息
}
}

void SLTErase(SLT** pphead, SLT* node)//任意删，删除当前节点
{
assert(pphead);
assert(node);//不必检查*pphead的合法性，查验node就行了

SLT* cur = *pphead;//走的是尾删的那一套思想
SLT* prev = NULL;
SLT* tail = node->next;
while (cur != node)
{
prev = cur;
cur = cur->next;
}

free(node);
//跟尾插一样，需要判断一下
if (prev)
prev->next = tail;
else
*pphead = tail;
}


SLT* SLTFind(const SLT** pphead, const SLTDataType x)//查找值为x的节点(第一次出现)
{
assert(pphead);

SLT* cur = (SLT*)*pphead;//指向头节点
while (cur)
{
if (cur->data == x)
return cur;//找到了，返回相关节点信息
cur = cur->next;
}

return NULL;//没有找到的情况
}

void SLTModify(SLT* node, const SLTDataType val)//修改 node 节点处的值
{
//注意：在调用函数时，可以通过链式访问，将查找函数的返回值作为形参一传入就行了
assert(node);//断言，如果节点node是空指针，是不能做修改的

node->data = val;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229

🪴主函数调用源文件部分

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void menu()
{
printf("0.退出1.打印\n");
printf("2.尾插3.尾删\n");
printf("4.头插5.头删\n");
printf("6.任意插(后插)7.任意删(后删)\n");
printf("8.任意插(前插)9.任意删(当前)\n");
printf("10.查找11.修改\n");
}

int main()
{
SLT* s = NULL;
int input = 1;
while (input)
{
menu();
printf("请选择:>");
scanf("%d", &input);
system("cls");//清屏函数，让显示效果更好
int val = 0;//待插入值
int pos = 0;//待查找节点值
switch (input)
{
case 0:
printf("成功退出\n");
break;
case 1:
SLTPrint(&s);
break;
case 2:
printf("请输入一个数:>");
scanf("%d", &val);
SLTPushBack(&s, val);
break;
case 3:
SLTPopBack(&s);
break;
case 4:
printf("请输入一个数:>");
scanf("%d", &val);
SLTPushFront(&s, val);
break;
case 5:
SLTPopFront(&s);
break;
case 6:
printf("请输入被插入的节点值:>");
scanf("%d", &pos);
printf("请输入一个数:>");
scanf("%d", &val);
SLTInsertAfter(SLTFind(&s, pos), val);
break;
case 7:
printf("请输入被删除的节点值:>");
scanf("%d", &pos);
SLTEraseAfter(SLTFind(&s, pos));
break;
case 8:
printf("请输入被插入的节点值:>");
scanf("%d", &pos);
printf("请输入一个数:>");
scanf("%d", &val);
SLTInsert(&s, SLTFind(&s, pos), val);
break;
case 9:
printf("请输入被删除的节点值:>");
scanf("%d", &pos);
SLTErase(&s, SLTFind(&s, pos));
break;
case 10:
printf("请输入被查找的节点值:>");
scanf("%d", &pos);
SLT* tmp = SLTFind(&s, pos);
printf("当前节点的地址为:%p\n", tmp);
break;
case 11:
printf("请输入被修改的节点值:>");
scanf("%d", &pos);
printf("请输入一个数:>");
scanf("%d", &val);
SLTModify(SLTFind(&s, pos), val);
break;
default :
printf("选择错误，重新选择!\n");
break;
}
}
SLTDestroy(&s);//每次程序运行结束，都会执行销毁函数
return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94

🌲相关OJ试题推荐

下面是几道关于 单链表 的OJ试题，可以试着解决一下，加强对链表的认识

  1. 203.移除链表元素
  2. 206.反转单链表
  3. 876.链表的中间结点
  4. 链表中倒数第k个结点
  5. 21.合并两个有序链表
  6. CM11 链表分割
  7. OR36 链表的回文结构
  8. 160.相交链表
  9. 141.环形链表
  10. 141.环形链表 ||
  11. 138.复制带随机指针的链表

🌳总结

以上就是关于 单链表 的全部内容了，单链表 中用到了 二级指针 这个东西，如果使用带哨兵位的 单链表 就可以不用 二级指针 ，但是这种结构用的比较少，单纯的学好 单链表 ，能快速提高我们对链表的认识，毕竟链表这个工具后续还会用到。从文中可以看出，单链表 相对于 顺序表 ，不用考虑空间问题，且头插头删效率很高，可惜 单链表 不支持下标的随机访问。总之，顺序表 和 单链表 各有各的用途，二者相辅相成，都是很不错的数据结构。

如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正

…

相关文章推荐
数据结构 | 顺序表
数据结构 | 时间复杂度与空间复杂度
C语言进阶——动态内存管理

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览44139 人正在系统学习中
C/C++/Linux交流学习
微信名片
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪