目录
前言 ........................................................................ 1 实验一 熟悉编程环境 ........................................................ 4 实验二 顺序表的基本操作 ..................................................... 5 实验三 单链表的基本操作 .................................................... 8 实验四 栈的基本操作 ....................................................... 11 实验五 队列的基本操作 ..................................................... 13 实验六 二叉树建立及遍历操作 ............................................... 15 实验七 二叉树的应用程序设计 ............................................... 16 实验八 图的建立及遍历操作 ................................................. 17 实验九 图的最小生成树算法的实现 ........................................... 20 实验十 图的最短路径算法的实现 ............................................. 21 实验十一 顺序表查找算法的实现 ............................................. 23 实验十二 二叉排序树的查找算法实现 ......................................... 25 实验十三 哈希表的应用实现 ................................................. 26 实验十四 插入排序算法的实现 ............................................... 27 实验十五 交换排序算法的实现 ............................................... 28 实验十六 选择排序算法的实现 ............................................... 29 综合实践：数据结构课程设计 ................................................. 31
- 1 -
前言
为了同学能够更好的完成实验任务，达到本课程的设置目的，锻炼自己的实践动手能力，请大家认真阅读本前言内容，希望能够给你一定的学习启示。
1． 关于实习步骤的要求和建议
从以往的教学经验来看，在初学阶段执行严格的实验步骤规范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的编成风格，培养严谨、科学、高效的工作方式。
在以往的教学实践中，学生经常出现的问题：
（1）实验时间不够，部分学生花两个学时不能找出程序错误（有的同学甚至一个错误都没有找出），一无所获，浪费机时。
（2）没有达到实验要求，在两个机时中没有完成实验任务，不可能体会数据结构的精髓，更不能很好地掌握内容，没有锻炼好独立思考、设计能力，最终没有达到本课程的要求。本课程独立32学时的实验是验证和考量学生对计算机软件设计基本能力的重要实践环节，独立做好每个实验是本课程的最基本要求。
（3）高级程序设计能力亟待提高，高级语言程序设计（C语言程序设计）是本门课程的编程基础，很多同学编程基础不过关，将大量时间浪费在以往知识的练习中，甚至有个别同学只会编写Hello Word程序，基本功太差。
（4）没有严谨 的实验作风，有的学生不屑于按实习步骤规范去做，甚至对于实习步骤的要求和建议看都不看一遍，认为那是浪费时间，这是及其害的。实习步骤规范不但可以培养科学化的工作作风，而且还能有效地避免错误。
本课程具体的要求如下：
（1） 认真独立完成每个必做实验，达到预期效果；实验过程中有任何问题及时与指导教师联系，在规定时间内没有完成实验的学生利用课余时间完成实验，实验过程中可以与同学相互交流，但实验任务必须独立完成。
（2） 高级语言程序设计不过关的同学，利用课余时间进行自学，必须达到能够熟练使用高级语言进行程序设计。
（3） 每次实验中的程序自己要保存好，为后继的实验奠定基础。本课程中的很多实验要使用到以前实验的代码，要保存好自己的代码（做好注释，注意书写格式），否则，不可能在两个机时之内完成实验任务。最后实验完成后由班长和学习委员将所有同学的实验代码以实验名称和姓名为目录，收齐后交给指导教师。
（4） 认真书写实验报告，实验报告要自己独立书写，书写要认真、细致，体现科学严谨的工作作风。 实验步骤规范如下：
（1）问题分析与系统的结构设计： 充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操
1
作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要综合考虑系统功能。要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，实验复杂是必须先使用流程图理解整个程序的设计思想和方法，这样便完成了系统结构设计。
（2）详细设计和编码
详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。在编码是，可以对详细设计的结果进一步求精，用高级语言表示出来。
程序的每一行最好不超过 60 个字符。每个子程序（或过程、函数）通常不要太长，以 40 行为宜。子程序（或过程、函数）包含的程序行数太多，易于造成理解的困难。控制 IF 、WHILE 等语句的连续嵌套的深度。程序的目的性必须明确。对每一段程序完成的作用，除非常明显的除外，都应加以注释。这会对程序的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。另外，对于输入输出语句，必须对它们的作用加以说明。否则，在调试程序时，无法了解系统需要输入说明，系统输出的又是什么。程序的书写，必须按照一定的规范。
（3）上机准备和静态检查 上机准备：
? 高级语言文本
? 熟悉机器的用户手册，熟悉常用的命令。
? 准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具
可供利用，可以自己先设计一些以供使用。 ? 静态检查
自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了解该程序的逻辑。 （4）上机调试程序
自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联调。调试正确后将源程序和运行结果加以列印输出。 （5）整理实习报告
? 需求及规格说明（问题描述，求解的问题是什么）。 ? 设计：
设计思想：存储结构、主要的算法思想。
设计表示：子程序（过程或函数）的规格说明，通过调用关系图表 示它们之间的调用关系。 实现注释：
详细设计表示：主要算法的框架。
? 用户手册：使用说明（用户如何使用程序，例如输入数据的类型、
格式和意义等，使用时注意的事项，输出的意义和格式等）。
? 调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体
会、时空复杂度等。 ? 附录
2
源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据。提倡用英文描述。 ? 实验报告要求：
在程序开发过程中，逐步形成各种必要的文档及资料。可以写在实验报告纸上，或以电子文档的形式进行书写。
2． 上机实验
每次实验前有实验的预备知识，请同学认真阅读，如果对预备知识没有掌握必须利用实验前的时间进行自学，必须熟练掌握，为本次实验做好知识的准备。
实验题目配合课程的进度，请同学们自己务必完成。为了锻炼自己的应用各种不同的数据结构的能力，尽可能的多作一些题目是非常必要的。在完成各种不同题目的过程中，对各种算法的时、空复杂性的分析，将帮助您在更高的角度解决各种应用问题。
有一定能力的同学可以选作每个实验中的思考内容，提高自己的能力和知识结构。
数据结构课程小组：程红林、鞠训光、戴磊、丁宾
2012年2月
3
实验一 熟悉编程环境
实验预备知识：
1．熟悉本课程的语言编译环境（TC或VC），能够用C语言编写完整的程序，并能够发现和改正错误。
2．能够灵活的编写C程序，并能够熟练输入C程序。
一、实验目的
1．熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。 2．能够熟练的将C程序存储到指定位置。
二、实验环境
⒈ 硬件：每个学生需配备计算机一台。 ⒉ 软件：Windows操作系统+Turbo C；
三、实验要求
1．将实验中每个功能用一个函数实现。
2．每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280和100的和是：380。）。
3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。
四、实验内容
1．在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。
2．编写一个输入某个学生10门课程成绩的函数（10门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。
3．编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有多个最高成绩，则每个最高成绩均输出。
4．编写一个求10门成绩平均成绩的函数。
5．编写函数求出比平均成绩高的所有课程及成绩。
五、思考题
1．如何实现求某个班中30名同学，某门课程的平均成绩？
2．如果这个同学的成绩来源于一个文件，如何从文件中读取其成绩，并将平均成绩也写入到本文件中。
六、报告要求
1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。
2．报告中应书写主要源程序，且源程序中要有注释。
3．报告中应包含运行结果及结果分析。如调试通过，请注明‘通过’并写出输入的数据及运行结果；如未调试通过或结果不正确，试分析原因。
4．报告最后包含实验总结和体会。
4