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

《数据结构课程设计校园导航系统课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计校园导航系统课程设计.doc（27页珍藏版）》请在三一办公上搜索。

1、课 程 设 计 课程名称数据结构题目名称校园导航系统专业班级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.

2、5退出导航系统128 结论12附录：131 引 言1.1 问题的提出 设计一个校园导航系统，为来访的客人提供各种信息查询服务。1.2国内外研究的现状 这个问题一直是国内外研究的热门话题。1.3任务与分析设计你的学校的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）2 程序的主要功能 （1）设计校园平面图，在校园景点选8个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查

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

4、 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

5、= 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) 北区田径场 (

6、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(tttt

7、t (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欢迎光临蚌埠学院，祝您旅程

8、愉快！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); print

9、f(_ 本次导航结束: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();

10、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迪杰斯特拉算法实现

11、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=I

12、NFINITY; 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

13、.5功能四：显示全校地图7.5退出导航系统8 结论在本次课程设计所做的校园导航系统中，最关键的问题是最短路径问题，在教材中有具体的算法迪杰斯特拉算法求最短路径问题。但是想一次性就把程序调试出来是不可能的，我们组也是经过多次讨论才把程序完整的调试出来。通过这次的课程设计，我们学到了很多知识，也认识到很多不足，那就是知识的不足和经验的缺乏。但是我们相信自己可以在以后的学习中不断进步。附录：源代码：#include#include #include #define MAX_V 30 /最大顶点个数 #define INFINITY 32767 /最大值 typedef struct char* ve

14、xsMAX_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);

15、/*修改控制台的颜色信息,改为白字蓝底的模式*/ 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);

16、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 i

17、f(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:

18、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(MGrap

19、h &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.ve

20、xs13 = 艺术楼; 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.

21、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

22、 = 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 =

23、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) 超

24、市 (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 ShortPa

25、th(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

26、(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

27、(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

28、(tttt 东门n); printf(tttt 9 n); printf(tttt . 体育馆 教职工寓 n); printf(tttt 12 n);printf(tttt n); system(pause);int jianjie(void)system(cls); FILE *fp; fp = fopen(E:in.txt , r); fseek( fp , 0 , SEEK_END ); int file_size; file_size = ftell( fp ); /printf( %d , file_size ); char *tmp; fseek( fp , 0 , SEEK_SET);/tmp = (char *)calloc( file_size,sizeof( char ) ); tmp = (char *)malloc( file_size * sizeof( char ) );memset(tmp, 0, file_size); fread(tmp,file_size,sizeof(char),fp); printf(%s ,tmp);system(pause);printf(nnnnnnnnnn