校园导航系统课程设计

1、键入文字好理爭院课程设计课程名称题目名称专业班级数据结构 校园导航系统13软件工程二O五年六月一日1 / 29键入文字目录1弓I言 51.1问题的提出51.2国内外研究的现状51.3任务与分析52程序的主要功能63程序运行平台64总体设计74.1数据结构类型定义74.2函数声明74.3创建导航图，即无向图84.4最短路径导航函数 85程序方法的说明95.1主菜单95.2主函数105.3迪杰斯特拉算法实现 136模块分析157系统测试157.1系统登录界面 157.2 功能一：学校简介 167.3功能二：两点最短距离导航 167.4功能三：某点到其他所有点的最短距离 177.5功能四：显示全校地

2、图 177.5退出导航系统188结论19附录:192 / 29键入文字蚌埠学院计算机科学与技术系本科课程设计成绩评定表项目权重分值具体要求得分文献阅读与调查论证0.20100能独立查阅文献和从事其它调研；有收集、加工各种信息的能力设计质量0.30100设计合理、功能齐备，程序运行正常，实验数据准确 可靠；有较强的实际动手能力论文撰写质量0.20100设计说明书完全符合规范化要求，用A4复印纸打印成文学习态度0.20100学习态度认真，科学作风严谨，严格按要求开展各项 工作，按期完成任务学术水平与创新0.10100设计有创意，有一定的学术水平或实用价值总分评语：等级：指导教师：年月日3 / 29

3、键入文字附件4分工协作说明（以列表形式具体说明每个人所做的工作）；课题名称学生姓名学号所做的工作校园导航系统张小蒙51302041036算法设计、程序调试、课程设计报 告撰写张浩51302041045算法设计、程序调试、课程设计报 告排版王威风51302041011算法设计、程序调试、课程设计报 告撰写柏祝林51302033026算法设计、程序调试、资料查询鲍金林51302041041部分算法设计、程序调试张红伟51302041043部分算法设计、程序调试、资料查 询杨伟平51302041006部分算法设计、程序调试4 / 29键入文字1.1问题的提出设计一个校园导航系统，为来访的客人提供各种

4、信息查询服务。1.2国内外研究的现状这个问题一直是国内外研究的热门话题。1.3任务与分析设计你的学校的平面图，至少包括 8个以上的场所，每两个场所间可以 有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）5 / 29键入文字2程序的主要功能（1）设计校园平面图，在校园景点选 8个左右景点。以图中顶点表示校园 内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等 有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一 条最短路径。3程序运行平台计算机 wi ndows7Virtua

5、l C+ 6.06 / 29键入文字4总体设计4.1数据结构类型定义#i nclude<stdio.h>#include <stdlib.h>最大顶点个数最大值#i nclude <stri ng.h>#defi ne MAX_V 30/#define INFINITY 32767 /typedef structchar* vexsMAX_V; / 顶点向量int arcsMAX_VMAX_V;邻接矩阵in t vex nu m,arcnum;图的当前顶点数和弧数MGraph;4.2函数声明int CreateUDN(MGraph & G); /创建

6、导航图函数声明extern have30;void ShortPath(MGraph & G,i nt vO,i nt pMAX_VMAX_V,i nt d); 短路径导航函数声明int have30;void men u(); /导航菜单函数声明void show1(); /显示全校面貌int jianjie();读取文件7 / 29键入文字4.3创建导航图，即无向图int CreateUDN(MGraph &G)函数描述：主要将每个节点进行命名，每个定点到其他所有定点的路径值用 邻接矩阵进行存储。例如：G.vexsO=" 小池塘"G.vexs1=&quo

7、t;东门"；作用：使0号定点命名为“小池塘”，1号节点命名为“东门”。G.arcs14 = G.arcs41 =260 ;作用：使1号定点到4号定点的路径赋值为260,同时4号定点到1号定点 的路径长度也为260.4.4最短路径导航函数void ShortPath(MGraph & G,i nt v0,i nt pMAX_VMAX_V,i nt d)函数描述：用迪杰斯特拉算法求最短路径。8 / 29键入文字5程序方法的说明5.1主菜单void menu()prin tf("ttttprin tf("tttt 学院各区名称 n");(1)小池塘(2

8、)东门西门 n");prin tf("tttt(4)北门(5)东区宿舍楼西南宿舍楼 n");prin tf("tttt(7)北区田径场(8)南区田径场(9)一号食堂 n");prin tf("tttt(10)二号食堂(11) A B C教学楼(12)重行楼 n");prin tf("tttt(13)行政楼(14)艺术楼(15)图书馆 n");prin tf("tttt(16)超市(17)医务室(18)没有了 n");prin tf("ttttttt请选择导航功能：n"

9、;);prin tf("tttttz/S»Z/S_z:n");prin tf("tttttz-(1)学校简介 n");prin tf("tttttz-两点最短距离导航 n");prin tf("tttttz-某点到其他所有点的最短距离 n");prin tf("tttttz-显示全校地图 n");prin tf("tttttz-退出导航系统 n");prin tf("tttttz*S»Z/S»Z/S_z:n");描述：程序主菜

10、单显示9 / 29键入文字5.2主函数void main()system("color 09"); /*修改控制台的颜色信息，改为白字蓝底的模式*/system("mode con: cols=140 lines=130"); /*设置运行时窗口大小 */MGraph G;int v0,i,e nd,j;int PMAX_VMAX_V;int DMAX_V;int choice,choice1;prin tf("ttttZ""s»z Z""s»z Z""s»

11、;z Z""s»z Z""s»z Z""s»z Z""s»z Z""s»z Z""s»z Z""s»z Z""S»Z Z""S»Z /III1prin tf("ntttt欢迎光临蚌埠学院，祝您旅程愉快！n");prin tf("ntttt蚌埠学院校园导游系统为你服务“ n");prin t

12、f("nttttCreateUDN(G);nn");while(1)menu();sca nf("%d",&choice); switch(choice) case 1: jia njie(); break;case 2: while(1) printf("分别输入起点和终点代号以空格分开n");sca nf("%d%d",&v0,&end);ShortPath(G,v0,P,D);printf(" 最短路径:n ");for(i=0;i<G.vex nu m;i+

13、)10 / 29键入文字if(Pe nd-1havei=1)prin tf("->%s",G.vexshavei);printf("n路径长度：dn",Dend-1);printf("A_A本次导航结束:n1.继续导航2.返回主菜单n");scan f("%d",&choice1);if(choice 1=2)break;else if(choice1<1|choice1>2)printf("你输入选项有误，请继续导航！! ！ n");break;case 3: pri

14、ntf("请输入出发点：");sca nf("%d",&v0);ShortPath (G,vO,P,D);prin tf("vO到其他所有点的最短路径为：n");for(i=O;i<G.vex nu m;i+)for(j=O;j<G.vex nu m;j+)if(Pihavej=1)prin tf("->%s",G.vexshavej);printf("n路径长度:%dn",Di);break;11 / 29键入文字case 4:show1();break;case 5

15、:break;default:prin tf("选择错误，请重新输入！n");if(choice=5)system("cls");prin tf("nnnnnn");prin tf(" ttti1n");prin tf(" ttt|感谢使用I n");prin tf(" ttt|蚌埠学院I n");prin tf(" ttt|智能导航系统I n");prin tf(" ttt11n");prin tf("nn");p

16、rintf(" tttwelcomto bengbu college,Good Bay!回车键退出。A_An");break;prin tf("nnnnnnnnnnnnnnnnnn");12 / 29键入文字5.3迪杰斯特拉算法实现void ShortPath(MGraph & G,i nt vO,i nt pMAX_VMAX_V,i nt d) /迪杰斯特拉发求最短路径int v,w,i,j,mi n;int fin alMAX_V;int k=1;for(v=0;v<G.vex nu m;+v)/初始化fin alv=0;dv=G.ar

17、csv0-1v;for(w=0;w<G.vex nu m;+w)pvw=0;if(dv<INFINITY)pvv0-1=1;pvv=1;dv0-1=0;fin alv0-1=1;have0=v0-1;for(i=1;i<G.vex nu m;+i)/其余的vex num-1个顶点min INFINITY;for(w=0;w<G.vex nu m;+w)if(!fi nalw)if(dw<min) /如有W点离更近13 / 29键入文字v=w;mi n=dw;fin alv=1;havek=v;k+;for(w=0;w<G.vex nu m;+w)更新当前最短

18、路径及距离if(!fi nalw &&(min+G.arcsvw<dw)dw=mi n+G.arcsvw;for(j=0;j<G.vex nu m;j+)pwj=pvj;pww=1;描述：迪杰斯特拉算法求最短路径。14 / 29键入文字6模块分析7系统测试7.1系统登录界面a D:ViiuaI+C+ +（支抒win? ） Microsoft Visual StudioCommoiniMSDevMBin>ebL*gff.e）fefc15 / 29键入文字7.3功能二：两点最短距离导航*D:V<sual+C+6r0) Miamoft Visual Stixi

19、ioComrw)rAM $Oev9S'jBiopebugff.exe,16 / 29键入文字7.4功能三：某点到其他所有点的最短距离7.5功能四：显示全校地图D:Vi!wal+C+6,0 （支持vwin? ） Mkrosoft Visiial StudioXCommoriVMSD&vSSBiriXDebijgW.exe817 / 29键入文字7.5退出导航系统D:Vis4jal+C+1&,0 （支持艸in? ） Mkrosoft VisuLal &tudioCommoriMSDev9S0inDebiiigff! exeB18 / 29键入文字8结论在本次课程设计

20、所做的校园导航系统中， 最关键的问题是最短路径问题，在 教材中有具体的算法一一迪杰斯特拉算法求最短路径问题。但是想一次性就把程 序调试出来是不可能的，我们组也是经过多次讨论才把程序完整的调试出来。通 过这次的课程设计，我们学到了很多知识，也认识到很多不足，那就是知识的不 足和经验的缺乏。但是我们相信自己可以在以后的学习中不断进步。附录：源代码：#include<stdio.h>#i nclude <stdlib.h>最大顶点个数最大值#i nclude <stri ng.h>#defi ne MAX_V 30/#defi ne INFINITY 32767

21、/typedef structchar* vexsMAX_V; /顶点向量int arcsMAX_VMAX_V;邻接矩阵in t vex num,arc nu m;图的当前顶点数和弧数MGraph;int CreateUDN(MGraph & G); /创建导航图函数声明extern have30;void ShortPath(MGraph & G,i nt vO,i nt pMAX_VMAX_V,i nt d);最短路径导航函数声明int have30;void menu(); /void show1(); / int jianjie();导航菜单函数声明显示全校面貌读取文件

22、19 / 29键入文字void mai n()/ system("color F2"); /*修改控制台的颜色信息，改为白字蓝底的模式*/ system("mode con: cols=140 lin es=130"); /*设置批处理运行时窗口大小的*/MGraph G;int v0,i,e nd,j;int PMAX_VMAX_V;int DMAX_V;int choice,choice1;prin tf("tttt/s»z /s»z /s»z /s»z /s»z /s»z /s&

23、#187;z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z/s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»zprin tf("nttttn");prin tf("ntt

24、ttn");n");欢迎光临蚌埠学院，祝您旅程愉快!蚌埠学院校园导游系统为你服务!prin tf("ntttt/s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»znn");/s»z /

25、s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»z /s»zCreateUDN(G);while(1)menu();sca nf("%d",&choice); switch(choice)case 1: jia njie();system("cls"); break;case 2: while(1)printf("分别输入起点和终点代号以空格分开n");scan f("%d%d&qu

26、ot;,&v0,&en d);20 / 29键入文字ShortPath(G,vO,P,D);printf("最短路径:n ");for(i=0;i<G.vex nu m;i+)if(Pe nd-1havei=1)prin tf("->%s",G.vexshavei);printf("n路径长度:%dn",Dend-1);n");printf("A_A本次导航结束:n1.继续导航2.返回主菜单scan f("%d",&choice1);if(choice 1=2

27、)system("cls");break;else if(choice1<1|choice1>2)printf("你输入选项有误，请继续导航！! ！ n");break;case 3: printf(" 请输入出发点：");sca nf("%d",&vO);ShortPath (G,vO,P,D);prin tf("vO到其他所有点的最短路径为：n");for(i=O;i<G.vex nu m;i+)for(j=O;j<G.vex nu m;j+)if(Pihav

28、ej=1)prin tf("->%s",G.vexshavej);21 / 29键入文字printf("n路径长度：dn",Di);system("pause");system("cls");break;case 4:system("cls");prin tf("nnnn");show1();system("cls");break;case 5:break;default:printf("选择错误，请重新输入！n"); if(ch

29、oice=5)system("cls");prin tf("nnnnnn");prin tf(" ttt感谢使用蚌埠学院1 n");prin tf(" tttI n");printf(" tttI n");22 / 29键入文字智能导航系welcom to BengBuprintf(" ttt统丨n");printf(" ttt 1n");prin tf("nn");printf("tttcollege,Good Bay!回车

30、键退出。A_An");break;prin tf("nnnnnnnnnnnnnnnnnn");/创建无向图int CreateUDN(MGraph &G)/采用数组(邻接矩阵)表示法,构造无向网G.int i = 0,j=0;G.vex num = 17; /图的定点数G.arc num = 51; /图的弧数G.vexs0=" 小池塘"G.vexs1="东门"；G.vexs2=" 西门"；G.vexs3=" 北门"；G.vexs4=" 东区宿舍楼"G.ve

31、xs5=" 西南宿舍楼"G.vexs6=" 北区田径场"G.vexs7=" 南区田径场"G.vexs8="一号食堂"G.vexs9="二号食堂"G.vexs10 = "A B C 教学楼"G.vexs11=" 重行楼"23 / 29键入文字G.vexs12=" 行政楼"G.vexs13=" 艺术楼"G.vexs14=" 图书馆"G.vexs15=" 超市"G.vexs16=&q

32、uot; 医务室"for(i=0;i<G.vex num;i+) /初始化路径长度for(j=0;j<G.vex nu m;j+)if(i=j)G.arcsij=0;elseG.arcsij=INFINITY; /初始化最大值 默认不邻接/为每一条边赋权 即路径长度 因为边是对称的G.arcs013 = G.arcs130 = 50;G.arcs07 =G.arcs70= 90;G.arcs14 = G.arcs41 =260 ;G.arcs47 = G.arcs74 =100;G.arcs57 = G.arcs75 =200;G.arcs414 = G.arcs144

33、=50;G.arcs614 = G.arcs146 =100;G.arcs714 = G.arcs147 =70;G.arcs714 =G.arcs147 =70;G.arcs410 = G.arcs104=100;G.arcs34 = G.arcs43 =200;G.arcs310 = G.arcs103 =100 ;G.arcs48 = G.arcs84 =60;G.arcs49 = G.arcs94 =50;G.arcs89 = G.arcs98 =150;G.arcs1014 = G.arcs1410 =100;G.arcs815 = G.arcs158 =70 ;24 / 29键入文

34、字G.arcs915=G.arcs159 =70;G.arcs416=G.arcs164=150;G.arcs916=G.arcs169 =50;G.arcs1112=G.arcs1211 =200;G.arcs1114=G.arcs1411 =220;G.arcs1213=G.arcs1312 =50;G.arcs1214=G.arcs1412 =70;G.arcs1316=G.arcs1613 =120;G.arcs214=G.arcs142 =100;return 1;void menu()prin tf("nnnn");prin tf("tttt学院各区名

35、称 n ”)；小池塘(2)东门prin tf("tttt(1)西门 n");prin tf("tttt(4)北门(5)东区宿舍楼西南宿舍楼 n");prin tf("tttt(7)北区田径场(8) 南区田径场(9)一号食堂 n");prin tf("tttt(10)二号食堂(11) A B C教学楼(12)重行楼 n");prin tf("tttt(13)行政楼(14)艺术楼(15)图书馆 n");prin tf("tttt(16)超市(17)医务室(18)没有了 n");p

36、rin tf("tttt nn");25 / 29键入文字请选择导航功能：n");prin tf("nn");prin tf("tttttttprin tf("tttttn");prin tf("ttttt(1)学校简介n");prin tf("ttttt(2)两点最短距离导航n");prin tf("ttttt(3)某点到其他所有点的最短距离n");prin tf("ttttt(4)显示全校地图n");prin tf("tt

37、ttt(5)退出导航系统n");prin tf("ttttt/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Z/S»Zn");prin tf("nnnn");/采用迪杰斯特拉算法，求最短路径void ShortPath(MGraph & G,i nt vO,i nt pMAX_VMAX_V,i nt d) /迪杰斯特拉发求最短路

38、径int v,w,i,j,mi n;int fin alMAX_V;int k=1;for(v=0;v<G.vex nu m;+v)/初始化fin alv=0;dv=G.arcsv0-1v;for(w=0;w<G.vex nu m;+w)pvw=0;if(dv<INFINITY)pvv0-1=1;pvv=1;26 / 29键入文字dvO-1=O;fin alvO-1=1;haveO=vO-1;for(i=1;i<G.vex nu m;+i)/其余的vex num-1个顶点min INFINITY;for(w=0;w<G.vex nu m;+w)if(!fi nalw)if(dw<min) / 如有W点离更近v=w;mi n=dw;fin alv=1;havek=v;k+;for(w=0;w<G.vex num;+w)更新当前最短路径及距离if(!fi nalw &&(min+G.arcsvw<dw)dw=mi n+G.arcsvw;for(j=O;j<G.vex nu m;j+)pwj=pvj;/凡是到v经过的顶点，到w也要经过pww=1;void show1()prin tf("