数据结构实验报告

实验一 抽象数据类型的表示与实现

（ 验证性实验 2 学时）

1.目的要求：

1) 熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现；

2) 理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）。

3) 认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，

并结合程序进行分析。

1. 实验内容：

1） 编写一个C程序，利用参数实现一组数据的最大值、最小值、平均值等的求解。

2） 编程实现抽象数据类型三元组的定义、存储、基本操作，并设计一个主菜单完成各

个功能的调用。

3.主要仪器设备及药品

1） PC机

2） Turbo C 2.0 或Visual C++

实验二 线性表实验

（ 验证性实验 2 学时）

1.目的要求：

4) 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；

5) 以线性表的各种操作（建立、插入、删除等）的实现为重点；

6) 通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、

链表的使用）。

7) 认真阅读和掌握本实验的参考程序，上机运行本程序， 保存和打印出程序的运行

结果，并结合程序进行分析。按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。

2. 实验内容：

1） 编程实现线性表两种存储结构中的基本操作的实现（线性表的创建、插入、删除和

查找等）

2） 设计一个菜单调用线性表的基本操作。

3.主要仪器设备及药品

1） PC机

2） Turbo C 2.0 或Visual C++

实验三 栈、队列以及递归算法的设计实验

（ 验证性、综合性、设计性实验 2 学时）

1.目的要求：

1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运

用它们。

2） 本实验训练的要点是“栈”的观点及其典型用法；

3） 掌握问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法。

2.实验内容：

1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；

2） 应用栈的基本操作，实现数制转换（任意进制）；

3） 利用栈，实现任一个表达式中的语法检查（如括号的匹配）。（选）

4） 设计一个迷宫，模拟迷宫求解的方法和路线，建议以图形方式进行演示。（选）

5） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、

出队列等）；

3.主要仪器设备及药品

1) PC机

2) Turbo C 2.0 或Visual C++

实验四 字符串、稀疏矩阵实验

（ 验证性、综合性实验 2 学时）

1.目的要求：

1) 熟悉字符串类型的实现方法和文本模式，掌握串的模式匹配算法（BF）,熟悉一般

文字处理软件的设计方法，较为复杂问题的分解求精方法。

2) 掌握特殊矩阵的压缩存储表示，了解稀疏矩阵的三元表顺序表示及基本操作的实

现。

2.实验内容：

1) 实现串的一种存储表示及有关操作。；

2) 设计一个文本编辑器，完成文本的插入、删除、查找、替换，要求有友好的操作界

面。（选）

3) 稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转置等）。

3.主要仪器设备及药品

1) PC机

2) Turbo C 2.0 或Visual C++

实验五 树及二叉树实验

（ 验证性、综合性实验 2 学时）

1.目的要求：

1) 树是一种重要的非线性数据结构，要求掌握二叉树的两种基本的存储结构，及各种

操作的算法实现（建立、遍历、线索化、最优二叉树），并能运用树结构分析解决一些实际问题。

2) 本实验训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其

编译码技术；完整的应用系统的用户界面设计和操作定义方法；路径遍历（树、图的遍历）技术。

2.实验内容：

1) 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，然

后按先序、中序、后序顺序分别遍历这棵二叉树。

2) 编写一个递归算法建立一棵二叉排序树，掌握二叉树的递归特性。

3) 利用二叉树来设计一个火车到站系统，模拟火车的入站和出站序列。（选）

4) 设计一个完整的编码系统：针对一篇文档，统计各个字符的出现次数（频度），并为

其设计Huffman编码，然后进行译码。

3.主要仪器设备及药品

1) PC机

2) Turbo C 2.0 或Visual C++

实验六 图及其应用实验

（ 验证性、综合性实验 2 学时）

1.目的要求：

1) 图是一种重要的非线性数据结构，要求掌握图的两种基本的存储结构（邻接矩阵、

邻接表），以及图的基本算法实现（建立、深度优先遍历、广度优先遍历），并能运用图结构分析解决一些实际问题。

2) 本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、遍

历、图的典型应用）

2.实验内容：

1) 建立无向图和有向图的邻接矩阵存储，计算顶点的度，并按要求输出图的基本信息。

2) 建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后按照要求

输出图的基本信息。

3) 编写完整的程序实现AOV网的拓扑排序。

4) 编程求AOE网的关键路径（选）。

5) 编程实现单源点最短路径算法的Dijkstr算法。

6) 根据一个社区的地理环境，选择合适的存储结构，并设计一个算法为一个服务点（如

学校、医院等）选择最佳位置。（选）

3.主要仪器设备及药品

1) PC机

2) Turbo C 2.0 或Visual C++

实验七 查找与排序实验

（ 验证性、综合性实验 4 学时）

1.目的要求：

1) 学生在实习中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。

2) 掌握运用查找和排序解决一些实际应用问题。

2.实验内容：

1) 实现各种查找算法（顺序查找、二分查找、二叉排序树的查找、哈希查找等），并计

算相应的ASL。

2) 实现各种内部排序算法（插入排序、选择排序等）。

3) 编写一个管理查询系统（如学籍信息、工资信息、等），要求： 程序采用交互工作方

式,完成如下功能：

a) 建立数据文件

b) 数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、快速等任选

一种)

c) 查询菜单: (用二分查找实现以下操作)

按姓名查询

按学号查询

按房号查询

打印任一查询结果（可以连续操作）

3.主要仪器设备及药品

1) PC机

2) Turbo C 2.0 或Visual C++