校园导游咨询(最短路径)

1、数据结构课程设计实验报告学 号：姓 名：提交日期：成 绩：东北大学秦皇岛分校设计题目：校园导游咨询一、实验目的（1）熟练掌握图的创建及遍历基本操作算法。（2）熟练掌握最短路径算法。（3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。二、需求分析 实验内容 【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1) 设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供

2、图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。 【测试数据】由读者根据实际情况指定。 【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。 【实现功能】这个系统给用户提供查询景点，浏览路径，寻找最佳的方案到达目的地，还提供了最佳路径。3、 概要设计 1.系统分析： 用的图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。2功能模块图；结束查看各景点游览路线

3、开始定义变量Void Menu()进入菜单Switch()选择功能退出系统浏览校园全景显示此图的邻接矩阵查看景点信息选择出发点和目的地3. 各个模块详细的功能描述（1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息。（2）浏览校园全景（Browser）：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出。（3）查看各景点游览路线（ShortestPath_DIJ）：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上。（4）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地

4、的最短路径。（5）查看景点信息(Search)：直接输入编号进行单个景点查询。（6）显示图的邻接矩阵(print)（7）退出系统(exit)4 详细设计 （1）图的结构typedef struct ArCell /对弧的定义int adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype; /数据域typedef structinfotype vex

5、sMAX_VERTEX_NUM; /顶点的数据域AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧数MGraph;（2） 各个函数的声明如下：void cmd(void);MGraph InitGraph(void); /初始化图void Menu(void); /整体菜单void Browser(MGraph *G); /遍历校园全景void ShortestPath_DIJ(MGraph * G); /景点所有路线void Floyd(MGraph *G); /两景点之间最短距离void Search(MGraph *G); /查看景点信息

6、void print(MGraph *G); /输出该图邻接矩阵（3） 主函数 void main(void) /定义主函数 system(color 1f); system(mode con: cols=100 lines=40); cmd(); /调用cmd（）（4） 主要函数迪杰斯特拉算法算法思想：依路径长度递增的次序求得各条路径/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; /flag=1保证输入编号有效 int final20, D20,

7、 p2020; /用迪杰斯特拉算法求网G的v0顶点到其余顶点v的最短路径Pv及带权长度Dv/若Pvw为1，则w是从v0到v当前求得最短路径上的顶点/finalv为1当且仅当v属于s(s是已求得最短路径的终点的集合)，即已经求得从v0到v的最短路径 while(flag) printf(请输入一个起始景点编号:); scanf(%d,&v0); /输入一个值赋给v0 if(v0G-vexnum) printf(景点编号不存在!请重新输入景点编号:); scanf(%d,&v0); if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; /v

8、不属于s，即v顶点还没有走过 Dv=G-arcsv0v.adj; /v0到v的弧权值 for(w=0;wvexnum;w+) pvw=0; /设置空路径 if(DvINFINITY) pvv0=1;pvv=1; /v0是从v0到v的顶点，v是从v0到v的顶点 Dv0=0;finalv0=1; /初始化，v0到v0的带权路径长度为0，最短路径,v0顶点属于s集 /开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集 for(i=1;ivexnum;i+) /其余G.vexnum-1个顶点 min=INFINITY; /当前所知离v0顶点的最近距离 for(w=0;wvexnum;w+)

9、if(!finalw) /w顶点在v-s中 if(Dwmin)v=w;min=Dw; /w顶点离v0顶点更近 finalv=1; /离v0顶点最近的v加入s集 for(w=0;wvexnum;w+) /更新当前的最短路径及距离 if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; /用来更新到每一个顶点的最短路径 for(v=0;vvexnum;v+) if(v0!=v) printf(%s,G-); /输出字符串 for(w=0;wvexnum;w+) if(pvw&w!=

10、v0) printf(-%s,G-); t+; if(tG-vexnum-1&v0!=v)printf( 总路线长%dmnn,Dv); /ShortestPath_DIJ endFloyd算法算法思想：从vi到vj的所有存在的路径中，选出一条长度最短的路径，即每一对顶点之间的最短路径。void Floyd(MGraph *G)/用Floyd算法求图中各对顶点v和w之间的最短路径Pvw及其/带权长度Dvw。若Pvwu为1，则u是从v到w当前求得最短/路径上的顶点。 int v,u,i,w,k,j,flag=1,p101010,D1010; for(v=0;vvexnum;v+

11、) /各对结点之间初始已知路径及距离 for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) /从v经u到w的一条路径更短 Dvw=Dvu+Duw; /修改权值 for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) printf(请输入出发点和目的地的编号:); sca

12、nf(%d%d,&k,&j); if(kG-vexnum|jG-vexnum) printf(景点编号不存在!请重新输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; printf(%s,G-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-); printf(-%s,G-); printf( 总路线长%dmn,Dkj);/Floyd end5、 测试结果程序界面：主界面： 1.浏览校园

13、全景2. 查看各景点所有游览路线输入景点编号1：输入顶点编号3：3.选择出发点和目的地 输入出发点和目的地的编号分别是：2和8 输入出发点和目的地的编号分别是：1和9 4.查看景点信息 查看景点信息：1查看景点信息4：5. 显示此图的邻接矩阵 6.退出系统6、 调试与分析 刚开始调试时出现很多错误，有些忘了写头文件，然后迅速从网上查到该词的头文件加在程序里。也有的函数忘记了提前声明导致了程序不能运行，以及其他各种问题。不过最后都能够通过各种途径调试出来，有查书的，也有向同学请教的。当程序能够正常运行出来时，界面显示也出现了很多问题。有的是因为少了换行符，导致界面排列不好。不过，最终都慢慢地改了

14、过来。七、心得与体会 经过两周的课程设计收获很多，在做课程设计之前，我觉得这是一项浩大的工程，总觉得自己会做不到。现在当我真的完成这个课程设计时，心里有一种成就感。这次课程设计，我学到了很多东西：学会了在编写几百行程序时如何查找错误，如何改错误；了解数据结构在编写比较复杂的程序的重要作用；对数据结构中定义无向图和创建无向图的理解更加深刻；最重要的是让我基本上明白了迪杰斯特拉算法和弗洛伊德算法。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应

15、用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。 课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦，得到了同学的帮助和指导，才能够使得这次课程设计顺利的进行下去

16、，这也让我明白，要多于别人交流才能更好的完善自己。 八、参考文献：数据结构（C语言版 严蔚敏，吴伟民清华大学出版社9、 附录该程序完整代码：#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include /头文件#include#include#includetypedef struct ArCell /对弧的定义int adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /一个二维数组,数组里元素类型为整型typedef struct /图中

17、顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype; /数据域typedef structinfotype vexsMAX_VERTEX_NUM; /顶点的数据域AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧数MGraph;MGraph b; /全局变量void cmd(void);MGraph InitGraph(void); void Menu(void); void Browser(MGraph *G); void Shortes

18、tPath_DIJ(MGraph * G); void Floyd(MGraph *G); void Search(MGraph *G); void print(MGraph *G); /*/void main(void) /定义主函数 system(color 1f); system(mode con: cols=100 lines=40); cmd(); /调用cmd（）/*/void cmd(void) /定义cmd（） int i; b=InitGraph(); MGraph G; Menu(); scanf(%d,&i); while(i!=6) switch(i) case 1:s

19、ystem(cls);Browser(&b);Menu();break; /system(cls);作用是清屏 case 2:system(cls);ShortestPath_DIJ(&b);Menu();break; case 3:system(cls);Floyd(&b);Menu();break; case 4:system(cls);Search(&b);Menu();break; case 5:system(cls);print(&b);Menu();break; case 6:exit(1);break; default:break; /每次显示选择的一项后，会继续显示主菜单men

20、u（） scanf(%d,&i); /输入的值d赋给i MGraph InitGraph(void) /初始化 MGraph G; int i,j; G.vexnum=10; /10个顶点 G.arcnum=14; /14条弧 for(i=0;iG.vexnum;i+) G.vexsi.num=i; /第i个景点的编号为i strcpy(G.,实验楼); /strcpy的头文件是string.h strcpy(G.roduction,实验器材齐全，承担各种建设项目，为学生提供有利的创新平台); strcpy(G.,图书馆); strcp

21、y(G.roduction,收藏丰富的图书，设施良好，有阅览室和电子阅览室，环境幽雅); strcpy(G.,网球场); strcpy(G.roduction,网球课训练基地，为热爱网球的同学提供场地); strcpy(G.,经管楼); strcpy(G.roduction,学校建校时所建，虽有点古老，但环境整洁，考研同学学习基地); strcpy(G.,旧操场); strcpy(G.roduction,设有旧篮球场旧足球场，是晚自习后，同学们运动的最佳场所);

22、strcpy(G.,二号学生宿舍); strcpy(G.roduction,经贸学院及计算机与通信工程学院的女生宿舍，地理位置优越); strcpy(G.,第一学生餐厅); strcpy(G.roduction,价格实惠，食物种类不多，各种饼的天下); strcpy(G.,工学馆); strcpy(G.roduction,学院最大的教学楼,共8层，楼内冬暖夏凉，学生学习的最佳场所); strcpy(G.,第六学生公寓); strcpy(G.ro

23、duction,新建的学生公寓，居住环境幽雅，设施良好，就餐方便); strcpy(G.,大学生会馆); strcpy(G.roduction,设施良好，举办各种活动以及各种重要讲座的最佳基地); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; G.arcs01.adj=20; G.arcs02.adj=100; G.arcs13.adj=40; G.arcs14.adj=150; G.arcs24.adj=10; G.arcs35.adj=200; G.arcs45.a

24、dj=60; G.arcs48.adj=80; G.arcs56.adj=10; G.arcs57.adj=60; G.arcs67.adj=50; G.arcs78.adj=240; G.arcs79.adj=200; G.arcs89.adj=300; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; /无向网 return G;/InitGraph endvoid Menu() /定义主菜单 printf(n 东北大学秦皇岛分校导游图n); printf( n); printf( 1.浏览校园全景

25、 n); printf( 2.查看各景点所有游览路线 n); printf( 3.选择出发点和目的地 n); printf( 4.查看景点信息 n); printf( 5.显示此图的邻接矩阵 n); printf( 6.退出系统 n); printf( n); printf(Option-:);void Browser(MGraph *G) int v; printf(n); printf(编号景点名称 简介 n); for(v=0;vvexnum;v+) printf(%-4d%-16s%-56sn,G-vexsv.num,G-,G-roduction)

26、; printf(n);/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; /flag=1保证输入编号有效 int final20, D20, p2020; /用迪杰斯特拉算法求网G的v0顶点到其余顶点v的最短路径Pv及带权长度Dv/若Pvw为1，则w是从v0到v当前求得最短路径上的顶点/finalv为1当且仅当v属于s(s是已求得最短路径的终点的集合)，即已经求得从v0到v的最短路径 while(flag) printf(请输入一个起始景点编号:);

27、 scanf(%d,&v0); /输入一个值赋给v0 if(v0G-vexnum) printf(景点编号不存在!请重新输入景点编号:); scanf(%d,&v0); if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; /v不属于s，即v顶点还没有走过 Dv=G-arcsv0v.adj; /v0到v的弧权值 for(w=0;wvexnum;w+) pvw=0; /设置空路径 if(DvINFINITY) pvv0=1;pvv=1; /v0是从v0到v的顶点，v是从v0到v的顶点 Dv0=0;finalv0=1; /初始化，v0到v0

28、的带权路径长度为0，最短路径,v0顶点属于s集 /开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集 for(i=1;ivexnum;i+) /其余G.vexnum-1个顶点 min=INFINITY; /当前所知离v0顶点的最近距离 for(w=0;wvexnum;w+) if(!finalw) /w顶点在v-s中 if(Dwmin)v=w;min=Dw; /w顶点离v0顶点更近 finalv=1; /离v0顶点最近的v加入s集 for(w=0;wvexnum;w+) /更新当前的最短路径及距离 if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for

29、(x=0;xvexnum;x+) pwx=pvx; pww=1; /用来更新到每一个顶点的最短路径 for(v=0;vvexnum;v+) if(v0!=v) printf(%s,G-); /输出字符串 for(w=0;wvexnum;w+) if(pvw&w!=v0) printf(-%s,G-); t+; if(tG-vexnum-1&v0!=v)printf( 总路线长%dmnn,Dv); /ShortestPath_DIJ endvoid Floyd(MGraph *G)/用Floyd算法求图中各对顶点v和w之间的最短路径Pvw及其/带权长度Dvw。若Pvwu为1，则u是从v到w当前求得最短/路径上的顶点。 int v,u,i,w,k,j,flag=1,p101010,D1010; for(v=0;vvexnum;v+) /各对结点之间初始已知路径及距离 for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u