简介这份资源是头歌平台“顺序表链表循环队列的基本操作和应用”实训题目的参考答案文档面向正在学习数据结构、需要完成在线作业或期末复习的高校学生。内容围绕顺序表、链表和循环队列三类线性结构展开覆盖插入、删除、查找、队列初始化、入队出队等核心操作并配有可运行的C/C代码实现便于对照调试与理解底层逻辑。文档不仅给出顺序表插入删除时的元素移动处理也展示了链表节点链接式修改以及循环队列中front、rear指针的循环管理方法有助于理解不同物理存储结构在相同操作上的效率差异。整个压缩包仅包含1个docx文档大小约99KB属于轻量级答案型资料打开即可查阅全部操作函数与实现思路。该资源已有10913人浏览学习可见其对同类学习者具有较高的参考价值。通过下载这份文档读者既能快速核对头歌平台相关题目的作答结果也能借助代码注释与函数模块梳理三类结构的算法步骤适合自学自查和考前强化使用。1. 顺序表、链表、循环队列为什么头歌实训总把这三关连在一起考打开头歌实践教学平台的数据结构实训第一节就是顺序表、链表、循环队列三件套。很多人上来就翻车不是不会写代码而是没搞懂平台到底在考什么。线性表是数据结构的基础顺序表用连续数组存链表用节点指针串循环队列则解决数组空间复用问题。这三关挨在一起本质是让你把“存储结构”和“逻辑结构”这对关系彻底想明白。这篇文章只讲一件事怎么写出能被判题引擎接受、又能应对边界用例的代码。2. 顺序表的基本操作从建表到插入删除四段代码说清边界顺序表的核心操作就是建表、插入、删除、查找。代码不多但边界条件一个都不能错。最常见的翻车点是位置参数到底从 0 还是从 1 开始算以及删除后 length 要不要减。2.1 结构体定义与建表length 存的是个数不是最大下标头歌的顺序表关卡一般要求你手写结构体和建表函数。我习惯用动态数组这样后面做并集、去重测试不用反复改 MAXSIZE。#include stdio.h #include stdlib.h #define INIT_SIZE 10 typedef struct { int *data; // 动态数组首地址 int length; // 当前元素个数 int capacity; // 当前容量 } SeqList; void initList(SeqList *L) { L-data (int*)malloc(INIT_SIZE * sizeof(int)); L-length 0; L-capacity INIT_SIZE; }这里的 length 是“已经存了多少个元素”不是“最后一个元素的下标”。举个例子空的顺序表 length 0但你插入第一个元素时它放在 data[0]下标是 length - 1。如果你把 length 当成最大下标插入和删除的位置判断就全乱了。capacity 是容量length 达到 capacity 时必须扩容否则下一次插入就越界。建表还有一个常见写法是直接读入 n 个元素循环调用插入函数。但插入函数每次都从尾部追加复杂度是 O(1)和读入顺序一致。注意一点动态数组即使初始化了也一定要在 insert 函数里写扩容分支否则只测 10 个元素没问题换一批大数据量的评测用例立刻段错误。2.2 按位置插入从后往前挪这一步写错就是整体覆盖插入操作是顺序表最重要的边界测试点。我一般把用户传来的位置定义为“从 1 开始的逻辑位置”也就是说第 1 个元素的下标是 0。这样符合人的直觉也符合大多数实训题目的描述。int insertList(SeqList *L, int pos, int value) { if (pos 1 || pos L-length 1) { return 0; // 位置非法 } if (L-length L-capacity) { // 扩容容量翻倍 int *newData (int*)realloc(L-data, L-capacity * 2 * sizeof(int)); if (newData NULL) return 0; L-data newData; L-capacity * 2; } // 从最后一个元素开始逐个后移 for (int i L-length; i pos; i--) { L-data[i] L-data[i - 1]; } L-data[pos - 1] value; L-length; return 1; }循环里i L-length; i pos; i--当 pos 1 时i 从 length 一直降到 1把 data[0] 的值复制到 data[1]最后在 data[0] 写新值。如果你把循环写成i pos - 1就会多挪一个位置导致 data[pos-1] 被自己的旧值覆盖插入结果变成重复一个元素。扩容用 realloc 是省事的做法但注意realloc 失败会返回 NULL直接赋值给 L-data 会把原指针丢了。所以我先用临时变量接返回值。头歌判题时如果内存不足经常报运行时错误这个细节值得提前防着。2.3 按位置删除覆盖方向与插入相反别忘了 length 减一删除操作同样拿位置参数做文章。逻辑位置从 1 开始但数组下标从 0 开始所以要把 pos 转成下标 pos - 1。int deleteList(SeqList *L, int pos) { if (pos 1 || pos L-length) { return 0; } // 从删除位置开始用后一个元素覆盖前一个 for (int i pos; i L-length; i) { L-data[i - 1] L-data[i]; } L-length--; return 1; }我见过有人把删除循环写成for (int i pos - 1; i L-length - 1; i)意思是只挪到倒数第二个元素。这种写法结果是等价的但下标上不太好读容易在写边界条件时晕。直接用i pos; i L-length更直观从逻辑位置 pos 对应的元素开始覆盖直到最后一个元素。真正容易踩的坑是删最后一个元素。pos L-length 时循环一次都不执行但 length-- 必须执行。如果函数提前写错把删除最后一个元素的情况直接 return 了那么这个顺序表就永远删不掉末位元素。自测时一定要删一次最后一个元素看看。2.4 顺序表应用求两个集合的并集考验的是查重而非插入头歌热词里有“求解一般集合的并集问题用顺序表实现”这是顺序表应用关的典型题。思路很简单先复制第一个集合再把第二个集合里不存在于结果的元素追加进去。难点在“是否存在”的判断而不是插入本身。int unionList(SeqList *A, SeqList *B, SeqList *C) { initList(C); // 先复制 A for (int i 0; i A-length; i) { insertList(C, C-length 1, A-data[i]); } // 遍历 B不重复才追加 for (int i 0; i B-length; i) { int exist 0; for (int j 0; j C-length; j) { if (C-data[j] B-data[i]) { exist 1; break; } } if (!exist) { insertList(C, C-length 1, B-data[i]); } } return C-length; }这里不用单独写 find 函数直接在并集里线性查重就行。集合元素本身无序别用二分查找因为你没法保证序列有序。头歌评测里可能会出现两个完全相同的集合或者其中一个为空集。空集情况下C 的长度应该等于另一个集合的长度代码里先复制 A 再处理 B就能自然应对。3. 链表的基本操作与应用头插、尾插、逆序与差集的指针套路链表比顺序表难在“看不见”的 next 指针。只要你画清楚每个时刻谁指向谁代码其实是机械操作。头歌链表关卡一般分建表、插入、删除、逆序、差集这几关下面从建表开始讲。3.1 头插法与尾插法建表方向决定了你的链表是正序还是逆序链表结构体定义基本固定带不带头节点要看题目要求。头歌大多数题目用带头节点的链表因为插入删除不用单独处理头指针统一先找前驱。typedef struct Node { int data; struct Node *next; } Node, *LinkList;尾插法建表保持输入顺序LinkList createByTail(int arr[], int n) { LinkList head (LinkList)malloc(sizeof(Node)); head-next NULL; Node *tail head; for (int i 0; i n; i) { Node *s (Node*)malloc(sizeof(Node)); s-data arr[i]; s-next NULL; tail-next s; tail s; } return head; }头插法建表每次都把新节点插到头节点后面输入顺序会变成逆序LinkList createByHead(int arr[], int n) { LinkList head (LinkList)malloc(sizeof(Node)); head-next NULL; for (int i 0; i n; i) { Node *s (Node*)malloc(sizeof(Node)); s-data arr[i]; s-next head-next; head-next s; } return head; }头插法的核心是s-next head-next; head-next s;这个顺序不能反过来。如果先写head-next s原链表就丢了s 就成了唯一节点。我刚开始写链表时经常在这一步翻车后来养成习惯先让新节点的 next 指向旧链表的头一个节点再把头节点的 next 改为新节点永远不要先动 head。3.2 按位置插入与删除删除节点的核心是找前驱不是找自己按位置插入必须找到待插入位置的前驱节点。比如要把节点插到第 pos 个位置需要找到第 pos-1 个节点 p然后新节点 s 插到 p 后面。int insertNode(LinkList head, int pos, int value) { Node *p head; int i 0; while (p ! NULL i pos - 1) { p p-next; i; } if (p NULL) return 0; // 位置超出范围 Node *s (Node*)malloc(sizeof(Node)); s-data value; s-next p-next; p-next s; return 1; }同理删除第 pos 个节点要找到第 pos-1 个节点 p然后让 p-next 跨越待删节点 qint deleteNode(LinkList head, int pos) { Node *p head; int i 0; while (p-next ! NULL i pos - 1) { p p-next; i; } if (p-next NULL) return 0; Node *q p-next; p-next q-next; free(q); return 1; }注意删除时 while 条件看的是p-next ! NULL而不是p ! NULL因为我们要保证 p 有后继可删。如果写成p ! NULL到最后 p 是尾节点p-next 为空再执行p-next q-next也没意义了而且 q 没有被正确赋值。3.3 单链表逆序三指针遍历比头插法更不容易出错热词里有“python 单链表逆序”C 语言版同样常考。逆序常见两种写法三指针法和头插法。头插法的思路是摘下原链表每个节点依次插到 head 后面代码简单但需要额外循环。三指针法更直观也是我推荐的。void reverseList(LinkList head) { Node *prev NULL; Node *curr head-next; Node *next NULL; while (curr ! NULL) { next curr-next; // 先记住后继 curr-next prev; // 反转当前节点 prev curr; // 前驱前移 curr next; // 当前节点前移 } head-next prev; // 头节点指向新首节点 }这里的陷阱是next curr-next必须放在curr-next prev之前。不少人写成先反转再取后继结果 next 已经是旧前驱链表后半段直接丢失。head 节点本身不动只改 head-next 指向新的第一个节点。单节点链表和空链表走一遍循环也不会出错这是这个写法最省心的地方。3.4 基于链表的差集逐节点查重注意结果链表别复用原链表头歌有“基于链表的两个集合的差集”这道题。差集的定义是A 中有但 B 中没有的元素。操作思路是遍历 A对每个元素在 B 中查找没找到就插入结果链表。这不难但结果链表必须新建不能直接在 A 上删节点。直接在 A 上删会导致 A 本身被修改后面再用 A 比较就全乱套了。LinkList differenceSet(LinkList A, LinkList B) { LinkList C (LinkList)malloc(sizeof(Node)); C-next NULL; Node *tail C; Node *pa A-next; while (pa ! NULL) { Node *pb B-next; int found 0; while (pb ! NULL) { if (pb-data pa-data) { found 1; break; } pb pb-next; } if (!found) { Node *s (Node*)malloc(sizeof(Node)); s-data pa-data; s-next NULL; tail-next s; tail s; } pa pa-next; } return C; }B 链表的遍历每次从头开始所以内层循环不能把 pb 的指针移动丢。找到重复元素后 break只跳出内层。外层 pa 继续遍历 A 的下一个节点。如果你用单链表逆序的思维去复用 A差集结果没问题但头歌的评测可能同时检查 A 是否被改动所以新建结果链表是最稳的。4. 循环队列的判空判满取模运算和少存一格的设计逻辑循环队列是顺序表的一种特殊用法难点不在队列本身而在“循环”两个字。数组长度固定front 和 rear 转着圈移动怎么区分空和满这是头歌循环队列关卡的评分重点。4.1 少用一个存储单元空是 front rear满是 (rear 1) % MAXSIZE front热词里有一句“假设以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队头”这是两种不同的实现方案。先用最经典的少存一格方案。#define MAXSIZE 6 typedef struct { int data[MAXSIZE]; int front; // 队头下标 int rear; // 队尾的下一个位置 } SqQueue; void initQueue(SqQueue *q) { q-front 0; q-rear 0; } int isFull(SqQueue *q) { return (q-rear 1) % MAXSIZE q-front; } int isEmpty(SqQueue *q) { return q-rear q-front; }为什么要少存一格因为如果不多留一个空位队空和队满的条件都会变成 front rear无法区分。这是循环队列最容易让人绕晕的地方。数组长度是 MAXSIZE逻辑上最多存储 MAXSIZE - 1 个元素。如果题目要求队列容量是 m那么数组长度要定义成 m最多存 m-1 个。判断队满用的是(rear 1) % MAXSIZE front。假设 MAXSIZE 6front 0rear 5那么 (51)%60队满。如果 rear 在数组末尾加 1 后取模回绕到 0再和 front 比较。取模运算保证了 rear 永远在 0 到 MAXSIZE-1 之间转圈不会越界。4.2 入队出队完整代码rear 指向的是下一个空位不是队尾元素入队操作把新元素放在 rear 指向的空位然后 rear 后移。出队把 front 指向的元素取出然后 front 后移。两者都必须用取模实现后移。int enQueue(SqQueue *q, int x) { if (isFull(q)) return 0; q-data[q-rear] x; q-rear (q-rear 1) % MAXSIZE; return 1; } int deQueue(SqQueue *q, int *x) { if (isEmpty(q)) return 0; *x q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; } int queueLength(SqQueue *q) { return (q-rear - q-front MAXSIZE) % MAXSIZE; }队长的公式(rear - front MAXSIZE) % MAXSIZE要背熟。如果 rear 在 front 后面差值为正取模不变。如果 rear 已经绕到 front 前面差值可能是负数加 MAXSIZE 再取模就能恢复正常。这个公式能同时处理两种情况不建议用 if 分支分情况讨论容易漏。注意出队函数里的*x是输出参数调用方要提前声明一个 int 变量接收。头歌有些题把出队函数设计成返回弹出的元素那就要注意队空时返回什么一般返回 -1 或一个特殊标记。看题目的函数声明来写别想当然。4.3 用 length 计数的方案rear 和 length 都在变判满只看 length热词里的另一种方案是“以 rear 和 length 分别指示环形队列的队尾和队长度”结构体里多一个 length 字段。这个方案的好处是队列可以存满 MAXSIZE 个元素不用再浪费一个位置。typedef struct { int data[MAXSIZE]; int front; int rear; int length; // 当前元素个数 } QueueWithLength; void initQueueWithLength(QueueWithLength *q) { q-front 0; q-rear 0; q-length 0; } int isFullWithLength(QueueWithLength *q) { return q-length MAXSIZE; } int isEmptyWithLength(QueueWithLength *q) { return q-length 0; } int enQueueWithLength(QueueWithLength *q, int x) { if (isFullWithLength(q)) return 0; q-data[q-rear] x; q-rear (q-rear 1) % MAXSIZE; q-length; return 1; } int deQueueWithLength(QueueWithLength *q, int *x) { if (isEmptyWithLength(q)) return 0; *x q-data[q-front]; q-front (q-front 1) % MAXSIZE; q-length--; return 1; }这种方案下front 仍然指向队头元素rear 仍然指向队尾的下一个位置但因为有了 length满队的判断不再依赖取模。入队后 length出队后 length--要注意顺序先操作 data再移动 rear再改 length。如果先把 length 再去写 data队满判断在入队前已经做过了逻辑上不冲突但代码可读性差。比起少存一格方案length 方案更推荐在头歌的“应用”题里使用因为队列元素可以全部用上而且求队长直接返回 length 字段不需要套公式。缺点是多维护一个变量判题时如果初始化的 length 忘了清零后面所有操作都会错位。5. 头歌判题避坑五条踩坑记录与一套排查顺序头歌平台的顺序表、链表、循环队列关卡代码量的要求并不高真正卡人的是评测环境和你对题目描述的解读。下面是五条我反复见到的踩坑记录按现象、原因、解决的顺序写。5.1 本地能运行提交却说编译错误或答案错误现象你的代码在本地 Dev-Cpp 或 VS 里跑得好好的贴到头歌平台上提示编译错误或者输出与预期不一致。原因头歌的每个关卡其实绑定了一个固定的函数签名和 main 函数。它不认你本地自定义的入口逻辑。比如题目要求你写void insertList(SeqList *L, int pos, int val)你在代码里写成int insertList(SeqList *L, int pos, int val)本地能跑平台直接编译不过。还有一种情况是输出格式平台要求每行末尾没有多余空格你多 print 了一个空格就会判答案错误。解决先把题目给出的函数声明原样抄到代码里一个字符都不改再在里面补实现。输出方面拿题目给的示例输入跑一遍用肉眼对比你的输出和示例输出的空格数量。我在本地测试时会在输出行末尾打印|用来检查空格和换行。平台判题时不会显示这个|它只看实际字符。5.2 段错误malloc 大小写错或忘记处理空链表现象评测反馈“运行时错误”或“段错误”本地小数据测试偶尔也能复现。原因链表初始化(LinkList)malloc(sizeof(Node))有人写成malloc(sizeof(LinkList))。LinkList 是结构体指针类型大小是 8 字节64 位系统而 Node 结构体至少 8 字节起步有些结构体还有对齐填充sizeof 不对导致分配的内存不足读写越界。另一个高发原因是遍历链表时没有判空比如while (p-next ! NULL)但 p 本身可能已经是 NULL。解决统一用malloc(sizeof(Node))写结构体变量不要用指针类型做 sizeof。遍历链表时如果函数允许空链表先判断head NULL或head-next NULL再进入循环。头歌的评测用例经常包含边界情况空链表、只有一个节点、删除最后一个节点。把这三组输入都跑一遍段错误的概率能降一大半。5.3 循环队列判满判空写反提交显示超时现象循环队列关卡提交后提示“时间超限”本地怎么跑都正常。原因队列操作里出现了 while 循环条件写成while (q-rear ! q-front)但你的判空函数返回的却是p-rear q-front时的 true。如果 while 条件用反比如本意是“队列不为空时处理”却写成while (isEmpty(q))那么循环里 front 一直移动但 isEmpty 始终为 true等于死循环。解决写判空、判满函数后每一个 while 条件都反过来读一遍。最稳妥的做法是全部用函数而不是直接比较(rear1)%MAXSIZE front。代码里写while (!isEmpty(q))一眼就能看出“队列非空才处理”。直接裸写取模比较别人难读自己也容易看反。5.4 顺序表插入删除的位置参数0 基和 1 基搞混现象插入的位置明明是第 3 个位置结果输出却把元素放到了第 4 个位置或者删除第 1 个元素时删掉的是第 2 个。原因题目描述写“第 i 个位置”通常是从 1 开始计数而数组下标从 0 开始。如果你在插入函数里直接拿 pos 当数组下标不转换成 pos - 1插入和删除都会往后错一位。反过来有些题目明确说“下标为 i 的位置插入”那就不需要减一。解决先看题目描述里的“位置”有没有“下标”两个字。没有“下标”二字默认从 1 开始所有数组访问都要写data[pos - 1]。自测用例固定做一个往空表第 1 个位置插入元素如果输出是 data[0] 有值说明转换正确。如果 data[0] 还是旧值data[1] 变成了新值立即检查所有下标访问。5.5 样例对了但还是错构造最小用例你敲的代码自己都不确定现象示例输入和示例输出完全一致但提交后仍报错连续几次都过不了第一个隐藏用例。原因示例只是让你理解题意真正的评测用例包含你没见过的边界。比如顺序表并集题示例里两个集合互有重叠但隐藏用例可能有一个集合是空集链表差集题隐藏用例可能让 A 和 B 完全相等差集为空表。解决把代码里的函数单独提出来在 main 里写一组自测用例。顺序表测空表、删空表、插满扩容链表测空链表、单节点、逆序空链表循环队列测容量为 1、MAXSIZE 为 2、空军入队、满队再入队。自测时在关键操作后打印 length、front、rear不要只打印输出数组。这些中间状态对不上输出再怎么对隐藏用例肯定会炸。6. 把三件套串在一个自测任务里验证代码能过的最后一个技巧最后分享一个我常用的验证方法把顺序表、链表、循环队列串成一个小任务模拟“排队取号”的过程。循环队列存号码取出的号码按顺序插入一个顺序表作为操作日志再用链表逆序打印最近三条日志。这个任务覆盖了三种结构的所有核心操作能一次把 2 到 4 章代码全测一遍。测试流程是固定的先初始化长度为 5 的循环队列依次入队 1 到 5此时队长应为 5出队两个元素再把 6、7 入队检查队列是否判满正确每出队一个号码就调用顺序表插入函数把号码追加到日志末尾最后用链表逆序函数把最近三条日志逆序打印出来。自测断言写三条缺一不可队列出队的第一个元素必须是 1顺序表日志长度必须等于出队次数链表逆序后第一个输出节点必须是最后一次出队的号码。三条全部通过你手头的三套代码就能应对头歌绝大多数隐藏用例。// 自测核心逻辑 for (int i 1; i 5; i) { enQueueWithLength(q, i); } int x -1; deQueueWithLength(q, x); // x 应为 1 insertList(log, log.length 1, x); // 写入日志做完这套测试再去提交头歌的关卡基本能做到一次过。我自己的教训是永远不要在只看了示例输出的情况下就提交那等于把黑匣子交给平台碰运气。头歌的隐藏用例本质是数据结构考试的常规边界你把边界在本地测熟平台就只剩代码格式这一关了。希望这篇笔记能帮你少走几个坑把顺序表、链表、循环队列的基础真正打牢。本文还有配套的精品资源点击获取