云南大学数据结实验指导书.pdf

数据结构实验指导书 张德海 李劲 朱艳萍 金鑫 刘宇 秦江龙 本书是以《数据结构》2015 版课程教学大纲和实验教学大纲为指导，分 别从实验（包含ABC 三个级别的实验）的九个方面（实验目的、问题描述、基本 要求、CDIO 项目要求、实验内容、实现提示、参考程序、教学环节组织以及思 考题）来组织内容。其中实验目的强调了每个实验要掌握的内容；问题描述是对 实验题目作进一步的解释；CDIO 项目要求给出了按CDIO 标准进行实现的基本要 求；实验内容是对基本实验和扩展实验的问题进行描述和标明要达到的层次，并 且对实现要求进行了规划；实现提示对整个实验的结构进行了组织和指导；而参 考程序则列出了实验要求中，特别是一些重要算法的参考描述；教学环节组织则 明确了教学中师生的互动及职责；思考题则是布置给学生对同类实验的一种思考 和提示。 一．关于实验步骤的要求和建议 从以往的教学事先实验的经验来看，在初学阶段执行严格的实验步骤规范 （包括上机操作规范），机时利用率会大大提高，有助于养成良好的程序编制风 格，培养严谨、科学、高效的工作方式。 在以往的教学实践中，经常发现很多学生抱怨说，花了两个小时才找出一个 错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自己。有的学 生不屑于按实验步骤规范去做，甚至对于实验步骤的要求和建议看都不看一遍， 认为那是浪费时间，这是及其害的。实验步骤规范不但可以培养科学化的工作作 风，而且还能有效地避免错误。 具体的步骤规范如下： 1.问题分析与系统的结构设计： 充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数 据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使 得对数据结构的存取通过这些操作加以实现。在这个过程中，要综合考虑系统功 能。要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个子程序（过 程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则 更加清晰，这样便完成了系统结构设计。 2.详细设计和编码 详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE 和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入 细节。在编码时，可以对详细设计的结果进一步求精，用高级语言表示出来。 程序的每一行最好不超过 60 个字符。每个子程序（或过程、函数）通常不 要太长，以 40 行为宜。子程序（或过程、函数）包含的程序行数太多，容易造 成理解的困难。控制 IF 、WHILE 等语句的连续嵌套的深度。程序的目的性必须 明确。对每一段程序完成的作用，除非常明显的除外（如：x = x + 1; 注释为 x 加 1，没有什么意义），都应加以注释。这会对程序的调试提供很多方便。根据 情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。另 外，对于输入输出语句，必须对它们的作用加以说明。否则，在调试程序时，无 法了解系统需要输入什么样的数据，系统输出的又是什么。程序的书写，必须按 照一定的规范，如保留字小写时涂黑，或者大写等等，风格要统一。具体的要求 可参看软件工程中的有关规定。 3.上机准备和静态检查 上机准备：  高级语言文本  熟悉机器的用户手册，熟悉常用的命令。  准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具可供 利用，可以自己先设计一些以供使用。  静态检查 自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了 解该程序的逻辑。 4.上机调试程序 自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联合调 试。调试正确后将源程序和运行结果加以打印输出。 5.实验报告的整理  需求及规格说明 问题描述，求解的问题是什么。  设计： 设计思想：存储结构、主要的算法思想。 设计表示：子程序（过程或函数）的规格说明，通过调用关系图表 示它 们之间的调用关系。 实现注释： 详细设计表示：主要算法的框架。  用户手册：使用说明。  调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体会、 时空复杂度等。  附录 源程序清单和结果：源程序必须有注