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

一、需求分析

（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].num=1; strcpy(g.v[0].name,"图书馆"); strcpy(g.v[0].info,"丰富的藏书资源"); g.v[1].num=2; strcpy(g.v[1].name,"体育馆"); strcpy(g.v[1].info,"杭州亚运会击剑馆，学生长跑打卡点"); g.v[2].num=3; strcpy(g.v[2].name,"六教"); strcpy(g.v[2].info,"第六教学楼"); g.v[3].num=4; strcpy(g.v[3].name,"四教"); strcpy(g.v[3].info,"这是学校的第四教学楼"); g.v[4].num=5; strcpy(g.v[4].name,"二教"); strcpy(g.v[4].info,"自动化学院，电子学院，机械学院"); g.v[5].num=6; strcpy(g.v[5].name,"一教"); strcpy(g.v[5].info,"计算机学院"); g.v[6].num=7; strcpy(g.v[6].name,"三教"); strcpy(g.v[6].info,"外国语学院"); g.v[7].num=8; strcpy(g.v[7].name,"七教"); strcpy(g.v[7].info,"第七教学楼，设备新颖"); g.v[8].num=9; strcpy(g.v[8].name,"十二教"); strcpy(g.v[8].info,"一般上公共课的地方"); g.v[9].num=10; strcpy(g.v[9].name,"十一教"); strcpy(g.v[9].info,"圣光机学院"); g.v[10].num=11; strcpy(g.v[10].name,"十教"); strcpy(g.v[10].info,"卓越学院，国际教育学院"); g.v[11].num=12; strcpy(g.v[11].name,"九教"); strcpy(g.v[11].info,"经济，会计，人艺数法学院"); g.v[12].num=13; strcpy(g.v[12].name,"学生活动中心"); strcpy(g.v[12].info,"这是举办文艺活动的场所"); } void Creat_maps() { int i,j; g.n=13;///13个景点 g.m=18;///18条双向路径 for(i=0; i<g.n; i++) ///初始化邻接矩阵 { for(j=0; j<g.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(i=0; i<13; 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(n==0) { break; } else if(n<0||n>13) { 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(i=0; i<g.n; i++) ///初始化距离与路径矩阵 { for(j=0; j<g.n; j++) { dist[i][j]=g.edgs[i][j]; if(i!=j&&dist[i][j]<INF) { path[i][j]=i; } else { path[i][j]=-1;///-1代表不可达 } } } //printf("%d\n",g.n); for(k=0; k<g.n; k++) { for(i=0; i<g.n; i++) { for(j=0; j<g.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 dis=0; int i,j; Stack[top]=s; top++; ///起点入栈 visited[s]=1;///标记入栈 for(i=0; i<g.n; i++) { if(g.edgs[s][i]>0&&g.edgs[s][i]!=INF&&!visited[i]) { ///表明两点可达且未被访问 if(i==e)///DFS到了终点，打印路径 { printf("第%d条路:",counts++); for(j=0; j<top; j++) { printf("%s->",g.v[Stack[j]].name); if(j<top-1)///统计路径长度 { dis=dis+g.edgs[Stack[j]][Stack[j+1]]; } } dis=dis+g.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; j=1; dis=0;///统计全程总长 printf("请输入你要游览的第%d个景点的编号（输入-1结束输入）：",j); scanf("%d",&vNum[j-1]); while(vNum[j-1]!=-1&&j<13) { printf("请输入你要游览的第%d个景点编号：",++j); scanf("%d", &vNum[j-1]); if(vNum[j-1]==-1) { break; } } printf("\n这是最佳访问路径："); for(i=0; vNum[i]>0&&vNum[i+1]>0; i++) { printf("%s->",g.v[vNum[i]-1].name);///输出路径上的起点 Floyd_print(vNum[i]-1,vNum[i+1]-1);///利用佛洛依德算法 dis+=dist[vNum[i]-1][vNum[i+1]-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(n<1||n>5) { printf("输入有误，请重新输入！！！\n"); continue; } else { if(n==1) { Search_info(); } else if(n==2) { 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(n==3) { Dis_map(); counts=1;///起始路径数为1 printf("请输入起点的景点：\n"); scanf("%d",&start); printf("请输入终点的景点：\n"); scanf("%d",&ends); Dfs_allpath(start-1,ends-1); } else if(n==4) { Dis_map(); Floyd();///弗洛伊德 Bestpath_Multispot(); } else if(n==5) { return 0; } } } return 0; }

四、设计和调试分析

1.原设计在边的属性中加上访问标志域mark,意图以!(p->mark)代替!InSet(w,ss)来判别是否需要检测该条边,后发现,如此只能求出第一对顶点之间的最短路径。在继续求其他对顶点的最短路径时,必须恢复所有边的访问标志为FALSE,则需要耗费O(e)的时间,并不比现在的算法优越,故舍去之。

2.考虑道路网多是稀疏网,故采用邻接多重表作存储结构,其空间复杂度为O(e),此时的时间复杂度也为O(e)。构建邻接多重表的时间复杂度为O(n+e),输出路径的时间复杂度为O(n)。由此,本导游程序的时间复杂度为O(n十e)。

3.由于导游程序在实际执行时,需要根据用户的临时输入求最短路径。因此,虽然迪杰斯特拉算法的时间复杂度比弗洛伊德算法低,但每求一条最短路径都必须重新搜索一遍,在频繁查询时会导致查询效率降低,而弗洛伊德算法只要计算一次,即可求得每一对顶点之间的最短路径,虽然时间复杂度为O(n'),但以后每次查询都只要查表即可,极大地提高了查询效率,而且,弗洛伊德算法还支持带负权的图的最短路径的计算。由此可见，在选用算法时,不能单纯地只考虑算法的渐近时间复杂度,有时还必须综合考虑各种因素。

五、用户手册

1、运行环境为win10环境，执行文件为：schoolguide.exe；

2、进入程序后：

六、测试结果

两个路径的最短：

总程序代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #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].num=1; strcpy(g.v[0].name,"图书馆"); strcpy(g.v[0].info,"丰富的藏书资源"); g.v[1].num=2; strcpy(g.v[1].name,"体育馆"); strcpy(g.v[1].info,"杭州亚运会击剑馆，学生长跑打卡点"); g.v[2].num=3; strcpy(g.v[2].name,"六教"); strcpy(g.v[2].info,"第六教学楼"); g.v[3].num=4; strcpy(g.v[3].name,"四教"); strcpy(g.v[3].info,"这是学校的第四教学楼"); g.v[4].num=5; strcpy(g.v[4].name,"二教"); strcpy(g.v[4].info,"自动化学院，电子学院，机械学院"); g.v[5].num=6; strcpy(g.v[5].name,"一教"); strcpy(g.v[5].info,"计算机学院"); g.v[6].num=7; strcpy(g.v[6].name,"三教"); strcpy(g.v[6].info,"外国语学院"); g.v[7].num=8; strcpy(g.v[7].name,"七教"); strcpy(g.v[7].info,"第七教学楼，设备新颖"); g.v[8].num=9; strcpy(g.v[8].name,"十二教"); strcpy(g.v[8].info,"一般上公共课的地方"); g.v[9].num=10; strcpy(g.v[9].name,"十一教"); strcpy(g.v[9].info,"圣光机学院"); g.v[10].num=11; strcpy(g.v[10].name,"十教"); strcpy(g.v[10].info,"卓越学院，国际教育学院"); g.v[11].num=12; strcpy(g.v[11].name,"九教"); strcpy(g.v[11].info,"经济，会计，人艺数法学院"); g.v[12].num=13; strcpy(g.v[12].name,"学生活动中心"); strcpy(g.v[12].info,"这是举办文艺活动的场所"); } void Creat_maps() { int i,j; g.n=13;///13个景点 g.m=18;///18条双向路径 for(i=0; i<g.n; i++) ///初始化邻接矩阵 { for(j=0; j<g.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(i=0; i<13; 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(n==0) { break; } else if(n<0||n>13) { 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(i=0; i<g.n; i++) ///初始化距离与路径矩阵 { for(j=0; j<g.n; j++) { dist[i][j]=g.edgs[i][j]; if(i!=j&&dist[i][j]<INF) { path[i][j]=i; } else { path[i][j]=-1;///-1代表不可达 } } } //printf("%d\n",g.n); for(k=0; k<g.n; k++) { for(i=0; i<g.n; i++) { for(j=0; j<g.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 dis=0; int i,j; Stack[top]=s; top++; ///起点入栈 visited[s]=1;///标记入栈 for(i=0; i<g.n; i++) { if(g.edgs[s][i]>0&&g.edgs[s][i]!=INF&&!visited[i]) { ///表明两点可达且未被访问 if(i==e)///DFS到了终点，打印路径 { printf("第%d条路:",counts++); for(j=0; j<top; j++) { printf("%s->",g.v[Stack[j]].name); if(j<top-1)///统计路径长度 { dis=dis+g.edgs[Stack[j]][Stack[j+1]]; } } dis=dis+g.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; j=1; dis=0;///统计全程总长 printf("请输入你要游览的第%d个景点的编号（输入-1结束输入）：",j); scanf("%d",&vNum[j-1]); while(vNum[j-1]!=-1&&j<13) { printf("请输入你要游览的第%d个景点编号：",++j); scanf("%d", &vNum[j-1]); if(vNum[j-1]==-1) { break; } } printf("\n这是最佳访问路径："); for(i=0; vNum[i]>0&&vNum[i+1]>0; i++) { printf("%s->",g.v[vNum[i]-1].name);///输出路径上的起点 Floyd_print(vNum[i]-1,vNum[i+1]-1);///利用佛洛依德算法 dis+=dist[vNum[i]-1][vNum[i+1]-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(n<1||n>5) { printf("输入有误，请重新输入！！！\n"); continue; } else { if(n==1) { Search_info(); } else if(n==2) { 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(n==3) { Dis_map(); counts=1;///起始路径数为1 printf("请输入起点的景点：\n"); scanf("%d",&start); printf("请输入终点的景点：\n"); scanf("%d",&ends); Dfs_allpath(start-1,ends-1); } else if(n==4) { Dis_map(); Floyd();///弗洛伊德 Bestpath_Multispot(); } else if(n==5) { return 0; } } } return 0; }