校园导航系统课程设计

1、键入文字 课程设计 课程名称数据结构校园导 题目名称航系统13软件工 专业班级 二O五年六月一日 1 / 29 键入文字 目录 1弓丨言 5 1.1问题的提出5 1.2国内外研究的现状5 1.3任务与分析5 2程序的主要功能6 3程序运行平台6 4总体设计7 4. 1数据结构类型定义7 4.2函数声明7 4.3创建导航图，即无向图8 4.4最短路径导航函数8 5程序方法的说明9 5. 1主菜单9 5.2主函数10 5. 3迪杰斯特拉算法实现13 6模块分析15 7系统测试15 7.1系统登录界面15 7.2功能一：学校简介16 7. 3功能二：两点最短距离导航 16 7.4功能三：某点到其他所

2、有点的最短距离17 7.5功能四：显示全校地图17 7. 5退出导航系统18 8结论19 附录：19 2/29 键入文字 蚌埠学院计算机科学与技术系本科课程设计成绩评定表 项目 权重 分值 具体要求 得分 文献阅读与 调查论证 0. 20 100 能独立杳阅文献和从事其它调研；有收集、加工各种 信息的能力 设计质量 0. 30 100 设计合理、功能齐备，程序运行正常，实验数据准 确可靠；有较强的实际动手能力 论文撰写质量 0. 20 100 设计说明书完全符合规范化要求，用A4复印纸打印 成文 学习态度 0. 20 100 学习态度认真，科学作风严谨，严格按要求开展各项 工作，按期完成任务

3、学术水平与 创新 0. 10 100 设计有创意，有一定的学术水平或实用价值 总分 评语： 等级：指导教师： 年月日 3/29 键入文字 附件4分工协作说明（以列表形式具体说明每个人所做的工作）； 课题名称 学生姓名 学号 所做的工作 校园导航系 统 张小蒙 51302041036 算法设计、程序调试、课程设 计报 告撰写 张浩 51302041045 算法设计、程序调试、课程设 计报 告排版 王威风 51302041011 算法设计、程序调试、课程设 计报 告撰写 柏祝林 51302033026 算法设计、程序调试、资料查 询 鲍金林 51302041041 部分算法设计、程序调试 张红伟

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

5、路径，存放路径长度等 有关信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供任意景点的问路查询，即查询任意两个景 点之间的一条最短路径。 3程序运行平台 计算机 windows7 Vi rtua I c+ 6. 0 6/29 键入文字 4总体设计 4.1数据结构类型定义 #include #include 最大顶点个 数 #inelude string.h #define MAX_V 30 / #define INFINITY 32767 / typedef struet char* vexsMAX_V; / 顶点向量 int arcsMAX_V MAX_V ;/

6、邻接矩阵 int vexnum, arenum;/图的当前顶点数和弧数MGraph; 4.2函数声明 int CreateUDN(MGraph / 创建导航图函数声明 extern have 30; void ShortPath (MGraph / 短 路径导航函数声明 i nt have 30; void menu() ; /导航菜单函数声明 void showl () ; /显示全校面貌int j ianj ie() ;/读取文件 4. 3创建导航图，即无向图 7/29 键入文字 int CreateUDN(MGraph 作用：使1号定点到4号定点的路径赋值为260,同时4号定点 到1号定

7、点的路径长度也为260. 4.4最短路径导航函数 void ShortPath (MGraph pr intf (tttt (13) 行政楼 (14)艺术楼 (15 图书馆 n”)； printf(Htttt (16) 超市 (1刀医务室 (18 + + printf(Htttt 厶K 1/ f nH); pr intf (tttt 4. / 学校简介 pr intf (tttt 两点最短距离导航 pr intf (tttt 某点到其他所有点短距 n”)； pr intf (tttt t r 、盒示全校地 pr intf (tttt + f A /r- 4 1 退出导航系 /.亠 n”); p

8、rintf(Htttt nH); 没有了 nM); printf(Htttt 描述：程序主菜单显示 5.2主函数 9/29 键入文字 void main() /system (co I or 09); /*修改控制台的颜色信息，改为白字蓝底 的模式*/ system (mode con: col s=140 lines 二 130); /* 设置运行时窗口大小 */ MGraph G; int vO, i, end, j ; int PMAX_VMAX_V; int DMAX_V; int choice,choicel; pr intf (tttt 欢迎光临蚌埠学院，祝您旅程愉快！ 蚌埠学院校

9、园导游系统为你服务 nnH); pr intf (nttt pr intf (nttt + pr intf (ntttt CreateUDN (G); wh i le(1) menu(); seanf (%d， switch (choice) case 1: j ianj ie(); break; case 2: whi le(1) printfC分别输入起点和终点代号以空格分开n”)； scanf (%d%d, ShortPath(G, vO, P, D) ; pr intf (最短路径:n ”)； for (i =0;i %s, G. vexshave i); pr intf Cn 路径长

10、度:%dn, Dend-1); printfCT本次导航结束：n1.继续导航2.返回主菜单 10 / 键入文字 nH); scanf (%dHr if (choice1=2) break; eIse i f (cho i cel2) pr intf(你输入选项有误，请继续导航！ ！ n”)；， break; case 3: printf (请输入出发点：);scanf (%d, ShortPath (G,vO,P,D); printfCvO到其他所有点的最短路径为:n”); for (i=0;iG. vexnum;i+) for (j=0; j%s, G. vexshavej); printf

11、 Cn 路径长度:%dn, Di); break; case 4: showl (); break; case 5: break; default: pr intf (选择错误，请重新输入！ n); 1 if (choice二二5)，system (cls); printf (nnnnnn); Pr intf( ttt | printfC1 ttt|感谢使用|n”)； printfC ttt|蚌埠学卩元| n); printfC ttt|智能导航系统| n); printf(” ttt 11 11 / 键入文字 printf (nnnM); pr intf (H tttwelcom to be

12、ngbu col lege, Good Bay! ! 回车键退出。 Tn”)； break; 1 pr i ntf(nnnnnnnnnnnnnnnnnn); 5. 3迪杰斯特拉算法实现 void ShortPath(MGraph int finalMAX_V; i nt k=1; for (v=0;vG. vexnum;+v) /初始化 finalv二0; dv=G. arcsv0-1 v; for (w=0;wG. vexnum;+w) P v w =0; if (dvINFINITY) pv v0-1=1; pv v=1; 1 dv0-1=0; finalv0-1=1; have0二vO-

13、1; for(i=1;iG. vexnum;+i) 12 / 键入文字 /其余的vexnum-1个顶点 min二INFINITY; for (w二0;wG. vexnum;+w) if(!fi naIw) if (dwmin) /如有W点离更近 v二w; min二dw; 1 finalv=1; havek二v; k+; for (w=0;wG. vexnum;+w) /更新当前最短路径及距离 if (!f inaI w for (j=0;jG. vexnum;j+) pwj=pvj; pw w二 1 ; 1 描述：迪杰斯特拉算法求最短路径。 13 / 键入文字 6模块分析 7系统测试 7. 1

14、系统登录界面 14 / 键入文字 7.2功能一：学校简介 7.3功能二：两点最短距 离导航 15 / 键入文字 7.4功能三：某点到其他所有点的 最短距离 7.5功能四：显示全校 地图 16 / 键入文字 7.5退出导航 系统 17 / 键入文字 8结论 在本次课程设计所做的校园导航系统中，最关键的问题是最短路 径问题，在 教材中有具体的算法一一迪杰斯特拉算法求最短路径问 题。但是想一次性就把程序调试出来是不可能的，我们组也是经过 多次讨论才把程序完整的调试出来。通过这次的课程设计，我们学 到了很多知识，也认识到很多不足，那就是知识的不足和经验的缺 乏。但是我们相信自己可以在以后的学习中不断进

15、步。 附录： 源彳弋召马：#i ncIude #i ncIude #i ncIude #define MAX_V 30 / #define INFINITY 32767 / 最大顶点个 typedef struct数 char* vexsMAX_V; / 顶点向量 int arcsMAX_V MAX.V;/ 邻接矩阵 int vexnum, arcnum;/图的当前顶点数和弧数MGraph; int CreateUDN(MGraph /创建导航图函数声明 extern have 30; void ShortPath (MGraph /最 短路径导航函数 声明int have 30;导航菜单函数

16、 void menu():尸明显ZF全校 / void面貌读取文件 18 / 键入文字 void main() / system (co I or F2”)； /*修改控制台的颜色信息，改为白字蓝底 的模式 */ system (mode con: col s=140 I ines=130) ; /* 设置批处 理运行时窗口 大小的*/ MGraph G; int vO, i,end,j; int PMAX_VMAX_V; int DMAX_V; int choice,choicel; pr intf (tttt n”)； pr intf (n= tttt w n); printf (Mn +

17、 CreateUDN (G); wh i le(1) menu (); scanf 欢迎光临蚌埠学院，祝您旅程愉快 蚌埠学院校园导游系统为你服务 printf (ntttt nn”)； switch (choice) case 1 : j i a njie(); system(cls); break; case 2: wh i le(1) printfC分别输入起点和终点代号以空格分开n”); scanf C%d%dMr 19 / 键入文字 ShortPath (G. vOr Pr D); pr intf (最短路径:n ”)； for(i=0;i%s, G. vexshavei); pr i

18、ntf (Hn 路径长度:%dn, Dend-1); ”）； printfCV本次导航结束：n1.继续导航2.返回 主菜单 scant (%d if (choice1=2) systemCcIs) ; break; eIse i f(choi cel2) printfC你输入选项有误，请继续导航！ ！ ！ nH); break; case 3: printf (请输入出发点：”)； scanf (%d, ShortPath (G, vO, P. D); pr intf CvO到其他所有点的最短路径为：n); for(i=0;iG vexnum;i+) for (j=0;j%sMrG. vexs

19、havej); 20 键入文字 pr intf (Mn 路径长度:%dnn, Di); 、system(”pause); system(cls); break; case 4: systemCcIs”)； pr intf (nnnn) ; showl (); system(”cls) ; break; case 5: break; default: printf (H选择错误，请重新输入！nH) ; i f (cho i ce=5) system(cls); pr intf (nnnnnn); pr intf ( ttt 1n”)； 感谢使 用 pr intf ( ttt n); pr int

20、f ( ttt n); 21 / 键入文字 printf ( ttt 统 I n); printf(H ttt| 1n); pr intf (nn); printf( ttt we I com col lege. Good Bay!回车键退出。nM); break; pr i ntf (nnnnnnnnnnnnnnnnnrT); 智能导航系 to BengBu /创建无向图 i nt CreateUDN(MGraph G.vexnum = 17; / G.arcnum = 51; / 图的定点数 图的弧数 G. vexs0二 G. vexs1二 G. vexs2二 G. vexs3= G. v

21、exs4二 G. vexs5二 G. vexs6二 G. vexs7= G. vexs8二 G. vexs9二 小池塘”； 东门”； 西门”； 北门”； 东区宿舍楼” 西南宿舍楼” 北区田径场” 南区田径场” 一号食堂”； 二号食堂”； G. vexs10二 “A B C 教学楼 G. vexs11=重行楼 22 / 键入文字 G. vexs12二 H G. vexs13二 H G. vexs14= G. vexs15二 H G. vexs16二 行政楼”; 艺术楼”; 图书馆“； 超市“； 医务室 for (i =0; i G. vexnum; i +) / 初始化路径长度 for (j=0

22、;jG vexnum;j+) if (i=j) G. arcsi j=0; G.arcsij二INFINITY; /初始化最大值默认不邻接 /为每一条边赋权即路径长度因为边是对称的 G. arcs013 = G. arcs13 0 = 50; G. arcs0 7二G.arcs刀0二 90; G. arcs1 4 = G. arcs4 1 G. arcs4 7 = G. arcs 7 4 =100; G. arcs5 7 = G. arcs7 5 二200; G. arcs4 14 =G. arcs14 4 =50; G. arcs6 14 =G. arcs 14 6 =100; G. arc

23、s7 14 =G. arcs14 7 =70; G. arcs7 14 =G.arcs14 7 =70; G. arcs410 二 G. arcs10 4=100; G. arcs3 4 = G. arcs4 3二200; G. arcs310 = G. arcs10 3 =100 ; G. arcs4 8二 G. arcs 8 4 =60; G. arcs4 9 = G. arcs9 4 =50; G. arcs8 9 = G. arcs 9 8 =150; G.arcs10 14 = G. arcs14 10 =100; G. arcs815 = G. arcs15 8 =70 ; 23

24、/ 键入文字 G. arcs915G.arcs15 9 =70 豊res叫 arcs164 = 50 豊res 9 16 g,心16 9 =50 G. arcs11 1 = G. arcs12 11 Grcs11 1 G.arcs14 11 G. arcs12 1 O1 G. arcs 12 1 G. arcs131 学院各区名称 G. arcs 13 12 UC G. arcs 14 12 re . G. arcs 16 13 IA rf 辛.arcs2叫，14 2 =100; return 1; void menu() pr intf (nnnn,); printf (Htttt pr i

25、ntf(ntttt (1) 小池塘 (2) 东门 (3) 西门 八 pr intf (tttt 北门 （5）东区宿舍楼 (6) 西南宿舍楼 pr i ntf (tttt (7) 北区田径场 （8）南区田径场 (9) 一号食堂 printf(tttt (10) 二号食堂 (11) ABC 教学 (12) 重行楼 pr intf (tttt (13) 行政楼 (14) 艺术楼 (15) 图书馆 八 pr i ntf (tttt (16) 超市 （ 医务室 (18) 没有了 八 pr i ntf (tttt nnH); 键入文字 pr i ntf (nrT pkntf (”ttt printf(nt

26、tt printfCAtWX printf(ttt printf(ttt printf(ttt printf(ttt 请选择导航功能: n”)； (1) 学校简介 (2) 两点最短距离导航 (3) 某点到其他所有点的最短距 (4) 显7F全彳父地图 (5) 退出导航系统 nH); pr i ntf (nnn n”)； /采用迪杰斯特拉算法，求最短路径 void ShortPath (MGraph int finalMAX_V; i nt k=1; for(v=0;vG. vexnum;+v) /初始化 finalv=0; dv=G. arcsv0-1 v; for (w=0;wG vexnum

27、;+w) pv w=0; if (dvINFINITY) pv v0-1=1 ; pv v=1; dv0-1=0; finalv0-1=1; have0=v0-1; for (i=1;iG vexnum;+i) /其余的vexnum-1个顶点 m i n二I NF INITY; for (w=0;wG. vexnum;+w) if (!finalw) i f (d w mi n) /如有W点离更近 25 / 键入文字 v=w; min二dw; 1 finalv=1; havek=v; k+; for (w二O;wG. vexnum;+w)/更新当前最短路径及距离 if (!final w for (j=0;jG. vexnum;j+) pw j=pv j； /凡是到V经过的顶点，到W也要经 过 pw w二 1; 1 1 void showl () pr intf (tttttt 欢迎使用蚌埠学院智能导航系统 26 键入文字 pr intf (tt蚌埠学院校区平面图 tttttnn”)； printf(tttt学校北门 n”)； pr intf (tttt| 十). pr intf (tttt | 寸匕门 北操场n”)； printf(nt