2022年数据结构地图导游系统含源码整理

《2022年数据结构地图导游系统含源码整理》由会员分享，可在线阅读，更多相关《2022年数据结构地图导游系统含源码整理（29页珍藏版）》请在金锄头文库上搜索。

1、数据结构地图课程设计含源码数据结构课程设计报告题目：XXXX大学校园导游系统院系名称：计算机学院专业名称：软件工程班级：2012级 01 班学生姓名：XX 学号（ 8 位） ：XX 指导教师：XX 设计起止时间：2013 年 12 月 16 日2013 年 12 月 27 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - 一.设计目的进一步的了解图的遍历的问题， 图的 DFS,BFS 的递归和非递归算法的实现，实现图的遍历，用

2、邻接矩阵和邻接表的存储方式存储图。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。提高综合运用所学的理论知识和方法独立分析和解决问题的能力。二. 设计内容1、设计并显示学校的校园平面图，地点（地点名称、地点介绍） ，路线（公里数）均不少于10 个。 （文件存储） 2 、提供图中任意地点相关信息的查询。 3 、提供图中任意地点的问路查询：

3、1）任意两个地点之间的一条最短的简单路径；（最短路径长度中转次数最少） 2）任意两个地点之间的一条最佳访问路线；（带权（公里数）最短路径长度） 3）任意两个地点之间的所有简单路径。 4 、提供图中所有地点的最佳布网方案； 5 、增加新地点和路线、撤销旧地点和路线。三概要设计1.各个模块详细的功能描述。int Locate(AdjMatrix *G ,char name); 根据景点名称查找景点编号int VexExit(); 判断景点是否存在int Creat(AdjMatrix *G); 创建无向图void Savefile(AdjMatrix *G); 将图保存到文件中void Readf

4、ile(AdjMatrix *G); 从指定文件中读取信息并存入图中void ShowSchool(AdjMatrix *G); 显示校园全景图void ShowRoute(AdjMatrix *G); 显示图的所有路线void ShowVex(AdjMatrix *G); 显示图中所含景点的信息void Serach(AdjMatrix *G); 查找景点void AddRoute(AdjMatrix *G); 增加新路线void DeleteRoute(AdjMatrix *G); 删除旧路线void AddVex(AdjMatrix *G); 增加新景点void DeleteVex(Ad

5、jMatrix *G); 删除旧景点void Dijkstra(AdjMatrix *G ,int start,int ending,int dist,int pathMAXVEX); 求起点到终点的最短路线void Prim(AdjMatrix *G ,int start); 采用 Prim 算法求得最短连通路线名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - void MiniSpanTree(AdjMatrix *G);

6、查询从某个景点的最短连通路线void DFS(AdjMatrix *G ,int start,int ending,int stack,int visited); 深度遍历查找所有路径void SimpleRoute(AdjMatrix *G); 查询两个景点间的最优路径void SearchAllRoute(AdjMatrix *G); 输出两景点之间的所有路径void menu(); 显示主菜单void menu1(); 开始菜单界面void menu2(); 退出菜单界面四详细设计1 功能函数的调用关系图；调用调用调用调用调用调用调用调用调用ShowSchool ShowRoute Se

7、rach VexExit Locate AddRoute DeleteVex ShortCut Locate DeleteRoute Locate VexExit MiniSpanTree Dijkstra Locate Prim SimpleRoute DFS SearchAllRoute DFS 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - - - - - - 2.功能模块图：choice=1 choice=2 choice=3 choic

8、e=4 choice=5 choice=6 choice=7 choice=8 choice=9 choice=10 choice=11 choice=12 choice=0 main Readfile ShowSchool menu choice Readfile ShowVex Readfile Serach AddRoute Savefile Readfile Readfile Readfile Readfile Readfile DeleteRoute Savefile AddVex MiniSpanTree SimpleRoute ShortCut Savefile DeleteVe

9、x Readfile Readfile Savefile SerachAllRoute Readfile 结束menu1 开始Savefile Creat menu2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 2 各功能函数的数据流程图；i=0 i=0 i+ i=0 i=0 choice=1 choice=2 Creat 输入 vexnum,arcnum ivexnum 输入 name,introduce iarcnum

10、 输入 start,ending,distance 结束Savefile 写入 vexnum,arcnum ivexnum 写入 name,introduce iarcnum 存入路线， 距离结束Readfile 读出 vexnum,arcnum ivexnum 保存 name,introduce iarcnum 保存路线， 距离结束Serach choice 输出名称为name信息输出编号为n 信息name n 结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29

11、页 - - - - - - - - - 调用调用调用调用AddRoute 输入 start,ending,distance Locate 在 arcs中存入 distance 结束DeleteRoute 输入 start,ending,distance 结束在 arcs中赋初值Locate AddVex 输入 name,introduce Locate 从图中最后一个节点依次往前覆盖结束在 arcs中初始化DeleteVex 输入 name,introduce Locate 结束vexnum+ vexnum+ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

12、 - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - 若是终点，直接输出3.重点设计及编码。（1）文件的保存与读取 ：1.将图的顶点数和边数写入文件2.将图的顶点名称和介绍写入文件，用for 循环控制；3.将图中路线的起点和终点以及距离写入文件；4.文件的读取与保存原理一样。编码：void Savefile(AdjMatrix *G); 将图保存到文件中void Readfile(AdjMatrix *G); 从指定文件中读取信息并存入图中DFS 用 for 查找起点的邻接点输出 stack 数组存放的路径标志该点

13、被访问存入 stack 数组stack 下标往后移名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - （2）深度遍历 ：用递归的方法，从某个节点出发，访问此节点，然后依次从出发节点的各个未被访问的邻接点出发深度优先搜索遍历；将走过的路径存入数组中， 找到终点时输出路径。 该函数模块用于查找两点之间的所有路径以及最优路径，找最优路径时，定义一个数组及最小值， 每次最小值更新， 就将路径值数组赋值到最优路径数组中去。编码： void

14、DFS(AdjMatrix *G ,int start,int ending,int stack,int visited); （3）最小生成树 prim 算法从图中的某一顶点v0 出发，选择与它关联的具有最小权值的边，将其顶点加入到生成树的顶点集合中， 以后的每一步从在生成树中的一个顶点，而另一个顶点不在生成树顶点集合中的各条边中选择权值最小的边，再把它的顶点加入到生成树顶点集合中，直到所有顶点都加入到生成树集合中编码： void Prim(AdjMatrix *G ,int start); /采用 Prim 算法求得最短连通路线(4) 最短路径 Dijkstra 算法用带权的邻接矩阵存储该带

15、权有向图，借助一个辅助的一维数组dist 记录从源点到其余各顶点的最短距离值，二维数组path 记录某顶点是否加入到集合S中，如果 pathi0=1, 则表示顶点 Vi 加入到集合 S 中，并且 pathi所在的行最终记录了从源点到 Vi 的最短路径上的各个顶点，否则，pathi0=0, 则表示顶点 Vi还在集合 V-S 中。编码：void Dijkstra(AdjMatrix *G ,int start,int ending,int dist,int pathMAXVEX); /求起点到终点的最短路线五测试数据及运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

16、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - 1 正常测试数据（ 3 组）及运行结果；（1） 查询景点时输入正确景点编号（2）校园所有景点的信息（3）查询两点之间的最优路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - 2非正常测试数据（ 2 组）及运行结果。（1） 输入错误的景点编号（2）输入不存在的景点名师资料总结 - -

17、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - 六调试情况，设计技巧及体会1 对自己的设计进行评价，指出合理和不足之处，提出改进方案；好的地方：（1）在文件的存储方面比较满意，先将图的顶点数目和边的数目存入文件，再将顶点信息存入， 最后将路线的信息存入文件中。达到了将整个图存入文件的目的，相对于其他存储方法较为简洁且功能完善。（2）对于查询、增加、删除部分，都先输出已有的景点路线信息，方便用户操作。并且在用户输入错误时会有相应的错误处理。（3）代

18、码的格式比较整齐，易读。考虑到了很多细节。不足的地方：（1） 每次对图进行操作，都要先从文件中读取重建一个图，比较繁琐；（2） 在查找中转路径次数最少的时候调用了查找所有路径的函数，先是找到所有路径再对次数进行比较， 并且若中转次数最少的路径不止一条时，最终只能输出一条路径，有缺陷，算法不够优化；2 对设计及调试过程的心得体会。课程设计刚开始时， 思路有点混乱， 只知道用文件把图存起来， 每次操作时将信息读入图中，具体该怎么实现，还真不知道。看了一下课本，决定用邻接矩阵存储图。 图的存储方式决定好后， 就开始文件的存储， 个人觉得在文件的存储方面想法不错， 但是在文件的写入与读取格式的地方出了

19、一点小问题，在调试的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 过程中对文件又熟悉了一点。 这次课程设计不像以前马马虎虎，漏掉取址符， 标点符号等， 只会出现逻辑错误， 在整个过程中也比较顺利。 当不会一些算法的时候，我会查阅资料以及上网百度。把所有的功能实现后就开始细化自己的代码，比如对用户错误输入的错误处理，写小函数如VexExit 来让程序更加模块化，以及对界面的改进，只希望自己的代码更加完美。七参考文献（1）数据

20、结构 (C 语言版 ) 严蔚敏 吴伟民 编著 清华大学出版社 2002 （2） 数据结构与算法王曙燕 王春梅 编著人民邮电出版社 2013 八附录： 源代码（电子版）#include #include #include #include #include #include #include #define MAXVEX 20 #define INFINITY 32768 typedef struct /顶点类型 int num; / 景点的编号char name20; /景点的名称char introduce100; / 景点的介绍Vextype; typedef struct /邻接矩阵 i

21、nt arcsMAXVEXMAXVEX; /边集，存放权值Vextype vexMAXVEX; /顶点集int vexnum; /顶点的数目int arcnum; /边的数目AdjMatrix; int Locate(AdjMatrix *G ,char name); /根据景点名称查找景点编号int VexExit(); /判断景点是否存在int Creat(AdjMatrix *G); /创建无向图void Savefile(AdjMatrix *G); /将图保存到文件中void Readfile(AdjMatrix *G); /从指定文件中读取信息并存入图中void ShowSchoo

22、l(AdjMatrix *G); /显示校园全景图void ShowRoute(AdjMatrix *G); /显示图的所有路线void ShowVex(AdjMatrix *G); /显示图中所含景点的信息名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - void Serach(AdjMatrix *G); /查找景点void AddRoute(AdjMatrix *G); /增加新路线void DeleteRoute(Ad

23、jMatrix *G); /删除旧路线void AddVex(AdjMatrix *G); /增加新景点void DeleteVex(AdjMatrix *G); /删除旧景点void Dijkstra(AdjMatrix *G,int start,int ending,int dist,int pathMAXVEX); /求起点到终点的最短路线void Prim(AdjMatrix *G ,int start); /采用 Prim 算法求得最短连通路线void MiniSpanTree(AdjMatrix *G); /查询从某个景点的最短连通路线void DFS(AdjMatrix *G,i

24、nt start,int ending,int stack,int visited); /深度遍历查找所有路径void SimpleRoute(AdjMatrix *G); /查询两个景点间的最优路径void SearchAllRoute(AdjMatrix *G); /输出两景点之间的所有路径void menu(); /显示主菜单void menu1(); /开始菜单界面void menu2(); /退出菜单界面int Locate(AdjMatrix *G ,char name) /根据景点名称查找景点编号 int i; for(i=1;ivexnum;i+) if(!strcmp(nam

25、e,G-vexi.name) return i; return -1; int VexExit(AdjMatrix *G ,int index) /判断景点是否存在 if(index0 & indexvexnum) return 1; else printf( 该景点不存在！ n); return 0; int Creat(AdjMatrix *G) /创建无向图 int i,j,k,weight; char name20; printf( 请输入校园图中的景点数目和路线数目：n); scanf(%d%d,&G-vexnum,&G-arcnum); for(i=1;ivexnum;i+) /权

26、值数组初始化for(j=1;jvexnum;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - G-arcsij=INFINITY; printf( 请输入校园图中 %d 个景点的名称及介绍： n,G-vexnum); for(i=1;ivexnum;i+) printf( 请输入第 %d 个景点 :,i); G-vexi.num=i; /flushall(); scanf(%s%s,G-vexi.name,G-vexi

27、.introduce); printf( 请输入校园图中的 %d 条路线 :n,G-arcnum); for(k=1;karcnum;k+) /存入路线 printf( 请输入第 %d 条路线： n,k); printf( 起点:); scanf(%s,name); i=Locate(G,name); printf( 终点:); scanf(%s,name); j=Locate(G,name); printf( 距离:); scanf(%d,&weight); G-arcsij=weight; G-arcsji=weight; return 1; void Savefile(AdjMatrix

28、 *G) /将图保存到文件中 FILE *fp; int i,j; fp=fopen(Graph.txt,wt); if(!fp) printf( 写文件出错，按任意键退出！n); getch(); exit(1); fprintf(fp,%d %dn,G-vexnum,G-arcnum); /先将图的顶点数目和边集数目存入文件，便于控制下面程序的for 循环for(i=1;ivexnum;i+) /接着存放顶点的信息fprintf(fp,%s %sn,G-vexi.name,G-vexi.introduce); for(i=1;ivexnum;i+) /最后存放边的信名师资料总结 - - -

29、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 息即路线信息for(j=1;jarcsij!=INFINITY) fprintf(fp,%s %s %dn,G-vexi.name,G-vexj.name,G-arcsij); printf(n 文件已成功保存，按任意键返回！n); getch(); fclose(fp); void Readfile(AdjMatrix *G) /从指定文件中读取信息并存入图中 FILE *fp; int i,j;

30、int start,ending; char startpoint20,endpoint20; int distance; fp=fopen(Graph.txt,rt); if(!fp) printf( 读文件出错，按任意键退出！n); getch(); exit(1); fscanf(fp,%d%d,&G-vexnum,&G-arcnum); /先读取文件中的前两个整型，存入图的顶点数目和边数目中/对图的权值数组进行初始化for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) G-arcsij=INFINITY; /从文件中读取顶点信息并存入图中for(i=1;ive

31、xnum;i+) G-vexi.num=i; fscanf(fp,%s%s,G-vexi.name,G-vexi.introduce); /从文件中读取路线并存入图中for(j=1;jarcnum;j+) fscanf(fp,%s%s%d,startpoint,endpoint,&distance); start=Locate(G ,startpoint); ending=Locate(G ,endpoint); G-arcsstartending=distance; G-arcsendingstart=distance; 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

32、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - - - - void ShowSchool() /显示校园全景图 printf(tt n); printf(tt xxxxxxxx大学校园平面图n); printf(tt n); printf(tt n); printf(tt 10.n); printf(tt 宿舍楼 2 宿舍楼 1 n); printf(tt 15n); printf(tt 11. 180 1070n); printf(tt 150 n); printf(tt 体旭日苑美n); print

33、f(tt 8.育9.7.食n); printf(tt 馆广n); printf(tt 200 场n); printf(tt n); printf(tt 60 6. n); printf(tt 130n); printf(tt 图书馆n); printf(tt 80 4.n); printf(tt n); printf(tt 5. 大活n); printf(tt 学动实验楼n); printf(tt 生中n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 -

34、 - - - - - - - - printf(tt 心n); printf(tt 20 n); printf(tt 100 2.n); printf(tt 教学楼n); printf(tt 40 50 n); printf(tt 3.行政楼南n); printf(tt 东西n); printf(tt 北n); printf(tt 1.北门n); printf(tt n); void ShowRoute(AdjMatrix *G) /显示图的所有路线 int i,j; printf(n 校园里一共有 %d 条路线 .nn,G-arcnum); for(i=1;ivexnum;i+) for(j

35、=1;jarcsij!=INFINITY) printf(%s%s t距离为：%dmn,G-vexi.name,G-vexj.name,G-arcsij); void ShowVex(AdjMatrix *G) /显示所有景点 int i; printf( 校园共有 %d 个景点，编号、名称及介绍如下:nn,G-vexnum); for(i=1;ivexnum;i+) printf(%d.%s: t%sn,i,G-vexi.name,G-vexi.introduce); void Serach(AdjMatrix *G) /查询景点 int i,n; char name20; printf(

36、请选择你要查询的方式： n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - printf(1.编号2.名称n); scanf(%d,&n); if(n = 1) printf( 请输入景点的编号 (1%d):,G-vexnum); scanf(%d,&n); if(VexExit(G,n) printf( 该景点情况及周围景点如下:n); printf(n%d.%s %snn,n,G-vexn.name,G-vexn.i

37、ntroduce); for(i=1;ivexnum;i+) /找出与该景点相关的路线if(G-arcsni != INFINITY) printf(%s%s: %dmn,G-vexn.name,G-vexi.name,G-arcsni); else if(n = 2) printf( 该校园有以下景点，请选择:n); for(i=1;ivexnum;i+) printf(%st ,G-vexi.name); printf(nn 请输入要查询景点的名称 :); scanf(%s,name); n=Locate(G ,name); /通过名称找到该景点的序号if(VexExit(G,n) pri

38、ntf(n 该景点名称、介绍及可以直达的景点如下:n); printf(n%d.%s %snn,n,G-vexn.name,G-vexn.introduce); for(i=1;ivexnum;i+) if(G-arcsni!=INFINITY) printf(%s%s: %dmn,G-vexn.name,G-vexi.name,G-arcsni); if(iG-vexnum+1) printf( 此景点为独立的点 ,返回!n); else printf( 输入错误，返回！ n); void AddRoute(AdjMatrix *G) /增加新路线 char name20; int star

39、t,ending,distance; ShowRoute(G); printf(n 请输入要增加路线的起点和终点名称:n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - printf(n 起点:); scanf(%s,name); start=Locate(G ,name); printf( 终点:); scanf(%s,name); ending=Locate(G ,name); printf( 距离:); scanf

40、(%d,&distance); /将新路线的距离存入权值数组中G-arcsstartending=distance; G-arcsendingstart=distance; G-arcnum+; /图的边集加 1 printf( 添加新路线成功。 n); void DeleteRoute(AdjMatrix *G) /删除路线 char name20; int start,ending; ShowRoute(G); printf(n 请输入要删除路线的起点和终点名称:n); printf( 起点: ); scanf(%s,name); start=Locate(G ,name); printf

41、( 终点: ); scanf(%s,name); ending=Locate(G ,name); if(G-arcsstartending = INFINITY) printf( 您要删除的路线不存在，请重新输入!n); /将对应权值数组中的元素赋值，删除路线else G-arcsstartending=INFINITY ; G-arcsendingstart=INFINITY ; G-arcnum-; printf( 删除路线成功。 n); void AddVex(AdjMatrix *G) /增加景点 int i; char name20; char intro100; printf( 该

42、校园包含以下景点 :n); for(i=1;ivexnum;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - - - - - - - - - printf(%d.%st ,i,G-vexi.name); printf(nn 请输入增加景点的名称和介绍:n); scanf(%s%s,name,intro); /图的顶点集先加 1，将增加景点的信息赋值到图的末尾景点中G-vexnum+; G-vexG-vexnum.num=G-vexnum; strcp

43、y(G-vexG-vexnum.name,name); strcpy(G-vexG-vexnum.introduce,intro); /对新增景点的权值数组元素赋初值for(i=1;ivexnum;i+) G-arcsG-vexnumi=INFINITY; for(i=1;ivexnum;i+) G-arcsiG-vexnum=INFINITY; printf( 增加景点成功 !n); void DeleteVex(AdjMatrix *G) /删除景点 int i,j,count=0; char name20; printf( 该校园有以下景点 :n); for(i=1;ivexnum;i+

44、) printf(%d.%st ,i,G-vexi.name); printf(nn 请输入删除景点的名称 :n); scanf(%s,name); i=Locate(G,name); if(VexExit(G,i) for(j=1;jvexnum;j+) /找出与该景点相关的路线数目if(G-arcsij!=INFINITY) count+; /先找到景点在图中的位置，从后往前依次覆盖原值for(i;ivexnum;i+) G-vexi.num=G-vexi+1.num; strcpy(G-vexi.name,G-vexi+1.name); strcpy(G-vexi.introduce,G

45、-vexi+1.introduce); G-vexnum-; /图的顶点集减 1 G-arcnum=G-arcnum-count; /图的边数目减去与删除景点有关的路线数目printf( 删除景点成功 !n); void Dijkstra(AdjMatrix *G ,int start,int ending,int dist,int pathMAXVEX) /求起点到终点的最短路线名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 29 页 - - - - - - - -

46、- /dist 数组记录各条最短路径长度，path 数组记录对应路径上的各顶点int mindist,i,j,k,t=1; for(i=1;ivexnum;i+) /初始化 disti=G-arcsstarti; if(G-arcsstarti!=INFINITY) pathi1=start; pathstart0=1; for(i=2;ivexnum;i+) /寻找各条最短路线 mindist=INFINITY; for(j=1;jvexnum;j+) /选择最小权值的路线if(!pathj0 & distjmindist) k=j; mindist=distj; if(mindist =

47、INFINITY) return ; pathk0=1; for(j=1;jvexnum;j+) /修改路线 if(!pathj0&G-arcskjarcskjarcskj; t=1; while(pathkt!=0) /记录最新的最短路线 pathjt=pathkt; t+; pathjt=k; pathjt+1=0; for(i=1;ivexnum;i+) if(i = ending) break; printf(%s-%s的最短路线为：n从%s,G-vexstart.name,G-vexending.name,G-vexstart.name); for(j=2;pathij!=0;j+)

48、 printf(-%s,G-vexpathij.name); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 29 页 - - - - - - - - - printf(-%s,距离为 %dmn,G-vexending.name,disti); void Shortcut(AdjMatrix *G) /寻找最短路线 char name20; int start,ending; int i; int distMAXVEX,pathMAXVEXMAXVEX=0; print

49、f( 校园里有以下景点 :n); for(i=1;ivexnum;i+) printf(%d.%st ,i,G-vexi.name); printf(n 请输入起点景点名称 :); scanf(%s,name); start=Locate(G ,name); printf( 请输入终点景点名称 :); scanf(%s,name); ending=Locate(G ,name); Dijkstra(G,start,ending,dist,path); void Prim(AdjMatrix *G ,int start) /采用 Prim 算法求得最短连通路线 struct int adjvex

50、; /存放顶点序号int lowcost; /存放权值closedgeMAXVEX; int i,e,k,m,mincost; closedgestart.lowcost=0; /起始点的权值初始化为0， 该顶点加入到生成树集合中/对除了出发点以外的所有顶点初始化对应的closedge数组for(i=1;ivexnum;i+) if(i != start) closedgei.adjvex=start; closedgei.lowcost=G-arcsstarti; /控制选中的 n-1 条符合条件的边for(e=1;evexnum-1;e+) /选择最小权值的边mincost=INFINIT

51、Y; for(k=1;kvexnum;k+) if(closedgek.lowcost!=0 & closedgek.lowcostvexclosedgem.adjvex.name,G-vexm.name,closedgem.lowcost); closedgem.lowcost=0; /标志该顶点加入到最小生成树集合中/更新 closedge数组信息for(i=1;ivexnum;i+) if(i!=m & G-arcsmiarcsmi; closedgei.adjvex=m; void MiniSpanTree(AdjMatrix *G) /查询从某个景点的最短连通路线 char name

52、20; int start; int i; for(i=1;ivexnum;i+) printf(%d.%st ,i,G-vexi.name); printf(n 请输入起始地点名称 : ); scanf(%s,name); start=Locate(G ,name); printf( 从%s开始的最短连通路线为 :nn,name); Prim(G,start); int m=1,min=INT_MAX; int path20=0; int tag; void DFS(AdjMatrix *G ,int start,int ending,int stack,int visited) /深度遍历

53、查找所有路径 int i, j; for(i=1; ivexnum; i+) if(G-arcsstarti != INFINITY & visitedi=0) if(i = ending)/ 如果深搜到了终点，就输出刚才经过的路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 29 页 - - - - - - - - - / tag 用于判断找最优路径还是所有路径if(tag=1) / 找所有路径时输出路径 for(j=0; j, G-vexstackj.name);

54、 printf(%sn, G-vexending.name); else /找最优路径时记录次数最少的路径if(m=min) min=m; for(j=0;jm;j+) pathj=stackj; else/如果该点不是终点 visitedi=1; stackm = i;/将该点存起来m+; DFS(G ,i,ending,stack,visited);/接着深搜visitedi=0; m-; void SimpleRoute(AdjMatrix *G) /查询两个景点间的最优路径（中转次数最少） char name20; int i; int start,ending; int stack2

55、0=0; int visited20=0; printf( 该校园包含以下景点 :n); for(i=1;ivexnum;i+) printf(%d.%st ,i,G-vexi.name); printf(n 请输入起始地点名称 : ); scanf(%s,name); start=Locate(G ,name); stack0=start; printf( 请输入终止地点名称 : ); scanf(%s,name); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 2

56、9 页 - - - - - - - - - ending=Locate(G ,name); visitedstart=1; tag=0; DFS(G,start,ending,stack,visited); printf(n 最优路径即中转次数最少的路径为：n); for(i=0;i,G-vexpathi.name); printf(%sn, G-vexending.name); void SearchAllRoute(AdjMatrix *G) /输出两景点之间的所有路径 char name20; int start,ending; int i; int stack20=0; int vis

57、ited20=0; printf( 校园中有以下景点 :n); for(i=1;ivexnum;i+) printf(%d.%st ,i,G-vexi.name); printf(n 请输入起始地点名称 : ); scanf(%s,name); start=Locate(G ,name); stack0=start; printf( 请输入终止地点名称 : ); scanf(%s,name); ending=Locate(G ,name); visitedstart=1; tag=1; DFS(G,start,ending,stack,visited); void menu1() /开始菜单界

58、面 system(color 0d); printf(nnnnnnnt*n); printf(t*ttttttt *n); printf(t*ttttttt *n); printf(t* 欢 迎 进 入 西 安 邮 电 大 学 校 园 导 游 系 统*n); printf(t*ttttttt *n); printf(t*ttttttt *n); printf(t*n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 29 页 - - - - - - - - - Sle

59、ep(2000); void menu2() /退出菜单界面 system(color 0d); printf(nnnnnnnt*n); printf(t*ttttttt *n); printf(t*ttttttt *n); printf(t*ttt 谢谢使用！ ttt *n); printf(t*ttttttt *n); printf(t*ttttttt *n); printf(t*nnnnnnn); Sleep(3000); void menu() /显示主菜单 system(color 2f ); printf(nnt* 欢迎使用西安邮电大学校园导游系统*n); printf(t*ttt

60、ttttt *n); printf(t*tt 1. 浏览校园全景图*n); printf(t*tt 2. 显示校园所有景点以及路线*n); printf(t*tt 3. 查询某景点信息*n); printf(t*tt 4. 增加路线*n); printf(t*tt 5. 撤销路线*n); printf(t*tt 6. 增加景点*n); printf(t*tt 7. 删除景点*n); printf(t*tt 8. 查 询 两 景 点 之 间 的 简 单 路 径 （ 中 转 次 数 最 少 ）*n); printf(t*tt 9. 查 询 两 景 点 之 间 的 长 度 最 短 路 线*n); p

61、rintf(t*tt 10.查 询 图 中 景 点 的 最 佳 布 网 方 案 （ 最 小 生 成 树 ）*n); printf(t*tt 11. 查询两景点之间的所有路径*n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 29 页 - - - - - - - - - printf(t*tt 12.输入校园图信息*n); printf(t*tt 0. 退出菜单*n); printf(t*tttttttt *n); printf(t*nn); int main()

62、AdjMatrix G; int choice; menu1(); system(cls); do menu(); printf(ttt 请输入你要选择项的编号：); scanf(%d,&choice); switch(choice) case 1: system(cls); Readfile(&G); ShowSchool(); printf(n 按任意键返回 .); getch(); system(cls); break; case 2: system(cls); Readfile(&G); ShowVex(&G);ShowRoute(&G); printf(n 按任意键返回 .); ge

63、tch(); system(cls); break; case 3: system(cls); Readfile(&G); Serach(&G); printf(n 按任意键返回 .); getch(); system(cls); break; case 4: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 29 页 - - - - - - - - - system(cls); Readfile(&G); AddRoute(&G); Savefile(&G); prin

64、tf(n 按任意键返回 .); getch(); system(cls); break; case 5: system(cls); Readfile(&G); DeleteRoute(&G); Savefile(&G); printf(n 按任意键返回 .); getch(); system(cls); break; case 6: system(cls); Readfile(&G); AddVex(&G); Savefile(&G); printf(n 按任意键返回 .); getch(); system(cls); break; case 7: system(cls); Readfile(

65、&G); DeleteVex(&G); Savefile(&G); printf(n 按任意键返回 .); getch(); system(cls);break; case 8: system(cls); Readfile(&G);SimpleRoute(&G); printf(n 按任意键返回 .); getch(); system(cls);break; case 9: system(cls); Readfile(&G); Shortcut(&G); printf(n 按任意键返回 .); getch(); system(cls); break; case 10: system(cls);

66、 Readfile(&G); MiniSpanTree(&G); printf(n 按任意键返回 .); getch(); system(cls);break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 29 页 - - - - - - - - - case 11: system(cls); Readfile(&G); SearchAllRoute(&G); printf(n 按任意键返回 .); getch(); system(cls);break; case 12: system(cls); Creat(&G); Savefile(&G); printf(n 按任意键返回 .); getch(); system(cls);break; case 0: system(cls); menu2();break; default: system(cls);break; while(choice); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 29 页 - - - - - - - - -