数据结构与算法设计实验指导
前 言
上机实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的检查者。
为了达到上述目的，本篇安排了6个主实验单元，除实验0作为预备练习之外，其它各单元的训练重点在于基本的数据结构，而不强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及几部分教学内容。在每个实验单元中安排有难度不等的4～9个实验题，每个题目的题号之后标有难度系数，对于特别推荐题也作了标记。与习题的情况类似，在一个单元之内比较题目难度才有意义。
此外，难度系数是根据题目的基本要求而给出的。每个实验题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等5个部分组成。 问题描述旨在为学生建立问题提出的背景环境，指明问题“是什么”；
基本要求则对问题进一步求精,划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；
测试数据部分旨在为检查学生上机作业提供方便，在完成实验题时应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据； 在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示；选做部分向那些尚有余力的学生提出了更严峻的挑战，同时也能开拓其他学生的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。
不难发现，这里与传统的做法不同，题目设计得非常详细。会不会限制学生的想象力，影响创造力的培养呢？回答是：软件发展的一条历史经验就是要限制程序设计者在某些方面的创造性，从而使其创造能力集中地用到特别需要创造性的环节之上。实验题目本身就给出了问题说明和问题分解求精的范例，使学生在无形中学会模仿，它起到把学生的思路引上正轨的作用，避免坏结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查。题目的设计策略是：一方面使其难度和工作量都较大，另一方面给学生提供的辅助和可以模仿的成分也较多。当然还应指出的是，提示的实现方法未必是最好的，学生不应拘泥于此，而应努力开发更好的方法和结构。
在实现的时候应注意，要尽量减少依赖于具体机器计算环境的用法，例如，某些机器上的Pascal语言编译程序版本允许语言中出现“EXIT”过程调用，作用是终止程序的执行。若使用，也应在注释中指出。这样得出的程序易于在不同机器上运行（有好的可移植性），而这里的主要目的在于培养良好的习惯。Pascal语言是结构化程序设计语言，具有递归能力，可移植性也较好，是特别推荐的实现语言。
本篇的一个特点是为实验制定了严格的规范。一种普遍存在的错误观念是，调试程序全凭运气。学生花2个小时的机上时间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该
第1页
数据结构与算法设计实验指导
如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实验步骤规范进行实验不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。
在每个实验单元提供了一个完整的实验报告示例，在起到实验报告规格范例作用的同时，还隐含地提供了很多有益的东西，比如，基于数据类型的系统划分方法；递归算法设计方法和技巧；对于有天然递归属性的问题如何构造非递归算法；以及所提倡的程序设计风格等等。但从另一方面看，计算机学科在不断发展，可以使用的语言工具越来越丰富，在本篇中的实验示例还只是应用面向过程的语言进行设计和编写程序，同样的实验题，学生也可以用面向对象的语言来实现。希望书中的实验报告示例能起到一个抛砖引玉的作用，以迎来学生更多更优良的设计范例。
华北工学院应用数学系计算教研室
2002．8
第2页
数据结构与算法设计实验指导
目 录
1. 实验步骤和实验报告规范
1. 1 实验报告的规范
2. 抽象数据类型
2.1 复数四则运算 2.2 有理数四则运算 2.3 海龟作图
3. 线性表
3.1运动会分数统计 3.2 约瑟夫环
3.3 集合的并、交和差运算 3.4 长整数四则运算
4. 栈、队列与递归算法设计
4.1 停车场管理 4.2车厢调度
4.3算术表达式求值演示 5. 串及其应用
5.1 文本格式化 5.2 简单行编辑程序 5.3 串基本操作的演示
6. 数组和广义表 6.1稀疏矩阵运算器
6.2识别广义的“头”或“尾”的演示
7. 树、图及其应用 7.1 图遍历的演示
7.2 教学计划编制问题 7.3 最小生成树问题 7.4 全国交通咨询模拟
8.存储管理、查找和排序
8.1伙伴存储管理系统演示 8.2哈希表设计 8.3 图书管理
8.4 平衡二叉树操作的演示 8.5英语词典的维护和识别
第3页
数据结构与算法设计实验指导
§1.1实验报告的规范
实验报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
一、需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定： （1）输入的形式和输入值的范围； （2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 二、概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的（调用）关系。 三、详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法（伪码算法达到的详细程度建议为：按照伪码算法可以在计算 机键盘直接输入高级程序设计语言程序）；画出函数和过程的调用关系图。 四、调试分析
内容包括：
a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析； b．算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想；
c．经验和体会等。 五、用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。 六、测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求 分析中所列。 七、附录
带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。
在以下各实验单元中都提供了实验报告实例。值得注意的是，实验报告的各种文档资 料，如；上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写（当然可以 也应该最后用实验报告纸誊清或打印）。
§2.1复数四则运算
［问题描述］
设计一个可进行复数运算的演示程序。 ［基本要求］
实现教科书1.2节例1-6中定义的6种基本运算，运算结果以复数的表示形式显示。 ［测试数据］
第4页
