数据结构与算法设计
实验指导书
西华大学
计算机与软件工程学院 计算机系
2019.2
前 言
《数据结构与算法设计》是计算机类相关专业的一门核心基础课程，也是计算机程序设计的重要理论技术基础，更是考研专业课之一。主要介绍线性结构、树结构、图结构、集合四种基本逻辑结构及存储实现，在此基础上介绍一些典型的算法设计技术和时间效率分析。课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习该课程，实验是一个关键的环节；在理解算法的基础上，上机实验是最佳途径。因此，实验环节的好坏是能否学好本课程的关键。为了更好地配合学生实验，特编写本实验指导书。
第1章 实验指导
1.1 实验意义
实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的检查者。
1.2 实验步骤
常用软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目远不如实际问题中的复杂程度高，但为培养一个软件工作者所应具备的科学工作方法和作风，也应该遵循以下五个步骤来完成实验题目： 1．问题分析和任务定义
设计之前，首先应该充分分析和理解问题，明确问题要求做什么，限制条件是什么等。 本步骤强调的是做什么，而不是怎么做。对问题的描述应该避开算法和所涉及的数据类型，而对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，那么结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等。还应为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。
2．逻辑设计和详细设计
逻辑设计，定义相应的数据类型，并按以数据结构为中心的原则划分模块，定义主程序和各个抽象数据类型。详细设计，定义相应的存储结构，写出各个函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，数据操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个操作的功能说明)，各主要模块的算法，画出模块之间的调用关系图。详细设计的结果是对数据结构和操作的进一步求精，写出数据存储结构的类型定义，写出函数形式的伪码算法。在求精的过程中，应该尽量避免陷入具体编程语言的语法细节，不必过早给出辅助的数据结构和局部变量等。 注：设计不是编码。 3．编码实现和静态检查
编码是把详细设计结果编写为具体的程序。在上机之前，严格的静态检查是必不可少的。静态检查的通常做法如下：
（1） 用设计好的测试数据，逐步执行程序（逐个测试每一个模块的正确性）； （2） 需深入理解程序的执行逻辑，再加入一些注解和断言。 4．上机准备和上机调试 上机准备包括以下几个方面：
（1）注意同一种高级语言不同版本之间的语法差别。
（2）熟悉语言的集成开发环境IDE（参阅用户手册），尤其熟悉常用操作的快捷键。 （3）掌握调试工具的用法，设计测试数据并手工执行得出正确结果。
（4）上机调试程序时要带该语言的教材、参考手册。调试最好逐个模块进行，自底向上即先调试低层的函数；调试过程中借助开发环境提供的各种调试功能，提高调试效率。调试中
遇到的各种异常现象往往是预料不到的，此时应确定疑点，通过修改程序来证实或绕过它。调试正确后，认真整理源程序及其注释，形成风格良好的源程序清单和执行结果。 5．撰写实验报告
按实验报告的具体要求和规范撰写。
1.3 实验报告
按照《西华大学计算机与软件工程学院上机实验报告》要求撰写实验报告。
1.4 实验考核
实验成绩构成，如下： ? 编程技术：30% ? 测试分析：20% ? 实验报告：50%
数据结构与算法设计实验指导书
