数据结构课程实践报告——校园导航系统
一、需求分析（1）设计校园平面图，其中所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息；（2）为来访客人提供图中任意景点相关信息的查询；（3）为来访客人提供途中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。1、由百度地图截图并通过自己标注得图如下：2、通过杭电距离图得出相应点的距离：二、概要设计：1．抽象数据类型
文章共5,170字 · 阅读需要大约18分钟
一键AI生成摘要，助你高效阅读
问答
·
一、需求分析
（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;
}
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
33
0- 0
已为社区贡献1条内容
所有评论(0)