《数据结构》实验指导书（24学时）.doc

实验一 线性结构
一、 实验目的：
1．掌握线性表的链式存储结构。
2．熟练地利用链式存储结构实现线性表的基本操作。
3．能熟练地掌握链式存储结构中算法的实现。
二、实验内容：
1．用头插法或尾插法建立带头结点的单链表。
2．实现单链表上的插入、删除、查找、修改、计数、输出等基本操作 。
三、实验要求：
1. 根据实验内容编写程序，上机调试、得出正确的运行程序。
2. 写出实验报告（包括源程序和运行结果）。
四、实验学时：4学时
五、实验步骤：
1．进入编程环境，建立一新文件；
2. 参考以下相关内容，编写程序，观察并分析输出结果。
① 定义单链表的数据类型，然后将头插法和尾插法、插入、删除、查找、修改、计数、输出等基本操作都定义成子函数的形式，最后在主函数中调用它，并将每一种操作前后的结果输出，以查看每一种操作的效果。
② 部分参考程序（略）
六、实践部分
选作实验可以从以下两个实验中任选一个：

1 试设计一元多项式相加（链式存储）的加法运算。
A（X）=7+3X+9X8+5X9
B（X）=8X+22X7-9X8
1．建立一元多项式；
2．输出相应的一元多项式；
3．相加操作的实现。

2 约瑟夫生死环
利用单循环链表存储结构，解决约瑟夫（Josephus）环问题。即：将编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一个正整数密码。开始时任选一个正整数作为报数上限值m,从某个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有的人全部出列为止。令n最大值取30。设计一个程序，求出出列顺序，并输出结果。
实验二 树形结构
一、 实验目的：
1．掌握二叉树的数据类型描述及二叉树的特性。
2．掌握二叉树的链式存储结构(二叉链表)的建立算法。
3．掌握二叉链表上二叉树的基本运算的实现。
二、实验内容：
从1、2中选择一项内容，再从3、4中选择一项内容
1．用递归实现二叉树的先序、中序、后序3种遍历。
2．用非递归实现二叉树的先序、中序、后序3种遍历。
3．计算二叉树的总结点数、叶子结点个数，以及二叉树的深度。
4．实现二叉树的层次遍历。
三、 实验要求：
1．根据实验内容编程，上机调试、得出正确的运行程序。
2．写出实验报告（包括源程序和运行结果）。
四、实验学时：4学时
五、实验步骤：
1．进入编程环境，建立一新文件；
2. 参考以下相关内容，编写程序，观察并分析输出结果。
① 将建立二叉树及先序、中序、后序3种遍历算法都写成子函数，然后分别在主函数中调用它，但在建立二又树中，必须把二叉树看成完全二叉树的形式。若不是完全二叉树，则在输入数据时，用虚结点(不存在)表示(本算法中，用“*”号代替)。
② 用非递归法实现二叉树的遍历
非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈顶指针。
③ 在二叉树遍历的基础上计算总结点数、叶子结点个数，以及二叉树的深度。
④ 实现二叉树的层次遍历
用一个一维数组代替队列，实现二叉树的层次遍历。

六、实践部分
选作实验可以从以下两个实验中任选一个：
1．给定权值5,29,7,8,14,23,3,11，建立哈夫曼树，输出哈夫曼编码。
2．对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。
算法提示：将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数调用它们。
实验三 图形结构
一、 实验目的
1．掌握图的数据类型描述及定义；
2．掌握用邻接矩阵和邻接表的方法描述图的存储结构；
3．理解并掌握深度优先遍历和广度优先遍历的存储结构。
二、实验内容：
从1、2中选择一项内容，再从3、4中选择一项内容
1．建立无向图的邻接矩阵，并实现插入、删除边的功能。
2．建立有向图的邻接表，并实现插入、删除边的功能。
3．建立一个包含6个结点的图，并实现该图的深度优先搜索遍历。
4．建立一个包含6个结点的图，并实现该图的广度优先搜索遍历。
三、实验要求：
1．根据实验内容编程，上机调试、得出正确的运行程序。
2．写出实验报告（包括源程序和运行结果）。
四、实验学时：4学时
五、实验步骤：
1.进入编程环境，建立一新文件；
2. 参考以下相关内容，编写程序，观察并分析输出结果。

① 内容1的知识要点：//邻接矩阵的存储结构
图由一个非空的顶点的集合和一个描述顶点之间关系(边)的集合组成。它可以定义为
G=(V，E)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图是一种复杂的数据结构。对于实际问题，需要根据具体图的结构特点以及所要实施的
操作，选择建立合适的存储结构。图的存储结构包括邻接矩阵和邻接表。
邻接矩阵：用一维数据组存储图中顶点的信息，用矩阵表示图中各顶点之间的相邻关系。
它属于静态存储方法。
邻接表：邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。顺序存储部分
用来保存图中顶点的信息，链式存储部分用来保存图中边的信息。

② 内容2的知识要点：//邻接表的存储结构
构造有向图链接表与无向图链接表的算法区别是：无向图两结点无向对偶，因而邻接表有一定的对偶性；有向图两结点间有向无对偶关系，因而建立邻接表时应根据输入的顶点及边的有向关系建立(当箭头方向离开结点为有关，当箭头方向指向结点为无关)。

③ 内容3的知识要点：//图的深度优先搜索遍历
深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从vo出发，访问vo的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问的顶点w2，然后从w2出发，访问w2的一个未被访问的邻接顶点w3，依此类推，直到一个所有邻接点都被访问过为止。
图采用邻接表作存储结构，图的深度优先遍历次序为
①→②→④→⑤→⑥→③
参考程序运行过程中，深度优先遍历时指针p的移动方向示意如图下所示，图中p1、p2、p3、p4、p5和p6为深度优先遍历图的各结点时，指针p的移动次序。

//图的广度优先搜索遍历
④ 内容4的知识要点：
广度优先遍历图的算法：首先访问指定的起始顶点v0,从v0出发，访问v0的所有未被访问的邻接顶点w1，w2，…，wk，然后再依次从w1，w2，…，wk出发，访问所有未被访问过的邻接顶点，依此类推，直到图中所有未被访问过的邻接顶点都被访问过为止。
根据广度优点遍历的规则，在其算法实现中，借助一个队列g－queue来存放已被访问过的顶点。从指定顶点开始，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依此类推，直至队列为空且图中结点均被访问过为止。
图的广度优先遍历次序为：
① →②→③→④→⑤→⑥
参考程序运行过程中，广度优先搜索时指针p的移动示意如下图所示，图中片p1、p2、p3、p4、p5和p6为广度优先遍历图的各结点指针p的移动次序。

六、实践部分
选作实验可以从以下两个实验中任选一个：
1、设计一个交通导航咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。
2、假设一个城市有n个小区，要实现n个小区之间的电网都能够相互接通，构造这个城市n个小区之间的电网，使总工程造价最低。请设计一个能满足要求的造价方案。可以用带权的无向图（即无向网）表示这n个小区之间的电网连接，其中顶点表示小区，权值表示城市之间电网建设的造价，构造一个无向网的最小生成树即是满足要求的最低电网连接造价方案。
实验四 查找和排序
一、 实验目的
1. 掌握各种查找算法的基本思想、适用条件及算法实现；
2. 熟练掌握二叉排序树的构造和查找方法；
3. 掌握各种排序算法的基本思想、适用条件及算法实现；
4. 掌握各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂性和稳定性的分析方法。
二、实验内容
从1、2中选择一项内容，再从3、4中选择一项内容
1. 建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。（为了简化算法，数据元素只含一个整型量关键字字段，数据元素的其余数据部分忽略不考虑。）
2. 查找表的存储结构为有序表，即表中记录按关键字大小排序存放。输入待查数据元素的关键字进行查找。
3. 随机函数产生10000个随机数，用直接插入、二分插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间。
4. 随机函数产生30000个随机数，用快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。
三、实验要求
1. 根据实验内容编程，上机调试、得出正确的运行程序。
2. 写出实验报告（包括源程序和运行结果）。
四、实验学时
2学时。
五、实验步骤：
1．进入编程环境，建立一新文件；
2. 参考以下相关内容，编写程序，观察并分析输出结果。

① 顺序查找的基本思想及程序实现
对于给定的关键字k，从表的一端开始，逐个进行数据元素的关键字和给定值的比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于k的节点，则查找失败。
建立一个顺序表，数据元素从下标为1的单元开始放入，下标为0的单元起监视哨作用，将待查的关键字存入下标为0的单元，顺序表从后向前查找，若直到下标为0时才找到关键字则说明查找失败；若不到下标为0时就找到关键字，则查找成功。

② 折半查找的基本思想及程序实现：
设查找表中的元素存放在数组r中，数据元素的下标范围为[low,high]，要查找的关键字值为key，中间元素的下标为mid=(low+high)／2 (向下取整)，令key与r[mid]的关键字比较：
l 若key=r[mid].key，查找成功，下标为m的记录即为所求，返回mid。
l 若key<r[mid].key，所要找的记录只能在左半部分记录中，再对左半部分使用折半查找法继续进行查找，搜索区间缩小了一半。
l 若key>r[mid].key，所要找的记录只能在右半部分记录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小了一半。
重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key说明查找成功；或者出现low的值大于high的情况，说明查找不成功。
建立一个有序表，数据元素从下标为1的单元开始放入。实现查找算法时，首先将low赋值为l，high等于最后一个数据元素的下标，然后将给定的关键字的值与查找区间[low，high]中间的数据元素的关键字比较， 实现查找过程。

③ 排序算法提示
为了产生随机数，必须用到头文件stdlib．h中的两个函数srand()和rand()来设置随机种子以及产生随机数。为了能够计时，必须用到头文件time．h中的time()和difftime()两个函数，time()用于截取计算机内的时钟，difftime()用于得到两次时钟间隔的时间(秒)。每一种排序方法都单独写成子函数形式，然后用主函数调用它。为了能查看排序前后的效果，可以单独写一个子函数输出数组结果，在排序前后分别调用它，可以看到排序前后的结果。

六、实践部分
选作实验可以从以下两个实验中任选一个：
1、编程实现一个开放式的高校本科招生最低录取分数线的查询系统，供师生和家长查询。高校自愿放入该校的信息，可能随时有高校加入。要求实现的查询功能有：①查询等于用户给定分数的高校；②查询大于(或小于)用户给定分数的高校；③查询最低录取分数线在用户给定的分数段中的高校。
提示：该实验主要的功能是查找，查找表为高校最低录取分数信息的集合。根据题意可知，该查找表中的元素个数可能随时增减，所以它是一个动态查找表，可采用树状结构保存。为了提高查询速度，可建立二叉排序树并在二叉排序树中实现查找。
第一个要求可以直接利用一般的二叉排序树的查找算法实现。
第二个要求可以利用比较二叉排序树根结点的关键字值和给定的分数实现，若前者大于或等于后者，根结点及其右子树中的结点全部满足要求，再在根结点的左子树中查找；否则只在根结点的右子树中查找即可。
第三个要求可以利用比较二叉排序树根结点的关键字值和给定的分数段实现，若前者在给定的分数段中，根结点就满足要求，则在根结点的左、右子树中继续查找即可：若前者
给定的分数段的左侧，只在根结点的右子树中查找即可；若前者在给定的分数段的右侧，只根节点的左子树中查找即可。

2、设计一个算法，指出一个无序序列中的任意一个元素是第几大元素（从小到大数），要求比较的次数最少。
实验五 综合实验
一、 实验目的
1. 熟练掌握各种数据结构的逻辑结构和存储结构；
2. 提高综合运用各种数据结构及其算法解决应用问题的能力；
3. 扩大编程量，完成模块化程序设计的全过程。
二、实验内容
模拟一个航班订票系统，要求能够录入、修改、删除和查询航班信息，并为顾客提供订票和退票服务。
三、实验要求
航班信息包括航班号（具有惟一性）、起降时间、起飞城市、抵达城市、航班票价、票价折扣、总座位数和出票数。航班信息管理和客户服务要求完成以下功能：
1. 录入航班信息：可成批录入（存于一个数据文件中），也可单个录入。
2. 修改航班信息：根据航班号修改航班信息。
3. 删除航班信息：根据航班号删除航班信息。
4. 查询航班信息：可以查询航线的情况。如：输入航班号，可查起降时间、起降城市、票价、票价折扣及航班是否满仓。或：输入起飞城市，查询航班的情况。
5. 订票：输入航班号和订票数量进行订票。如果机票不足，可以提供相关可选航班或无票信息。
6. 退票：输入航班号和退票数量，可进行退票，并修改相关的文件。
四、实验学时
6学时。
五、实验步骤
1. 根据实验内容编程，上机调试、得出正确的运行程序。
2. 写出实验报告（包括源程序和运行结果）。
六、实践部分
可以选作哈夫曼编码的实验：
对一份长短不定的由ASCII字符构成的报文按照以下步骤进行编码和译码：
编码：
(1) 扫描报文文件，完成ASCII字符频度的统计；
(2) 依据ASCII字符出现的频度建立哈夫曼树；
(3) 根据哈夫曼树的信息对报文文件进行编码并写入输出文件。
译码：
(4) 扫描由二进制符号构成的文件，根据哈夫曼树对其进行译码，并把译码后的信息写入另一输出文件。