校园导航系统.docx
《校园导航系统.docx》由会员分享，可在线阅读，更多相关《校园导航系统.docx（28页珍藏版）》请在冰点文库上搜索。
校园导航系统
题号:
第七题
题目:
校园导航问题
1,需求分析:
设计您的学校的平面图,至少包括10个以上的景点（场所）,每两个景点间可以有不同的路,且路长也可能不同,找出从任意景点到达另一景点的最佳路径（最短路径）。
要求:
（1）以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。
（4）修改景点信息。
实现提示:
一般情况下,校园的道路就是双向通行的,可设计校园平面图就是一个无向网。
顶点与边均含有相关信息。
选做内容:
（1）提供图的编辑功能:
增、删景点;增、删道路;修改已有信息等。
（2）校园导游图的仿真界面。
2,设计:
2、1设计思想:
<1>,数据结构设计:
（1）图。
采用邻接矩阵存储,其中图所用到的结构体为:
typedefstruct
{
SeqListvertices;//表示图中的顶点
intEdge[MaxVertices][MaxVertices];//表示图中的边
intnumOfEdge;//表示图中边的数目
}AdjMGraph;
（2）景点。
用顺序表存储。
所用到的结构体为:
typedefstruct
{
charname[20];//顶点名称
intcode;//顶点代号
charintroduction[50];//顶点信息简介
}DataType;
（3）景点之间的连接描述,所用到的结构体为:
typedefstruct
{
introw;
intcol;
intweight;
}RowColWeight;
用图来存放所提供的所有景点,然后用线性表来存放每一个景点的信息,其中包括景点的名称,代号,信息简介,以及其它的一些信息。
这样就将对景点的操作,变成对图中各顶点的操作。
<2>,算法设计:
关于本课题的算法,很大部分来源于这学期数据结构课程的学习,其中包括:
图的创建,线性表的一些操作。
对于具体的问题实现,都有不同的算法,在下面的分析中,我将详细说明
2、2设计表示:
<1>,函数调用关系及函数说明:
首先,main（）函数调用Creat（）函数,用来创建图,然后调用menu（）函数来选择用户所要进行的操作。
其中menu（）函数就就是一个菜单供使用者来选择她所要进行的相关操作,比如信息的查询,最短路径查询之类。
对于要求1:
以图中顶点表示校园内各景点,存放景点名称、代号、简介等信
息;以边表示路径,存放路径长度等有关信息。
图的创建设计流程图为:
Creat（）函数原型为:
voidCreat（AdjMGraph*G,DataTypev[],RowColWeightE[],intn,inte）
其中,G为所创建的图结构体对象,v[]为所有顶点的集合,它就是DataType
型,这个类型前面已经介绍过;E[]存放着各顶点之间的连接关系,它就是RowColWeight型,前面也介绍过;n表示顶点的个数;e表示边数。
Creat（）函数的功能就就是实现图的创建,将已知的景点的一些信息,转换成图的
信息,并进行存储。
对于要求2:
为来访客人提供图中任意景点相关信息的查询。
流程图为:
menu（）函数的原型为:
voidmenu（）她就就是一个菜单,供用户选择她们所要进行的操作。
Information1（）函数原型为:
voidInformation1（）它的功能就就是输入查询景点的信息,并调用Information（）
Information（）函数原型为:
voidInformation（AdjMGraphG,charscenery[]）G依然就是所创建的图的结构
体对象,后面所有的G都就是表示这个意思;scenery[]就是在Information1（）中输入的景点的
名称。
此函数的功能就就是根据输入的景点的名称来查询其相关的信息。
对于要求3:
为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条
最短路径。
流程图为:
Path1（）函数原型为:
voidPath1（）它的功能就就是输入查询景点的名称,并调用Path（）
Path（）函数原型为:
voidPath（AdjMGraphG,charsceneryname[],charsceneryname1[]）
其中sceneryname[],sceneryname1[]就就是在Path1（）函数中所输入的景点的名称,这
个函数的功能就就是通过这两个景点的名称找到它们在线性表中的位置,然后调用Floyd（）
函数,查找出它们的最短路径,并输出所要的信息。
Floyd（）函数原型为:
voidFloyd（intcost[][MaxVertices],intn,intweight[][MaxVertices],intpath[][MaxVertices]）
其中参数cost[][MaxVertices]即就是图中边的邻接存储矩阵,weight[][MaxVertices]用来存放经
此算法后的各顶点间的最短路径的值,path[][MaxVertices]就就是每两个顶点之间最短路径中
到达目的顶点的前一个顶点的位置。
Path（）函数中的输出信息就就是据此而来。
对于要求4:
修改景点信息。
流程图为:
Modify（）函数原型为:
voidModify（）它不带任何参数,功能就是通过手动输入景点名称,然后找到景点的存储空间,然后在修改相应的信息。
对于选做要求:
增加景点。
其工作流程图为:
AddVertic（）函数原型为:
voidAddVertic（）她不带任何参数,该函数的功能就是在这个函数里面输入景点的信息,然后调用ListInsert（）函数,将所要增加的顶点信息插入到线性表中。
ListInsert（）函数原型为:
voidListInsert（SeqList*L,inti,DataTypex）参数L表示顶点存储的线性表,i表示要插入的位置,x表示要插入的景点的信息。
同时我在插入顶点时也将她与其她顶点之间的距离设置为MaxWeight,这样做主要就是为了方便在Floyd函数里面求最短路径
对于选做要求:
删除景点。
其工作流程图为
DeleteVertic（）函数原型为:
voidDeleteVertic（）她不带任何参数,该函数的功能就就是在函数体里面输入要删除的景点的名称,然后根据名称找到该景点在线性表中的存储位置,然后调用线性表中的
ListDelete（）函数进行相应顶点的删除。
ListDelete（）函数原型为:
ListDelete（SeqList*L,inti,DataType*x）其中参数L为存放顶点信息的线性表,i表示要删除顶点在线性表中的存放位置,,x就就是要删除的那一个景点。
它的功能就就是从线性表中删除指定的顶点。
对于选做要求:
增、删道路,流程图为:
AddRoad（）与DeleteRoad（）两函数原型为:
voidAddRoad（）与voidDeleteRoad（）。
这两个函数都不带参数,它们的功能就就是在这两个函数里面输入要删除要增加或者的边连接的两个景点的名称,然后在线性表中找到这两个景点的相对存储空间,最后调用InsertEdge（）或者DeleteEdge（）函数。
InsertEdge（）与DeleteEdge（）两函数原型为:
voidInsertEdge（AdjMGraph*G,intv1,intv2,intweight）
voidDeleteEdge（AdjMGraph*G,intv1,intv2）这两个函数中同名参数所代表的意义就是相同的,其中v1,v2就是所输入景点在线性表中的相对位置;weight就就是增加的边的权值
<2>函数接口说明
我所设计整个程序就就是一些子函数的集合,每个功能都对应一个或者几个子函数,她们之间可以没有任何限制,只要能保证程序正确运行就可以调用,特别就是AdjMGraph、h
AdjMGraph、h与SeqList、h头文件之中的函数,她们被很多函数调用过。
这其中都没有任何特殊类型的函数
2、3详细设计:
根据题目分析,对于信息查询与修改功能,设计如下:
1,输入景点名称
2,从线性表头扫描到表尾,
if（找到该景点）输出景点结构体信息
else输出提示信息找不到该顶点
实现查找最短路径,设计如下:
1,景点名称
2,根据输入的信息找到它们所在的线性表中的位置
3,调用Floyd算法找出最短路径
4,输出信息
实现增删景点功能,设计如下:
1,增加或者删除景点的名称
2,if（输入景点）,将景点信息保存在相应的结构体中,并插入到线性表尾;
if（删除景点）,找到景点在线性表中所在的位置,然后将景点信息从线性表中删除
实现增删道路功能,设计如下:
1,入增加或删除道路连接的两个景点的名称;
2,找到它们的相对位置;
3,if（删除道路）,将连接它们的边置为MaxWeight;
if（增加道路）,将输入的边值赋给相应的邻接矩阵表;
3,调试分析:
<1>,调试过程中遇到的问题与解决方案:
1,关于最短路径的输出问题。
在进行最短路径输出时,我刚开始时只能正序输出,具体的描述为:
比如,我要查寻从东区到东湖的最短路径,那么它能正确输出结果,她的形式为:
东区——>主楼——>西体育馆——>隧道——>北大门——>东湖。
但就是,当我逆向输出时,得到的结果却有点问题,经过分析调试后,找到了错误的所在。
在找最短路径的时候我用的就是Floyd算法,在这个算法中有三重循环,形式均为:
for（k=0;k2,关于新增加景点后再找最短路径问题。
比如我再新增一个景点,如北区食堂,并输入相关信息,然后插入到线性表尾,当我再找从东区到东湖的最短距离时,输出的最短路径将变为:
东区——>食堂——>东湖。
经过分析调试后,其原因也就是出在Floyd算法那,在Floyd算法中,有这么一个判断if（weight[i][j]>weight[i][k]+weight[k][j]）,由于我在输入新景点信息时并没有建立它与其它景点之间的连接信息,所以在图中,该新景点与其它景点之间的边得连接信息就是空的,也就就是说在邻接矩阵中,它的边得信息就是空的,那么在进行if（weight[i][j]>weight[i][k]+weight[k][j]）判断时weight[新增景点序号][其它景点序号]的值将就是一个很大的负数,所以最短路径将会出错。
解决这个问题的方法就就是在增加新景点时就将它与其它景点之间的边（距离）设置为MaxWeight,这时如果再用Floyd函数进行最短路径的求解时就不会再出现问题了。
另外,在做这个题时也还出现过一些其她的小问题,不过都比较容易解决,这里我就不再列出了……
<2>,算法的时空复杂度分析
对应题目的要求,我总共提供了八个选项操作对于每一个操作的分析如下:
1,相关信息的查询。
在这个操作中允许使用者输入一个景点名称,然后再根据景点名称来或取其相关的信息,这个操作要扫描线性表,其时间复杂度为o（n）,空间复杂度为o（n）;
2,最短路径查询。
实现这个功能用到了Floyd算法,她用到了一个三重的for（）循环,故其时间复杂度为o（n^3）,空间复杂度为o
（1）;
3,修改景点信息。
要修改信息,必须首先找到景点所在的存储位置,那么就需要扫描线性表,其时间复杂度为o（n）,空间复杂度为o
（1）;
4,增加景点。
增加景点信息时,直接将此景点结构体信息插入到线性表表尾,而不需要进行遍历,其时间复杂度与空间复杂度均为o
（1）;
5,删除景点。
删除景点时必须找到所要删除景点所在的位置,这样就必须遍历线性表,除此之外,删除后线性表还要进行移动操作,其时间复杂度为o（n）,空间复杂度为o（n1）;
6,增加道路。
增加道路也要扫描线性表,找到要增加路的两景点的存储位置,然后再根据找到的存储位置去改变邻接矩阵的边的值,改变邻接矩阵的时间复杂度为o
（1）,其总时间消耗在线性表的扫描上,故最终其时间复杂度为o（n）,空间复杂度为o
（1）;
7,删除道路。
删除道路与增加道路类似,都就是先找到存储位置,然后再改变邻接矩阵,它的时空复杂度分别为o（n）,o
（1）;
8,浏览所有景点。
浏览所有景点的实质就就是从头到尾遍历线性表,然后输出遍历到的节点的信息,其时间复杂度为o（n）,空间复杂度为o
（1）。
4,用户手册:
使用说明:
当用户将程序经过编译,连接后,点击运行,在DOS环境里面将瞧到一个选项菜单,菜单里面提供了8种操作,同时输出了一行提示信息:
请选择您想进行的操作。
然后用户可以输入一个1——8之间的数字进行选择性的操作,例如,您想进行信息的查询操作,您可以从键盘输入数字‘1’;当然,一般而言先应该进行“浏览所有景点名称”操作。
如果您选择了浏览所有景点名称操作,在屏幕上将会显示出10个景点的名称,这些景点就是事先加进去的,用户可以对这些景点进行任何程序所提供的操作。
下面,我将详细介绍本程序的使用方法:
在浏览景点后,菜单将会继续显示出来,为您提供操作选择。
如果您想进行“相关信息的查询”操作,输入数字‘1’,然后程序将会提醒您输入查询景点的名称,在您输入景点名称后回车即可。
如果您想进行“最短路径查询”操作,首先输入数字‘2’,然后程序将会提醒您输入查询的景点的名称,您输入按要求输入所提供的两个景点名称即可,要注意的就是景点名称间以空格隔开,最后程序就会告诉您最短的路径,以及最短路的长度。
如果您想修改景点的信息,同样先输入数字‘3’,然后程序就会提醒您输入所要修改景点的名称,您可以根据要求输入一个景点的名称,然后回车,之后屏幕上就会显示您所输入的景点的所有信息,同时会有三个修改选项供用户选择,然后您可以输入1——3之间的一个数字进行选择性的修改。
比如,您可以输入‘1’对景点名称进行修改,修改完后又会返回到菜单项继续选择。
如果您想进行“增加景点”操作,可以输入数字‘4’,然后程序就会提示您输入新增加的景点的名称,代号,信息简介,各种输入之间以空格隔开。
当输入完毕后回车,景点也就成功加入了,然后用户可以再次选择第八项操作浏览所有景点名称,检测新输入的景点就是否已经成功添加。
如果您想进行“删除景点”操作,可以输入数字‘5’,回车后系统将会提示您输入要删除的景点的名称,您可以输入您想要删除的景点的名称,然后回车,这样删除景点的操作就已经完成,您同样可以选择第八项操作,检测就是否成功删除了景点。
如果您想进行“增加道路”操作,您可以输入数字‘6’,然后回车,系统将会提示您输入增加道路所连接的两个景点的名称,输入两景点名称后回车,然后系统又会提示输入增加道路的长度,输入后回车,这时增加道路操作也就完了。
用户如果想要检查道路就是否增加成功可以进行“最短路径查询”操作。
如果您想进行“删除道路”操作,您可以输入数字‘7’,然后系统就会提示您输入删除道路所连接的两景点的名称,输入名称后回车即可,当然,如果您想检测删除就是否成功您可以选择“最短路径查询”操作。
备注:
经过测试,本程序的所有操作都能正常执行,您可以选择性的对她进行操作,同时也可以混合着操作,混合操作就是检测错误的最好的一个方法。
5,测试数据及测试结果:
菜单显示为:
****************菜单**********************
1,相关信息查询
2,最短路径查询
3,修改景点信息
4,增加景点
5,删除景点
6,增加道路
7,删除道路
8,浏览所有景点名称
*******************************************
请选择您想进行的操作:
8
东区博物馆主楼图书馆西体育馆隧道北综北体育馆
北大门东湖
请选择您想进行的操作:
1
请输入您所想要查询的景点的名称:
博物馆
您输入的景点的名称就是:
博物馆
您输入的景点的代码为:
11
您输入的景点的相关信息有:
有各种化石
请选择您想进行的操作:
2
请输入您要查询的两景点的名称:
东区东湖
最短路径为:
108
从东区点到东湖景点的最短路径为:
东区——>主楼——>西体育馆——>隧道——>北大门——>东湖
请选择您想进行的操作:
3
您想修改的景点的名称为:
隧道
您输入的景点的名称就是:
隧道
您输入的景点的代码为:
15
您输入的景点的相关信息有:
自主修建
您想修改什么信息？
1,名称;2,代号;3,信息简介:
1
请输入要修改的的景点的新名称:
地大隧道
请选择您想进行的操作:
8
东区博物馆主楼图书馆西体育馆地大隧道北综北体育馆北大门东湖
请选择您想进行的操作:
4
请输入增加节点的名称,代号,信息简介:
北一楼34教师办公室
请选择您想进行的操作:
1
请输入您所想要查询的景点的名称:
北一楼
您输入的景点的名称就是:
北一楼
您输入的景点的代码为:
34
您输入的景点的相关信息有:
教师办公室
请选择您想进行的操作:
5
请输入您要删除景点的名称:
北一楼
请选择您想进行的操作:
8
东区博物馆主楼图书馆西体育馆地大隧道北综北体育馆北大门东湖
请选择您想进行的操作:
6
输入您要增加的道路链接的两个景点名称:
东区北综
输入您要增加的道路的长度:
50
请选择您想进行的操作:
2
请输入您要查询的两景点的名称:
东区北综
最短路径为:
50
从东区点到北综景点的最短路径为:
东区——>北综
请选择您想进行的操作:
7
输入您要删除的道路链接的两个景点名称:
东区北综
请选择您想进行的操作:
2
请输入您要查询的两景点的名称:
东区北综
最短路径为:
103
从东区点到北综景点的最短路径为:
东区——>主楼——>西体育馆——>地大隧道——>北大门——>北综
6,源程序清单:
school、cpp//程序源文件
AdjMGraph、h//图的相关操作头文件
AdjMGraphCreat、h//创建图的头文件
SeqList、h//线性表操作头文件
Floyd、h//Floyd算法头文件
Operation、h//自己所定义的一些操作的头文件
Inquiry、h//查询信息包含的头文件
//详细school、cpp程序源文件
#include
#include
#include
#defineMaxSize20//线性表的最大数组空间
#defineMaxVertices20//景点个数所允许的最大值
#defineMaxWeight1000//无穷边权值
#include"Floyd、h"
#include"AdjMGraphCreat、h"
#include"Inquiry、h"
AdjMGraphG;
#include"Operation、h"
voidmain（）
{
//初始景点信息
DataTypea[]={{"东区",10,"研究生院"},{"博物馆",11,"有各种化石"},{"主楼",12,"学校的标志建筑"},{"图书馆",13,"藏书50万册"},{"西体育馆",14,"主要供西区学生使用"},{"隧道",15,"自主修建"},{"北综",16,"北区标志楼"},{"北体育馆",17,"主要供北区学生使用"},{"北大门",18,"外出通道"},{"东湖",19,"武汉最美的湖"}};
//邻接矩阵的表示
RowColWeightrcw[]={{0,1,20},{0,2,30},{0,3,35},{1,0,20},{1,3,20},{2,0,30},{2,3,15},{2,4,30},{3,0,35},{3,1,20},{3,2,15},{3,4,30},{4,2,30},{4,3,30},{4,5,10},{5,4,10},{5,6,35}
{5,8,8},{6,5,35},{6,7,20},{6,8,25},{6,9,5},{7,6,20},{7,8,10},{8,5,8},{8,6,25},{8,7,10},{9,6,5};
intn=10,e=28;//景点数与边数
Creat（&G,a,rcw,n,e）;//构造图
menu（）;
}
//详细Floyd、h头文件
voidFloyd（intcost[][MaxVertices],intn,intweight[][MaxVertices],intpath[][MaxVertices]）
{
//初始化
inti,j,k;
for（i=0;i{
for（j=0;j{
weight[i][j]=cost[i][j];
path[i][j]=-1;
}
}
//n次递推
for（k=0;k{
for（i=0;i{
for（j=0;j{
if（weight[i][j]>weight[i][k]+weight[k][j]）
{
weight[i][j]=weight[i][k]+weight[k][j];
path[i][j]=k;
}
}
}
}
}
//详细Inquiry、h头文件
voidInformation（AdjMGraphG,charscenery[]）
{
inti;
for（i=0;i{
if（strcmp（G、vertices、list[i]、name,scenery）==0）
{
printf（"您输入的景点的名称就是:
%s\n",G、vertices、list[i]、name）;
printf（"您输入的景点的代码为:
%d\n",G、vertices、list[i]、code）;
printf（"您输入的景点的相关信息有:
%s\n\n",G、vertices、list[i]、introduction）;
break;
}
}
if（i==G、vertices、size）
{
printf（"您所查询的景点不在我们所提供的范围内！
\n\n"）;
}
}
voidPath（AdjMGraphG,charsceneryname[],charsceneryname1[]）
{
inti,j,k,n
升级会员 