数据结构课程设计-校园导航系统课程设计.doc

键入文字课 程 设 计 课程名称数据结构题目名称校园导航系统专业班级13软件工程学生姓名学 号指导教师 二一五年六月一日目录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附录：131 引 言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(ttt