《数据结构实验指导书》
潘向辉/吴学毅编写
印包学院数字媒体技术专业
2011年3月
实验说明
【实验环境】
操作系统：Microsoft Windows XP/2000。

编程语言：C语言
【实验要求】
1.实验前，了解实验目的、实验内容及相关的基本理论知识，并按照实
验内容要求设计程序流程，书写预习报告；
2.本课程实验均为单人单组，独立完成；
3.实验所用计算机固定，以便实现实验之间的延续性；
4.按要求完成实验内容，在实验结束后按照格式和规范撰写实验报告。

【实验项目及学时分配】
【实验报告及考核】
1．实验报告撰写符合格式及规范要求，详见实验报告撰写格式及规范；2．本课程实验占课程总成绩的15%。

实验（一）线性表
一、实验项目
名称：线性表课时：4学时
二、实验要求
1、掌握顺序表的定义与实现，包括查找、插入、删除算法的实现；
2、掌握在各种链表结构中实现线性表操作的基本方法，能在实际应
用中选用适当的链表结构；
三、实验环境
Widows操作系统、C语言
四、实验内容
（1）顺序表
建立一如下表所示的学生信息表
使用结构体，用顺序表完成以下内容：
1.初始化线性表为空；
2.依次输入数据元素；（由键盘输入）
3.完成数据元素的插入、删除操作；
4.取第i个数据元素；
5.依次显示当前线性表中的数据元素。

（2）单链表
建立一个单链表，依次输入数据元素0～9。

使用结构体，用单链表完成以下内容：
1.初始化单链表；
2.在单链表指定位置插入一个数据元素；
3.删除指定位置的一个数据元素；
4.取第i个数据元素；
5.查找数据元素x 是否在单链表中；
6.销毁单链表；
五、思考题：
在什么情况下使用顺序表比链表好？
实验（二）栈和队列
一、实验项目
名称：栈和队列课时：2学时
二、实验要求
1、掌握栈的顺序表示、链表表示以及相应操作的实现。

特别注意栈
空和栈满的条件；
2、掌握队列的顺序表示、链表表示以及相应操作的实现。

特别是循
环队列中队头与队尾指针的变化情况；
三、实验环境
Widows操作系统、VC6.0
四、实验内容
分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：
判断一个字符序列是否是回文。

回文是指一个字符序列以中间字符为基准，两边字符完全相同。

如：“ABCDEDCBA”。

字符串长度小于等于80，用于判断回文的字符串不包括字符串的结束标记符。

基本要求：
（1）字符序列可由用户从键盘随意输入；
（2）可以连续测试多个字符序列，由用户决定退出测试程序；
算法思想：
判断回文的算法思想是：把字符串中的字符逐个分别存入队列和堆栈中，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文。

基本操作：
回文判断操作主要包括入栈和入队列、退栈和出队列操作。

在对堆栈以及队列进行操作之前，必须对队列以及堆栈进行初始化。

若使用链式堆栈和链式队列，操作结束后必须销毁链表。

五、思考题：
1、栈有哪些特点及与一般线性表有哪些区别？
2、队列有哪些特点及于一般线性表有哪些区别？
实验（三）二叉树的构建、基本操作和遍历
一、实验项目
名称：二叉树的构建、基本操作和遍历 课时：4学时
二、实验要求
1、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；
2、熟练掌握二叉树的遍历方法及遍历算法；
3、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。

三、实验环境
Widows 操作系统、VC6.0
四、实验内容
（1）二叉树
建立如下图所示的二叉树：
要求：1、建立带头结点的二叉树，将二叉树初始化为空； 2、依次将二叉树的所有结点插入，建立上图所示的二叉树； 3、用户可由键盘输入数据实现对二叉树各结点的插入、删除等操作； 4、打印二叉树；
5、对二叉树实现前序、中序、后序遍历； 算法思想：
建立一棵只有头结点的二叉树，并通过调用插入左子树和插入右子树操作，依次将上图中的结点插入二叉树中，利用二叉树的特殊中序遍历方法将该树以凹入表示法打印显示。

最后，调用二叉树的前序、中序、后序遍历函数对二叉树进
A
B
C D
E
F
G
行遍历，并显示遍历结果。

(2)、哈夫曼树
设有字符集{A、B、C、D}，各字符在电文中出现的次数集为{1，3，5，7}，设计各字符的哈夫曼编码。

要求：
1、构造字符集的哈夫曼树，其结点数据结构如下：
2、由哈夫曼树构造哈夫曼编码，输出权值及其对应的编码。

算法思想：
首先，由给定的n个权值构造有2n-1个结点的哈夫曼树。

在哈夫曼树中，其叶结点的权值为相应的给定权值，非叶结点的权值为其孩子结点的权值之和。

哈夫曼树构造过程如下：
1. 根据给定的 n 个权值 {w1，w2，…，w n}，构成的 n 棵二叉树的森林 F
= {T1，T2，…，T n}，其中每棵二叉树 T i 中只有一个权值为 w i 的结点，
其左、右子树均为空；
2. 在 F 中选取根结点的权值最小和次小的两棵树作为左、右子树构造一棵
新的二叉树，且置新二叉树的根结点的权值为其左、右子树上根结点的权值
之和；
3. 在 F 中删除这两棵二叉树，并将新二叉树加入到 F 中；
4. 重复 2 和 3，直到 F 中只含一棵树为止。

这棵树就是哈夫曼树。

其次，对n个结点的哈夫曼树进行不等长编码。

保证任何一个字符的哈夫曼编码不为另一字符的哈夫曼编码的前缀。

五、思考题：
已知一棵二叉树的层序序列是ABCDEFGHIJ,中序序列是DBGEHJACIF,试画出此二叉树。

实验（四）图的建立、基本操作以及遍历
一、实验项目
名称：图的建立、基本操作以及遍历课时：4学时
二、实验要求
1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围；
2、熟练掌握几种常见图的遍历方法及遍历算法；
三、实验环境
Widows操作系统、VC6.0
四、实验内容
选用任一种图的存储结构，建立如下图所示的带权有向图：
要求：1、建立边的条数为零的图；
2、依次将图的边以及相应的权值插入，建立如上图所示的图，并将结点
集合和权值集合输出；
3、对所建立的图进行深度优先搜索或广度优先搜索，输出图的遍历序列；算法思想：
首先，选定所使用的图的存储结构（邻接矩阵存储或邻接表存储），建立图的结构体定义。

根据所选用的结构建立边条数为零的图，依次插入图的结点和图的各有向边以及权值wei ght；再次，将图的结点集合以及权值集合输出，以验证所建立图的正确性；最后，调用图的遍历函数，实现图的深度优先遍历或广度优先遍历，并输出遍历序列。

五、思考题：
1、采用邻接表存储的图的深度优先遍历算法类似于二叉树的哪种遍历？
2、采用邻接表存储的图的广度优先遍历算法类似于二叉树的哪种遍历？
实验（五）排序与查找算法实现
一、实验项目
名称：排序与查找算法实现课时：2学时
二、实验要求
1、熟练掌握几种常见的排序方法及优缺点；
2、熟练掌握几种常见的查找方法及其性能的评价；
3、上机完成常见排序与查找功能的程序。

三、实验环境
Widows操作系统、VC6.0
四、实验内容
编写程序实现任一排序和查找功能。

要求：
1、数据元素个数n可由用户随意确定，且有0<n<80；
2、可连续测试多组数据元素；
3、数据元素由键盘输入；
4、将输入的数据元素进行排序后，实现任意查找功能；若查找成功，
则返回数据元素在数组中的下标和数据元素本身，若查找不成功，
则输出查找失败信息；
5、最后，将经过排序的数据元素输出，用以验证。

五、思考题：
在待排序的元素序列基本有序的前提下，哪种排序方法效率最高？
附录A
附录A
西安理工大学实验报告
课程__________实验名称__________第页共页系别________________ 实验日期年月日专业班级________组别_____ 实验报告日期年月日姓名________________学号_____________
实验报告内容
验证性实验
一、预习准备：实验目的
实验环境
实验原理
实验内容和要求
二、实验过程：程序流程图
实验中的关键语句
编写及调试程序中遇到的问题及解决方法
三、实验总结：实验结果及分析
实验总结
思考题
设计性实验：
一、预习准备：实验目的
实验环境
实验内容和实验方案
程序流程图
二、实验过程：实验中的关键语句
编写及调试程序中遇到的问题及解决方法
三、实验总结：实验结果及分析
实验总结
思考题。