数据结构课程实践报告——校园导航系统

一、需求分析1设计校园平面图其中所含景点不少于10个。以图中顶点表示校内各景点存放景点名称、代号、简介等信息以边表示路径存放路径长度等相关信息2为来访客人提供图中任意景点相关信息的查询3为来访客人提供途中任意景点的问路查询即查询任意两个景点之间的一条最短的简单路径。1、由百度地图截图并通过自己标注得图如下2、通过杭电距离图得出相应点的距离二、概要设计 1抽象数据类型图的定义如下:ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R:R{VR} VR-{(v,w)| v,wEv,v,w)表示v和w之间存在路径} 基本操作P: CreateGraph (G,V, VR) 初始条件:V是图的顶点集,VR是图中边的集合。操作结果:按V和VR的定义构造图G。 DestroyGraph(G) 初始条件:图G存在。操作结果:销毁图G。 LocateVex (G,u) 初始条件:图G仔在,u和G中顶点有相同特征。 2、主程序 int main() { 定义变量并初始化 While (1); 创建校园地图 选择导航功能 输出距离 } 三、详细设计 1、顶点边和图类型 #define INF 999999 #define M 20 int dist[M][M];///距离 int path[M][M];///路径 int Stack[M];///路径栈 int top;///栈顶 int counts;///记录路径数 int visited[M];///标记数组 struct vertex///景点信息结构体 { int num;///景点编号 char name[20];///景点名称 char info[300];///景点介绍 }; struct maps { int n;///点数 int m;///边数 vertex v[M]; int edgs[M][M];///邻接矩阵 } g; ///景点图的结构体 图的基本操作 void Creat_vertex() 创建景点信息结构体 void Creat_maps() 创建校园地图 void Search_info() 查找校园景点信息 void Floyd() 用弗洛伊德算法计算最短路径 void Floyd_print(int s, int e) 打印最短路径 void Dfs_allpath(int s,int e) 用DFS算法遍历所有路径 void Bestpath_Multispot() 多景点的最短路径计算 void Dis_menu() 菜单展示 void Creat_vertex() { g.v[0].num1; strcpy(g.v[0].name,图书馆); strcpy(g.v[0].info,丰富的藏书资源); g.v[1].num2; strcpy(g.v[1].name,体育馆); strcpy(g.v[1].info,杭州亚运会击剑馆学生长跑打卡点); g.v[2].num3; strcpy(g.v[2].name,六教); strcpy(g.v[2].info,第六教学楼); g.v[3].num4; strcpy(g.v[3].name,四教); strcpy(g.v[3].info,这是学校的第四教学楼); g.v[4].num5; strcpy(g.v[4].name,二教); strcpy(g.v[4].info,自动化学院电子学院机械学院); g.v[5].num6; strcpy(g.v[5].name,一教); strcpy(g.v[5].info,计算机学院); g.v[6].num7; strcpy(g.v[6].name,三教); strcpy(g.v[6].info,外国语学院); g.v[7].num8; strcpy(g.v[7].name,七教); strcpy(g.v[7].info,第七教学楼设备新颖); g.v[8].num9; strcpy(g.v[8].name,十二教); strcpy(g.v[8].info,一般上公共课的地方); g.v[9].num10; strcpy(g.v[9].name,十一教); strcpy(g.v[9].info,圣光机学院); g.v[10].num11; strcpy(g.v[10].name,十教); strcpy(g.v[10].info,卓越学院国际教育学院); g.v[11].num12; strcpy(g.v[11].name,九教); strcpy(g.v[11].info,经济会计人艺数法学院); g.v[12].num13; strcpy(g.v[12].name,学生活动中心); strcpy(g.v[12].info,这是举办文艺活动的场所); } void Creat_maps() { int i,j; g.n13;///13个景点 g.m18;///18条双向路径 for(i0; ig.n; i) ///初始化邻接矩阵 { for(j0; jg.n; j) { g.edgs[i][j]INF; } } g.edgs[0][1]g.edgs[1][0]341;///写入边的信息 g.edgs[0][2]g.edgs[2][0]1000; g.edgs[0][7]g.edgs[7][0]500; g.edgs[1][3]g.edgs[3][1]200; g.edgs[1][4]g.edgs[4][1]200; g.edgs[2][7]g.edgs[7][2]400; g.edgs[2][10]g.edgs[10][2]300; g.edgs[3][4]g.edgs[4][3]300; g.edgs[4][5]g.edgs[5][4]300; g.edgs[4][6]g.edgs[6][4]100; g.edgs[5][6]g.edgs[6][5]300; g.edgs[5][8]g.edgs[8][5]200; g.edgs[6][8]g.edgs[8][6]200; g.edgs[6][12]g.edgs[12][6]100; g.edgs[6][7]g.edgs[7][6]200; g.edgs[8][9]g.edgs[9][8]500; g.edgs[9][11]g.edgs[11][9]450; g.edgs[10][11]g.edgs[11][10]300; } void Search_info() { int i,n; printf(杭州电子科技大学的景点有\n); for(i0; i13; i) { printf(%d:%s\n,g.v[i].num,g.v[i].name); } while(1) { printf(请输入你想要查询的景点编号\n); printf(按0退出\n\n); scanf(%d,n); getchar(); if(n0) { break; } else if(n0||n13) { printf(输入有误请重新输入\n\n); continue; } else { printf(%d:%s\n,g.v[n-1].num,g.v[n-1].name); printf(%s\n\n,g.v[n-1].info); } } return ; } void Floyd() ///弗洛伊德 { int i,j,k; for(i0; ig.n; i) ///初始化距离与路径矩阵 { for(j0; jg.n; j) { dist[i][j]g.edgs[i][j]; if(i!jdist[i][j]INF) { path[i][j]i; } else { path[i][j]-1;///-1代表不可达 } } } //printf(%d\n,g.n); for(k0; kg.n; k) { for(i0; ig.n; i) { for(j0; jg.n; j) { if(dist[i][j](dist[i][k]dist[k][j])) { dist[i][j]dist[i][k]dist[k][j];///更新 path[i][j]k; ///path用于记录最短路径上的结点*/ } } } } return ; } void Floyd_print(int s, int e) { if(path[s][e]-1||path[s][e]e||path[s][e]s)///递归终止条件 { return; } else { Floyd_print(s,path[s][e]);///将中间点作为终点继续打印路径 printf(%s-,g.v[path[s][e]].name);///打印中间景点名字 Floyd_print(path[s][e],e);///将中间点作为起点继续打印路径 } } void Dfs_allpath(int s,int e) { int dis0; int i,j; Stack[top]s; top; ///起点入栈 visited[s]1;///标记入栈 for(i0; ig.n; i) { if(g.edgs[s][i]0g.edgs[s][i]!INF!visited[i]) { ///表明两点可达且未被访问 if(ie)///DFS到了终点打印路径 { printf(第%d条路:,counts); for(j0; jtop; j) { printf(%s-,g.v[Stack[j]].name); if(jtop-1)///统计路径长度 { disdisg.edgs[Stack[j]][Stack[j1]]; } } disdisg.edgs[Stack[top-1]][e]; printf(%s\n,g.v[e].name);///打印终点 printf(总长度是%dm\n\n,dis); } else///不是终点接着DFS { Dfs_allpath(i,e); top--;///支路全被访问一遍,顶点出栈 visited[i]0;///出栈点标记为已出栈允许下次访问 } } } } void Bestpath_Multispot() { int vNum[M] {0}; int i,j,dis; j1; dis0;///统计全程总长 printf(请输入你要游览的第%d个景点的编号输入-1结束输入,j); scanf(%d,vNum[j-1]); while(vNum[j-1]!-1j13) { printf(请输入你要游览的第%d个景点编号,j); scanf(%d, vNum[j-1]); if(vNum[j-1]-1) { break; } } printf(\n这是最佳访问路径); for(i0; vNum[i]0vNum[i1]0; i) { printf(%s-,g.v[vNum[i]-1].name);///输出路径上的起点 Floyd_print(vNum[i]-1,vNum[i1]-1);///利用佛洛依德算法 disdist[vNum[i]-1][vNum[i1]-1]; } printf(%s\n\n,g.v[vNum[j-2]-1].name);///*输出路径上的终点*/ printf(全程总长为%dm\n\n,dis); } void Dis_menu() { printf(\n); printf( ************杭州电子科技大学导游咨询系统***********\n\n); printf( ***** 1.杭电景点信息查询 ******************\n); printf( ***** 2.两景点之间最短路查询 ******************\n); printf( ***** 3.两景点间所有路径查询 ******************\n); printf( ***** 4.多景点间访问路线查询 ******************\n); printf( ***** 5.退出系统 ******************\n); printf( *******************************************************\n); return ; } 主程序 int main() { int i,n; int start,ends; Creat_vertex(); Creat_maps(); Dis_map(); while(1) { Dis_menu(); printf(请输入需要操作的命令\n); scanf(%d,n); getchar(); if(n1||n5) { printf(输入有误请重新输入\n); continue; } else { if(n1) { Search_info(); } else if(n2) { Dis_map(); printf(请输入起点的景点\n); scanf(%d,start); printf(请输入终点的景点\n); scanf(%d,ends); Floyd();///弗洛伊德 printf(从%s到%s最短距离是%d\n,g.v[start-1].name,g.v[ends-1].name,dist[start-1][ends-1]); printf(%s-,g.v[start-1].name); Floyd_print(start-1, ends-1); printf(%s\n,g.v[ends-1].name); } else if(n3) { Dis_map(); counts1;///起始路径数为1 printf(请输入起点的景点\n); scanf(%d,start); printf(请输入终点的景点\n); scanf(%d,ends); Dfs_allpath(start-1,ends-1); } else if(n4) { Dis_map(); Floyd();///弗洛伊德 Bestpath_Multispot(); } else if(n5) { return 0; } } } return 0; }四、设计和调试分析1.原设计在边的属性中加上访问标志域mark,意图以!(p-mark)代替!InSet(w,ss)来判别是否需要检测该条边,后发现,如此只能求出第一对顶点之间的最短路径。在继续求其他对顶点的最短路径时,必须恢复所有边的访问标志为FALSE,则需要耗费O(e)的时间,并不比现在的算法优越,故舍去之。2.考虑道路网多是稀疏网,故采用邻接多重表作存储结构,其空间复杂度为O(e),此时的时间复杂度也为O(e)。构建邻接多重表的时间复杂度为O(ne),输出路径的时间复杂度为O(n)。由此,本导游程序的时间复杂度为O(n十e)。3.由于导游程序在实际执行时,需要根据用户的临时输入求最短路径。因此,虽然迪杰斯特拉算法的时间复杂度比弗洛伊德算法低,但每求一条最短路径都必须重新搜索一遍,在频繁查询时会导致查询效率降低,而弗洛伊德算法只要计算一次,即可求得每一对顶点之间的最短路径,虽然时间复杂度为O(n),但以后每次查询都只要查表即可,极大地提高了查询效率,而且,弗洛伊德算法还支持带负权的图的最短路径的计算。由此可见在选用算法时,不能单纯地只考虑算法的渐近时间复杂度,有时还必须综合考虑各种因素。五、用户手册1、运行环境为win10环境执行文件为schoolguide.exe2、进入程序后六、测试结果两个路径的最短总程序代码#includecstdio #includecstring #includealgorithm #includestack #define INF 999999 #define M 20 int dist[M][M];///距离 int path[M][M];///路径 int Stack[M];///路径栈 int top;///栈顶 int counts;///记录路径数 int visited[M];///标记数组 using namespace std; struct vertex///景点信息结构体 { int num;///景点编号 char name[20];///景点名称 char info[300];///景点介绍 }; struct maps { int n;///点数 int m;///边数 vertex v[M]; int edgs[M][M];///邻接矩阵 } g; ///景点图的结构体 void Creat_vertex() { g.v[0].num1; strcpy(g.v[0].name,图书馆); strcpy(g.v[0].info,丰富的藏书资源); g.v[1].num2; strcpy(g.v[1].name,体育馆); strcpy(g.v[1].info,杭州亚运会击剑馆学生长跑打卡点); g.v[2].num3; strcpy(g.v[2].name,六教); strcpy(g.v[2].info,第六教学楼); g.v[3].num4; strcpy(g.v[3].name,四教); strcpy(g.v[3].info,这是学校的第四教学楼); g.v[4].num5; strcpy(g.v[4].name,二教); strcpy(g.v[4].info,自动化学院电子学院机械学院); g.v[5].num6; strcpy(g.v[5].name,一教); strcpy(g.v[5].info,计算机学院); g.v[6].num7; strcpy(g.v[6].name,三教); strcpy(g.v[6].info,外国语学院); g.v[7].num8; strcpy(g.v[7].name,七教); strcpy(g.v[7].info,第七教学楼设备新颖); g.v[8].num9; strcpy(g.v[8].name,十二教); strcpy(g.v[8].info,一般上公共课的地方); g.v[9].num10; strcpy(g.v[9].name,十一教); strcpy(g.v[9].info,圣光机学院); g.v[10].num11; strcpy(g.v[10].name,十教); strcpy(g.v[10].info,卓越学院国际教育学院); g.v[11].num12; strcpy(g.v[11].name,九教); strcpy(g.v[11].info,经济会计人艺数法学院); g.v[12].num13; strcpy(g.v[12].name,学生活动中心); strcpy(g.v[12].info,这是举办文艺活动的场所); } void Creat_maps() { int i,j; g.n13;///13个景点 g.m18;///18条双向路径 for(i0; ig.n; i) ///初始化邻接矩阵 { for(j0; jg.n; j) { g.edgs[i][j]INF; } } g.edgs[0][1]g.edgs[1][0]289;///写入边的信息 g.edgs[0][2]g.edgs[2][0]305; g.edgs[0][7]g.edgs[7][0]506; g.edgs[1][3]g.edgs[3][1]285; g.edgs[1][4]g.edgs[4][1]220; g.edgs[2][7]g.edgs[7][2]460; g.edgs[2][10]g.edgs[10][2]500; g.edgs[3][4]g.edgs[4][3]348; g.edgs[4][5]g.edgs[5][4]159; g.edgs[4][6]g.edgs[6][4]158; g.edgs[5][6]g.edgs[6][5]355; g.edgs[5][8]g.edgs[8][5]254; g.edgs[6][8]g.edgs[8][6]250; g.edgs[6][12]g.edgs[12][6]290; g.edgs[6][7]g.edgs[7][6]209; g.edgs[8][9]g.edgs[9][8]503; g.edgs[9][11]g.edgs[11][9]455; g.edgs[10][11]g.edgs[11][10]340; } void Search_info() { int i,n; printf(杭州电子科技大学的景点有\n); for(i0; i13; i) { printf(%d:%s\n,g.v[i].num,g.v[i].name); } while(1) { printf(请输入你想要查询的景点编号\n); printf(按0退出\n\n); scanf(%d,n); getchar(); if(n0) { break; } else if(n0||n13) { printf(输入有误请重新输入\n\n); continue; } else { printf(%d:%s\n,g.v[n-1].num,g.v[n-1].name); printf(%s\n\n,g.v[n-1].info); } } return ; } void Floyd() ///弗洛伊德 { int i,j,k; for(i0; ig.n; i) ///初始化距离与路径矩阵 { for(j0; jg.n; j) { dist[i][j]g.edgs[i][j]; if(i!jdist[i][j]INF) { path[i][j]i; } else { path[i][j]-1;///-1代表不可达 } } } //printf(%d\n,g.n); for(k0; kg.n; k) { for(i0; ig.n; i) { for(j0; jg.n; j) { if(dist[i][j](dist[i][k]dist[k][j])) { dist[i][j]dist[i][k]dist[k][j];///更新 path[i][j]k; ///path用于记录最短路径上的结点*/ } } } } return ; } void Floyd_print(int s, int e) { if(path[s][e]-1||path[s][e]e||path[s][e]s)///递归终止条件 { return; } else { Floyd_print(s,path[s][e]);///将中间点作为终点继续打印路径 printf(%s-,g.v[path[s][e]].name);///打印中间景点名字 Floyd_print(path[s][e],e);///将中间点作为起点继续打印路径 } } void Dfs_allpath(int s,int e) { int dis0; int i,j; Stack[top]s; top; ///起点入栈 visited[s]1;///标记入栈 for(i0; ig.n; i) { if(g.edgs[s][i]0g.edgs[s][i]!INF!visited[i]) { ///表明两点可达且未被访问 if(ie)///DFS到了终点打印路径 { printf(第%d条路:,counts); for(j0; jtop; j) { printf(%s-,g.v[Stack[j]].name); if(jtop-1)///统计路径长度 { disdisg.edgs[Stack[j]][Stack[j1]]; } } disdisg.edgs[Stack[top-1]][e]; printf(%s\n,g.v[e].name);///打印终点 printf(总长度是%dm\n\n,dis); } else///不是终点接着DFS { Dfs_allpath(i,e); top--;///支路全被访问一遍,顶点出栈 visited[i]0;///出栈点标记为已出栈允许下次访问 } } } } void Bestpath_Multispot() { int vNum[M] {0}; int i,j,dis; j1; dis0;///统计全程总长 printf(请输入你要游览的第%d个景点的编号输入-1结束输入,j); scanf(%d,vNum[j-1]); while(vNum[j-1]!-1j13) { printf(请输入你要游览的第%d个景点编号,j); scanf(%d, vNum[j-1]); if(vNum[j-1]-1) { break; } } printf(\n这是最佳访问路径); for(i0; vNum[i]0vNum[i1]0; i) { printf(%s-,g.v[vNum[i]-1].name);///输出路径上的起点 Floyd_print(vNum[i]-1,vNum[i1]-1);///利用佛洛依德算法 disdist[vNum[i]-1][vNum[i1]-1]; } printf(%s\n\n,g.v[vNum[j-2]-1].name);///*输出路径上的终点*/ printf(全程总长为%dm\n\n,dis); } void Dis_menu() { printf(\n); printf( ************杭州电子科技大学导游咨询系统***********\n\n); printf( ***** 1.杭电景点信息查询 ******************\n); printf( ***** 2.两景点之间最短路查询 ******************\n); printf( ***** 3.两景点间所有路径查询 ******************\n); printf( ***** 4.多景点间访问路线查询 ******************\n); printf( ***** 5.退出系统 ******************\n); printf( *******************************************************\n); return ; } void Dis_map() { printf(\n *杭州电子科技大学校园景点地图一览*\n\n); printf( 1)图书馆 13学生活动中心 \n); printf( 3六教 8七教 -----| \n); printf( ◎ ◎---------------| | \n); printf( |------------| | | \n); printf( 2体育馆 9十二教 10十一教 | \n); printf( 4四教 7三教 | 11十教 12九教 \n); printf( -------|------------------—-|------|---------| | \n); printf( | | | ◎-------| \n); printf( | | | \n); printf( | | ◎ | \n); printf( 5二教 6一教 | \n); printf( |--------------------------------| | \n); } int main() { int i,n; int start,ends; Creat_vertex(); Creat_maps(); Dis_map(); while(1) { Dis_menu(); printf(请输入需要操作的命令\n); scanf(%d,n); getchar(); if(n1||n5) { printf(输入有误请重新输入\n); continue; } else { if(n1) { Search_info(); } else if(n2) { Dis_map(); printf(请输入起点的景点\n); scanf(%d,start); printf(请输入终点的景点\n); scanf(%d,ends); Floyd();///弗洛伊德 printf(从%s到%s最短距离是%d\n,g.v[start-1].name,g.v[ends-1].name,dist[start-1][ends-1]); printf(%s-,g.v[start-1].name); Floyd_print(start-1, ends-1); printf(%s\n,g.v[ends-1].name); } else if(n3) { Dis_map(); counts1;///起始路径数为1 printf(请输入起点的景点\n); scanf(%d,start); printf(请输入终点的景点\n); scanf(%d,ends); Dfs_allpath(start-1,ends-1); } else if(n4) { Dis_map(); Floyd();///弗洛伊德 Bestpath_Multispot(); } else if(n5) { return 0; } } } return 0; }