数据结构与算法分析 课程设计报告 设计题目： 校园导航咨询系统 专 业 学 号 姓 名 2013 年 3 月 3 日 一、问题描述 设计你的学校的平面图，至少包括 10 个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）（参考课本 P186-P192）。 二、需求分析 本程序分为五个模块，分别是显示校园全景、查询景点信息、问路查询系统、查看游览路线和退出系统。 （1 ） 显示校园全景 展示校园概貌图和各景点编号、名称。 （2 ） 查询景点信息 输入要查询的景点编号，显示景点的编号、名称和景点的简单介绍。 （3 ） 问路查询系统 输入要参观的两个景点的编号（按从大到小输入），显示两个景点间的最短路径游览方式和最短路径长。 （4 ） 查看游览路线 查询某个景点到其他景点的所有路径，并显示其长度。 （5 ） 退出系统 查询完毕关闭窗口，显示退出系统的界面 三、概要设计 1、主要函数： void main() 主函数，程序入口 csinfo() 初始化景点信息 csroad() 初始化道路信息 showpath() 显示校园全景 search() 查询景点信息 floyd() 弗洛伊德函数，查询两个景点之间的最短路径所要经过的中间节点 print(int i,int j) 打印两个景点的路径及最短距离 shortpath() 问路查询，求最短路径 ShortestPath_DIJ(Maph * M) 利用Dijkstra 算法来计算出起点到各个顶点之间的最短路径,以v0 为起点 menu() 显示菜单选项 2、主要变量： ps[MaxPointNum] 定义主要景点信息，存放景点的编号、名称、简要介绍等信息 char name[20] 景点名称 char number[15] 景点编号 char info[100] 景点简介信息 MaxPointNum 最大景点个数 INFINITY 近似无穷大，表示两景点不可达 Maph M 全局变量,定义 M 为Maph 类型 int shortest[MaxPointNum][MaxPointNum] 定义全局变量存贮最短路径 int path[MaxPointNum][MaxPointNum] 定义存贮路径 3、存储结构： 3.1 图的类型定义 typedef struct { char name[20]; //景点名称 char number[15]; //景点代号 char info[100]; //景点信息 }Elemtype; //景点类型 3.2 定义景点 typedef struct { int num; //顶点编号 Elemtype data; //顶点信息 }Point; //定义顶点 3.3 定义全局变量 typedef struct { Point ps[MaxPointNum]; //存放顶点的一维数组 ...
