2）实验要求：在程序中定义下述函数，并实现要求的函数功能：
CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图 3）实验提示:
? 图的存储可采用邻接表或邻接矩阵； ? 图存储数据类型定义 （邻接表存储）
# define MAX_VERTEX_NUM 8 //顶点最大个数 typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; int weight; //边的权
}ArcNode; //表结点
# define VertexType int //顶点元素类型 typedef struct VNode
{int degree,indegree;//顶点的度，入度 VertexType data; ArcNode *firstarc;
}Vnode /*头结点*/,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;//顶点的实际数，边的实际数 }ALGraph;
4）注意问题:
? 注意理解各算法实现时所采用的存储结构。 ? 注意区别正、逆邻接。
2． 利用最小生成树算法解决通信网的总造价最低问题（实验类型：综合型）
19
1）问题描述：若在n个城市之间建通信网络，秩序架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。
2）实验要求：利用克鲁斯卡尔算法求网的最小生成树 3) 实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点数不超过10个，网中边的权值设置成小于100。 3． 教学计划编制问题（实验类型：综合型）
1）问题描述：软件专业的学生要学习一系列课程，其中有些课程必须在其先修课完成后才能学习。
2）实验要求：假设每门课程的学习时间为一个学期，试为该专业的学生设计教学计划，使他们能在最短时间内修完专业要求的全部课程。
3) 实现提示：
? 以顶点代表课程，弧代表课程的先后修关系，按课程先后关系建立有向无环图。 ? 利用拓扑排序实现。
4． 给定实际背景，解决最短路径问题（实验类型：综合型） 1）问题描述：假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
2）实验要求：利用Dijkstra算法或Floyd算法求最低的票价或最少的时间
3) 实现提示：
20
? 该问题可以归结为一个求带权有向图中顶点间最短路径的问题。
? 分别建立以票价（或搭乘所需时间）为权的有向图，再利用Dijkstra算法或Floyd算法求最短路径及其路径长度。
实验五 查找算法应用
一、实验目的
1、实验设置基本要求：理解二叉排序树、AVL树的查找、
插入、删除、建立算法的思想及程序实现；掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。运用折半查找、分块查找、二叉排序树、散列表等查找算法解决实际问题。 2、实验设置较高要求：利用B+树设计大数据集索引结构。 二. 实验学时：
课内实验学时：4学时 课外实验学时：8学时 三、备选实验题目
1. 哈希表查找（实验类型：综合型）
1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。
2）实验要求：要求表的平均查找长度不超过R，完成相应的建表和查表程序。
21
3) 实现提示：假设人名为汉语拼音形式。代填入哈希表人名共30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用再散列法处理冲突。
2. 构造二叉排序树，并进行中序遍历（实验类型：综合型） 1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序述进行中序遍历，得到有序序列。
2）实验要求：该二叉排序树以二叉链表存储
3）实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。
3. 折半查找算法（实验类型：验证型）
1）问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键字。如果有，输出它在整数串中的位置；如果没有，输出-1
2）实验要求：
? 利用折半查找算法查找
? 用递归和非递归两种方式实现折半查找算法 3) 实现提示：
? 递归实现参考书上折半查找算法的实现 ? 非递归算法利用栈实现
4. 借助B树实现图书索引管理（实验类型：综合型） 1）问题描述：图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等。设计一个图书管理系统，将上述业务活动借助计算机系统完成。
2）实验要求：作为演示系统，不必使用文件，全部数据可以在内存中存放。
22
3) 实现提示：建立B树结构，利用B树插入、删除算法做入库、出库操作。
23