大学的每个专业都要制定教学计划。

数据结构课程实验指导书—第一个实验

实习步骤

（一）问题分析和任务定义

在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什么。注意：本步骤强调的是做什么？而不是怎么做。

主要完成三个方面的工作：

（1）分析并确定问题要处理的对象（数据）是什么。例如：输入数据的类型、值的

范围以及输入的形式。

（2）分析并确定要实现的功能是什么。也就是说要对输入的数据进行什么样的处理。

注意：对问题中描述的需要实现的功能，应避开算法（具体的实现方法）和所

涉及的数据类型，仅需对所需完成的任务做出明确的定义。

（3）分析并确定处理后的结果如何显示。

这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据；以及相应的输出结果。

（二）数据类型和系统设计

当需求分析结束，明确问题要求后，开始为编写程序设计合适的数据结构和算法。本步骤分概要设计和详细设计两步实现。

概要设计指的是，对问题描述中涉及的操作对象定义相应的抽象数据类型，并设计合适的算法；以及定义程序各个功能模块和模块之间的关系。在这个过程中，要根据问题的功能需求综合考虑，设计时空复杂度最优的抽象数据结构和算法（注意：实现提示和给出的部分代码中以及给出了建议）。抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体，算法思想和过程明确有效，程序结构清晰、合理、简单和易于调试。作为概要设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），主要模块的算法思想，并画出模块之间的调用关系图。

详细设计则定义相应的物理存储结构（抽象数据类型的物理实现）并写出各基本操作的伪码算法，以及主要模块算法的具体步骤。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，算法书写规范（采用文字性的步骤描述或者算法流程图的形式都行）。在求精的过程中，应尽量避免陷入语言细节，不必过早描述辅助数据结构和局部变量。

（三）编码实现和静态检查

在实验过程中，题目中会给出程序的部分源代码，根据实习第二步的设计结果以及源代码的提示，编码实现程序的其余部分。

编码是把详细设计的结果进一步求精为程序设计语言程序。对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。

写出编码的程序后，在上机（编译和调试）之前，认真的静态检查是必不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为纠查错误是编译器的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率是极低的。

静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。

－ 1 －

数据结构课程实验指导书—第一个实验

（四）上机准备和上机调试

上机准备包括一下几个方面：

（1）熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，

以便顺利进行上机的基本活动。

（2）上机调试程序时要带一本高级语言教材或手册。

（3）掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误

砍柴工”。计算机各专业的学生应该能够熟练运用高级语言的程序调试器

DEBUG调试程序。

上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试底层函数。必要时可以另写一个调用驱动程序。这种表面上的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。

在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想”，而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。

（五）总结和整理实习报告

按照实习报告的格式完成整个实习报告。同时总结和思考，回味设计的过程，体会调试的过程，总结编程中的收获，记录实习过程的体会，交流程序设计各个步骤的心得。“学而不思则罔，思而不学则殆。”在程序设计中，只有做到勤思考、善总结，才能不断进步。

－ 2 －

数据结构课程实验指导书—第一个实验

实习报告规范

实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：

1．需求分析

以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：

（1）输入的形式和输入值的范围；

（2）输出的形式；

（3）程序所能达到的功能；

（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2．概要设计

说明本程序中用到的所有抽象数据类型的定义、算法的基本思想、主程序的流程以及各程序模块之间的层次（调用）关系。

3．详细设计

（1）实现概要设计中定义的所有数据类型（物理数据结构），对每个操作只需要写出伪码

算法；

（2）算法的具体步骤；

（3）算法的时空分析和改进设想；

（4）画出函数的调用关系图。

（5）输入和输出的格式。

4．调试分析

调试过程中遇到的问题，以及如何解决的；

5．测试结果

根据实验提供的测试数据，列出你所编写的程序的测试结果。

6．用户使用说明（可选）

说明如何使用编写的程序，详细列出每一步的操作步骤。

7．实验心得（可选）

对实验设计与实现过程的回顾和分析，以及经验和体会。

8．附录（可选）

带注释的源程序。如果是提交源程序电子版，只需列出程序文件名的清单。

－ 3 －

数据结构课程实验指导书—第一个实验

实验5教学计划编制问题

背景

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

问题描述

若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。

基本要求

（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先

修课的课程号。

（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指

定的文件中。

实现提示

基于拓扑排序实现教学计划流程的求取。如果拓扑排序不成功，表示问题无解。

－ 4 －