发布时间 : 星期三 文章数据结构实验指导书(1)更新完毕开始阅读
数据结构试验指导书
由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。 输入样例：
6 8 1 1 2 2 3 3 4 4 5 5 6 6 4 3 6 1 5 输出样例：
1 2 3 4 5 6 5 4 3 2 1 实验说明：
1．类型定义（邻接表存储）
#define MAX_VERTEX_NUM 20 //顶点最大个数 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc;
int weight; //边的权值 }ArcNode; //表结点
#define VertexType int //顶点元素类型 typedef struct VNode{ VertexType data; ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM]; // typedef struct{
AdjList vertices;
int vexnum, arcnum; //顶点的实际数，边的实际数 int kind; }ALGraph;
2．上述类型定义可以根据实际情况适当调整。 3．算法4、5分别利用栈、队列实现非递归算法。
注意问题：
1．注意理解各算法实现时所采用的存储结构。
27
数据结构试验指导书
2．注意区别正、逆邻接。
28
数据结构试验指导书
实验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];
29
数据结构试验指导书
typedef struct{
VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs;
int vexnum, arcnum; //顶点的实际数，边的实际数 GraphKind kind; }MGraph;
注意问题：
注意理解各算法实现时所采用的存储结构。30