本科毕业论文---校园导航系统设计.doc

课 程 设 计 课程名称数据结构题目名称校园导航系统专业班级 学生姓名 二一五年六月一日目录1 引 言41.1 问题的提出41.2国内外研究的现状51.3任务与分析52 程序的主要功能53 程序运行平台54 总体设计54.1数据结构类型定义54.2函数声明54.3创建导航图，即无向图54.4最短路径导航函数55 程序方法的说明55.1主菜单65.2主函数65.3迪杰斯特拉算法实现96 模块分析107 系统测试107.1系统登录界面107.2功能一：学校简介107.3功能二：两点最短距离导航107.4功能三：某点到其他所有点的最短距离117.5功能四：显示全校地图117.5退出导航系统128 结论12附录：13蚌埠学院计算机科学与技术系本科课程设计成绩评定表项目权重分值具体要求得分文献阅读与调查论证0.20100能独立查阅文献和从事其它调研；有收集、加工各种信息的能力设计质量0.30100设计合理、功能齐备，程序运行正常，实验数据准确可靠；有较强的实际动手能力论文撰写质量0.20100设计说明书完全符合规范化要求，用A4复印纸打印成文学习态度0.20100学习态度认真，科学作风严谨，严格按要求开展各项工作，按期完成任务学术水平与创新0.10100设计有创意，有一定的学术水平或实用价值总分评语：等级： 指导教师： 年 月 日 附件4 分工协作说明（以列表形式具体说明每个人所做的工作）；课题名称学生姓名学号所做的工作校园导航系统张小蒙51302041036算法设计、程序调试、课程设计报告撰写张 浩51302041045算法设计、程序调试、课程设计报告排版王威风51302041011算法设计、程序调试、课程设计报告撰写柏祝林51302033026算法设计、程序调试、资料查询鲍金林51302041041部分算法设计、程序调试张红伟51302041043部分算法设计、程序调试、资料查询杨伟平51302041006部分算法设计、程序调试1 引 言1.1 问题的提出 设计一个校园导航系统，为来访的客人提供各种信息查询服务。1.2国内外研究的现状 这个问题一直是国内外研究的热门话题。1.3任务与分析设计你的学校的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）2 程序的主要功能 （1）设计校园平面图，在校园景点选8个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。3 程序运行平台 计算机 windows7 Virtual c+ 6.04 总体设计 4.1数据结构类型定义#include#include #include #define MAX_V 30 /最大顶点个数 #define INFINITY 32767 /最大值 typedef struct char* vexsMAX_V; /顶点向量 int arcsMAX_VMAX_V;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧数 MGraph;4.2函数声明int CreateUDN(MGraph &G); /创建导航图函数声明 extern have30;void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d);/最短路径导航函数声明int have30; void menu(); /导航菜单函数声明void show1(); /显示全校面貌int jianjie();/读取文件4.3创建导航图，即无向图int CreateUDN(MGraph &G) 函数描述：主要将每个节点进行命名，每个定点到其他所有定点的路径值用邻接矩阵进行存储。例如： G.vexs0 = 小池塘; G.vexs1 = 东门; 作用：使0号定点命名为“小池塘”，1号节点命名为“东门”。 G.arcs14 = G.arcs41 =260 ;作用：使1号定点到4号定点的路径赋值为260，同时4号定点到1号定点的路径长度也为260.4.4最短路径导航函数void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d)函数描述：用迪杰斯特拉算法求最短路径。5 程序方法的说明5.1主菜单void menu() printf(tttt 学院各区名称 n); printf(tttt (1) 小池塘 (2) 东门 (3) 西门 n); printf(tttt (4) 北门 (5) 东区宿舍楼 (6) 西南宿舍楼 n); printf(tttt (7) 北区田径场 (8) 南区田径场 (9) 一号食堂 n); printf(tttt (10) 二号食堂 (11) A B C教学楼 (12) 重行楼 n); printf(tttt (13) 行政楼 (14) 艺术楼 (15) 图书馆 n); printf(tttt (16) 超市 (17) 医务室 (18) 没有了 n); printf(ttttttt请选择导航功能：n); printf(tttttn); printf(ttttt (1) 学校简介 n); printf(ttttt (2) 两点最短距离导航 n); printf(ttttt (3) 某点到其他所有点的最短距离 n); printf(ttttt (4) 显示全校地图 n); printf(ttttt (5) 退出导航系统 n); printf(tttttn); 描述：程序主菜单显示。5.2主函数void main() /system(color 09); /*修改控制台的颜色信息,改为白字蓝底的模式*/ system(mode con: cols=140 lines=130); /*设置运行时窗口大小*/ MGraph G;int v0,i,end,j; int PMAX_VMAX_V; int DMAX_V;int choice,choice1; printf(tttt n); printf(ntttt欢迎光临蚌埠学院，祝您旅程愉快！n); printf(ntttt蚌埠学院校园导游系统为你服务 n); printf(nttttnn);CreateUDN(G); while(1)menu();scanf(%d,&choice);switch(choice)case 1: jianjie();break;case 2: while(1) printf(分别输入起点和终点代号以空格分开n); scanf(%d%d,&v0,&end); ShortPath(G,v0,P,D); printf(最短路径:n ); for(i=0;i%s,G.vexshavei); printf(n路径长度:%dn,Dend-1); printf(_ 本次导航结束:n1.继续导航 2.返回主菜单n); scanf(%d,&choice1); if(choice1=2) break; else if(choice12)printf(你输入选项有误，请继续导航！n); break; case 3: printf(请输入出发点：); scanf(%d,&v0); ShortPath (G,v0,P,D); printf(v0到其他所有点的最短路径为：n); for(i=0;iG.vexnum;i+) for(j=0;j%s,G.vexshavej); printf(n路径长度:%dn,Di); break;case 4: show1();break;case 5: break;default: printf(选择错误，请重新输入！n); if(choice=5) system(cls);printf(nnnnnn);printf( ttt n); printf( ttt 感谢使用 n); printf( ttt 蚌埠学院 n); printf( ttt 智能导航系统 n); printf( ttt n);printf(nn);printf( tttwelcom to bengbu college,Good Bay!回车键退出。_n); break; printf(nnnnnnnnnnnnnnnnnn);5.3迪杰斯特拉算法实现void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d) /迪杰斯特拉发求最短路径 int v,w,i,j,min; int finalMAX_V; int k=1; for(v=0;vG.vexnum;+v)/初始化 finalv=0; dv=G.arcsv0-1v; for(w=0;wG.vexnum;+w) pvw=0; if(dvINFINITY) pvv0-1=1; pvv=1; dv0-1=0; finalv0-1=1; have0=v0-1; for(i=1;iG.vexnum;+i) /其余的vexnum-1个顶点 min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw) if(dwmin) /如有W点离更近 v=w; min=dw; finalv=1; havek=v; k+; for(w=0;wG.vexnum;+w)/更新当前最短路径及距离 if(!finalw&(min+G.arcsvwdw) dw=min+G.arcsvw; for(j=0;jG.vexnum;j+) pwj=pvj; pww=1; 描述：迪杰斯特拉算法求最短路径。6 模块分析。7 系统测试7.1系统登录界面7.2功能一：学校简介7.3功能二：两点最短距离导航7.4功能三：某点到其他所有点的最短距离7.5功能四：显示全校地图7.5退出导航系统8 结论在本次课程设计所做的校园导航系统中，最关键的问题是最短路径问题，在教材中有具体的算法迪杰斯特拉算法求最短路径问题。但是想一次性就把程序调试出来是不可能的，我们组也是经过多次讨论才把程序完整的调试出来。通过这次的课程设计，我们学到了很多知识，也认识到很多不足，那就是知识的不足和经验的缺乏。但是我们相信自己可以在以后的学习中不断进步。附录：源代码：#include#include #include #define MAX_V 30 /最大顶点个数 #define INFINITY 32767 /最大值 typedef struct char* vexsMAX_V; /顶点向量 int arcsMAX_VMAX_V;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧数 MGraph; int CreateUDN(MGraph &G); /创建导航图函数声明 extern have30;void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d);/最短路径导航函数声明int have30; void menu(); /导航菜单函数声明void show1(); /显示全校面貌int jianjie();/读取文件void main() /system(color F2); /*修改控制台的颜色信息,改为白字蓝底的模式*/ system(mode con: cols=140 lines=130); /*设置批处理运行时窗口大小的*/ MGraph G;int v0,i,end,j; int PMAX_VMAX_V; int DMAX_V;int choice,choice1; printf(tttt n); printf(ntttt 欢迎光临蚌埠学院，祝您旅程愉快！ n); printf(ntttt 蚌埠学院校园导游系统为你服务！ n); printf(nttttnn);CreateUDN(G); while(1)menu();scanf(%d,&choice);switch(choice)case 1: jianjie();system(cls);break; case 2: while(1) printf(分别输入起点和终点代号以空格分开n); scanf(%d%d,&v0,&end); ShortPath(G,v0,P,D); printf(最短路径:n ); for(i=0;i%s,G.vexshavei); printf(n路径长度:%dn,Dend-1); printf(_ 本次导航结束:n1.继续导航 2.返回主菜单n); scanf(%d,&choice1); if(choice1=2)system(cls);break; else if(choice12)printf(你输入选项有误，请继续导航！n); break; case 3: printf(请输入出发点：); scanf(%d,&v0); ShortPath (G,v0,P,D); printf(v0到其他所有点的最短路径为：n); for(i=0;iG.vexnum;i+) for(j=0;j%s,G.vexshavej); printf(n路径长度:%dn,Di); system(pause); system(cls);break; case 4:system(cls);printf(nnnn);show1();system(cls);break;case 5:break;default: printf(选择错误，请重新输入！n); if(choice=5) system(cls);printf(nnnnnn);printf( ttt n); printf( ttt 感谢使用 n); printf( ttt 蚌埠学院 n); printf( ttt 智能导航系统 n); printf( ttt n);printf(nn);printf( ttt welcom to BengBu college,Good Bay!回车键退出。_n); break; printf(nnnnnnnnnnnnnnnnnn);/创建无向图int CreateUDN(MGraph &G) /采用数组(邻接矩阵)表示法,构造无向网G. int i = 0,j=0; G.vexnum = 17; /图的定点数 G.arcnum = 51; /图的弧数 G.vexs0 = 小池塘; G.vexs1 = 东门; 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 = 医务室; for(i=0;iG.vexnum;i+) /初始化路径长度 for(j=0;jG.vexnum;j+) if(i=j) G.arcsij=0; else G.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 =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 ; 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() printf(nnnn); printf(tttt 学院各区名称 n); printf(tttt (1) 小池塘 (2) 东门 (3) 西门 n); printf(tttt (4) 北门 (5) 东区宿舍楼 (6) 西南宿舍楼 n); printf(tttt (7) 北区田径场 (8) 南区田径场 (9) 一号食堂 n); printf(tttt (10) 二号食堂 (11) A B C教学楼 (12) 重行楼 n); printf(tttt (13) 行政楼 (14) 艺术楼 (15) 图书馆 n); printf(tttt (16) 超市 (17) 医务室 (18) 没有了 n); printf(tttt nn); printf(nn); printf(ttttttt请选择导航功能：n); printf(tttttn); printf(ttttt (1) 学校简介 n); printf(ttttt (2) 两点最短距离导航 n); printf(ttttt (3) 某点到其他所有点的最短距离 n); printf(ttttt (4) 显示全校地图 n); printf(ttttt (5) 退出导航系统 n); printf(tttttn); printf(nnnn); /采用迪杰斯特拉算法，求最短路径void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d) /迪杰斯特拉发求最短路径 int v,w,i,j,min; int finalMAX_V; int k=1; for(v=0;vG.vexnum;+v)/初始化 finalv=0; dv=G.arcsv0-1v; for(w=0;wG.vexnum;+w) pvw=0; if(dvINFINITY) pvv0-1=1; pvv=1; dv0-1=0; finalv0-1=1; have0=v0-1; for(i=1;iG.vexnum;+i) /其余的vexnum-1个顶点 min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw) if(dwmin) /如有W点离更近 v=w; min=dw; finalv=1; havek=v; k+; for(w=0;wG.vexnum;+w)/更新当前最短路径及距离 if(!finalw&(min+G.arcsvwdw) dw=min+G.arcsvw; for(j=0;jG.vexnum;j+) pwj=pvj; /凡是到v经过的顶点，到w也要经过 pww=1; void show1()printf(tttttt 欢迎使用蚌埠学院智能导航系统 n); printf(ttttttt蚌埠学院校区平面图nn); printf(tttt 学校北门n); printf(tttt n); printf(tttt 北门北操场n); printf(tttt 重行楼 n); printf(tttt n); printf(tttt A B C教学楼 n); printf(tttt n); printf(tttt 宿舍楼1 n); printf(tttt 图书馆 . n); printf(tttt . n); printf(tttt 行政楼 . n); printf(tttt 西门 小池塘 . n); printf(tttt 艺术楼 . n); printf(tttt . n); printf(tttt 8 n); printf(tttt