数据结构课程设计校园导航系统课程设计.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<stdio.h>#include <stdlib.h> #include <string.h> #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<G.vexnum;i+) if(Pend-1havei=1) printf("->%s",G.vexshavei); printf("n路径长度:%dn",Dend-1); printf("_ 本次导航结束:n1.继续导航 2.返回主菜单n"); scanf("%d",&choice1); if(choice1=2) break; else if(choice1<1|choice1>2)printf("你输入选项有误，请继续导航！n"); break; case 3: printf("请输入出发点："); scanf("%d",&v0); ShortPath (G,v0,P,D); printf("v0到其他所有点的最短路径为：n"); for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) if(Pihavej=1) printf("->%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;v<G.vexnum;+v)/初始化 finalv=0; dv=G.arcsv0-1v; for(w=0;w<G.vexnum;+w) pvw=0; if(dv<INFINITY) pvv0-1=1; pvv=1; dv0-1=0; finalv0-1=1; have0=v0-1; for(i=1;i<G.vexnum;+i) /其余的vexnum-1个顶点 min=INFINITY; for(w=0;w<G.vexnum;+w) if(!finalw) if(dw<min) /如有W点离更近 v=w; min=dw; finalv=1; havek=v; k+; for(w=0;w<G.vexnum;+w)/更新当前最短路径及距离 if(!finalw&&(min+G.arcsvw<dw) dw=min+G.arcsvw; for(j=0;j<G.vexnum;j+) pwj=pvj; pww=1; 描述：迪杰斯特拉算法求最短路径。6 模块分析。7 系统测试7.1系统登录界面7.2功能一：学校简介7.3功能二：两点最短距离导航7.4功能三：某点到其他所有点的最短距离7.5功能四：显示全校地图7.5退出导航系统8 结论在本次课程设计所做的校园导航系统中，最关键的问题是最短路径问题，在教材中有具体的算法迪杰斯特拉算法求最短路径问题。但是想一次性就把程序调试出来是不可能的，我们组也是经过多次讨论才把程序完整的调试出来。通过这次的课程设计，我们学到了很多知识，也认识到很多不足，那就是知识的不足和经验的缺乏。但是我们相信自己可以在以后的学习中不断进步。附录：源代码：#include<stdio.h>#include <stdlib.h> #include <string.h> #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<G.vexnum;i+) if(Pend-1havei=1) printf("->%s",G.vexshavei); printf("n路径长度:%dn",Dend-1); printf("_ 本次导航结束:n1.继续导航 2.返回主菜单n"); scanf("%d",&choice1); if(choice1=2)system("cls");break; else if(choice1<1|choice1>2)printf("你输入选项有误，请继续导航！n"); break; case 3: printf("请输入出发点："); scanf("%d",&v0); ShortPath (G,v0,P,D); printf("v0到其他所有点的最短路径为：n"); for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) if(Pihavej=1) printf("->%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;i<G.vexnum;i+) /初始化路径长度 for(j=0;j<G.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;v<G.vexnum;+v)/初始化 finalv=0; dv=G.arcsv0-1v; for(w=0;w<G.vexnum;+w) pvw=0; if(dv<INFINITY) pvv0-1=1; pvv=1; dv0-1=0; finalv0-1=1; have0=v0-1; for(i=1;i<G.vexnum;+i) /其余的vexnum-1个顶点 min=INFINITY; for(w=0;w<G.vexnum;+w) if(!finalw) if(dw<min) /如有W点离更近 v=w; min=dw; finalv=1; havek=v; k+; for(w=0;w<G.vexnum;+w)/更新当前最短路径及距离 if(!finalw&&(min+G.arcsvw<dw) dw=min+G.arcsvw; for(j=0;j<G.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 东门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
