实验08 最小生成树、拓扑排序和最短路径
实验学时：2学时 实验类型：上机
背景知识：图的存储、遍历及其应用。 目的要求：
掌握图的常见应用算法的思想及其程序实现。
实验内容：
（1）键盘输入数据，分别建立一个有向图的邻接表和一个无向图的邻接矩阵。 （2）输出该邻接表和邻接矩阵。
（3）以有向图的邻接表为基础输出它的拓扑排序序列。 （4）以无向图的邻接矩阵为基础实现最小生成树的PRIM算法。
（5）以有向图的邻接矩阵为基础实现Dijkstra算法输出单源点到其它顶点的最短路径。 （6）在主函数中设计一个简单的菜单，分别调试上述算法。 （7）*综合训练：校园导航 1）问题描述：
在给出校园各主要建筑的名称信息及有路线连通的建筑之间的距离（或行进时间）的基础上，利用校园导航系统计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线。
2）设计要求：文件读入或键盘方式读入校园主要建筑信息及建筑间的距离（或行进时间）信息。创建完地图后，以文件形式保存，以免重复创建。计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线，并输出该路线（包括经过哪些建筑）及其总距离（或总行进时间）。 实验说明： 1．类型定义
邻接表存储见实验07 邻接矩阵存储示例
#define MAX_VERTEX_NUM 20 //顶点最大个数 typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef struct ArcCell{
VRType adj;
int weight; //边的权值
}ArcCell; AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]; typedef struct{
31
VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs;
int vexnum, arcnum; //顶点的实际数，边的实际数 GraphKind kind; }MGraph;
注意问题：
注意理解各算法实现时所采用的存储结构。
32
实验09 二叉排序树的基本操作
实验学时：2学时
实验类型：上机
背景知识：树表查找。 目的要求：
掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。 实验内容：
（1） 随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指
定关键字元素。
（2） * 建立AVL树并实现删除某一指定关键字元素。 （3） *综合训练： 树种统计
随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。首先输入正整数N（≤105），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（不区分大小写）。按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，每种树的信息占一行。 实验说明： 1．存储定义
参见实验05二叉链表的存储。
2．各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。 注意问题：
1．注意建立二叉排序树时相同元素的处理。
2．注意理解动态查找概念。
33
实验10 哈希表的生成
实验学时：2学时
实验类型：上机
背景知识：哈希查找。 目的要求：
掌握哈希存储结构的思想，能选择合适的哈希函数，实现不同冲突处理方法的哈希表的查找、建立。 实验内容：
（1）设计哈希函数及处理冲突的方法；
（2）键盘输入数据，利用设计的哈希函数及线性探测法生成哈希表； （3）用同样的输入数据和哈希函数，用链地址法处理冲突生成哈希表； （4）在主函数中设计一个简单的菜单，分别调试上述算法； （5）分析两种方法的平均查找长度。 （6）*综合训练：QQ帐户的申请与登陆
首先输入一个正整数N（≤105），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。
针对每条指令，给出相应的信息：
1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”； 3）若老帐户登陆成功，则输出“Login: OK”；
4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”； 5）若老帐户密码错误，则输出“ERROR: Wrong PW”。 实验说明：
各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。 注意问题：
1．注意建立哈希表时相同元素的处理。
2．注意理解哈希查找思想。
34
实验11 常用的内部排序算法
实验学时：2学时 实验类型：上机 背景知识：各种排序方法 目的要求：
1．掌握常见的内部排序算法的思想及其适用条件。 2．掌握常见的内部排序算法的程序实现。
实验内容：
输入一组关键字序列分别实现下列排序：
（1） 实现简单选择排序、直接插入排序和冒泡排序。 （2） 实现希尔排序算法。 （3） 实现快速排序算法。 （4） 实现堆排序算法。 （5） * 快速排序的非递归算法。 （6） * 实现折半插入排序。
（7） 在主函数中设计一个简单的菜单，分别测试上述算法。
（8） * 综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。
实验说明：
1．类型定义
#define MAXSIZE 100 /*参加排序元素的最大个数*/ typedef int KeyType; typedef struct { KeyType key;
InfoType otherinfo; // 其他字段 }RedType; typedef struct {
RedType r[MAXSIZE+1];
int length; /*参加排序元素的实际个数*/ }SqList;
2．算法5可以借助栈实现。
注意问题：
35