校园导航系统

PAGEPAGE4题号：第七题题目：校园导航问题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()函数就是一个菜单供使用者来选择他所要进行的相关操作，比如信息的查询，最短路径查询之类。main()main()menu()Creat()menu()Creat()对于要求1：以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。图的创建设计流程图为：Creat()main()Creat()main() Creat()函数原型为：voidCreat(AdjMGraph*G,DataTypev[],RowColWeightE[],intn,inte)其中，G为所创建的图结构体对象，v[]为所有顶点的集合，它是DataType型，这个类型前面已经介绍过；E[]存放着各顶点之间的连接关系，它是RowColWeight型，前面也介绍过；n表示顶点的个数；e表示边数。Creat()函数的功能就是实现图的创建，将已知的景点的一些信息，转换成图的信息，并进行存储。menu()对于要求2：为来访客人提供图中任意景点相关信息的查询。流程图为：menu()Information()Information1()Information()Information1() menu()函数的原型为：2，找到它们的相对位置；3，if(删除道路)，将连接它们的边置为MaxWeight；if(增加道路)，将输入的边值赋给相应的邻接矩阵表；3，调试分析：<1>，调试过程中遇到的问题与解决方案：1,关于最短路径的输出问题。在进行最短路径输出时，我刚开始时只能正序输出，具体的描述为：比如，我要查寻从东区到东湖的最短路径，那么它能正确输出结果，他的形式为：东区——>主楼——>西体育馆——>隧道——>北大门——>东湖。但是，当我逆向输出时，得到的结果却有点问题，经过分析调试后，找到了错误的所在。在找最短路径的时候我用的是Floyd算法，在这个算法中有三重循环，形式均为：for(k=0;k<n;k++)，它们都是从零开始的，所以在顺序输出时没问题，但是逆序的时候就需要进行一个判断，正序与逆序循环输出是相反的。2，关于新增加景点后再找最短路径问题。比如我再新增一个景点，如北区食堂，并输入相关信息，然后插入到线性表尾，当我再找从东区到东湖的最短距离时，输出的最短路径将变为：东区——>食堂——>东湖。经过分析调试后，其原因也是出在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<stdio.h>#include<string.h>#include<malloc.h>#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<n;i++) { for(j=0;j<n;j++) { weight[i][j]=cost[i][j]; path[i][j]=-1; } } //n次递推 for(k=0;k<n;k++) { for(i=0;i<n;i++) { for(j=0;j<n;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<G.vertices.size;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,m,count=0; n=G.vertices.size; intweight[MaxVertices][MaxVertices],path[MaxVertices][MaxVertices]; intvalue[MaxVertices]; for(i=0;i<G.vertices.size;i++) { if(strcmp(G.vertices.list[i].name,sceneryname)==0) { j=i; } if(strcmp(G.vertices.list[i].name,sceneryname1)==0) { k=i; } } Floyd(G.Edge,n,weight,path); m=path[j][k]; printf("最短路径为：%d\n",weight[j][k]); if(m==-1) { printf("从%s点到%s景点的最短路径为：\n",sceneryname,sceneryname1); printf("%s——>%s\n",sceneryname,sceneryname1); } else { while(m!=-1) { value[count]=m; if(j<k) k=m; elsej=m; m=path[j][k]; count++; } printf("从%s点到%s景点的最短路径为：\n",sceneryname,sceneryname1); printf("%s——>",sceneryname); if(j<k) { for(i=count-1;i>=0;i--) { printf("%s——>",G.vertices.list[value[i]].name); } printf("%s\n",sceneryname1); } else { for(i=0;i<count;i++) { printf("%s——>",G.vertices.list[value[i]].name); } printf("%s\n",sceneryname1); } } }//详细Operation.h头文件voidmenu();//查询景点信息的函数voidInformation1(){ charsceneryname[20]; printf("请输入您所想要查询的景点的名称："); scanf("%s",sceneryname); Information(G,sceneryname); menu();}//查询最短路径的函数voidPath1(){ charsceneryname[20],sceneryname1[20]; printf("请输入你要查询的两景点的名称："); scanf("%s%s",sceneryname,sceneryname1);Path(G,sceneryname,sceneryname1); menu(); printf("\n");}//修改景点信息的函数voidModify(){ charsceneryname[20]; inti,x; printf("您想修改的景点的名称为："); scanf("%s",sceneryname); Information(G,sceneryname); for(i=0;i<G.vertices.size;i++) { if(strcmp(G.vertices.list[i].name,sceneryname)==0) { printf("您想修改什么信息？1，名称；2，代号；3，信息简介:"); scanf("%d",&x); if(x==1) { printf("请输入要修改的的景点的新名称："); scanf("%s",G.vertices.list[i].name); break; } if(x==2) { printf("请输入要修改的的景点的新代号："); scanf("%d",&(G.vertices.list[i].code)); break; } if(x==3) { printf("请输入要修改的的景点的新信息简介："); scanf("%s",G.vertices.list[i].introduction); break; } } } menu();}//增加景点的函数voidAddVertic(){ inti,k; DataTypever;printf("请输入增加节点的名称，代号，信息简介:\n"); scanf("%s%d%s",,&(ver.code),roduction); ListInsert(&(G.vertices),G.vertices.size,ver); k=G.vertices.size-1; for(i=0;i<G.vertices.size;i++) { if(k!=i) { G.Edge[k][i]=MaxWeight; G.Edge[i][k]=MaxWeight; } elseG.Edge[k][i]=0; } menu();}voidDeleteVertic(){ DataTypex; charname[20]; inti,k; printf("请输入您要删除景点的名称：");scanf("%s",name);for(i=0;i<G.vertices.size;i++) { if(strcmp(G.vertices.list[i].name,name)==0) { k=i; } } ListDelete(&(G.vertices),k,&x); for(i=0;i<G.vertices.size;i++) { if(k!=i) { G.Edge[k][i]=MaxWeight; G.Edge[i][k]=MaxWeight; } elseG.Edge[k][i]=0; } menu();}//删除景点的函数voidAddRoad(){ charname[20],name1[20]; intlength,i,j,k;printf("输入您要增加的道路链接的两个景点名称：");scanf("%s%s",name,name1); printf("输入您要增加的道路的长度:"); scanf("%d",&length); for(i=0;i<G.vertices.size;i++) { if(strcmp(G.vertices.list[i].name,name)==0) { j=i; } if(strcmp(G.vertices.list[i].name,name1)==0) { k=i; } }InsertEdge(&G,j,k,length);InsertEdge(&G,k,j,length); menu();}voidDeleteRoad(){ charname[20],name1[20]; inti,j,k;printf("输入您要删除的道路链接的两个景点名称：");scanf("%s%s",name,name1); for(i=0;i<G.vertices.size;i++) { if(