头歌顺序表链表循环队列实训：边界条件与评测避坑指南

简介头歌平台数据结构实验配套答案覆盖顺序表、单链表与循环队列的基本操作和应用题面向正在完成头歌实训或复习数据结构的本科生与自学者。压缩包仅含1个docx文档大小约99KB文档针对各子任务给出可直接运行的C/C函数实现如顺序表的插入删除查找、单链表的建表与遍历以及循环队列的初始化、销毁、清空、判空、求队长、取队头、入队、出队和遍历接口均已完成并保留Begin/End标记便于对照检查。描述中还梳理了顺序表插入删除时的元素搬移思路、链表修改指针的高效插入删除方式以及循环队列解决假溢出问题的原理可辅助理解不同存储结构的适用场景。该资源已有10913人学习题目覆盖度和写法参考价值较高适合备考或刷题时快速查阅。1. 头歌顺序表、链表、循环队列实训先读懂评测再动手写头歌Educoder实践教学平台上的顺序表、链表、循环队列“基本操作和应用”实训几乎每届学数据结构的人都要碰一次。这道坎卡人的地方不在教材概念——插入、删除、取模谁都会背——而在评测机制平台只认你写的那几个函数主函数由评测代码接管输入样例一变边界条件就全露馅。这篇笔记按头歌过关顺序拆这三类数据结构的完整实现讲清每个参数的取值边界和平台评测的隐蔽要求适合正在一关关截图求助的同学也适合备考笔试时要快速捡起代码手感的人。2. 顺序表的基本操作从初始化到按值删除先跑通头歌的最小实现2.1 头歌顺序表题目的固定套路结构体与函数清单头歌顺序表关卡一般会让你补全一个.c文件。结构体定义通常是教学版的标准写法一个定长数组加一个整型长度。你只负责实现题目列出来的函数主函数和输出格式由平台控制。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList;逻辑说明data 数组存元素length 记录当前元素个数。初始化、插入、删除、查找四个函数是几乎所有顺序表实训的必考项。注意题目给的头文件里可能已经写过#define MAXSIZE你提交的代码不要重复定义否则编译报重定义错误。参数说明SeqList作为结构体按值传递会整体拷贝整个数组代价高且改不动原表。凡是需要修改表内容的函数参数一律写成SeqList *L只读不写的查找函数可以用值传递省得误改数据。2.2 初始化与插入位置边界是第一道坎初始化很简单难的是插入。位置参数pos到底从 0 开始还是从 1 开始直接决定你差一不差一。多数头歌题目不额外声明时默认数组下标从 0 开始也就是pos允许的取值范围是 0 到length闭区间。void InitList(SeqList *L) { L-length 0; } int ListInsert(SeqList *L, int pos, int e) { int i; if (pos 0 || pos L-length) return 0; // 插入位置越界 if (L-length MAXSIZE) return 0; // 表已满 for (i L-length; i pos; i--) { L-data[i] L-data[i - 1]; // 从后往前依次后移 } L-data[pos] e; L-length; return 1; }逻辑说明插入的本质是从最后一个元素开始逐个后移腾出pos位置。i pos这个条件保证移动终点恰好是pos 1不会覆盖掉还没移动的元素。如果写成i pos你会把data[pos]原有的值先覆盖到data[pos1]看起来没丢数据但在连续插入时会错位。参数说明pos允许等于length意思是插到表尾此时循环不执行直接赋值。返回 1 表示成功返回 0 表示失败。头歌的判题器通常会输出这个返回值失败时返回 0 已在预期输出里写死你不能返回 -1 或别的值。注意如果题目描述写的是“在第 i 个元素之前插入”且第 1 个元素对应data[0]那调用时要把逻辑位置 i 减 1 再传进ListInsert。这个换算在函数外做不要在函数内再减一次。2.3 删除与按值查找两个方向相反的移动逻辑删除比插入容易写反。插入是从尾部往前移删除是从前往后移。很多同学把插入循环倒过来用在删除里结果删一个元素后半段数据全乱了。int ListDelete(SeqList *L, int pos) { int i; if (pos 0 || pos L-length) return 0; // 注意 pos length 时无元素可删 for (i pos; i L-length - 1; i) { L-data[i] L-data[i 1]; // 从前往后前移 } L-length--; return 1; } int LocateElem(SeqList L, int e) { int i; for (i 0; i L.length; i) { if (L.data[i] e) return i 1; // 返回逻辑位置 } return 0; }逻辑说明ListDelete的循环停在L-length - 1最后一个元素的前移目标位置是L-length - 2原来的末尾变成冗余位长度减一后自然被忽略。LocateElem按值查找返回的是逻辑位置即下标加 1这样做的好处是用 0 表示“找不到”否则下标为 0 的元素会跟“找不到”产生歧义——这就是头歌里“查找第一个等于 x 的元素”关卡最常见的扣分点。参数说明LocateElem用值传递是因为它不改表如果你手滑把形参写成指针平台调用时传的是L而不是L编译直接失败。删除的边界是pos L-length不算合法因为length指向的是最后一个元素的下一格那里没有元素。2.4 顺序表应用合并两个有序顺序表应用类题目喜欢考“合并两个有序顺序表成一个新的有序表”。手机上看到题目别急着写两层循环有序合并用双指针一次扫描就能完成时间复杂度 O(n)。void MergeList(SeqList A, SeqList B, SeqList *C) { int i 0, j 0, k 0; while (i A.length j B.length) { if (A.data[i] B.data[j]) { C-data[k] A.data[i]; } else { C-data[k] B.data[j]; } } while (i A.length) C-data[k] A.data[i]; while (j B.length) C-data[k] B.data[j]; C-length k; }逻辑说明两个有序表谁小谁先进 C。某一方先耗尽后剩下的元素直接整个续到 C 尾部不需要再比较。C必须是第三个独立表不能拿 A 或 B 自己充当 C否则会互相覆盖。参数说明A、B 按值传入C 用指针因为 C 的 length 要被回填。如果题目要求去重你要在进入C前先判断C-data[k-1]是否等于当前元素等于就跳过。这个去重判断在头歌的“集合合并”变体里几乎是必考的。提示合并前先确认 A、B 确实有序。头歌有的样例故意给无序输入你需要在合并前自行排序或改用其他算法否则结果只对一半。3. 链表的基本操作尾插、遍历、逆置和集合差集3.1 链表题的结构体与带头结点问题链表实训在头歌上出现的频率比顺序表更高考察点也更多。结构体定义基本统一关键分歧在“带头结点”还是“不带头结点”。头歌绝大多数实验采用带头结点版本头结点本身不存数据只作为统一操作入口。这个设计让插入第一个元素和插入中间元素共用同一套代码也让你在求差集、删第一个结点时不用单独写 if 判空分支。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;逻辑说明LinkList是指向头结点的指针也常直接用来表示整条链表。带头结点时头指针永远指向那个空数据结点不会因删除第一个元素而变成 NULL这是它比不带头结点版本好写的地方。参数说明有些头歌题只定义了struct LNode没有 typedef 出LinkList你自己用typedef struct LNode *LinkList;补上即可。如果题目里既有LNode又有LinkList的名字别为了省事只写LNode *保持和题目标识符一致能少踩一个编译冲突的坑。3.2 尾插建表与链表遍历先把骨架搭对头歌链表题第一关通常就是“创建链表并遍历输出”。尾插法需要维护一个尾指针否则每次插入都要从头遍历到尾部数据量大时平台会报运行超时。LinkList CreateListTail(int n) { LinkList head (LinkList)malloc(sizeof(LNode)); LNode *tail head; head-next NULL; int i, x; for (i 0; i n; i) { scanf(%d, x); LNode *p (LNode *)malloc(sizeof(LNode)); p-data x; p-next NULL; tail-next p; tail p; } return head; } void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }逻辑说明head-next NULL这行不能省。头结点初始化时 next 是随机值不置空会导致遍历直接越界。插入新结点时新结点的next必须显式置 NULL因为malloc出来的内存不会自动清零。参数说明CreateListTail返回头指针主函数里用LNode *L CreateListTail(n)接收。尾插法建表后最后一个结点的 next 天然是 NULL遍历循环才能正确终止。打印时带头结点版本从L-next开始如果你习惯从L开始打印会把头结点的垃圾值打出来。3.3 就地逆置不申请新结点三指针就够了“链表逆置”是头歌链表实训必考的综合题也是很多人第一次接触“就地修改”这种说法。题目如果写明“不得新建结点”头插法重建表就违规了要在原链表上改指针方向。void ReverseList(LinkList L) { if (L NULL || L-next NULL) return; LNode *pre NULL; LNode *cur L-next; LNode *next; while (cur ! NULL) { next cur-next; // 先记住后继 cur-next pre; // 指向前驱 pre cur; // 前驱前移 cur next; // 当前结点前移 } L-next pre; // 头结点指向原链表的尾结点 }逻辑说明三个指针的分工是cur指向当前要改 next 方向的结点pre是它的前驱next提前保存它的后继。cur-next一旦被改写原后继就丢了所以next cur-next必须放在最前面。循环结束后pre恰好停在原链表最后一个结点把它挂到头结点后面完成逆置。参数说明空链表或只有一个元素的链表不用逆置函数开头直接 return。头歌的评测会专门测这两种边界少写这个判断会得到一次“运行时错误”或“答案错误”。3.4 基于链表的集合差集把遍历和删除组合起来差集题目的表述是“求两个链表的差集 A-B即把 A 中出现在 B 里的元素删掉”。这道题把链表遍历、查找、删除三个基本功全部串起来是头歌链表关卡的压轴戏。int InList(LinkList L, int e) { LNode *p L-next; while (p ! NULL) { if (p-data e) return 1; p p-next; } return 0; } void Difference(LinkList A, LinkList B) { LNode *pre A; LNode *cur A-next; while (cur ! NULL) { if (InList(B, cur-data)) { pre-next cur-next; // 跳过当前结点 free(cur); // 释放被删结点 cur pre-next; // 不移动 pre } else { pre cur; cur cur-next; } } }逻辑说明删除链表结点必须知道被删结点的前驱所以用pre和cur两个指针同步走。当cur需要删除时pre-next直接指向cur-nextcur后移pre原地不动当cur需要保留时pre和cur一起后移。这个“一动一不动”的差异是链表删除最常见的丢链原因。参数说明InList遍历 B 链查找元素是否存在若题目要求“删除所有重复出现的元素”那每删一次后还要用新的cur继续比对上面代码已经天然支持。如果 B 链表无序这个解法是 O(n*m) 复杂度头歌数据量小能过但你在笔试时最好提一句“可先排序再优化”。4. 循环队列的基本操作rear 和 length 方案下队满与队空怎么判4.1 头歌循环队列题的经典结构体数组 q 加 rear 和 length循环队列题目的题干常以这句话出现“假设以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队尾位置和元素个数”。这比教科书上牺牲一个存储单元的方案更直白——用 length 记录元素个数队满队空判断就不再依赖front和后继位置的比较。#define QUEUE_MAX 100 typedef struct { int data[QUEUE_MAX]; int rear; // 指向队尾元素的下一个位置 int length; // 当前元素个数 } CircularQueue;逻辑说明rear的含义是“下一个元素入队时的存放下标”不是队尾元素本身的下标。数组下标范围是 0 到QUEUE_MAX - 1元素全满时length QUEUE_MAX一个空闲格都不剩所以不需要预留空位。参数说明你提交时可以把QUEUE_MAX改成题目给的m、数组名改成q思路不变。这里用长名字是为了避免和评测代码里的全局标识符撞车这个坑在第 5 章会专门讲。4.2 入队与出队取模运算让下标回绕入队出队是循环队列的核心。入队时先把元素放进rear指向的位置然后rear加 1 取模出队时根据rear和length反推队头位置。int EnQueue(CircularQueue *Q, int e) { if (Q-length QUEUE_MAX) return 0; // 队满 Q-data[Q-rear] e; Q-rear (Q-rear 1) % QUEUE_MAX; // 回绕到头部 Q-length; return 1; } int DeQueue(CircularQueue *Q, int *e) { if (Q-length 0) return 0; // 队空 int front (Q-rear - Q-length QUEUE_MAX) % QUEUE_MAX; *e Q-data[front]; Q-length--; return 1; }逻辑说明(Q-rear 1) % QUEUE_MAX是循环队列的核心。rear QUEUE_MAX - 1时再加 1 变成QUEUE_MAX取模后回到 0。队头位置用(Q-rear - Q-length QUEUE_MAX) % QUEUE_MAX推导当前最后入队的元素在rear - 1处往前数length个就是最老的元素。加QUEUE_MAX再取模是为了防止负数下标。参数说明DeQueue的第二个参数是int *e出队元素通过指针带回这是 C 语言函数返回多个值的常见做法。调用时写DeQueue(Q, x)少写会传入一个未初始化指针程序直接崩溃。出队不用真的移动数组元素length减一后队头位置自动变为下一个元素。提示很多同学在这个结构体里手动维护一个front变量入队时动 rear、出队时动 front结果和 length 的逻辑互相打架。既然选择 rearlength 方案就不要引入 front队头位置统一用公式计算。4.3 循环队列应用报数出队问题循环队列最常见的应用关卡是“报数问题”也叫约瑟夫环。n 个人围成一圈编号 1 到 n从 1 开始报数报到 m 的人出列然后下一个人继续从 1 报数输出所有人的出列顺序。void Josephus(int n, int m) { CircularQueue Q; InitQueue(Q); int i, e; for (i 1; i n; i) { EnQueue(Q, i); } while (Q.length 0) { for (i 1; i m; i) { // 前 m-1 个人出队再入队 DeQueue(Q, e); EnQueue(Q, e); } DeQueue(Q, e); // 第 m 个人直接出列 printf(%d , e); } printf(\n); }逻辑说明队列本身就是环形结构出队再入队恰好模拟“人绕圈继续报数”。内层循环每执行一次队头元素被搬到队尾相当于这个人报完数回到队列末尾等待下一轮。报到 m 的人不再入队直接输出完成一次出列。参数说明m 等于 1 时内层循环一次都不执行报到 1 直接出列符合题意。m 大于当前剩余人数时内层循环仍然安全因为每出队一个就入队一个队列长度在循环中保持不变不会提前变空。如果题目要求输出的是“最后一个剩下的人”把每个出队元素存起来最后打印队列里剩下的唯一元素即可。5. 头歌过关检查常见报错与避坑记录5.1 现象本地跑得好好的平台上就是答案错误很多人在 DevC 或 VS 里运行样例输出结果和题目给的一模一样交到头歌上却报“答案错误”。仔细用肉眼比对又会发现和预期输出几乎一样只是末尾空格的差别。原因头歌实践教学平台的输出评测是逐字符精确匹配的。printf(%d , e)和printf(%d, e)在视觉上几乎一样但评测器会把末尾多出的空格算作错误。顺序表遍历输出、链表打印这类关卡最常栽在这里。解决提交前把题目的样例输出复制到本地文件里自己程序的输出也重定向到文件用diff命令比对。没有 Linux 环境的在 Windows 下用fc命令也能看到第一个不同字符的精确位置。凡题目要求在数字之间用空格分隔的最后一个数字后一律不要加空格。5.2 现象插入位置总差一位删的永远不是想要的那个元素顺序表和链表的插入删除题目逻辑都对但测试里“在位置 i 插入”总是插到 i1 的位置。这种差一问题在头歌上会连续错好几个测试点而且输出结果看着就像整体偏移了一位。原因题目里的“位置”是从 1 数还是从 0 数没有统一标准。数组下标天然从 0 开始但自然语言里的“第一个元素”又常从 1 起算。如果你在ListInsert内部直接写pos作为数组下标而题目期望的是逻辑位置就全错了。解决先在题目描述里找“下标从 0 开始”或“位置从 1 开始”的字样。没有明确说明时按以下经验处理头歌平台对数据结构题默认 C 语言下标从 0 数但会明确写出“第 1 个位置”的就对应pos 1的逻辑位置函数内先做pos pos - 1再作为数组下标使用。你可以写一个临时测试把位置值打印出来但更稳妥的是做题前把题目样例手算一遍下标对应关系不要靠猜。5.3 现象链表遍历程序卡死平台提示运行超时或返回非零链表建好后一遍历就死循环本地环境也能复现调试发现指针转圈圈总也走不到 NULL。或者遍历第一次正常第二次访问同一链表时崩溃。原因这两个现象根因通常是同一个——某个结点的next没有置 NULL。最常见的是头插法建表时新结点p-next L-next循环结束后最后一个结点的 next 指回头部形成了意外的环尾插法如果忘了p-next NULL这个结点的 next 是 malloc 留下的随机地址遍历会冲进非法内存。解决写链表操作后养成一个检查习惯从L-next出发遍历并用计数器限制步数超过链表长度立即跳出防止死循环。建表代码里每一个malloc出来的结点都要显式写p-next NULL不要依赖编译器行为。如果是循环单链表的要求遍历终止条件从p ! NULL改成p ! L并在题目要求处保留环。5.4 现象循环队列明明有空位入队却失败或者队空了还能出队用 rear 和 length 方案实现循环队列入队到一半时返回失败打印 length 却还没到最大值。稍加观察发现队头位置的推导结果和实际存的数据对不上。原因把两种循环队列实现方案混在一起用了。教科书里有“牺牲一个存储单元”的版本队满条件是(rear 1) % m front也有“计数器 length”版本队满条件是length m。你把第一种方案的判队满逻辑套在第二种方案的结构体里length还没到 mrear 和 front 已经相邻自然提前判定队满。解决确认题目结构体里有没有length字段。有length就只认length队满判length m队空判length 0不要再用front和rear的关系判断。反过来如果题目用的是牺牲空位方案就完全不要引入 length只用 front、rear 判断。两套边界逻辑绝不能混写。5.5 现象头歌编译报错错误信息指向一个莫名的标识符冲突本机编译零错误上传到头歌后报“redefinition of M”或“conflicting types for q”。你明明没有在代码里重复定义报错却指向系统评测代码里的某个符号。原因头歌把学生代码和评测模板拼接到同一个.c文件里编译。你取的变量名如果比较通用比如M、q、len、pos容易和评测程序里的全局变量或宏定义冲突。本机编译器没有这个拼装过程所以完全看不出来。解决提交用的代码里尽量让全局命名带前缀。队列容量用QUEUE_MAX而不是M数组名用queue_data而不是q长度字段保持题目定义里的length就好因为那是结构体成员名不参与全局冲突。如果平台报错仍然指向某个符号直接重命名你自己代码中所有同名符号重命名后重新提交。这个操作不改变任何逻辑却能消除一大批“编译失败”的假性错误。6. 把顺序表、链表、循环队列整理成自己的过关模板这三类结构练完后值得做的一件事是把代码按固定顺序整理成一个模板文件先是结构体定义再是初始化、插入、删除、遍历最后是应用函数。头歌做新题时先复制模板骨架再针对题目要求修改细节比每次从头写要快得多也少很多笔误。模板的组织顺序我一般这样固定先写typedef struct和必要的宏定义然后写初始化函数接着写插入和删除再写遍历和查找最后写应用题。这个顺序照搬了教材里“基本操作到高级应用”的递进也符合头歌关卡从易到难的排列。更重要的是每个函数都在开头写好边界判断顺序表和循环队列先判满判空链表先判 NULL这样测试数据再刁钻也不会让函数崩溃。自测时建议把题目给的样例输入存成一个test.txt本地编译后直接用./a.out test.txt重定向跑再和样例输出做比对。不必每次都手敲输入尤其循环队列和约瑟夫环的样例动辄十几行手敲一旦错一个数字浪费的是半小时排查时间。提交前把临时写的main函数注释掉只保留题目要求实现的函数避免和平台的主函数冲突。我自己的习惯是给每个函数写一行注释说明位置参数的语义是“从 0 开始的下标”还是“从 1 开始的逻辑序号”。这个习惯救过我一次做链表删除那一关时我对着屏幕排了大半小时的差一错误最后发现题目里“第 i 个结点”按逻辑位置计数而我的函数内部直接拿它当了遍历步数。从那以后每道题动手前先确认清楚位置的起算点代码里该减 1 的地方提前减掉。这套模板不只是为了过实训。顺序表的内存连续性、链表的不连续存储、循环队列的取模回绕这三个底层思维几乎覆盖了后续栈、串、图的全部存储结构的理解。头歌上的过关只是起点把它整理成自己随时能看懂、能改动的代码片段笔试和面试前翻一遍比临时抱佛脚翻课件有用得多。希望帮到你。本文还有配套的精品资源点击获取