云南大学软件学院数据结构实验6.docVIP

实验难度： A □ B □ C □ 序号 学号 姓名 成绩 指导教师 （签名） 学　　期：　　2017秋季学期 任课教师: 　　 　　 实验题目: 组员及组长: 　 　　 承担工作：　 　　 联系电话: 　 　　　　　 电子邮件: 　 完成提交时间： 年 月 日 　 一、【实验构思（Conceive）】(10%) （本部分）.基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息，将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离；根据用户的输入信息用迪杰斯特拉算法计算出任意两个地点之间的最短路径，并用二维数组来存储相关的信息，输出给用户；同时用数组存储各个地点的相关信息，当用户输入要了解的地点名称是，调用相关函数输出该地点的相关信息给用户。 2、在程序中运用到了图的相关知识以及迪杰斯特拉算法和哈密尔顿图的遍历等，无向图的相关知识和相关操作，还有图的存储及相关的数据结构。 二、【实验设计(Design)】(20%) （本部分） int main() { int v0, v1; int i, num; char flag; Create(NUM, 11); do { flag = Menu(); switch (flag) { case1: system(cls);//清空屏幕的当前内容 List();//输出景点列表 printf(\n请选择起点景点（0~26）：); scanf(%d, v0); printf(\n请选择终点景点（0~26）：); scanf(%d, v1); ShortPath(v0);//求出最短路径 Output(v0, v1);//输出结果 printf(\n请按任意键继续...\n); getchar();//利用getchar()函数让程序运行到上一行时，等待下下一个按键时才返回 getchar(); break; case2: system(cls); List(); printf(\n请输入您要查找的景点编号： ); scanf(%d, num); for (i = 0; iNUM; i++) { if (num == g.vex[i].number) { printf(\n你要查找的景点信息如下：); printf(\n%s:, g.vex[i].sight); printf(%s\n\n, g.vex[i].description); printf(\n按任意键返回...); getchar(); getchar(); break; } } if (i == NUM) { printf(\n没有找到！); printf(\n按任意键返回...); getchar(); getchar(); } break; casee: exit(0); } } while (flag != 0); return 0; } 流程图： 子程序模块包括：地点列表函数、输出函数、哈密尔顿图的遍历函数、迪杰斯特拉算法判断最短路径函数、创建图的函数。 各模块之间的调用关系：在主函数中调用列表函数，输出个地点，同时调用最短路径判断函数，计算出两地点之间的最短路径；调用输出函数来输出相关的信息给用户，调用图的创建函数来创建校园个地点所表示的无向图。在哈密尔顿图的遍历函数中递归调用该函数本身来实现校园内所有地点的遍历。 核心关键算法： 迪杰斯特拉算法： void ShortPath(int num)//迪杰斯特拉算法最短路径函数，num为入口点的编号 { int v, w, i, t;//v, w, i为计数变量 int final[NUM]; int min; for (v = 0; vNUM; v++) { final[v] = 0;//假设从顶点num到顶点v没有最