数据结构之单链表

注本文所示代码均为C一.单链表概念链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。其结构就像一列火车一样淡季时⻋次的⻋厢会相应减少旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉。加上不会影响其他⻋厢每节⻋厢都是独⽴存在的。1. 结点与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“节点/结点”。定义链表就是定义结点结点的组成主要有两个部分当前结点要保存的数据和保存下⼀个结点的地址指针变量。图中指针变量 plist保存的是第⼀个结点的地址我们称plist此时“指向”第⼀个结点如果我们希望plist“指向”第⼆个结点时只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独⽴申请的即需要插⼊数据时才去申请⼀块结点的空间我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。2. 链表的性质1、链式机构在逻辑上是连续的在物理结构上不⼀定连续2、结点⼀般是从堆上申请的3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续结合前⾯学到的结构体知识我们可以给出每个结点对应的结构体代码假设当前保存的结点为整型struct SListNode { int data; // 结点数据数据域 struct SListNode* next; // 指针变量用于保存下一个结点的地址指针域 };在存储整型数据时实际是向操作系统申请内存空间。这块内存不仅用于存储整型值还需存储下一结点的地址若无下一结点则存空地址。遍历链表时只需从当前结点获取下一结点地址即可按序从首结点走到尾结点。二.单链表的模拟实现首先声明结点的类型用typedef重命名int便于后续修改保存的数据类型1.源文件Slist.h链表结构以及函数声明#pragma once #include stdio.h #include stdlib.h #include assert.h // 链表存储的数据类型 typedef int SLTDataType; // 单链表结点结构 typedef struct SListNode { SLTDataType data; // 数据域 struct SListNode* next; // 指向下一个结点 } SLTNode; // 申请新结点 SLTNode* BuySListNode(SLTDataType x); // 打印链表 void SListPrint(SLTNode* phead); // 尾插 void SListPushBack(SLTNode** pphead, SLTDataType x); // 头插 void SListPushFront(SLTNode** pphead, SLTDataType x); // 头删 void SListPopFront(SLTNode** pphead); // 查找结点 SLTNode* SListFind(SLTNode* phead, SLTDataType x); // 在pos位置之前插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在pos位置之后插入 void SListInsertAfter(SLTNode* pos, SLTDataType x); // 删除pos位置的结点 void SListErase(SLTNode** pphead, SLTNode* pos); // 删除pos位置后的结点 void SListEraseAfter(SLTNode* pos); // 销毁链表 void SListDestroy(SLTNode** pphead);以上代码展示单链表的核心结构与接口用 SLTNode 结构体封装数据与指针通过类型重定义让 SLTDataType 适配不同需求。从基础的结点申请 SLTNodeBuy 、打印 SLTNodePrint 到头尾的增删 PushBack / PushFront / PopFront 等再到指定位置的插入 SLTInsert / SLTInsertAfter 、删除 SLTERase / SLTERaseAfter 以及查找、销毁一套完整的单链表操作体系为数据的链式存储与灵活处理筑牢基石是深入理解链表逻辑与实现的关键代码片段 。2.头文件Slist.cpp2.1 申请和打印链表结点#include Slist.h // 创建并返回一个数据为x的新结点 SLTNode* SLTNodeBuy(SLTDataType x) { // 申请结点内存空间 SLTNode* pucur (SLTNode*)malloc(sizeof(SLTNode)); if (pucur) // 内存申请成功 { pucur-data x; // 给结点赋值数据 pucur-next nullptr; // 后继指针置空 return pucur; // 返回新结点地址 } else // 内存申请失败 { perror(malloc fail); // 打印错误信息 exit(1); // 异常退出程序 } } // 遍历打印整个链表 void SLTNodePrint(SLTNode* phead) { SLTNode* pucur phead; // 遍历指针指向头结点 while (pucur) // 遍历到链表末尾为止 { cout pucur-data -; // 打印当前结点数据 pucur pucur-next; // 指针后移 } cout NULL endl; // 打印链表结束标记 }这段代码实现了单链表的基础构建模块SLTNodeBuy 函数负责动态申请内存创建结点初始化数据与指针为链表搭建“基石”SLTNodePrint 函数则通过遍历将链表数据按顺序打印让链表内容“可视化” 。二者一建一显是单链表操作流程里的基础支撑从结点诞生到数据呈现逐步搭建起链表使用的基本逻辑 。注nullptr和NULL是一个效果nullptr是C语法NULL是C语言语法2.2 链表的尾插和头插// 链表尾部插入节点函数 // 参数pphead 二级指针指向头指针的地址x 要插入节点的数据 void SLTNodePushBack(SLTNode** pphead, SLDataType x) { // 断言防止二级指针为空避免非法访问 assert(pphead); // 创建新节点数据为x SLTNode* node SLTNodeBuy(x); // 判断头指针是否为空链表是否为空 if (*pphead nullptr) { // 链表为空新节点作为头节点 *pphead node; } else { // 链表不为空定义遍历指针pcur指向头节点 SLTNode* pcur *pphead; // 循环找到尾节点next指针为null的节点 while (pcur-next) { pcur pcur-next; } // 尾节点的next指向新节点完成尾部插入 pcur-next node; } } // 链表头部插入节点函数 // 参数pphead 二级指针指向头指针的地址x 要插入节点的数据 void SLTNodePushFront(SLTNode** pphead, SLDataType x) { // 断言防止二级指针为空避免非法访问 assert(pphead); // 创建新节点数据为x SLTNode* node SLTNodeBuy(x); // 新节点的next指向原头节点 node-next *pphead; // 头指针更新为新节点完成头部插入 *pphead node; }这段代码聚焦单链表的头尾插入逻辑SLTNodePushBack 先判链表是否为空空则新结点作头否则遍历找尾结点链接新结点实现尾插SLTNodePushFront 更简洁新结点直接链原头结点再更新头指针完成头插。两种插入方式精准覆盖链表数据添加的首尾场景是构建链表动态结构的关键操作 。2.3 链表的尾删和头删// 链表尾删删除链表最后一个节点 void SLTNodePopBack(SLTNode** pphead) { // 断言二级指针非空 链表不为空 assert(pphead *pphead); SLTNode* pcur *pphead; // 遍历指针从头节点开始 // 情况1链表只有1个节点 if (pcur-next nullptr) { free(*pphead); // 释放头节点内存 *pphead nullptr; // 头指针置空链表置空 } else { SLTNode* prev nullptr;// 保存尾节点的前一个节点 // 循环找到尾节点pcur-next为空 while (pcur-next) { prev pcur; pcur pcur-next; } prev-next nullptr; // 前驱节点断链成为新尾节点 free(pcur); // 释放原尾节点内存 pcur nullptr; // 指针置空防止野指针 } } // 链表头删删除链表第一个节点 void SLTNodePopFront(SLTNode** pphead) { // 断言二级指针非空 链表不为空 assert(pphead *pphead); // 保存原头节点的下一个节点注意运算符优先级* - SLTNode* next (*pphead)-next; free(*pphead); // 释放原头节点内存 *pphead next; // 头指针指向新头节点 }以上代码实现单链表的头尾删除操作SLTNodePopBack 先断言确保有效再分链表仅有一个结点和多个结点情况前者直接释放并置空后者遍历找尾结点前驱断链释放SLTNodePopFront 则简洁处理保存头结点后继释放原头结点并更新头指针。两种删除逻辑精准维护链表结构是链表动态管理的基础实现 。2.4 链表结点的查找// 链表查找节点函数 // 参数pcur 头指针x 要查找的数据 void SLTNodeFind(SLTNode* phead, SLDataType x) { // 断言头指针非空避免空指针访问 assert(phead); // 定义遍历指针pcur初始指向头节点 SLTNode* pcur phead; // 循环遍历链表注意原代码条件为pcur-next会跳过最后一个节点 while (pcur-next) { // 指针后移遍历下一个节点 pcur pcur-next; // 检查当前节点数据是否为目标值 if (pcur-data x) { cout 找到了 endl; // 找到目标节点输出提示 exit(1); // 退出程序 } } // 遍历完链表未找到目标节点 cout 未找到; exit(1); // 退出程序 }以上代码中的单链表查找函数从断言入参合法性开始通过指针遍历链表结点一旦发现目标数据立即输出“找到了”并终止程序遍历结束未匹配输出“未找到”同样终止。逻辑直接用 exit 强制结束虽简单却也让流程在找到或遍历完后干脆收尾是基础查找功能的朴素实现 。2.5 指定位置前插入和指定位置后插入// 在pos节点**前面**插入数据x的新节点 // pphead头指针二级指针pos指定插入位置节点x新节点数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x) { // 断言链表非空 pos节点有效 assert(*pphead pos); // 创建数据为x的新节点 SLTNode* node SLTNodeBuy(x); SLTNode* prev *pphead; // 保存pos的前驱节点 SLTNode* pcur *pphead; // 遍历指针 // 如果pos是头节点直接调用头插接口 if (pos *pphead) { SLTNodePushFront(pphead, x); } else { // 循环找到pos的前驱节点pcur-next pos while (pcur-next ! pos) { prev pcur; pcur pcur-next; } // 前驱节点连接新节点新节点连接pos完成前插 prev-next node; node-next pcur; } } // 在pos节点**后面**插入数据x的新节点 // pos指定插入位置节点x新节点数据 void SLTInsertAfter(SLTNode* pos, SLDataType x) { // 断言pos节点有效非空 assert(pos); // 创建数据为x的新节点 SLTNode* node SLTNodeBuy(x); // 保存pos原来的后继节点 SLTNode* pcur pos-next; // pos连接新节点 pos-next node; // 新节点连接原后继节点完成后插 node-next pcur; }以上代码实现单链表两种插入逻辑SLTInsert 处理指定位置前插入先断言合法性创建新结点区分插入位置是否为头结点非头结点时遍历找前驱完成链接SLTInsertAfter 则简洁实现指定位置后插入新结点链入 pos 后继让链表插入操作覆盖不同场景是灵活构建链表结构的实用函数 。2.6 指定位置删除和指定位置后删除// 删除pos指向的节点 // pphead头指针二级指针pos待删除节点 void SLTErase(SLTNode** pphead, SLTNode* pos) { // 断言链表非空 pos节点有效 assert(*pphead pos); // 如果pos是头节点直接调用头删接口 if (pos *pphead) { SLTNodePopFront(pphead); } else { SLTNode* pcur *pphead; // 循环找到pos的前驱节点pcur-next pos while (pcur-next ! pos) { pcur pcur-next; } // 前驱节点跳过pos连接pos的后继 pcur-next pos-next; free(pos); // 释放pos节点内存 pos nullptr; // 指针置空防止野指针 } } // 删除pos节点**后面**的节点 // pos指定节点不能是尾节点 void SLTEraseAfter(SLTNode* pos) { // 断言pos非空 pos有后继节点否则无法删除 assert(pos pos-next); SLTNode* del pos-next; // 保存待删除的后继节点 pos-next del-next; // pos跳过待删节点连接后继的后继 free(del); // 释放待删节点内存 del NULL; // 指针置空防止野指针 }以上代码实现单链表结点删除功能SLTErase 处理指定结点删除先断言有效性若为头结点则调用头删函数否则遍历找前驱断链释放SLTEraseAfter 专注删除指定结点后继断言后继存在后保存、断链、释放两种删除逻辑覆盖不同场景保障链表结构动态维护 。2.7 销毁链表// 销毁整个单链表释放所有节点内存 // pphead头指针二级指针 void SListDestroy(SLTNode** pphead) { assert(*pphead); // 断言链表非空 SLTNode* pcur *pphead; // 遍历指针从头节点开始 while (pcur) // 遍历直到链表末尾 { SLTNode* next pcur-next; // 保存当前节点的下一个节点 free(pcur); // 释放当前节点内存 pcur next; // 指针后移继续遍历 } pcur NULL; // 遍历指针置空防止野指针 }以上代码中的 SListDestroy 函数是单链表的“收尾清理工”通过断言确保链表存在用指针针遍历每次先保存下⼀结点再释放当前结点逐步摧毁链表最后置空指针避免野指针完成单链表内存的有序回收让动态分配的资源“有始有终” 。3. 测试文件3.1 测试代码如下#includeSlist.h // 链表功能测试函数 void test1() { cout 单链表初始化及打印endl; SLTNode* node1SLTNodeBuy(1); // 创建数据为1的节点 SLTNode* node2 SLTNodeBuy(2); // 创建数据为2的节点 SLTNode* node3 SLTNodeBuy(3); // 创建数据为3的节点 SLTNode* node4 SLTNodeBuy(4); // 创建数据为4的节点 node1-next node2; // 节点1连接节点2 node2-next node3; // 节点2连接节点3 node3-next node4; // 节点3连接节点4 node4-next NULL; // 尾节点置空 SLTNodePrint(node1); // 打印初始化链表 cout 单链表的尾插 endl; SLTNodePushBack(node1, 44); // 尾部插入数据44 SLTNodePrint(node1); // 打印尾插后链表 cout 单链表的头插 endl; SLTNodePushFront(node1, 11); // 头部插入数据11 SLTNodePrint(node1); // 打印头插后链表 cout 在node3之前插入数据33 endl; SLTInsert(node1, node3, 33); // node3节点前插入数据33 SLTNodePrint(node1); // 打印插入后链表 } // 主函数入口 int main() { test1(); // 执行链表测试 return 0; }以上代码是单链表功能的实战检验test1 函数里手动构建链表结点并串联接着依次用尾插、头插、指定位置前插入等操作配合打印函数直观呈现单链表增删逻辑。main 函数调用 test1 让链表从构建到操作的完整流程跑通是验证单链表功能实现的简洁用例 。3.2 测试结果如下图所示调试控制台输出清晰展现单链表操作流程初始化构建 1→2→3→4 链表经尾插添 44、头插加 11 再在 node3 前插入 33 每步操作后链表结构直观呈现完美验证尾插、头插、指定位置插入功能是代码逻辑与实际效果的生动映射 。