零基础吃透静态链表（数组模拟链表）：从原理到代码，新手全疑问一次性解决

本文面向刚入门数据结构、已掌握动态链表但看不懂静态链表的新手全程从已知到未知循序渐进拆解所有核心知识点、代码逻辑和新手高频误区看完就能彻底吃透静态链表。目录什么是静态链表和动态链表的核心区别静态链表的核心规则新手必记静态链表核心函数逐行精讲新手最容易踩的 8 个误区 疑问全解答静态链表完整可运行示例核心知识点总结一、先搞懂什么是静态链表和动态链表有什么区别我们最开始都是先学会了动态链表再接触静态链表所以已经掌握的知识入手拉齐认知。1.1 回顾动态链表动态链表的每个结点是通过malloc在堆上动态分配的结构体和核心逻辑如下// 动态链表结点结构 typedef struct Node { int data; // 存放有效数据 struct Node *next; // 指针存下一个结点的内存地址 } Node;核心逻辑用next指针存下一个结点的内存地址把结点串成链表空指针用NULL表示 “没有下一个结点”即链表结尾内存管理结点用malloc动态申请free动态释放1.2 静态链表的定义与核心设计思想静态链表本质就是用数组来模拟链表的结构也叫数组模拟链表。它的出现是为了解决早期编程语言没有指针如早期 BASIC无法实现链表的问题现在学习它是为了掌握「用下标模拟指针」的设计思想这在内存池、缓存设计、嵌入式开发等场景中应用广泛。静态链表的核心设计提前申请一块固定大小的数组作为整个链表的「内存池」数组的每个元素就是一个链表结点不用真实的内存指针而是用数组下标来模拟next指针这个「伪指针」我们叫它cur游标数组里的结点分为两类一类存有效数据叫数据链表另一类是未使用的空闲结点叫备用链表 / 空闲结点池1.3 静态链表的结构体定义静态链表的结点结构体国内教材通用的标准写法如下// 静态链表的最大容量即数组的总长度 #define MAXSIZE 100 // 静态链表结点结构 typedef struct { int data; // 存放有效数据和动态链表的data完全一致 int cur; // 游标存下一个结点的数组下标替代动态链表的next指针 } SNode, SLinkList[MAXSIZE];其中SLinkList[MAXSIZE]就是定义了一个长度为MAXSIZE的数组每个元素都是SNode类型的结点也就是我们的整个「内存池」space。二、静态链表的核心规则新手必记这是你看懂所有代码、避开所有误区的基础必须先记牢。2.1 cur 的本质用数组下标模拟 next 指针cur变量里存的永远是下一个结点在数组里的下标而不是数值本身举个最直观的例子代码space[1].cur 3;的含义是下标为 1 的结点它的下一个结点是数组里下标为 3 的元素也就是space[3]它完全等价于动态链表的p-next q;p 指向 1 号结点q 指向 3 号结点额外说明数组下标从 0 开始计数因此数组的 0 号位置 下标为 0 的元素 space[0]数组的 3 号位置 下标为 3 的元素 space[3]以此类推完全对应无任何偏移。2.2 空指针的约定不同教材的差异说明动态链表用NULL表示空指针静态链表则用一个特殊数字表示 “没有下一个结点”不同教材 / 代码的约定不同但核心逻辑完全一致只要同一套代码内约定统一即可表格约定类型空指针表示适用场景教材通用版严蔚敏《数据结构》0国内高校最常用的经典约定0 号结点不存数据cur0代表链表结尾通用简化版-1避免和 0 号下标冲突新手更容易理解特殊标记版-2专门用cur-2标记「该结点是空闲结点」方便快速判断结点状态本文全程采用严蔚敏教材的经典约定用0表示空指针对应动态链表的NULL0 号结点不存储有效数据专门作为备用链表的头结点2.3 核心设计双链表共用同一数组 space这是新手最困惑的问题数据链表和备用链表不是两个链表吗为什么都用同一个space数组核心逻辑space数组就是一块提前申请好的「内存池」数据链表和备用链表只是这块内存池里两种不同角色的结点它们共用同一块数组空间通过cur指针分别串成两条完全独立的链表。我们给两条链表做明确的职责划分1备用链表空闲结点池作用管理数组里所有未被使用的空闲结点等价于动态链表的「堆内存」头指针固定为space[0].cur永远指向备用链表的第一个空闲结点结尾用cur0表示备用链表为空无可用空闲结点核心操作Malloc_SL分配结点从这里取结点Free_SL回收结点把不用的结点还回来2数据链表作用存储有效数据功能和动态链表完全一致头指针必须单独用一个变量保存比如int data_head;绝对不能用space[0].cur结尾用cur0表示数据链表的结尾核心操作插入、删除、遍历逻辑和动态链表完全一致仅把next指针替换为cur下标30 号结点的专属职责必须明确0 号结点永远不存储有效数据它的唯一作用就是作为备用链表的头结点管理整个空闲结点池。这也是数据链表的头结点不能是 0 号的核心原因0 号结点已经被备用链表占用它的cur永远指向备用链表的第一个空闲结点和数据链表没有任何关系。三、静态链表核心函数逐行精讲新手必看这一部分拆解最开始可能看不懂的 3 个核心函数每一行都配逻辑类比和状态模拟看完就能彻底懂。3.1 初始化函数InitSpace_SL把数组连成备用链表函数作用把整个space数组的所有结点通过cur指针串成一条备用链表完成静态链表的初始化提前准备好完整的空闲结点池。// 初始化静态链表的备用链表 void InitSpace_SL(SLinkList space) { // 将一维数组space中各分量链成一个备用链表space[0].cur为头指针 // 0表示空指针 for (int i 0; i MAXSIZE - 1; i) { space[i].cur i 1; } space[MAXSIZE - 1].cur 0; }逐行拆解for 循环space[i].cur i 1;让数组里的第i个结点指向第i1个结点完成链表的串联i0时space[0].cur 1→ 0 号结点指向 1 号结点i1时space[1].cur 2→ 1 号结点指向 2 号结点...直到iMAXSIZE-2时space[MAXSIZE-2].cur MAXSIZE-1→ 倒数第二个结点指向最后一个结点space[MAXSIZE - 1].cur 0;让数组最后一个结点的cur0即指向空指针作为备用链表的结尾。初始化后的状态模拟以MAXSIZE6为例表格数组下标 ispace[i].cur所属链表说明01备用链表头指向备用链表的第一个结点 1 号12备用链表空闲结点23备用链表空闲结点34备用链表空闲结点45备用链表空闲结点50备用链表尾链表结尾指向空指针 0此时备用链表链路0 → 1 → 2 → 3 → 4 → 5 → 0数据链表为空。3.2 结点分配函数Malloc_SL从备用链表取空闲结点对应动态链表的malloc函数作用是从备用链表中取出一个空闲结点返回它的下标给数据链表使用。// 分配结点若备用空间链表非空则返回分配的结点下标否则返回0 int Malloc_SL(SLinkList space) { // 步骤1取出备用链表的第一个空闲结点的下标 int i space[0].cur; // 步骤2如果备用链表非空还有空闲结点 if (space[0].cur) { // 步骤3把备用链表的头指针后移到下一个空闲结点 space[0].cur space[i].cur; } // 步骤4返回分配到的结点下标 return i; }逻辑类比 逐行拆解这个函数的本质就是从单链表的头部删除一个结点这个单链表就是备用链表。用你熟悉的动态链表类比瞬间就能懂动态链表删除头结点 → 先存下头结点地址 → 把头指针移到头结点的 next → 返回原头结点地址静态链表分配空闲结点 → 先存下第一个空闲结点的下标i→ 把备用链表头指针space[0].cur移到i的下一个结点 → 返回i分配过程模拟基于上面的初始化状态我们执行Malloc_SL(space)分配第一个结点步骤 1i space[0].cur→i1步骤 2space[0].cur1≠0进入 if 判断步骤 3space[0].cur space[1].cur→space[0].cur2步骤 4返回i1分配后的状态表格数组下标 ispace[i].cur所属链表说明02备用链表头现在指向备用链表的第一个结点 2 号1待设置数据链表已被分配可用来存储数据23备用链表空闲结点34备用链表空闲结点45备用链表空闲结点50备用链表尾链表结尾此时备用链表链路0 → 2 → 3 → 4 → 5 → 0数据链表已分配 1 号结点我们可以用data_head1记录数据链表的头。3.3 结点回收函数Free_SL把不用的结点还回备用链表对应动态链表的free函数作用是把数据链表中不再使用的结点回收到备用链表中让它重新变成可分配的空闲结点。// 回收结点将下标为k的空闲结点回收到备用链表 void Free_SL(SLinkList space, int k) { // 步骤1让被回收的结点k指向当前备用链表的第一个结点 space[k].cur space[0].cur; // 步骤2让备用链表的头指针指向被回收的结点k space[0].cur k; }逻辑类比 逐行拆解这个函数的本质就是在单链表的头部插入一个结点这个单链表还是备用链表。继续用动态链表类比动态链表头插新结点 → 让新结点的 next 指向原头结点 → 把头指针指向新结点静态链表回收结点 k → 让 k 的 cur 指向原备用链表的第一个结点space[0].cur→ 把备用链表头指针space[0].cur指向 k回收过程模拟基于上面的分配状态现在我们回收 1 号结点执行Free_SL(space, 1)步骤 1space[1].cur space[0].cur→space[1].cur2步骤 2space[0].cur 1→space[0].cur1回收后的状态表格数组下标 ispace[i].cur所属链表说明01备用链表头现在指向备用链表的第一个结点 1 号12备用链表已被回收变回空闲结点23备用链表空闲结点34备用链表空闲结点45备用链表空闲结点50备用链表尾链表结尾此时备用链表链路回到初始化状态0 → 1 → 2 → 3 → 4 → 5 → 01 号结点被成功回收。四、新手最容易踩的 8 个误区 疑问全解答这里汇总了入门阶段的所有核心疑问一次性彻底解决。误区 1数据链表和备用链表是两个独立的数组错误它们是共用同一个space数组的两条独立链表只是数组里的结点分为两种角色被数据链表的cur串起来的结点就是数据结点用来存有效数据被备用链表的cur串起来的结点就是空闲结点用来等待分配它们的区别仅在于cur指向的链路不同本质都是space数组里的元素。误区 20 号结点是数据链表的头结点错误0 号结点的唯一职责是作为备用链表的头结点永远不存储有效数据。数据链表的头结点必须用一个单独的变量比如int data_head来保存和 0 号结点没有任何关系。误区 3可以通过space[0].cur找到数据链表的第一个结点完全错误这是新手最核心的误区space[0].cur永远只指向备用链表的第一个空闲结点和数据链表没有任何关系。举个例子你分配了 1 号结点作为数据链表的头那么data_head1此时space[0].cur2指向的是备用链表的第一个结点 2 号和数据链表的头 1 号完全无关你永远只能通过自己定义的data_head变量找到数据链表的第一个结点。误区 4备用链表的结点一定是连续的下标 1 一定是备用链表的开始错误初始化时备用链表是连续的0→1→2→3→4→5→0此时下标 1 是备用链表的开始但执行多次分配和回收后备用链表的顺序会被完全打乱变成不连续的比如你先分配 1、2、3 号结点再回收 2 号结点此时备用链表的链路是0→2→4→5→0备用链表的第一个结点是 2 号而非 1 号结点也不是连续的。误区 5space[i].cur 3是指向数值 3错误space[i].cur 3的含义是让 i 号结点指向数组里下标为 3 的那个结点space[3]而非指向数值 3 本身。cur里存的永远是数组的下标也就是下一个结点的「位置」不是数据值。误区 6不同教材的空指针约定不一样哪个是对的没有对错之分只是约定不同核心逻辑完全一致。不管是用 0、-1 还是 - 2 表示空指针本质都是用一个特殊数字表示 “没有下一个结点”。只要你在同一套代码里保持约定统一就不会有任何问题。新手入门建议先掌握严蔚敏教材的经典约定cur0表示空这是国内数据结构课程、考试最常用的版本。疑问 7怎么区分数组里的结点是数据结点还是空闲结点有两种通用判断方法根据你的实现约定选择经典方法严蔚敏教材看结点是否在备用链表的cur链路上如果一个结点从space[0].cur出发顺着cur能找到那它就是空闲结点如果一个结点不在备用链表链路里但从data_head出发顺着cur能找到那它就是被使用的数据结点标记方法用特殊的cur值标记空闲结点比如约定cur-2表示该结点是空闲结点只要结点的cur-2就是空闲的否则就是被使用的。这种方法判断更简单但会占用一个特殊的cur值。疑问 8静态链表到底有什么用为什么不直接用动态链表静态链表的核心优势和不可替代的使用场景无指针环境早期无指针的编程语言只能用数组模拟链表固定内存池提前申请固定大小的数组不会出现动态内存分配的内存碎片问题在嵌入式、单片机等内存受限的场景中广泛应用高性能结点的分配和回收都是 O (1) 时间复杂度比malloc/free快很多在高频分配回收的场景中优势明显持久化存储静态链表的数组可以直接写入磁盘不需要处理指针的序列化问题在简单的持久化场景中非常实用五、静态链表完整可运行示例下面是一套完整可直接运行的代码包含静态链表的初始化、结点分配、尾插法插入、遍历、回收全流程可以直接运行观察每一步的状态变化。#include stdio.h // 静态链表最大容量 #define MAXSIZE 10 // 静态链表结点结构 typedef struct { int data; int cur; } SNode, SLinkList[MAXSIZE]; // 1. 初始化备用链表 void InitSpace_SL(SLinkList space) { for (int i 0; i MAXSIZE - 1; i) { space[i].cur i 1; } space[MAXSIZE - 1].cur 0; } // 2. 分配结点 int Malloc_SL(SLinkList space) { int i space[0].cur; if (space[0].cur) { space[0].cur space[i].cur; } return i; } // 3. 回收结点 void Free_SL(SLinkList space, int k) { space[k].cur space[0].cur; space[0].cur k; } // 4. 数据链表尾插法插入元素 int ListInsert_Tail(SLinkList space, int *data_head, int val) { // 分配新结点 int new_node Malloc_SL(space); if (new_node 0) { printf(备用链表为空分配失败\n); return -1; } // 给新结点赋值 space[new_node].data val; space[new_node].cur 0; // 新结点作为尾结点cur0 // 如果数据链表为空新结点作为头结点 if (*data_head 0) { *data_head new_node; return 0; } // 找到数据链表的尾结点 int p *data_head; while (space[p].cur ! 0) { p space[p].cur; } // 把新结点插入到尾部 space[p].cur new_node; return 0; } // 5. 遍历数据链表 void ListTraverse(SLinkList space, int data_head) { if (data_head 0) { printf(数据链表为空\n); return; } int p data_head; printf(数据链表元素); while (p ! 0) { printf(%d , space[p].data); p space[p].cur; } printf(\n); } // 主函数测试静态链表 int main() { SLinkList space; int data_head 0; // 数据链表的头指针初始为空0 // 1. 初始化静态链表 InitSpace_SL(space); printf( 静态链表初始化完成 \n); // 2. 插入元素 ListInsert_Tail(space, data_head, 10); ListInsert_Tail(space, data_head, 20); ListInsert_Tail(space, data_head, 30); printf( 插入元素10、20、30完成 \n); // 3. 遍历数据链表 ListTraverse(space, data_head); // 4. 查看备用链表的头结点 printf(当前备用链表的第一个空闲结点下标%d\n, space[0].cur); return 0; }运行结果 静态链表初始化完成 插入元素10、20、30完成 数据链表元素10 20 30 当前备用链表的第一个空闲结点下标4代码核心说明这里的data_head就是我们单独定义的、用来保存数据链表头结点下标的变量所有对数据链表的操作都要通过这个变量进行space[0].cur只用来管理备用链表和数据链表完全无关整个操作逻辑和动态链表完全一致仅把next指针替换为cur下标六、总结静态链表核心知识点一句话记忆核心本质静态链表就是用数组模拟链表用数组下标cur模拟next指针双链表设计同一个space数组里有两条独立的链表存数据的数据链表、管空闲的备用链表0 号结点职责永远是备用链表的头结点不存有效数据space[0].cur永远指向备用链表的第一个空闲结点数据链表头必须单独用变量保存和 0 号结点无关核心操作初始化是把数组连成备用链表分配是从备用链表头部删结点回收是往备用链表头部插结点空指针约定经典约定用 0 表示空指针不同教材约定不同核心逻辑完全一致如果这篇文章帮你彻底搞懂了静态链表欢迎点赞、收藏、关注如果还有任何疑问欢迎在评论区留言我会一一解答。