1、设计质量0.30设计合理、功能齐备，程序运行正常，实验数据准确 可靠；有较强的实际动手能力论文撰写质量设计说明书完全符合规范化要求，用 A4复印纸打印成文学习态度学习态度认真，科学作风严谨，严格按要求开展各项 工作，按期完成任务学术水平与创新0.10设计有创意，有一定的学术水平或实用价值总分评语：等级：指导教师： 年 月 日附件4分工协作说明（以列表形式具体说明每个人所做的工作）；课题名称学生姓名学号所做的工作校园导航系统张小蒙51302041036算法设计、程序调试、课程设计报 告撰写张浩51302041045算法设计、程序调试、课程设计报 告排版王威风51302041011柏祝林51302
2、033026算法设计、程序调试、资料查询鲍金林51302041041部分算法设计、程序调试张红伟51302041043部分算法设计、程序调试、资料查 询杨伟平513020410061.1问题的提出设计一个校园导航系统，为来访的客人提供各种信息查询服务。1.2国内外研究的现状这个问题一直是国内外研究的热门话题。1.3任务与分析设计你的学校的平面图，至少包括 8个以上的场所，每两个场所间可以 有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）2程序的主要功能（1） 设计校园平面图，在校园景点选 8个左右景点。以图中顶点表示校园 内各景点，存放景点名称、代号、简介等信息；
3、以边表示路径，存放路径长度等 有关信息。（2） 为来访客人提供图中任意景点相关信息的查询。（3） 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一 条最短路径。3程序运行平台计算机 wi ndows7 Virtual C+ 6.04总体设计4.1 数据结构类型定义#i nclude#include 最大顶点个数最大值#i nclude #defi ne MAX_V 30 /#define INFINITY 32767 /typedef structchar* vexsMAX_V; / 顶点向量int arcsMAX_VMAX_V; 邻接矩阵in t vex nu m,arcnum;
4、 图的当前顶点数和弧数MGraph;4.2函数声明int CreateUDN（MGraph & G）; / 创建导航图函数声明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（）; 读取文件4.3创建导航图，即无向图G）函数描述：主要将每个节点进行命名，每个定点到其他所有定点的路径值用 邻接矩阵进行存储。例如：G.vexsO= 小池塘;G.ve
5、xs1=东门；作用：使0号定点命名为“小池塘”，1号节点命名为“东门”。G.arcs14 = G.arcs41 =260 ;使1号定点到4号定点的路径赋值为260,同时4号定点到1号定点 的路径长度也为260.4.4最短路径导航函数 G,i nt v0,i nt pMAX_VMAX_V,i nt d）用迪杰斯特拉算法求最短路径。5程序方法的说明5.1主菜单void menu（）prin tf（tttt 学院各区名称 n）;（1）小池塘（2）东门西门 n（4）北门（5）东区宿舍楼西南宿舍楼 n（7）北区田径场（8）南区田径场（9）一号食堂 n（10）二号食堂（11） A B C教学楼（12）重行
6、楼 n（13）行政楼（14）艺术楼（15）图书馆 n（16）超市（17）医务室（18）没有了 nttttttt请选择导航功能：ntttttz/SZ /S_z:-（1）学校简介 n-两点最短距离导航-某点到其他所有点的最短距离-显示全校地图-退出导航系统*SZ描述：程序主菜单显示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;
7、int choice,choice1;Zsz ZSZ ZZ /III 1ntttt欢迎光临蚌埠学院，祝您旅程愉快！n蚌埠学院校园导游系统为你服务 “ nCreateUDN（G）; nnwhile（1）menu（）;sca nf（%d,&choice）; switch（choice） case 1: jia njie（）; break;case 2: while（1） printf（分别输入起点和终点代号以空格分开n%d%dv0,&end）;ShortPath（G,v0,P,D）; 最短路径:n for（i=0;i%s,G.vexshavei）;n 路径长度：dn,Dend-1）;A_A 本次导
8、航结束:n1.继续导航2.返回主菜单nscan f（choice1）;if（choice 1=2）break;else if（choice12） 你输入选项有误，请继续导航！ ! ！ ncase 3: 请输入出发点：v0）;ShortPath （G,vO,P,D）;vO 到其他所有点的最短路径为：for（i=O;for（j=O;jj+）if（Pihavej=1）,G.vexshavej）;n 路径长度:%dn,Di）;case 4:show1（）;case 5:default: 选择错误，请重新输入！if（choice=5）clsnnnnnn ttt i 1 n ttt |感谢使用I n蚌埠学
9、院智能导航系统 ttt 1nn tttwelcom to bengbu college,Good Bay!回车键退出。A_Annnnnnnnnnnnnnnnnnn5.3迪杰斯特拉算法实现 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+v）/初始化fin alv=0;dv=G.arcsv0-1v;for（w=0;w+w）pvw=0;if（dvINFINITY）pvv0-1=1;pvv=1;dv0-1=0;fin alv0-1=1;have0=v0-
10、1;for（i=1;+i）/其余的vex num-1个顶点min INFINITY;if（!fi nalw）if（dwmin） / 如有W点离更近v=w;mi n=dw;fin alv=1;havek=v;k+;+w） 更新当前最短路径及距离fi nalw &（min+G.arcsvwebL*gff.e）fefc*D:Vsual+C+6r0 ） Miamoft Visual StixiioComrw）rAM $Oev9SjBiopebugff.exe,某点到其他所有点的最短距离D:Vi!wal+C+6,0 （支持vwin? ） Mkrosoft Visiial StudioXCommoriVM
11、SD&vSSBiriXDebijgW.exe87.5退出导航系统D:Vis4jal+C+1&,0 （支持艸in? ） Mkrosoft VisuLal &tudioCommoriMSDev9S0inDebiiigff! exeB8结论在本次课程设计所做的校园导航系统中， 最关键的问题是最短路径问题，在 教材中有具体的算法一一迪杰斯特拉算法求最短路径问题。但是想一次性就把程 序调试出来是不可能的，我们组也是经过多次讨论才把程序完整的调试出来。通 过这次的课程设计，我们学到了很多知识，也认识到很多不足，那就是知识的不 足和经验的缺乏。但是我们相信自己可以在以后的学习中不断进步。附录：源代码：#in
12、clude#defi ne INFINITY 32767 /in t vex num,arc nu m; 最/sz /s switch（choice）case 1:while（1）en d）;ShortPath（G,vO,P,D）;最短路径:n1.继续导航2.返回主菜单if（choice 1=2）vO）;pausennnn if（choice=5） ttt统 丨n ttt 1 ncollege,Good Bay! 回车键退出。/创建无向图/采用数组（邻接矩阵）表示法,构造无向网G.int i = 0,j=0;G.vex num = 17; / 图的定点数G.arc num = 51; / 图的
13、弧数G.vexs0=G.vexs2= 西门G.vexs3= 北门G.vexs4= 东区宿舍楼G.vexs5= 西南宿舍楼G.vexs6= 北区田径场G.vexs7= 南区田径场G.vexs8= 一号食堂G.vexs9= 二号食堂G.vexs10 = A B C 教学楼G.vexs11= 重行楼G.vexs12= 行政楼G.vexs13= 艺术楼G.vexs14= 图书馆G.vexs15= 超市G.vexs16= 医务室G.vex num;i+） / 初始化路径长度if（i=j）G.arcsij=0;elseG.arcsij=INFINITY; / 初始化最大值 默认不邻接/为每一条边赋权 即路
14、径长度 因为边是对称的G.arcs013 = G.arcs130 = 50;G.arcs07 =G.arcs70= 90;G.arcs47 = G.arcs74 =100;G.arcs57 = G.arcs75 =200;G.arcs414 = G.arcs144 =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.arcs
15、48 = G.arcs84 =60;G.arcs49 = G.arcs94 =50;G.arcs89 = G.arcs98 =150;G.arcs1014 = G.arcs1410 =100;G.arcs815 = G.arcs158 =70 ;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;nn
