深 入 剖 析 单 链 表：从 原 理 到 实 战 应 用
💻作 者 简 介：曾 与 你 一 样 迷 茫，现 以 经 验 助 你 入 门 数据 结 构。
💡个 人 主 页：@笑口常开xpr 的 个 人 主 页
📚系 列 专 栏：硬 核 数 据 结 构 与 算 法
✨代 码 趣 语：巧 妙 的 数 据 结 构 搭 配 简 单 的 代 码，远 比 反 过 来 效 果 好 得 多。
💪代 码 千 行，始 于 坚 持，每 日 敲 码，进 阶 编 程 之 路。
📦gitee 链 接：gitee
线 性 表 的 顺 序 存 储 结 构 的 特 点 是 逻 辑 关 系 上 相 邻 的 两 个 元 素 在 物 理 位 置 上 也 相 邻，因 此 可 以 随 机 存 取 表 中 任 一 元 素。然 而，从 另 一 方 面 来 看，这 个 特 点 也 铸 成 了 这 种 存 储 结 构 的 弱 点：在 作 插 入 或 删 除 操 作 时，需 移 动 大 量 元 素。本 篇 博 客 将 讨 论 线 性 表 的 另 一 种 表 示 方 法 - - - 链 式 存 储 结 构，由 于 它 不 要 求 逻 辑 上 相 邻 的 元 素 在 物 理 位 置 上 也 相 邻，因 此 它 没 有 顺 序 存 储 结 构 所 具 有 的 弱 点，但 同 时 也 失 去 了 顺 序 表 可 随 机 存 取 的 优 点。
顺 序 表 的 问 题
- 中 间 / 头 部 的 插 入 删 除，时 间 复 杂 度 为 O(N)。
- 增 容 需 要 申 请 新 空 间，拷 贝 数 据，释 放 旧 空 间。会 有 不 小 的 消 耗。
- 增 容 一 般 是 呈 2 倍 的 增 长，势 必 会 有 一 定 的 空 间 浪 费。例 如 当 前 容 量 为 100，满 了 以 后 增 容 到 200，我 们 再 继 续 插 入 了 5 个 数 据，后 面 没 有 数 据 插 入 了，那 么 就 浪 费 了 95 个 数 据 空 间。
单 链 表
单 链 表 与 顺 序 表 区 别
顺 序 表：使 用 一 组 地 址 连 续 的 存 储 单 元 来 依 次 存 放 线 性 表 的 结 点，因 此 结 点 的 逻 辑 顺 序 和 物 理 顺 序 是 一 样 的。
链 表：使 用 一 组 任 意 的 存 储 单 元 来 存 放 线 性 表 的 结 点，这 组 存 储 单 元 可 以 是 连 续 的，也 可 以 是 非 连 续 的，甚 至 是 零 散 分 布 在 内 存 的 任 何 位 置 上。因 此，链 表 的 逻 辑 顺 序 和 物 理 顺 序 不 一 样 相 同。
相 关 概 念
结 点：在 存 储 线 性 表 的 每 个 数 据 元 素 值 的 同 时 存 储 指 示 其 后 继 元 素 结 点 的 地 址（位 置）信 息，这 两 部 分 信 息 组 成 的 存 储 映 像 称 为 链 表 的 结 点。结 点 是 链 表 中 存 储 数 据 的 最 小 单 元，每 个 结 点 通 过 指 针 与 其 他 结 点 建 立 逻 辑 关 系，形 成 链 式 结 构。结 点 在 内 存 中 无 需 连 续 存 储，其 顺 序 由 指 针 指 向 决 定。
数 据 域：存 储 数 据 元 素 信 息 的 域，即 存 储 每个 结 点 的 值。
指 针 域：存 储 数 据 元 素 的 直 接 后 继 的 地 址（位 置）的域。
链：指 针 域 中 存 储 的 信 息 称 作 指 针 或 链。
链 式 存 储 结 构：n 个 结 点 链 接 成 一 个 链 表，即 为 线 性 表 的 链 式 存 储 结 构。
线 性 链 表：链 表 中 的 每 个 结 点 中 只 包 含 一 个 指 针 域， 故 又 称 作 线 性 链 表 或 单 链 表。
链 表 定 义
链 表 是 一 种 物 理 存 储 结 构 上 非 连 续、非 顺 序 的 存 储 结 构，数 据 元 素 的 逻 辑 顺 序 是 通 过 链 表 中 的 指 针 链 接 次 序 实 现 的。
单 链 表 定 义
单 链 表 是 一 种 通 过 指 针 串 联 节 点 的 动 态 数 据 结 构，每 个 节 点 包 含 数 据 域 和 指 针 域（指 向 下 一 个 节 点 的 地 址）。与 顺 序 表 相 比，它 无 需 预 先 分 配 连 续 内 存 空 间，插 入 和 删 除 操 作 仅 需 修 改 指 针 指 向，具 有 高 效 的 动态 性。但 其 访 问 节 点 必 须 从 头 遍 历，时 间 复 杂 度 为 O(n)。
存 储 结 构
物 理 结 构
物 理 结 构 是 指 数 据 元 素 及 其 逻 辑 关 系 在 计 算 机 内 存 中 的 具 体 存 储 方 式，实 实 在 在 数 据 在 内 存 中 的 变 化，关 注 的 是 “数 据 如 何 在 硬 件 中 实 际 存 放”。它 是 机 器 视 角 下 的 实 现 模 型，直 接 影 响 数 据 操 作 的 效 率。
逻 辑 结 构
逻 辑 结 构 是 从 数 据 元 素 之 间 的 逻 辑 关 系 角 度 出 发，抽 象 描 述 数 据 元 素 之 间 的 关 联 方 式，不 涉 及 数 据 的 存 储 方 式 和 具 体 实 现。为 了 方 便 理 解，形 象 化 画 出 来 的。它 是 用 户 视 角 下 的 数 据 模 型，关 注 的 是 “数 据 元 素 如 何 相 互 连 接”。
单 链 表 的 操 作 实 现
代 码 全 貌 与 功 能 介 绍
整 个 顺 序表 由 三 个 主 要 文 件 构 成：SList.h、SList.c 和 test.c。这 种 多 文 件 的 架 构 设 计，有 助 于 将 不 同 功 能 模 块 分 离，提 高 代 码 的 可 读 性、可 维 护 性 与 可 扩 展 性。
SList.h
SList.h 包 含 了 单 链 表 所 需 的 头 文 件 引 用、常 量 定 义 以 及 函 数 声 明。
test.c
test.c 是 单 链 表 的 主 逻 辑 文 件，负 责 处 理 用 户 输 入 和 代 码 流 程 的 控 制。
SList.c
SList.c 则 实 现 了 单 链 表 的 具 体 功 能 函 数。
下 面 展 示
完 整 代 码。
读 者 可 以 将 这 段 代 码 复 制 到 自 己 的 编 译 器 中 运 行。
SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//第一种写法
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//指针的类型是结构体
//SListNode* next;C语言不行,C++可以
//STLnode* next;//编译器的查找规则,只能在重定义之后才能使用
}STLNode;
//第2种写法
//typedef int SLTDataType;
//
//struct SListNode
//{
// SLTDataType data;
// struct SListNode* next;//指针的类型是结构体
// //SListNode* next;C语言不行,C++可以
// //STLnode* next;//编译器的查找规则,只能在重定义之后才能使用
//};
//
//typedef struct SListNode STLNode;
//创建结点并将值填入数据域中
STLNode* BuySTLNode(SLTDataType x);
//输出
void STLPrint(STLNode* phead);
//尾插
void STLPushBack(STLNode** phead, SLTDataType x);
//头插
void STLPushFront(STLNode** pphead, SLTDataType x);
//尾删
void STLPopBack(STLNode** phead);
//头删
void STLPopFront(STLNode** pphead);
//单链表查找
STLNode* STLFind(STLNode* pphead, SLTDataType x);
//pos之前插入
void STLInsertFront(STLNode** pphead, STLNode* pos, SLTDataType x);
//pos位置删除
void STLErase(STLNode** pphead, STLNode* pos);
//pos后面插入
void STLInsertAfter(STLNode* pos, SLTDataType x);
//pos位置后面删除
void STLEraseAfter(STLNode* pos);
//链表销毁
void STLDestory(STLNode** pphead);
//函数指针
void STLMiddlePos(int(*pf)(STLNode** pphead, SLTDataType x), STLNode** pphead, int num);
void STLMiddlePush(int(*pf)(STLNode** pphead, SLTDataType x), STLNode** pphead);
//从文件中加载
void STLLoadSList(STLNode** pphead);
//将链表保存到文件
void STLSaveSList(STLNode** pphead);
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void menu()
{
printf("****************************************************\n");
printf("***** 0. STLExit 1. STLPrint *****\n");
printf("***** 2. STLPushBack 3. STLPopBack *****\n");
printf("***** 4. STLPushFront 5. STLPopFront *****\n");
printf("***** 6. STLInsertFront 7. STLErase *****\n");
printf("***** 8. STLInsertAfter 9. STLEraseAfter *****\n");
printf("****************************************************\n");
}
void test()
{
int input = 0;
STLNode* plist = NULL;
STLLoadSList(&plist);
do
{
menu();
printf("请输入你想要进行的操作:>\n");
scanf("%d", &input);
switch (input)
{
case 0:
STLSaveSList(&plist);
STLDestory(&plist);
break;
case 1:
STLPrint(plist);
break;
case 2:
STLMiddlePush(STLPushBack, &plist);
break;
case 3:
STLPopBack(&plist);
STLPrint(plist);
break;
case 4:
STLMiddlePush(STLPushFront, &plist);
break;
case 5:
STLPopFront(&plist);
STLPrint(plist);
break;
case 6:
STLMiddlePos(STLInsertFront, &plist, 6);
break;
case 7:
STLMiddlePos(STLErase, &plist, 7);
break;
case 8:
STLMiddlePos(STLInsertAfter, &plist, 8);
break;
case 9:
STLMiddlePos(STLEraseAfter, &plist, 9);
break;
default:
printf("无效输入,请重新输入\n");
break;
}
} while (input);
}
int main()
{
test();
return 0;
}
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void STLPrint(STLNode* phead)
{
//空的顺序表可以打印,只是数据为空
//assert(phead);//不能
STLNode* cur = phead;
//while(cur)
while (cur != NULL)//cur->next != NULL最后一个数据没有输出,不能写
{
printf("%d->", cur->data);
cur = cur->next;//cur的地址不断覆盖,不能++,不能保证空间是连续的
//一块空间的初始地址和结束地址不一样,一块空间的结束地址和下一块空间的起始地址一样
}
printf("NULL\n");
}
STLNode* BuySTLNode(SLTDataType x)
{
STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
if (newnode == NULL)
{
perror("SLPushBack");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//上一个节点链接下一个节点的地址
//不为空链表的尾插,尾插的本质是原尾节点要存储新的尾节点的地址
void STLPushBack(STLNode** pphead, SLTDataType x)
{
assert(pphead);//*pphead为地址一定不为空,值可以为空
STLNode* newnode = BuySTLNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾---尾结点
STLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
//错误---头结点
//while (tail != NULL)
//{
// tail = tail->next;
//}
//tail = newnode;
}
}
void STLPushFront(STLNode** pphead, SLTDataType x)
{
assert(pphead);
STLNode* newnode = BuySTLNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//一定不能为空,要断言
//pphead
void STLPopBack(STLNode** pphead)
{
//必须有数据才能删除
//检查
assert(pphead);
assert(*pphead);
//if (*pphead == NULL)
//{
// return;
//}
//只有一个节点
//有多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//方法1
//找尾
STLNode* prev = NULL;
STLNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;//tail是局部变量
prev->next = NULL;
//方法2
//STLNode* tail = *pphead;
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}
}
void STLPopFront(STLNode** pphead)
{
//检查
assert(*pphead != NULL);
//if (*pphead == NULL)
//{
// return;
//}
STLNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
STLNode* STLFind(STLNode* pphead, SLTDataType x)
{
STLNode* cur = pphead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void STLInsertFront(STLNode** pphead, STLNode* pos, SLTDataType x)
{
//不能实现尾插
assert(pos);
assert(pphead);
if (pos == *pphead)
{
STLPushFront(pphead, x);
}
else
{
//找到pos的前一个位置
STLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
STLNode* newnode = BuySTLNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void STLErase(STLNode** pphead, STLNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (*pphead == pos)
{
STLPopBack(pphead);
}
else
{
STLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;//可以不写,因为pos为形参
}
}
//pos后面插入
void STLInsertAfter(STLNode* pos, SLTDataType x)
{
assert(pos);
STLNode* newnode = BuySTLNode(x);
newnode->next = pos->next;
pos->next = newnode;
//错误,原因是找不到pos->next
//pos->next = newnode;
//newnode->next = pos->next;
}
//假设有一个链表,只给出pos,让在前面插入,如何实现
//可以先在后面插入,然后交换
//pos位置后面删除
void STLEraseAfter(STLNode* pos)
{
assert(pos);
assert(pos->next);
//方法1
//STLNode * del = pos->next;
//pos->next = pos->next->next;
//free(del);
//del = NULL;
//方法2
STLNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void STLDestory(STLNode** pphead)
{
assert(pphead);
STLNode* cur = *pphead;
while (cur)
{
//逐个释放结点
STLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
void STLMiddlePos(int(*pf)(STLNode** pphead, SLTDataType x), STLNode** pphead, int num)
{
int x = 0;
int y = 0;
STLPrint(*pphead);
if (num == 6)
{
printf("请输入你想要插入的数字:>\n");
scanf("%d", &x);
printf("请输入你想要插入哪个数字的前面:>\n");
scanf("%d", &y);
STLNode* ret = STLFind(*pphead, y);
STLInsertFront(pphead, ret, x);
}
else if (num == 7)
{
printf("请输入你想要删除哪个数字:>\n");
scanf("%d", &x);
STLNode* ret = STLFind(*pphead, x);
STLErase(pphead, ret);
}
else if (num == 8)
{
printf("请输入你想要插入的数字:>\n");
scanf("%d", &x);
printf("请输入你想要插入哪个数字的后面:>\n");
scanf("%d", &y);
STLNode* ret = STLFind(*pphead, y);
STLInsertAfter(ret, x);
}
else
{
printf("请输入你想要删除哪个数字后面的数字:>\n");
scanf("%d", &x);
STLNode* ret = STLFind(*pphead, x);
STLEraseAfter(ret);
}
STLPrint(*pphead);
}
void STLMiddlePush(int(*pf)(STLNode** pphead, SLTDataType x), STLNode** pphead)
{
int x = 0;
printf("请输入你想要插入的数字:>\n");
scanf("%d", &x);
pf(pphead, x);
STLPrint(*pphead);
}
void STLLoadSList(STLNode** pphead)
{
FILE* pf = fopen("SList.txt", "r");
if (pf == NULL)
{
perror("STLLoadSList");
return;
}
STLNode* cur = *pphead;
SLTDataType data = 0;
while (fscanf(pf, "%d", &data) == 1)
{
STLPushBack(pphead, data);
}
fclose(pf);
pf = NULL;
}
void STLSaveSList(STLNode** pphead)
{
FILE* pf = fopen("SList.txt", "w");
if (pf == NULL)
{
perror("STLSaveSList");
return;
}
STLNode* cur = *pphead;
while (cur)
{
fprintf(pf, "%d ", cur->data);
cur = cur->next;
}
fclose(pf);
pf = NULL;
printf("保存文件成功\n");
}
单 链 表 的 功 能 说 明
代 码 效 果 展 示
菜 单 展 示
每 次 循 环 开 始 时 会 显 示 菜 单，内 容 包 括：
STLExit：退 出 程 序 并 将 单 链 表 保 存 到 文 件 中
STLPrint：输 出
STLPushBack：尾 插
STLPopBack：尾 删
STLPushFront：头 插
STLPopFront：头 删
STLFrontInsert：从 一 个 数 的 前 面 插 入
STLErase：擦 除 某 个 指 定 的 数
STLInsertAfter：从 一 个 数 的 后 面 插 入
STLEraseAfter：删 除 指 定 数 的 后 面 的 数 字
退 出 单 链 表（STLExit）
输 入 0 后，程 序 会 将 单 链 表 中 的 信 息 保 存 到 文 件 “SList.txt” 中。释 放 内 存 并 销 毁 顺 序 表， 然 后 退 出 程 序。
输 出 单 链 表（STLPrint）
输 入 1 后，程 序 会 在 屏 幕 上 显 示 目 前 已 经 保 存 的 单 链 表。
尾 插（STLPushBack）
输 入 2 后，程 序 会 提 示 用 户 输 入 插 入 的 数 字。输 入 完 成 后，数 字 被 添 加 到 单 链 表 的 末 尾，然 后 输 出 修 改 后 的 单 链 表。
尾 删（STLPopBack）
输 入 3 后，单 链 表 的 末 尾 的 一 个 数 字 会 被 删 除，然 后 输 出 修 改 后 的 单 链 表。
头 插（STLPushFront）
输 入 4 后，程 序 会 提 示 用 户 输 入 插 入 的 数 字。输 入 完 成 后，数 字 被 添 加 到 单 链 表 的 第 一 个 位 置，然 后 输 出 修 改 后 的 单 链 表。
头 删（STLPopFront）
输 入 5 后，单 链 表 的 第 一 个 位 置 的 数 字 会 被 删 除 并 输 出 删 除 后 的 单 链 表，然 后 输 出 修 改 后 的 单 链 表。
从 某 一 个 数 字 的 前 面 插 入（STLInsertFront）
输 入 6 后，程 序 首 先 输 出 单 链 表，然 后 会 提 示 用 户 输 入 插 入 的 数 字 和 要 插 入 数 字 的 位 置。输 入 完 成 后，数 字 被 添 加 到 单 链 表 的 要 输 入 数 字 的 前 面，然 后 输 出 修 改 后 的 单 链 表。
删 除 指 定 的 数 字（STLErase）
输 入 7 后，程 序 会 提 示 用 户 输 入 想 要 删 除 的 数 字。输 入 完 成 后，想 要 删 除 的 数 字 会 被 清 除，然 后 输 出 修 改 后 的 单 链 表。
从 某 一 个 数 字 的 后 面 插 入（STLInsertAfter）
输 入 8 后，程 序 首 先 输 出 单 链 表，然 后 提 示 用 户 输 入 插 入 的 数 字 和 要 插 入 数 字 的 位 置。输 入 完 成 后，数 字 被 添 加 到 单 链 表 的 要 输 入 数 字 的 后 面，然 后 输 出 修 改 后 的 单 链 表。
删 除 指 定 数 字 后 面 的 数 字（STLEraseAfter）
输 入 9 后，程 序 首 先 输 出 单 链 表，然 后 提 示 用 户 输 入 要 删 除 的 数 字。输 入 完 成 后，要 删 除 数 字 后 面 的 数 字 会 被 删 除，然 后 输 出 修 改 后 的 单 链 表。
代 码 详 解
SList.h
#pragma once
#pragma once 是 一 个 预 处 理 指 令，用 于 防 止 头 文 件 被 重 复 包 含。在 大 型 项 目 中，多 个 源 文 件 可 能 会 包 含 同 一 个 头 文 件，使 用 #pragma once 可 以 确 保 头 文 件 的 内 容 只 被 编 译 一 次，避 免 重 复 定 义 的 错 误。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include 指 令 用 于 引 入 必 要 的 标 准 库 头 文 件：
stdio.h：提 供 标 准 输 入 输 出 函 数，如 printf、scanf 等。
assert.h：提 供 assert 宏，用 于 在 运 行 时 检 查 程 序 的 断 言 条 件。
stdlib.h：提 供 内 存 管 理 函 数（如 malloc、realloc、free）和 其 他 标 准 库 函 数。
typedef int SLTDataType;
#define 指 令 用 于 定 义 一 些 常 量：
typedef int SLTDataType：将 int 重 新 命 名 成 SLTDataType
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //数据域,存储节点数据
struct SListNode* next;//指针域,指向下一个节点
}STLNode;
定 义 了 一 个 名 为 SListNode 的 结 构 体 并 重 新 命 名 为 STLNode，用 于 表 示 整 个 单 链 表：
next：指 向 同 类 型 结 构 体 的 指 针，用 于 连 接 链 表 中 的 节 点。每 个 节 点 通 过 next 指 向 下 一 个 节 点，最 后 一 个 节 点 的 next 通 常 置 为 NULL（表 示 链 表 结 束）。
data：整 数，记 录 当 前 单 链 表 中 的 节 点 数 据。
注 意
1、必 须 使 用 struct 结 构 体 名* 声 明 指 针 域，如 struct SListNode* next;。
2、不 能 直 接 使 用 typedef 后 的 别 名 STLNode* next;因 为 typedef 是 在 结 构 体 声 明 之 后 才 生 效。
//创建结点并将值填入数据域中
STLNode* BuySTLNode(SLTDataType x);
//输出
void STLPrint(STLNode* phead);
//尾插
void STLPushBack(STLNode** phead, SLTDataType x);
//头插
void STLPushFront(STLNode** pphead, SLTDataType x);
//尾删
void STLPopBack(STLNode** phead);
//头删
void STLPopFront(STLNode** pphead);
//单链表查找
STLNode* STLFind(STLNode* pphead, SLTDataType x);
//pos之前插入
void STLInsertFront(STLNode** pphead, STLNode* pos, SLTDataType x);
//pos位置删除
void STLErase(STLNode** pphead, STLNode* pos);
//pos后面插入
void STLInsertAfter(STLNode* pos, SLTDataType x);
//pos位置后面删除
void STLEraseAfter(STLNode* pos);
//链表销毁
void STLDestory(STLNode** pphead);
//函数指针
void STLMiddlePos(int(*pf)(STLNode** pphead, SLTDataType x), STLNode** pphead, int num);
void STLMiddlePush(int(*pf)(STLNode** pphead, SLTDataType x), STLNode** pphead);
//从文件中加载
void STLLoadSList(STLNode** pphead);
//将链表保存到文件
void STLSaveSList(STLNode** pphead);
函 数 声 明，定 义 了 对 单 链 表 进 行 操 作 的 各 个 功 能 函 数：
BuySTLNode：动 态 分 配 内 存 创 建 1 个 新 节 点，初 始 化 数 据 域 为 x，指 针 域 为 NULL。主 要 用 于 插 入 节 点 时 调 用。
STLPrint：遍 历 链 表 并 输 出 每 个 节 点 的 数 据，格 式 为 数 据 -> 数 据 -> NULL。
STLPushBack：在 链 表 尾 部 插 入 新 节 点，数 据 为 x。
STLPushFront：在 链 表 头 部 插 入 新 节 点，数 据 为 x。
STLPopBack：删 除 链 表 尾 部 节 点。
STLPopFront：删 除 链 表 头 部 节 点。
STLFind：遍 历 链 表 查 找 数 据 为 x 的 节 点。
STLInsertFront：在 目 标 节 点 pos 之 前 插 入 新 节 点，数 据 为 x。
STLErase：用 于 从 顺 序 表 中 删 除 指 定 的 数 字。
STLInsertAfter：在 目 标 节 点 pos 之 后 插 入 新 节 点，数 据 为 x。
STLEraseAfter：删 除 目 标 节 点 pos 的 后 继 节 点。
STLDestory：释 放 链 表 所 有 节 点 内 存，并 将 头 指 针 置 为 NULL。
STLMiddlePos：通 过 函 数 指 针 动 态 调 用 插 入 / 删 除 函 数，处 理 用 户 输 入 的 位 置 操 作。
STLMiddlePush：通 过 函 数 指 针 动 态 调 用 插 入 函 数，处 理 用 户 输 入 的 插 入 值。
STLLoadSList：从 文 件 中 读 取 数 据，通 过 尾 插 法 构 建 链 表。
STLSaveSList：将 链 表 数 据 写 入 文 件。
SList.c
遍 历 与 打 印（STLPrint）
void STLPrint(STLNode* phead)
{
//空的顺序表可以打印,只是数据为空
//assert(phead);//不能
STLNode* cur = phead;
//while(cur)
while (cur != NULL)//cur->next != NULL最后一个数据没有输出,不能写
{
printf("%d->", cur->data);
cur = cur->next;//cur的地址不断覆盖,不能++,不能保证空间是连续的
//一块空间的初始地址和结束地址不一样,一块空间的结束地址和下一块空间的起始地址一样
}
printf("NULL\n");
}
注 意
1、允 许 空 链 表（直 接 输 出 NULL），这 里 不 能 断 言，如 果 断 言 程 序 会 报 错。不 需 要 断 言 头 指 针 phead 非 空 的 原 因 是：允 许 空 链 表 作 为 合 法 输 入，如 果 链 表 为 空 则 输 出 NULL。循 环 条 件 cur != NULL 确 保 不 会 访 问 空 指 针，即 使 phead 为 NULL 也 不 会 引 发 错 误。而 顺 序 表 需 要 断 言 是 为 了 检 查 指 针 的 有 效 性，在 空 的 顺 序 表 中 可 能 存 在 野 指 针，头 指 针 phead 是 野 指 针（未 初 始 化 或 指 向 已 释 放 的 内 存），直 接 解 引 用 *phead 会 触 发 未 定 义 行 为。
2、使 用 cur != NULL 而 非 cur->next != NULL，避 免 遗 漏 最 后 一 个 节 点。
3、使 用 cur = cur->next; 而 不 使 用 ++ 的 原 因 是 指 针 的 算 术 运 算 仅 适 用 于 连 续 内 存 的 场 景，此 时 相 邻 元 素 的 地 址 差 是 固 定 的（等 于 单 个 元 素 的 大 小）。单 链 表 的 节 点 地 址 是 动 态 分 配 的，相 邻 节 点 的 地 址 差 不 确 定，无 法 通 过 固 定 偏 移 量 访 问。只 能 通 过 节 点 的 next 指 针 获 取 后 继 节 点 的 地 址，即 cur = cur->next;
总 结
顺 序 表
1、顺 序 表 的 指 针 失 效 风 险 更 高
顺 序 表 的 表 头 指 针 直 接 指 向 内 存 块，若 指 针 无 效（如 NULL 或 野 指 针），第 一 步 访 问 就 会 崩 溃。
2、顺 序 表 的 遍 历 方 式 不 依 赖 后 续 指 针
顺 序 表 通 过 下 标 或 偏 移 量 遍 历，无 需 检 查 每 个 元 素 的 “下 一 个 指 针” 是 否 有 效，因 此 指 针 有 效 性 是 遍 历 的 前 提，必 须 在 开 头 断 言。
单 链 表
1、单 链 表 的 节 点 通 过 指 针 链 接，节 点 在 内 存 中 非 连 续 存 储，每 个 节 点 包 含 数 据 域 和 指 向 下 一 节 点 的 指 针 next。
2、表 头 指 针 可 能 为 NULL（空 链 表），此 时 直 接 返 回 即 可，无 需 访 问 内 存。
节 点 创 建 与 初 始 化（BuySTLNode）
STLNode* BuySTLNode(SLTDataType x)
{
STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
if (newnode == NULL)
{
perror("SLPushBack");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
作 用：动 态 分 配 内 存 并 初 始 化 新 节 点，返 回 节 点 指 针。
内 存 安 全：malloc 后 检 查 NULL，防 止 内 存 分 配 失 败 导 致 程 序 崩 溃。
尾 插
void STLPushBack(STLNode** pphead, SLTDataType x)
{
assert(pphead);//*pphead为地址一定不为空,值可以为空
STLNode* newnode = BuySTLNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾---尾结点
STLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
//错误---头结点
//while (tail != NULL)
//{
// tail = tail->next;
//}
//tail = newnode;
}
}
1、使 用 二 级 指 针 的 原 因 是 因 为 单 链 表 的 头 指 针 本 质 是 一 个 指 针 变 量，单 链 表 的 头 指 针 为 STLNode* plist，它 存 储 的 是 链 表 第 一 个 节 点 的 地 址，函 数 内 部 对 plist 的 修 改 不 会 影 响 实 参 pphead。当 函 数 参 数 为 二 级 指 针
STLNode** pphead 时，pphead 指 向 实 参 plist 的 地 址。通 过 解 引 用 可 以 访 问 并 修 改 实 参 plist 的 值。
2、在 尾 插 时 应 先 创 建 节 点 然 后 遍 历 单 链 表 将 节 点 链 接 起 来。
头 插
void STLPushFront(STLNode** pphead, SLTDataType x)
{
assert(pphead);
STLNode* newnode = BuySTLNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
头 插 时 应 首 先 创 建 新 节 点，然 后 新 节 点 的 next 指 向 原 头 节 点 最 后 更 新 头 指 针 为 新 节 点 地 址。
尾 删
void STLPopBack(STLNode** pphead)
{
//必须有数据才能删除
//检查
assert(pphead);
assert(*pphead);
//if (*pphead == NULL)
//{
// return;
//}
//只有一个节点
//有多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//方法1
//找尾
STLNode* prev = NULL;
STLNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;//tail是局部变量
prev->next = NULL;
//方法2
//STLNode* tail = *pphead;
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}
}
该 函 数 通 过 二 级 指 针 操 作 链 表，在 确 保 链 表 非 空 的 前 提 下，通 过 遍 历 找 到 尾 节 点 及 其 前 驱，释 放 尾 节 点 并 正 确 更 新 指 针，实 现 单 链 表 的 尾 删 操 作。
头 删
void STLPopFront(STLNode** pphead)
{
//检查
assert(*pphead != NULL);
//if (*pphead == NULL)
//{
// return;
//}
STLNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
该 函 数 通 过 二 级 指 针 确 保 链 表 非 空 后，将 头 指 针 更 新 为 原 头 节 点 的 下 一 个 节 点，并 释 放 原 头 节 点 内 存，实 现 单 链 表 的 头 删 操 作。
查 找 数 字
STLNode* STLFind(STLNode* pphead, SLTDataType x)
{
STLNode* cur = pphead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
该 函 数 遍 历 链 表，若 找 到 数 据 域 等 于 x 的 节 点 则 返 回 其 地 址，否 则 返 回 NULL，实 现 单 链 表 的 查 找 操 作。
指 定 数 字 的 后（前） 面 插 入
void STLInsertFront(STLNode** pphead, STLNode* pos, SLTDataType x)
{
//不能实现尾插
assert(pos);
assert(pphead);
if (pos == *pphead)
{
STLPushFront(pphead, x);
}
else
{
//找到pos的前一个位置
STLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
STLNode* newnode = BuySTLNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void STLInsertAfter(STLNode* pos, SLTDataType x)
{
assert(pos);
STLNode* newnode = BuySTLNode(x);
newnode->next = pos->next;
pos->next = newnode;
//错误,原因是找不到pos->next
//pos->next = newnode;
//newnode->next = pos->next;
}
STLInsertFront 函 数 在 给 定 节 点 pos 前 插 入 新 节 点（若 pos 是 头 节 点 则 调 用 头插 法），需 通 过 二 级 指 针 修 改 头 指 针；STLInsertAfter 函 数 在 给 定 节 点 pos 后 插 入 新 节 点，直 接 操 作 pos 的 next 指 针，无 需 二 级 指 针。
删 除 指 定 位 置 后 面 的 数字
void STLEraseAfter(STLNode* pos)
{
assert(pos);
assert(pos->next);
//方法1
//STLNode * del = pos->next;
//pos->next = pos->next->next;
//free(del);
//del = NULL;
//方法2
STLNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
通 过 断 言 确 保 给 定 节 点 pos 及 其 后 继 节 点 存 在，删 除 pos 的 后 继 节 点 并 释 放 其 内 存，实 现 单 链 表 的 指 定 位 置 后 删 除 操 作。
数 据 持 久 化
void STLLoadSList(STLNode** pphead)
{
FILE* pf = fopen("SList.txt", "r");
if (pf == NULL)
{
perror("STLLoadSList");
return;
}
STLNode* cur = *pphead;
SLTDataType data = 0;
while (fscanf(pf, "%d", &data) == 1)
{
STLPushBack(pphead, data);
}
fclose(pf);
pf = NULL;
}
void STLSaveSList(STLNode** pphead)
{
FILE* pf = fopen("SList.txt", "w");
if (pf == NULL)
{
perror("STLSaveSList");
return;
}
STLNode* cur = *pphead;
while (cur)
{
fprintf(pf, "%d ", cur->data);
cur = cur->next;
}
fclose(pf);
pf = NULL;
printf("保存文件成功\n");
}
这 两 个 函 数 实 现 了 单 链 表 的 文 件 读 写 功 能，STLLoadSList 从 文 件 SList.txt 读取 整 数 数 据，通 过 尾 插 法 构 建 链 表；STLSaveSList 将 链 表 中 的 数 据 写 入SList.txt，格 式 为 空 格 分 隔 的 整 数 序 列。两 者 均 包 含 完 整 的 文 件 操 作 错 误 处 理，确 保 内 存 安 全 和 文 件 资 源 释 放。
test.c
菜 单 界 面
void menu()
{
printf("****************************************************\n");
printf("***** 0. STLExit 1. STLPrint *****\n");
printf("***** 2. STLPushBack 3. STLPopBack *****\n");
printf("***** 4. STLPushFront 5. STLPopFront *****\n");
printf("***** 6. STLInsertFront 7. STLErase *****\n");
printf("***** 8. STLInsertAfter 9. STLEraseAfter *****\n");
printf("****************************************************\n");
}
使 用 星 号 (*) 绘 制 边 框，提 供 清 晰 的 视 觉 界 面。
数 字 编 号 对 应 不 同 功 能，方 便 用 户 选 择。
主 循 环 逻 辑
void test()
{
int input = 0;
STLNode* plist = NULL;
STLLoadSList(&plist);
do
{
menu();
printf("请输入你想要进行的操作:>\n");
scanf("%d", &input);
switch (input)
{
case 0:
STLSaveSList(&plist);
STLDestory(&plist);
break;
case 1:
STLPrint(plist);
break;
case 2:
STLMiddlePush(STLPushBack, &plist);
break;
case 3:
STLPopBack(&plist);
STLPrint(plist);
break;
case 4:
STLMiddlePush(STLPushFront, &plist);
break;
case 5:
STLPopFront(&plist);
STLPrint(plist);
break;
case 6:
STLMiddlePos(STLInsertFront, &plist, 6);
break;
case 7:
STLMiddlePos(STLErase, &plist, 7);
break;
case 8:
STLMiddlePos(STLInsertAfter, &plist, 8);
break;
case 9:
STLMiddlePos(STLEraseAfter, &plist, 9);
break;
default:
printf("无效输入,请重新输入\n");
break;
}
} while (input);
}
循 环 控 制：使 用 do-while 确 保 至 少 执 行 一 次 菜 单 选 择。
选 项 处 理：通 过 switch 分 支 调 用 不 同 功 能 函 数。
安 全 退 出：退 出 前 保 存 数 据 并 释 放 内 存，防 止 资 源 泄 漏。
程 序 入 口
int main()
{
test();
return 0;
}
main 函 数 是 程 序 的 入 口 点，调 用 test 函 数 启 动 顺 序 表，最 后 返 回 0 表 示 程 序 正 常 结 束。
总 结
至 此，关 于 数 据 结 构 单 链 表 的 探 索 暂 告 一 段 落，但 你 的 编 程 征 程 才 刚 刚 启 航。编 写 代 码 是 与 计 算 机 逻 辑 深 度 对 话，过 程 中 虽 会 在 结 构 设 计、算 法 实 现 的 困 境 里 挣 扎，但 这 些 磨 砺 加 深 了 对 代 码 逻 辑 和 数 据 组 织 的 理 解。愿 你 合 上 电 脑 后，灵 感 不 断，在 数 据 结 构 的 世 界 里 持 续 深 耕，书 写 属 于 自 己 的 编 程 传 奇，下 一 次 开 启，定 有 全 新 的 精 彩 等 待。小 编 期 待 重 逢，盼 下 次 阅 读 时 见 证 你 们 更 大 的 进 步，共 赴 代 码 之 约！