数据结构实验指导

（第一版）

计算机科学与技术系。

数据结构》课程组。

目录。1 概述 1

1.1《数据结构》课程实验的地位与作用 1

1.2 实验的目的和要求 1

1.3 本书安排 1

2 实验环境选择 3

3 实验类型 5

4 实验步骤 6

4.1验证型实验的一般步骤 6

4.2设计型实验和综合型实验的一般步骤 6

5 实验报告规范 9

6 实验内容 10

6.1 实验一线性表 10

题目1：顺序表的基本操作 10

题目2：链表的基本操作 11

题目3：双向链表的基本操作 11

题目4：一元稀疏多项式的表示及基本操作 12

题目5：约瑟夫环 12

题目6：记事本 13

6.2 实验二栈、队列与递归算法设计 13

题目1：数制转换问题 14

题目2：回文判断 14

题目3：括号匹配的检验 15

题目4：商品货架管理 15

题目5：四则运算实现 16

题目6：停车场管理 17

6.3 实验三树及其应用 18

题目1：二叉树的建立与遍历 18

题目2：二叉树的层序遍历 19

题目3：二叉排序树 19

题目4：哈夫曼编码设计 20

6.4 实验四图及其应用 20

题目1：图的邻接矩阵存储和广度优先遍历 20

题目2：图的邻接表存储和深度遍历 21

题目3：最小生成树问题 21

题目4：排课序列 22

6.5 实验五：排序与查找的综合应用 22

题目1：查找和排序的基本算法 22

题目2：快速排序 23

题目3：二叉排序树 23

题目4：堆排序算法 24

题目5：统计成绩 24

附录a 实验报告封面 25

附录b 实验报告示例 26

附录c 实验工具使用 30

数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

由于以下原因，使得掌握这门课程具有较大难度：

内容多，时间短，给学习带来困难；

贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；

隐含在各部分的技术和方法丰富，也是学习的重点和难点；

先修课程中所介绍的专业性知识不多，加大了学习难度。

由于数据结构课程的技术性与实践性，其实践环节十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。

在掌握基本算法的基础上，掌握分析、解决实际问题的能力。通过实验实践内容的训练，突出构造性思维训练的特征，提高学生组织数据及编写大型程序的能力。

上机实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。较大的实验题比平时的习题要复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力。

实验还能使书上的知识变“活”，达到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：

机器是比任何教师都严格的检查者。

为了达到上述目的，本书安排了5个实验单元，各单元的训练重点在于基本的数据结构和经典算法。各单元与教科书的各章只具有粗略的对应关系，某些实验题可能涉及多个部分的教学内容。在每个单元中安排有难度不等的4~6个实验题目，每人可以从中选做一个实验题。

建议选做难度略高于自己所做过的最难题目的难度，切忌过分追求难题。较大的综合型题目适合于多人合作。

每个实验题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等5个部分组成。

问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；

基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；

测试数据部分旨在为检查学生上机作业提供方便，在完成实验题时应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；

实现提示对实现中的难点及其解法思路等问题作了简要提示；

选做内容向那些尚有余力的实验者提出了更严峻的挑战，同时也能开拓其他读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。

书中题目设计得比较详细，给出了问题说明和问题分解求精的范例，使读者在无形中学会模仿，它起到把读者的思路引上正轨的作用，避免不良结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查。题目设计策略是：一方面使其难度和工作量都较大，另—方面给读者提供的辅助和可以模仿的部分也较多。

当然还应指出的是，提示的实现方法未必是最好的，读者不应拘泥于此，而应争取找出更好的方法和结构。

在实现的时候应注意，要尽量减少依赖于具体机器计算环境的用法，若使用，也应在注释中指出。这样得出的程序易于在不同机器上运行，有好的可移植性。c语言是结构化程序设计语言，具有递归能力，可移植性也较好，是特别推荐的实现语言。

本书的另一个特点是为实验制定了严格的规范。一种普遍存在的错误观念是，调试程序全凭运气。学生花2个小时的机上时间只找出一个错误，甚至一无所获的情况是常见的。

其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实验步骤规范进行实验，不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。

在附录c中提供了一个完整的实验报告示例，在起到实验报告规格范例作用的同时，还隐含地提供了很多有益的东西，比如基于数据类型的系统划分方法以及所提倡的程序设计风格等等。计算机学科在不断发展，可以使用的语言工具越来越丰富，在本书中的实验示例是应用面向过程的语言进行设计和编程，同样的实验题，也可以用面向对象的语言来实现。

数据结构的抽象数据类型（adt）特点决定了可以采用多种工具来描述，每种描述工具都有不同的实验环境。本课程采用类c语言作为描述语言，可采用turbo c或者 visual c++ 6.0集成开发环境。

另外，在实验中，实验者通常对dos程序、console程序、windows程序区分不清，归纳如下：

dos程序。

过去在dos环境下开发的程序，称为dos程序，该类程序以main为程序进入点，可以调用c runtime函数，但不能调用win32 api函数。dos程序仍然可以在windows的dos box中运行。

windows程序。

dos 编程方式属过程驱动。windows 编程方式属消息驱动，程序的工作是产生消息，传递消息和处理消息。windows系统有一个存放消息的队列，每个应用程序也有一个消息队列。

windows系统先将收到的消息存放在系统队列中；然后再分发到相应的应用程序队列中。应用程序则从自身的队列中获取消息并进行处理。基本流程见图2.1。

数据结构实验指导

数据结构实验指导

数据结构实验指导

数据结构实验指导

其他用户还读了