数据结构第二周往往是整个学期的一道分水岭。第一周还在聊抽象数据类型、时间复杂度的概念题第二周立刻切换到线性表、链表的建存取删要求你手写代码还要求能应付笔试里的各种变形。很多同学就在这个节点开始焦虑说链表指针看懂了自己一实现就错栈和队列规则都懂一上机就乱。这里我可以直接说很正常。数据结构这门课是把“逻辑结构”和“存储实现”第一次强行绑在一起它需要的是想清楚再写而不是边写边想。这篇文章围绕第二周的学习内容把线性表、栈、队列、双端队列这些重点拆开讲再聊一聊实验报告、常见坑和调试经验希望能帮正在啃这本书的人少走几步弯路。1. 第二周学习内容先看清地图再动手1.1 从课程大纲看第二周的位置绝大多数学校的《数据结构》课程第一周是绪论第二周就开始进入线性表。有的教材把顺序表和链表分开成章有的像严蔚敏版线性表一章讲完王道、天勤、李春葆这些辅导书基本也是这个顺序。也就是说第二周的目标非常明确把顺序表、单链表搞到能默写的程度再开始接触栈和队列的应用。为什么这么强调“默写”因为线性表是后面所有存储结构的母型。树的孩子表示法要用链表拼图的邻接表也要用链表拼栈和队列本身就是线性表的受限版本。这一周如果只是“会做题”没有把链表的底层操作写透第三周开始学树和图就一定会吃力。我在带学生的时候见过太多例子前面线性表靠背应付过去后面指针数组混在一起代码基本只能看着参考答案读完全提不出自己的实现。但也要有个取舍。第二周时间就这么多不可能把顺序表、单链表、双链表、循环链表、栈、队列一遍全精通。我建议第一优先级是顺序表和单链表第二优先级是栈和队列双链表和循环链表可以放在第三周强化。因为前四个是后面绝大多数算法题的底座后两个更多是变形应用绝大多数老师第二周也只是点到为止。1.2 顺序表 vs 链表理解背后的选择逻辑第二周最容易遇到的问题是顺序表和链表放到一起比看完了感觉都会可一合上书又觉得什么都没抓住。这里我推荐一个办法自己画一张对比表然后回答三个问题——随机访问谁快中间插入谁方便内存空间谁更省维度顺序表链表存储方式连续的一段内存靠数组下标访问分散节点靠指针串起来随机访问第 i 个元素O(1)直接用 a[i-1] 定位O(n)要从头一个个走到第 i 个末尾插入/删除O(1)只要容量够O(1)有尾指针的话中间插入/删除O(n)要把后面元素整体搬动O(1) 定位之后改指针即可额外空间基本无但要预分配每个节点多存一个指针缓存友好度高连续内存访问快低节点分散容易缺页很多同学把链表的查找复杂度记成 O(1)理由是“链表插入删除都很快”。这里要纠正一个误区定位和操作是两件事。单链表在头部插入确实是 O(1)但你得先找到头部如果要在中间任意位置插入光“找到那个位置”就已经 O(n) 了改指针本身才是 O(1)。考试和面试里很喜欢考察这个区分比如“在已知节点 p 后面插入一个新节点”和“在未知节点位置插入一个新节点”复杂度完全不同前者可以做到 O(1)后者必须先遍历定位。实际操作上第二周写顺序表比写链表容易但链表更能暴露一个人的功底。我的建议是先细细地写一个顺序表的插入删除再写一个带头节点的单链表建立、遍历、插入、删除。完成这两个小实验再去碰后面的栈和队列会顺很多。2. 栈、队列与双端队列操作受限的线性表2.1 栈后进先出内存管理的王者栈的实现其实很简单你用一个数组加一个 top 指针就能模拟。真正难的是理解它为什么无处不在。函数调用要压栈表达式求值要压栈浏览器的后退也是栈撤销操作还是栈。第二周学栈我建议别急着背题目先做个具体的案例括号匹配。比如对字符串([]{})用一个栈依次扫描字符遇到左括号就入栈遇到右括号就和栈顶匹配如果匹配成功就弹出栈顶最后栈为空才说明括号是合法配对的。整个过程不到二十行代码却把栈“先进后出、只能从栈顶操作”的核心体现得淋漓尽致。等你写完这个再看中缀表达式转后缀、函数调用栈会自然产生联系。写栈代码时有一个常见的坎top 初始值到底是 -1 还是 0。两种写法都有人用关键是入栈出栈条件别写反。如果 top 初值为 -1入栈要先 top 再赋值出栈要先取值再 top--。如果 top 初值为 0入栈是 a[top] x出栈是 top--。我见过太多人把这两个搞混结果栈里永远少一个元素或者越界。建议挑一种固定下来每次上机前默写一遍几周后就不会再纠结。第二周用数组模拟栈通常比用链表模拟栈更稳妥。链表栈虽然看起来高级但初学者很容易在内存释放和指针悬空上翻车。第一阶段先把数组栈写熟链表栈可以放到后面和链表操作一起练。2.2 队列先进先出环形队列的边界问题队列的现实应用同样非常多操作系统进程调度、消息队列、打印机缓冲、广度优先搜索。第二周要实现的通常不是简单的链式队列而是循环队列——因为顺序队列反复入队出队会出现“假溢出”明明是空位置却用不了。循环队列的难点在边界判断。核心公式就两个队尾入队rear (rear 1) % MaxSize队头出队front (front 1) % MaxSize。判断队满是(rear 1) % MaxSize front也就是说牺牲一个存储单元来区分队空和队满。如果你判断队满写成rear MaxSize那排队列一超过数组长度就会越界或者明明没满也被误判为满。我建议在纸上画一个四个格子的环手动模拟入队、出队、再入队的过程把 front 和 rear 的移动标清楚。这个动作看起来初级却是解决一切循环队列问题的最快方法。等你能徒手画出队列满与空的状态那些队长计算题就不会再错——比如(rear - front MaxSize) % MaxSize这个求队长公式不理解画圈的人很容易写成绝对值。队列的另一种实现是链式队列用一个头节点加 front、rear 指针。第二周如果时间不够链式队列可以简单带过但至少要明白它不会假溢出所以循环队列主要用来解决顺序存储的浪费问题。2.3 双端队列看似灵活最容易懵近年不少教材和考试把双端队列加了进来很多人在查“数据结构 双端队列”这个关键词。双端队列就是允许在两端插入删除的队列听起来好像只是放宽了限制但考试题经常让人头大。常见题型是给你一个输入序列限定“输出受限”或“输入受限”的双端队列问能得到哪些输出序列。这里的关键是先把“受限”两个字圈出来。输入受限是指只能在某一端插入、另一端不能插入但两端都可以删除输出受限则反过来。很多人丢分是因为凭直觉脑补操作把受限当成两端都可入可出。正确做法是画一个横着的双端队列把输入输出方向标成箭头每一步只能按题目允许的操作移动元素。实际工程里Python 的collections.deque就是双端队列适合做滑动窗口、最近使用列表、任务队列等。但在第二周真正的重点还是回到“它是线性表的受限版本”这个本质上双端队列的底层可以用链表做也可以用循环数组做。你只要掌握了顺序表和链表双端队列的代码实现反而容易。刚开始不要贪多把限制条件分析清楚比手写双端队列代码更重要这也是第二周笔试中比较容易得分的一块。3. 排序算法与复杂度第二周有必要热个身3.1 这周适合碰哪几个排序算法很多教材把排序算法放在后半学期但多年经验告诉我第二周最好写一遍直接插入排序、冒泡排序、简单选择排序。原因很简单这三种排序的主体操作都是数组遍历、元素比较和交换刚好能复习顺序表而且理解了它们后面学 O(nlogn) 那一票高级排序时才有对比基础。直接插入排序是最贴近“扑克牌理牌”思路的算法。核心代码也不长void insertSort(int a[], int n) { int i, j, tmp; for (i 1; i n; i) { tmp a[i]; // 先把待插入元素保存 j i - 1; while (j 0 a[j] tmp) { a[j 1] a[j]; // 比 tmp 大的元素往后挪 j--; } a[j 1] tmp; // 找到位置插入 } }这段代码如果第二周能不看答案写出来说明你对数组下标边界和元素覆盖顺序已经有了直觉。写不出来也没关系但一定要画图理解为什么从后往前搬而不是从前往后。从前往后会直接把还没比较的元素覆盖掉这是初学者最常见的错。排完序后再算一下它的平均复杂度 O(n^2)、最好 O(n)、最坏 O(n^2)第一周学的时间复杂度概念就有东西落地了。冒泡排序和选择排序同样值得手写。冒泡排序要理解“每一趟把最大的元素浮到末尾”选择排序要理解“每一趟待排序区里选出最小的放到最前面”。它们看起来很像但稳定性不同这部分下面重点说。3.2 时间复杂度和空间复杂度别再靠背第二周真正需要建立的计算能力是把“时间复杂度”从名词变成工具。很多同学只记住排序是 O(n^2)却说不清为什么。实际上你只需要数一数嵌套循环的执行次数插入排序最坏情况是每个元素都要往前比对 i 次累加起来是 12...n约等于 n^2/2所以是 O(n^2)。空间复杂度是一个更容易被忽略的点。排序里像插入排序、冒泡排序、选择排序都只用了几个临时变量辅助空间是 O(1)。而归并排序需要额外的一个数组所以辅助空间是 O(n)。递归算法还要把递归调用栈的空间算进去比如快速排序的空间复杂度是 O(log n)但递归版的最坏情况会到 O(n)。这些细节笔试里经常考尤其考研 408 真题喜欢在“空间复杂度”上做文章。再来看稳定性这是第二周最容易混淆的概念。稳定不是“排序性能稳定”而是“相等元素的相对顺序不改变”。比如先按姓名排序再按成绩排序如果算法稳定成绩相同的同学还能保持姓名顺序如果不稳定可能乱掉。插入排序和冒泡排序都是稳定的选择排序不稳定。举个例子序列[5, 8, 5, 1]第一趟选择排序会把最小的 1 换到第一位导致两个 5 的相对顺序可能改变。理解这个例子之后就不会再瞎背稳定性结论了。排序算法平均时间复杂度最坏时间复杂度辅助空间稳定性插入排序O(n^2)O(n^2)O(1)稳定冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(n^2)O(logn)不稳定第二周不需要急着掌握全部但至少要把前面三行的复杂度来源和稳定性道理讲清楚。后面学快排和堆排时再对比它们的平均最好最坏情况。4. 用什么语言、看什么书第二周最容易纠结的问题4.1 C、C 还是 Python别把语言当成数据结构本身如果学校用的是 C 语言版教材第二周一定要亲手把结构体、指针、动态内存分配用起来。很多书上伪代码写得很好但到机器上跑起来问题百出多是因为对malloc和指针类型转换不熟。建议先写两个小项目一个顺序表一个带头节点的单链表每天至少过一遍创建、插入、删除、查找。有 C 基础的同学可以用引用简化参数传递写起来更顺手但别跳过指针。比如链表节点定义struct Node { int data; Node* next; };你要清楚Node*和Node的区别清楚p-next和(*p).next是同一个东西。读懂指针后面学树的时候才能看懂root-left、root-right。Python 的写法则完全不同。Python 里的list已经把很多线性表操作封装好了你可以直接用list.append模拟入栈用list.pop模拟出栈写起来很快。但如果你要用 Python 交数据结构上机作业一定要展示你理解底层逻辑而不是只调用现成容器。比如用类实现链表 Node自己写insert、delete方法而不是拿list假装是链表。有些课程方向偏数据应用会提到 pandas 创建数据结构这类说法。pandas 中的 Series 和 DataFrame 确实是 Python 数据领域里的常用结构但它们是建立在更底层的数据结构之上的抽象和数据结构教材里的栈、队列、链表不是同一层概念。第二周看到这些名词不要慌记住数据结构培养的是抽象能力具体语言只是实现工具。4.2 严蔚敏、王道、李春葆这些教材怎么用教材选型也是第二周绕不开的问题。严蔚敏的《数据结构C语言版》是很多学校指定的教材体系严谨但代码和类 C 伪代码混在一起初学者经常看完算法步骤却不知道在哪里写 main。我的经验是把它当字典和原理书用不要指望照抄它的代码到编译器里就能跑。王道考研数据结构书适合题型总结和刷题尤其适合准备 408 的人。但它毕竟不是教材很多知识点直接以结论形式给出来如果你连基本概念都还没建立直接刷王道会变成“背题”。更好的节奏是先在学校教材里看懂原理再用王道检验掌握程度最后拿历年真题练速度。李春葆的教材整体实例比较多适合做上机实验参考。第二周如果遇到实验报告不妨翻翻他的例题思路。但有一点要避开部分版本的《学习指导》存在印刷勘误网上也有勘误汇总表。用之前最好先查一下所持版次有没有已知错误免得拿着错答案对题。如果你还没买书先去图书馆翻一版对比例题步骤和习题解析确认没有明显笔误再入手。还有不少院校比如山大软件学院这类实践导向比较强的专业第二周可能直接抛出综合实验。这个时候不要慌大胆用学校安排的上机环境先把功能跑起来再回头对照教材补概念。不要因为实验题没做过就想着放弃绝大多数综合实验就是把顺序表、链表的操作串起来而已。5. 第二周实验报告怎么写才不白写5.1 一份报告的基本骨架第二周的实验报告通常围绕线性表展开要么是顺序表的插入删除要么是单链表的建立、查找、删除与反转。有些网络教育和电大课程会把它称为形考作业这也是一种实验报告只是提交形式更模板化。我建议一份报告至少包含这么几个部分实验目的说明这周实验要验证哪几个知识点。实验内容与需求分析把题目用自己的话描述一遍指出输入、输出和核心约束。数据结构设计说明用到顺序表还是链表为什么选它。核心算法思路写出关键函数的设计思想最好配时间和空间复杂度分析。关键代码片段只贴核心函数不要整篇源代码堆上去。运行结果给出代表性输入输出最好有边界情况。问题分析与调试过程记录遇到的错误、排查思路和最终解决办法。很多学生只写“源代码 三张运行截图”这真的非常可惜。老师想看到的不是你会复制代码而是你出了问题怎么排错。把一个内存越界或者指针断链的问题写清楚哪怕没完全解决都比你贴十段能跑的代码更有价值。5.2 常见扣分点和加分细节我是一个经常帮学生看实验报告的人说几个最常见的扣分点一是没有复杂度分析。一个链表的插入删除算法光写“时间复杂度 O(1)”是不够的必须说明为什么在“已知前驱节点”的前提下才成立如果按值查找前驱就还是 O(n)。二是实验目的空泛写什么“掌握数据结构的基本操作”。要具体一点比如“掌握单链表逆置的指针修改过程理解使用三个辅助指针的遍历方法”。三是代码没有注释。第二周上机代码不算长但如果老师要求截止时间前交没有注释的代码很难证明是你自己实现的。四是没有对边界条件的测试。顺序表插入第一位置、删除最后位置链表空表插入这些情况写进运行结果里绝对是加分项。还有一个加分细节如果你能在报告中画出顺序表插入时的元素移动示意图或者链表反转时每一步指针的变化报告的档次会明显高出一截。手画可以用 word 箭头也可以用代码画 ASCII 示意。重点是让老师看到你真的理解了过程而不是只给了最终结果。6. 第二周上机最常见的坑与排查方法6.1 链表指针画图比空想有用凡是链表报错十有八九是对 NULL 的判断和指针赋值顺序出了问题。比如把新节点 p 插入到单链表 q 的后面正确顺序是p-next q-next; q-next p;这两行顺序不能反过来。如果先写q-next p那么 q 原来后面的节点就丢了链表从这里断开后面所有操作都会出问题。另一个高频 bug 是遍历链表时不让当前指针指向下一个节点死循环在同一个节点上。比如写while(p ! NULL)循环体内却忘了p p-next结果程序一直打印同一个节点的 data。这种错误看起来很低级但在上机压力下真的很常见。我的习惯是写链表的修改操作之前先在草稿纸上画方框和箭头标出哪些指针要改再对着图写代码。有人觉得这麻烦但对新手来说画图是最省时间的调试方式。等你熟练之后再尝试直接在脑海里模拟。我在实际带人的过程中几乎所有链表指针错误一画图立刻就能自查出来根本不需要到编译器里反复猜。链表还有个隐蔽问题就是内存管理。用 C 语言手动malloc的节点删除时要记得freefree 之后不要再访问这个节点否则就成了悬空指针。C 里new出来的节点用delete删除。很多同学上机时不开内存检查工具直到程序崩溃才发现释放问题。如果环境允许多用 ASANAddressSanitizer或者简单的日志打印来辅助调试。6.2 栈和队列的边界条件栈经常出的问题就那几个top 初始值是 -1 还是 0入栈前有没有判满出栈前有没有判空。可以封装isEmpty()和isFull()两个小函数避免在每处操作里都重复判断而导致不一致。顺序栈判满的条件通常是top MaxSize - 1循环队列判满条件是(rear 1) % MaxSize front。 这些公式不难但如果你二周内不动手写考前临时背很容易弄混。循环队列的队满条件之所以要牺牲一个存储单元是因为如果不牺牲队空和队满都会出现front rear没法区分。另一个办法是使用 size 字段记录当前元素个数这样可以不牺牲存储单元但第二周课本大多采用牺牲一个格子的做法。做题时先看题目默认的是哪种规则用不同的规则队长计算公式也不一样。还有一个小坑队列长度计算公式(rear - front MaxSize) % MaxSize里多出来的 MaxSize是为了防止负数取模。很多语言对负数取模的行为和数学上不一致比如-2 % 5在 C 语言里结果是 -2不是 3。所以一定要先加上 MaxSize再取模。6.3 调试技巧用日志和最小用例缩短排错时间第二周开始我认为最值得培养的习惯是写最小测试用例。比如测试链表删除函数不要一上来就建 100 个节点的链表而是先建一个只有 3 个节点的链表分别测试删除头节点、删除中间节点、删除尾节点的情况。一个节点出问题你立刻能定位到是哪段逻辑而不是被一长串输出淹没。另一个很有用的技巧是在每个关键操作后打印链表当前所有节点。比如在插入、删除后写一个printList(head)就能直观看到链表结构有没有被破坏。这个方法对新手极其友好比单步调试断点更快因为链表出问题往往是结构断了打印一两次就能发现问题位置。用调试器时注意观察指针变量在 IDE 的变量面板里展开指针看 next 是不是指向合理的节点有没有出现 0x0 地址。如果你发现某个指针指向了完全不可能的地方那八成是野指针或者 free 后没有置空。最后说一句关于“卡住了”的心态。数据结构第二周卡住很正常不要觉得是自己笨。我当时学链表反转也卡了好几天后来是把每一步指针变化画在纸上才彻底想通的。如果你发现某个概念到第三天还想不明白休息一下换个角度先做会做的题回头再看那个点。上机时间不在多而在于是否专注地写透每一处细节。