简介《数据结构教案》是面向高校计算机类专业教师及初学者的教学参考文档围绕《数据结构C语言版》课程设计覆盖绪论、数据类型、抽象数据类型、算法设计、数据结构的实现等核心模块。资源共1个doc文件压缩包大小522KB以Word教案形式呈现内含2011-2012学年56学时的课时授课计划、教学目的与要求、重点难点提示及课堂讲授过程安排每个章节还区分了讲授、举例、小结与作业环节适合教师直接用于备课调整或学生梳理知识框架。文档对数据元素、数据对象、逻辑结构四类关系、抽象数据类型三元组表示等概念做了重点展开并给出类C语言描述规范与算法分析思路帮助读者把握从问题建模到算法实现的教学主线。目前已有420人学习下载适合需要系统掌握数据结构课程脉络、快速建立授课或复习体系的读者参考使用。 数据结构教案这个资源拿在老师手里是教学执行蓝图拿在学生手里就是一条完整的复习路径。这份教案来自山东科技大学泰山科技学院信管专业2011—2012学年56学时教材用《数据结构C语言版》参考书配高一凡的《数据结构算法实现及解析》。它跟网上那些PPT讲义和习题集最大的差别在颗粒度每一节课都写明了教学目的、重点难点、课堂进程时间分配、课后作业连课程引入用几分钟、举例放在哪个环节都做了安排。适合带课老师直接改进度复用适合期末复习的学生按课时定位薄弱点也适合准备考研数据结构的人对照检查自己学到哪了。有一点要先说清楚教案默认用类C语言描述算法阅读前需要一点点C语言基础课程讲到串为止树、图和排序在后续课程里展开。2. 绪论与算法分析四类逻辑结构先钉死O 记号别当玄学2.1 数据、数据元素、数据对象与数据结构四个概念的分工数据结构这门课的第一道坎不是写代码而是四个长得有点像的术语。数据是所有能被输入到计算机并被处理的符号集合范围最宽数据元素是其中的一个“个体”比如学生成绩表里的一行记录数据对象是性质相同的数据元素的集合比如整门课所有学生的成绩记录数据结构则是在数据对象上叠加“关系”之后形成的东西。教案里给的形式定义是数据结构是一个二元组记作DS其中 D 是数据元素的有限集合S 是 D 上关系的有限集合。这个定义在后面讲树、讲图时还会反复出现。数据的逻辑结构被归纳成四类这四类的区分标准是元素之间关系的“度数”集合没有关系线性结构是一对一树形结构是一对多图状结构是多对多。结构类型元素间关系典型例子集合松散元素间无明确关系不考虑排序时的人数名单线性结构严格的一对一关系按学号排列的学生成绩表树形结构严格的一对多关系系、班级、学生的归属关系图状结构多对多关系城市交通路网顺着这个分类看整本教材的编排就清楚了线性表处理一对一树和图各自展开。理解逻辑结构之后还有个关键区分——逻辑结构和存储结构是两回事。逻辑结构解决“元素之间是什么关系”存储结构解决“这个关系在内存里怎么表示”顺序映象和链式映象是两种最基本的表示手段。顺序映象靠物理相邻表达逻辑相邻链式映象靠指针显式维护关系这一对概念会贯穿整门课。2.2 抽象数据类型的三元组表示ADT 怎么落到 C 代码抽象数据类型ADT是绪论里另一个容易绕晕的点。教案给出的定义是一个数学模型以及定义在此数学模型上的一组操作。它强调一个关键理念——使用的人只关心逻辑特征不需要了解存储方式定义的人同样不必要关心它如何存储。这就是为什么要引入三元组表示法ADT 抽象数据类型名 { 数据对象、数据关系、基本操作 }也就是DSP三元组D 是数据对象S 是 D 上的关系集P 是对 D 的基本操作集。教案绪论部分用复数类型演示了这套写法翻译成类 C 语言就是下面这样typedef struct { float realPart; // 实部 float imagPart; // 虚部 } Complex; // 构造复数 Z实部和虚部分别赋 v1、v2 void AssignComplex(Complex *Z, float v1, float v2) { Z-realPart v1; Z-imagPart v2; } // 用 sum 返回两个复数 z1、z2 的和值 void Add(Complex z1, Complex z2, Complex *sum) { sum-realPart z1.realPart z2.realPart; sum-imagPart z1.imagPart z2.imagPart; }这段代码体现的就是“数据抽象和数据封装”两个特征。外部调用 Add 时只传两个复数进去完全不关心 Complex 内部是两个 float 还是一个数组将来真要改成用极坐标存储只要保证 AssignComplex 和 Add 的行为不变调用方代码一行都不用动。这是 ADT 最重要的实用价值把变化隔离在类型内部这也是后续每一章定义线性表、栈、队列时都要先写 ADT 再写实现的原因。教案在绪论阶段花一整节课讲这个不是概念游戏是在给后面的所有数据结构立规矩。2.3 算法的五个特性与时间复杂度加法准则、乘法准则一次说清算法的定义是为了解决某类问题而规定的一个有限长的操作序列。教案强调算法必须满足五个特性——有穷性、确定性、可行性、有输入、有输出。设计算法时通常考虑四个目标正确性、可读性、健壮性、高效率与低存储量需求。前三个是“能不能用”最后一个是“好不好用”时间复杂度就是在回答“好不好用”的问题。衡量算法效率有两种方法事后统计法和事前分析估算法。事后统计的缺点很直接——必须先把程序跑起来而且机器性能、编译器优化程度会掩盖算法本身的优劣。事前分析则看几个因素算法选用的策略、问题的规模、编写程序的语言、编译程序产生的机器代码质量、计算机执行指令的速度。把这些因素剥离开剩下来的核心就是语句的执行次数。时间复杂度用大 O 记号表示。严格的数学定义是若 T(n) 和 f(n) 是定义在正整数集合上的两个函数T(n)O(f(n)) 表示存在正的常数 c 和 n0使得当 n≥n0 时满足 0≤T(n)≤cf(n)。教案给了四条程序分析法则实际算复杂度时最常用的是后两条循环语句用乘法准则依次执行的语句段用求和准则。若算法的两个部分时间复杂度为 T1(n)O(f(n)) 和 T2(n)O(g(n))则求和准则 T1(n)T2(n)O(max(f(n), g(n)))乘法准则 T1(n)×T2(n)O(f(n)×g(n))。拿教案里那道一元多项式求值的作业题来说要求不用求幂函数计算 Pn(x)a0a1xa2x²…anxⁿ 在 x0 处的值。最直观的写法是每一项都自己累乘算 x 的幂// 方法一普通累加循环嵌套算幂 double PolyNaive(double a[], int n, double x) { double sum a[0]; // 常数项直接加 for (int i 1; i n; i) { double term 1.0; for (int j 0; j i; j) { term * x; // 用累乘代替求幂函数 } sum a[i] * term; } return sum; // 时间复杂度 O(n^2) }这段代码里外层循环跑 n 次内层循环平均跑 n/2 次总执行次数大约是 n²/2所以时间复杂度是 O(n²)。换成秦九韶算法Horner 规则从最高次项往回收就完全不一样了// 方法二Horner 规则从最高次项开始层层回代 double PolyHorner(double a[], int n, double x) { double sum a[n]; // 从最高次系数开始 for (int i n - 1; i 0; i--) { sum sum * x a[i]; // 每步一次乘法一次加法 } return sum; // 时间复杂度 O(n) }第二种写法只用一次循环每轮做一次乘法和一次加法时间复杂度降到 O(n)。当 n100 时朴素写法要做约 5000 次乘法Horner 只要 100 次这就是复杂度分析对算法选型的实际意义。写作业时有一点要注意教案明确要求“规定算法中不能使用求幂函数”所以第两种写法里的 sum*x 累计方式才是本题的标准答案直接用 pow 函数会被判不符合题意。2.4 空间复杂度与输入输出的两种实现方式算法的存储空间需求用空间复杂度描述定义为 S(n)O(g(n))表示随着问题规模 n 的增大算法运行所需存储量的增长率与 g(n) 的增长率相同。算法的存储量包括三部分输入数据所占空间、程序本身所占空间、辅助变量所占空间。平时分析时重点关注的是第三部分比如递归调用会占用额外的递归工作栈空间这是后面栈一章要展开的内容。教案这道多项式作业题还要求讨论输入输出的两种传递方式通过参数表中的参数显式传递或者通过全局变量隐式传递。显式传递的优点是函数边界清晰不依赖外部状态适合复用和测试缺点是参数列表可能变长调用时书写繁琐。隐式传递的优点是代码简洁但函数隐蔽地依赖全局变量多个函数同时修改同一个全局变量时很难排查调试时容易翻车。常见的做法是优先显式传递确实需要共享的数据再用全局变量并且限定修改范围这也是工程上一直强调的“低耦合”思路的雏形。3. 线性表顺序存储是静态思维链表才是动态解药3.1 线性表的类型定义与十一个基本操作线性表是由 nn≥0个类型相同的数据元素组成的有限序列。n 称为线性表的表长n0 时称为空表。抽象数据类型 LinearList 的数据关系定义为 R1{ai-1, ai| ai-1, ai∈D, i2,…,n}也就是说每个元素最多只有一个前驱和一个后继这种结构在计算机里最容易表达也最常用。教案把线性表的基本操作分成三大类结构初始化与销毁操作、引用型操作、加工型操作。引用型操作不改变表的内容加工型操作会修改表。操作分类操作名作用初始化/销毁InitList / DestroyList构造空表 / 销毁表引用型ListEmpty / ListLength判空 / 求表长引用型PriorElem / NextElem求前驱 / 后继引用型GetElem / LocateElem按位取值 / 按值定位引用型ListTraverse遍历访问加工型ClearList / PutElem置空 / 修改元素值加工型ListInsert / ListDelete插入 / 删除元素学线性表只需要记住一个核心决策逻辑上相邻的元素物理上可以相邻也可以不相邻。前者叫顺序表后者叫链表两种选择带来完全不同的代价结构。顺序表定位快、插入删除慢链表插入删除快、定位慢。后面所有关于线性表的讨论本质上都是在权衡这一对矛盾。3.2 顺序表插入和删除的移动代价顺序表用一组地址连续的存储单元依次存放数据元素用数据元素的存储顺序表示逻辑顺序。这是最简单也最直观的存储方式但它有一个绕不开的代价插入和删除元素时需要大量移动数据元素。插入操作的实现逻辑是先把从第 i 个位置到最后一个位置的元素全部往后移一位再把新元素放进去。关键点是必须从最后一个元素开始往前逐个移动顺序反了就会覆盖数据#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; // 存放元素的数组 int length; // 当前表长 } SeqList; // 在顺序表 L 的第 i 个位置插入 ei 从 1 开始计数 int ListInsert(SeqList *L, int i, int e) { if (i 1 || i L-length 1) return 0; // 位置越界校验 if (L-length MAXSIZE) return 0; // 表满校验 for (int j L-length - 1; j i - 1; j--) { L-data[j 1] L-data[j]; // 从后往前逐个后移 } L-data[i - 1] e; L-length; return 1; }这段代码里最容易被忽略的细节是循环下标的起点。j 从 L-length-1 开始也就是最后一个有数据的元素先把它挪到空位上再依次往前挪。如果反过来从 i-1 开始往前挪第一个被移动的元素就会把相邻元素覆盖掉整张表直接乱套。删除操作逻辑对称从第 i1 个元素开始往前逐个移动平均移动次数约 (n-1)/2时间复杂度同样是 O(n)。教案把顺序表的问题总结得很直白插入或删除时产生大量数据元素移动对长度变化较大的线性表要一次性分配足够的存储空间而这些空间常常得不到充分利用线性表的容量难以扩充。这三个问题就是顺序表的边界也是链式存储存在的理由。3.3 单链表头结点、逐个插入与重复结点删除单链表用一组地址任意的存储单元存放数据元素这组存储单元可以连续也可以不连续。每个结点由数据域和指针域组成C 语言描述如下typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域指向后继结点 } LNode, *LinkList;生成链表的过程是一个结点“逐个插入”的过程。操作步骤是先建立一个空表输入数据元素 an建立结点并插入再输入 an-1建立结点并插入依次类推直到输入 a1 为止。这样建出来的链表数据在逻辑上还是 a1 到 an 的顺序因为每次新结点都插到了表头位置这种插法叫头插法。头插法的特点是实现简单但要注意生成后的链表顺序与输入顺序相反如果要求输出顺序跟输入一致就得改成尾插法或者建表后反转。教案第二周的作业题是删除单链表中值重复的结点使结果表中各结点值均不相同。实现思路是先取开始结点中的值将它与其后的所有结点值一一比较发现相同就删除然后再取第二个结点的值重复上述过程直到最后一个结点。删除时要特别注意指针的衔接否则链表会断掉// 删除单链表中所有值重复的结点 void DeleteDup(LinkList L) { LNode *p L-next; // 外层结点作为比较基准 while (p ! NULL) { LNode *q p; // q 始终指向 r 的前驱 LNode *r p-next; // r 从基准结点之后开始扫描 while (r ! NULL) { if (r-data p-data) { q-next r-next; // 先让前驱的 next 跳过 r free(r); // 再释放 r r q-next; // r 移动到下一个比较位置 } else { q r; // 不相等则 q、r 同步后移 r r-next; } } p p-next; // 换下一个基准结点 } }这个算法的核心在于维护前驱指针 q。删除 r 时必须先把 q-next 改到 r-next才能安全释放 r释放后 r 要从 q-next 继续取不能直接把 r 往后挪因为 r 已经被释放了。很多初学者在这里翻车free(r) 之后还拿 r 去取 next访问的是已经释放的内存程序行为完全不可预测。这个算法的时间复杂度是 O(n²)但胜在逻辑简单、原地操作不需要额外空间。3.4 循环链表、双向链表与一元多项式循环链表是单链表的变体最后一个结点的指针域指向头结点形成一个环。它的好处是从任意一个结点出发都能遍历整张表判空条件也从“头结点指针为 NULL”变成“头结点指针指向自身”。双向链表则在每个结点里增加一个 prior 指针指向前驱代价是每个结点多占一个指针的存储空间换来的是双向遍历和前驱定位的 O(1) 复杂度。一元多项式是线性表应用的经典例子。计算机里可以用一个线性表表示多项式 P(p0, p1, …, pn)教案给出的抽象数据类型定义要求数据对象 TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数数据关系中要求 ai-1 的指数值小于 ai 的指数值也就是按指数递增有序排列。实现时直接用已有的带头结点有序链表来表示typedef OrderedLinkList polynomial; // 用带头结点的有序链表表示多项式两个多项式相加时同时扫描 Pa 和 Pb 两个链表谁的指数小就先把谁接进结果链表指数相等时系数相加和为 0 就删除该结点不为 0 则更新系数一个链表扫描完后把另一个的剩余结点全部接上。这里三个分支缺一不可漏掉指数相等分支是后面最常见的问题。顺序表和链表怎么选教案给了一个很实用的判断框架对比维度顺序表链表存储空间连续需预分配任意按需分配但每个结点多一个指针按位访问O(1) 直接定位O(n) 从头遍历插入/删除O(n) 移动元素O(1) 修改指针已知位置时空间利用率可能浪费预分配空间无浪费但指针有开销实际场景里频繁按位置访问、表长相对稳定时用顺序表频繁增删、表长变化大时用链表。工程中还会见到动态数组如 C 的 vector这种折中方案本质是在顺序存储的基础上做容量扩容理解顺序表的三个局限后再看动态数组的实现就不会觉得陌生。4. 栈、队列与串受限线性表的六种典型应用4.1 栈后进先出与六个应用场景栈是只能在表尾进行插入和删除操作的线性表允许操作的一端叫栈顶 top另一端叫栈底 bottom。它的特点是后进先出就像餐馆里一叠盘子后放上去的盘子反而最先被拿走。教案用这个生活例子引出栈然后一口气给了六个应用场景数制转换、括号匹配、行编辑、迷宫求解、表达式求值、实现递归。六个场景看似不相关本质都是同一个问题——需要按“后发生的先处理”的顺序保存中间状态。数制转换是最好入手的例子。十进制数 N 转换成 d 进制数的原理是反复做除法N(N div d)×dN mod d每次取余数最后倒序输出余数就是结果。这个“先算出的余数最后输出”的顺序恰好就是栈的语义// 十进制 N 转 d 进制除基取余余数入栈最后出栈 void Conversion(int N, int d) { SeqStack S; InitStack(S); while (N 0) { Push(S, N % d); // 余数压入栈 N N / d; // 整除更新 N } while (!StackEmpty(S)) { int e; Pop(S, e); printf(%d, e); // 出栈顺序即目标进制的高位到低位 } }这段程序的参数 N 是被转换的十进制数d 是目标进制。比如 N13、d2循环里依次压入余数 1、0、1、1出栈后输出 1101正好是 13 的二进制形式。写的时候要注意循环条件是 N0如果 N 本身是 0应该先压一个 0 再出栈否则输出为空。括号匹配的检验用“期待的急迫程度”来描述。扫描表达式遇到左括号就入栈遇到右括号就与栈顶左括号配对。出错有三种情况和栈顶左括弧不相匹配栈中没有左括弧等在那里表达式扫描完了栈里还有左括弧没等到匹配。三种情况对应三种返回错误覆盖了所有括号不匹配的可能。行编辑问题也类似设一个输入缓冲区遇到“#”做退格、遇到“”做退行本质上就是字符栈的入栈和出栈。迷宫求解用栈记录当前路径当前位置入栈表示“纳入路径”出栈表示“从当前路径上删除前一通道块”。表达式求值的核心是操作数、运算符和界限符三类元素配合运算符优先级表用两个栈完成。递归函数的运行过程则依赖一个递归工作栈每一层调用的局部数据都存在自己的栈帧里。4.2 队列链队列与循环队列队满队空怎么判断队列是先进先出的线性表只允许在队尾插入、队头删除。教案用“排队”这个生活场景引入然后给出了完整的基本操作集InitQueue、DestroyQueue、QueueEmpty、QueueLength、GetHead、ClearQueue、EnQueue、DeQueue、QueueTravers。队列的实现有两种链队列和循环队列。链队列用链表实现设置队头指针 front 和队尾指针 rear入队操作在 rear 后挂新结点出队操作从 front 摘结点逻辑上比顺序队列简单。循环队列是为了解决顺序队列“假溢出”问题的方案把数组首尾相接出队后空出来的位置可以继续复用。循环队列最关键的坑是队满和队空的判断因为 front 和 rear 相等时既可能是空也可能是满#define MAXQSIZE 100 typedef struct { int *base; // 存放元素的数组 int front; // 队头下标 int rear; // 队尾下标 } SqQueue; // 循环队列入队 int EnQueue(SqQueue *Q, int e) { // 队满条件rear 再走一步就追上 front if ((Q-rear 1) % MAXQSIZE Q-front) { return 0; // 队满入队失败 } Q-base[Q-rear] e; // 元素放到队尾 Q-rear (Q-rear 1) % MAXQSIZE; // 尾指针后移取模 return 1; } // 循环队列出队 int DeQueue(SqQueue *Q, int *e) { if (Q-front Q-rear) { return 0; // 队空出队失败 } *e Q-base[Q-front]; Q-front (Q-front 1) % MAXQSIZE; return 1; }这段代码默认的做法是牺牲一个存储单元来区分队满和队空队空条件是 frontrear队满条件是 (rear1)%MAXQSIZEfront也就是让 rear 永远不真正追上 front两者之间至少隔一个空位。如果不想牺牲存储单元可以给结构体加一个 size 计数器入队加一、出队减一size0 判空、sizeMAXQSIZE 判满两种方案各有利弊但加计数器之后取模公式里的“加一判断”就不再适用这是二选一的设计决策。4.3 串定长顺序存储与堆存储的选择串是数据元素为字符的线性表教案要求熟悉串的七种基本操作并掌握两种存储结构定长顺序存储和堆存储。定长顺序存储用一个固定长度的字符数组保存串实现简单但最大的问题是长度溢出——超过数组上限的字符会被截断而且做插入、替换操作时频繁移动字符效率低。堆存储则是动态分配空间串的长度可以根据需要增长插入、连接操作更灵活代价是存储管理更复杂需要自己维护内存的申请和释放。教案在串这一章安排的作业是“对串的操作的应用”没有给具体题目常见做法是实现一个子串查找或串替换功能。工程上选哪种存储结构判断标准很简单串的长度是否基本固定固定用定长变化大用堆。这个决策和顺序表与链表的取舍逻辑完全一致说明数据结构的选型思想是一以贯之的。4.4 递归一个需要栈支撑的过程递归函数的运行过程类似于多个函数的嵌套调用差别仅在于调用函数和被调用函数是同一个函数。为了保证每一层递归调用都是对“本层”的数据进行操作执行递归函数的过程中需要一个递归工作栈每进入一层就压入一个栈帧保存本层的参数、局部变量和返回地址退出时弹出。教案在栈这一章把递归当作栈的第六个典型应用来讲这个定位很重要。递归不是玄学它就是函数调用只是被调用的那个函数恰好是它自己。教材里后来会讲到用栈模拟递归、把递归改成非递归原理就是手动维护这个栈帧。这也是为什么数据结构课程要把栈放在递归前面讲——理解了递归工作栈才能理解递归的代价每层调用都要占用栈空间深度过大时栈会溢出这是后面要单独排查的问题。5. 数据结构高频翻车点五个踩坑记录与排查思路这一章把实际写代码时最容易翻车的五个问题集中列出来每条都按“现象、原因、解决”的顺序排查。这些问题在教案对应的章节里其实都埋了伏笔但教案是授课节奏不会把每个坑单独拎出来放大这里补上。5.1 顺序表插入后数据被莫名覆盖现象在顺序表中间位置插入一个元素插入位置之后的数据变得乱七八糟有的元素重复出现有的直接丢了。原因插入的移动循环写成了从前往后搬第一个被移动的元素把相邻位置的原始值覆盖掉后续搬的都是被污染过的值。教案里明确要求从最后一个元素开始倒着移动这一步在纸上画图时很清楚一写代码就容易顺手写成正序。解决循环下标从 L-length-1 递减到 i-1先搬最后一个元素再依次往前搬搬之前先做位置越界和表满两个校验避免数组越界写。5.2 循环队列队满和队空分不清现象循环队列刚初始化就入队几个元素再判断队满时结果不对或者队里明明有元素出队却提示队空。原因用 frontrear 同时判断队空和队满没有做单元牺牲。循环队列里 front 和 rear 相等时有两种可能一个元素都没有或者队列满到 rear 恰好绕一圈追上 front。解决默认方案是牺牲一个存储单元队满条件改为 (rear1)%MAXQSIZEfront保证 rear 和 front 之间永远隔一个空位如果不想牺牲空间就加一个 size 计数器记录元素个数入队加一、出队减一用 size 判断空和满。5.3 链表删除重复结点后链表断了现象用双循环删除单链表中的重复结点程序运行到一半出现段错误或者打印链表时从删除点之后的内容丢失。原因删除结点 r 时没有先把前驱 q 的 next 指针接到 r 的 next 上就直接 free 了 r或者 free 之后还用 r 去取 next。被释放的内存已经不属于程序访问它属于未定义行为。解决删除操作固定三步走——先把 q-next 指向 r-next再 free(r)最后把 r 更新为 q-next 继续比较。注意删除后 q 不能动因为 q 是前驱只有遇到不相等的情况才让 q 和 r 同步后移。5.4 递归深度一大就崩现象用递归实现斐波那契数列或阶乘n 稍微大一点程序就跑得很慢再大直接栈溢出把递归改成循环后立刻就好了。原因递归工作栈每一层都要保存参数和返回地址深度到几千上万层就会耗尽栈空间而像斐波那契这种递归f(n)f(n-1)f(n-2) 会重复计算大量子问题时间复杂度接近 O(2ⁿ)慢是必然的。解决递归深度不确定时改循环子问题重复时加记忆化用一个数组缓存已算过的值能写成尾递归的尽量尾递归。判断标准很简单——递归深度和问题规模同量级增长时就要考虑栈溢出的风险。5.5 一元多项式相加结果丢项现象计算 PaPaPb 之后结果里少了一些项特别是指数相同的项只保留了一边的系数。原因两个有序链表相加时没有处理指数相等的情况。正确逻辑是三个分支Pa 指数小把 Pa 结点接入结果Pa 指针后移Pb 指数小把 Pb 结点接入结果Pb 指针后移指数相等系数相加后判断和是否为 0为 0 删结点不为 0 更新系数然后两个指针同时后移。漏掉第三个分支指数相等的项就会被跳过。解决写之前先在纸上把两个多项式各写一行用三个手指分别指两个链表的当前结点和结果链表的尾结点模拟一遍三种情况再动手写代码。6. 用停车场管理实验做一次综合验收栈和队列的完整落地清单6.1 实验模型与测试数据停车场管理实验是教案第四周安排的实践环节它的设计很巧妙用一个栈模拟停车场、一个队列模拟便道再加一个临时栈模拟为出车让路的过程。实验要求停车场内只有一个能停放 n 辆汽车的狭长通道汽车按到达时间由北向南排列大门在最南端车满后后来的车在门外便道等待有车离开时排在便道第一位的车驶入。训练的核心是栈和队列的组合运用。实验给定了一组测试数据n2输入包含五组到达和三组离开。每辆车的记录是三个数据项动作A 到达、D 离去、E 结束、车牌号、时刻。输入含义预期处理结果A151号车5时刻到达停入停车场1号位A2102号车10时刻到达停入停车场2号位D1151号车15时刻离去2号车让路后1号车出场收费A3203号车20时刻到达直接停入空出的位置A4254号车25时刻到达停入停车场2号位A5305号车30时刻到达停车场满到便道排队D2352号车35时刻离去4号车让路2号车出场收费D4404号车40时刻离去5号车从便道驶入停车场E00结束程序终止这组数据把每一种边界都覆盖到了满员后到达、离场时需要倒车让路、便道车辆补位一套流程走完栈和队列的基本操作基本都练到了。6.2 核心模拟逻辑实验的核心模拟逻辑可以压缩成三个动作到达时停车场不满就入栈满了就入队离开时先检查该车在停车场还是在便道在停车场则把挡路的车依次挪进临时栈等目标车出场后再从临时栈倒回停车场同时按停留时间收费开头是便道的车离开则直接出队。代码骨架如下// A 到达停车场栈不满则入栈满则入便道队列 void HandleArrive(Car c, Stack *park, Queue *lane) { if (!IsStackFull(park)) { Push(park, c); // 停车场有空位直接停入 } else { EnQueue(lane, c); // 停车场满到便道排队等待 } } // D 离去目标车在停车场中则让路车进临时栈再倒回 void HandleDepart(Car c, Stack *park, Stack *temp, int nowTime) { Car cur; while (1) { Pop(park, cur); // 从停车场栈顶弹出 if (cur.num c.num) break; // 找到目标车 Push(temp, cur); // 挡路的车先挪到临时栈 } int stay nowTime - cur.arriveTime; // 离开时刻减到达时刻 printf(车%d停留%d分钟收费%d\n, cur.num, stay, stay * fee); while (!IsStackEmpty(temp)) { Pop(temp, cur); Push(park, cur); // 让路的车按原序倒回停车场 } if (!IsQueueEmpty(lane)) { DeQueue(lane, cur); Push(park, cur); // 便道第一辆车补位 } }这段代码里最关键的是让路车的倒回顺序。临时栈 pop 出来的顺序与挡路车的原顺序相反直接 Push 回去正好恢复原序这就是栈的特性在起作用。很多人在这一步翻车把挡路车挪进临时栈之后忘了倒回或者倒回时顺序搞反导致停车场内的车序错乱。验证方法很简单就按上面那组测试数据走一遍每一步都检查栈顶和队首是谁。做完这个实验栈和队列的掌握程度基本就清楚了我以前带学生上实验课总有人把离开操作写成直接删除目标车忘了把挡路的车倒进临时栈最后停车场里的顺序全乱了。从那以后我每次讲栈和队列的收尾课都强制自己走一遍完整流程先口述数据流再动手写代码最后用边界测试数据验证。这份教案的价值正在于此——它把每一章都拆成了可执行的教学步骤对照着课时计划逐节过一遍比闷头刷题更能把概念串成体系希望帮到你。本文还有配套的精品资源点击获取