校园导航系统0001

1、-/题号：第七题题目：校园导航问题1, 需求分析:设计你的学校的平面图，至少包括10个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径）。要求:（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路 径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询 ，即查询任意两个景点之间的一条最短路径。（4）修改景点信息。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均 含有相关信息。选做内容：（1）提供图的编辑功能：增

2、、删景点；增、删道路；修改已有信息等。（2）校园导游图的仿真界面。2, 设计:2.1设计思想:<1>，数据结构设计：（1 ）图。采用邻接矩阵存储，其中图所用到的结构体为：typ edef structSeqList vertices;/表示图中的顶点int EdgeMaxVerticesMaxVertices;/ 表示图中的边int numOfEdge;表示图中边的数目AdjMGra ph;(2)景点。用顺序表存储。所用到的结构体为:typ edef struct顶点名称/顶点代号/顶点信息简介char n ame20;int code;char in troducti on 50

3、;DataT ype;(3) 景点之间的连接描述，所用到的结构体为：typ edef structint row;int col;int weight; RowColWeight;用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其中包括景点的名称，代号，信息简介，以及其它的一些信息。这样就将对景点的操作，变成对图中各顶点的操作。<2>，算法设计：关于本课题的算法，很大部分来源于这学期数据结构课程的学习，其中包括： 图的创建，线性表的一些操作。对于具体的问题实现，都有不同的算法，在下面的分析中, 我将详细说明2.2设计表示:<1>,函数调用关系及函数说明：

4、首先，main()函数调用Creat()函数，用来创建图，然后调用menu()函数来选择用户所要进行的操作。其中 men u()函数就是一个菜单供使用者来选择他所要进行的相关操作，比如 信息的查询，最短路径查询之类。对于要求1:以图中顶点表示校园内各景点，存放景点名称、代号、简介等信 息；以边表示路径，存放路径长度等有关信息。图的创建设计流程图为：mai n()Creat()Creat()函数原型为：void Creat(AdjMGraph *G , DataType v, RowColWeight E, int n,int e)其中，G为所创建的图结构体对象，v为所有顶点的集合，它是Data

5、Type型，这个类型前面已经介绍过；E存放着各顶点之间的连接关系，它是RowColWeight型,前面也介绍过；n表示顶点的个数；e表示边数。Creat()函数的功能就是实现图的创建，将已知的景点的一些信息，转换成图的信息，并进行存储。对于要求2:为来访客人提供图中任意景点相关信息的查询。流程图为:menu()In formatio n1()*1 In formatio n()menu()函数的原型为:void men u()他就是一个菜单，供用户选择他们所要进行的操作。Information)函数原型为：voidIn formatio n1()它的功能就是输入查询景点的信息，并调用In fo

6、rmatio n()Information()函数原型为：void Information(AdjMGraph G , char seenery) G 依然是所创建的图的结构体对象，后面所有的 G都是表示这个意思；seenery是在Information1()中输入的景点的 名称。此函数的功能就是根据输入的景点的名称来查询其相关的信息。对于要求3:为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条 最短路径。流程图为：menu()Path1()Path()1 Floyd()P ath1()函数原型为：Path()void Path1()它的功能就是输入查询景点的名称，并调用Path

7、 ()函数原型为：void Path(AdjMGraph G ,char sceneryname, char sceneryname1) 其中seeneryname, seeneryname1就是在 Path1()函数中所输入的景点的名称，这个函数的功能就是通过这两个景点的名称找到它们在线性表中的位置，然后调用Floyd()函数，查找出它们的最短路径，并输出所要的信息。Floyd()函数原型为：void Floyd (in t cost MaxVertices,i nt n,i nt weightMaxVertices,i nt p athMaxVertices) 其中参数cost MaxVe

8、rtices即是图中边的邻接存储矩阵，weightMaxVertices用来存放经此算法后的各顶点间的最短路径的值，PathMaxVertices就是每两个顶点之间最短路径中到达目的顶点的前一个顶点的位置。P ath()函数中的输出信息就是据此而来。对于要求4:修改景点信息。流程图为:menu()* Modify()ModifyO函数原型为：void ModifyO 它不带任何参数，功能是通过手动输入景点名称，然后找到景点的 存储空间，然后在修改相应的信息。对于选做要求：增加景点。其工作流程图为：menu()* AddVertic()*1 ListI nsert()AddVerticO函数原型

9、为：void AddVertic()他不带任何参数，该函数的功能是在这个函数里面输入景点的信息，然后调用ListInsert()函数，将所要增加的顶点信息插入到线性表中。Listlnsert()函数原型为：voidListInsert(SeqList *L, int i, DataType x)参数 L 表示顶点存储的线性表，i 表示要插入的位置,x表示要插入的景点的信息。同时我在插入顶点时也将他与其他顶点之间的距 离设置为Maxweight，这样做主要是为了方便在Floyd函数里面求最短路径对于选做要求：删除景点。其工作流程图为menu()DeleteVertic()*1 ListDelet

10、e ()DeleteVerticO函数原型为：void DeleteVerticO他不带任何参数，该函数的功能就是在函数体里面输入要删除的景点的名称，然后根据名称找到该景点在线性表中的存储位置，然后调用线性表中的ListDelete ()函数进行相应顶点的删除。ListDelete ()函数原型为：ListDelete(SeqList *L, int i, DataType *x) 其中参数 L为存放顶点信息的线性表，i表示要删除顶点在线性表中的存放位置，,x就是要删除的那一个景点。它的功能就是从线性表中删除指定的顶点。对于选做要求：增、删道路，流程图为：AddRoadO和DeleteRoad

11、()两函数原型为：void AddRoadO和void DeleteRoad()。这两个函数都不带参数，它们的功能就是在这两 个函数里面输入要删除要增加或者的边连接的两个景点的名称，然后在线性表中找到这两个景点的相对存储空间，最后调用InsertEdge ()或者DeleteEdge ()函数。InsertEdge ()和 DeleteEdge ()两函数原型为：void InsertEdge(AdjMGraph *G , int v1, int v2, int weight)void DeleteEdge(AdjMGraph *G, int v1, int v2) 这两个函数中同名参数所代表

12、的意义 是相同的，其中v1, v2是所输入景点在线性表中的相对位置；weight就是增加的边的权值<2>函数接口说明我所设计整个程序就是一些子函数的集合，每个功能都对应一个或者几个子函数，他们之间可以没有任何限制，只要能保证程序正确运行就可以调用，特别是AdjMGra ph.h,AdjMGraph.h和SeqList.h头文件之中的函数，他们被很多函数调用过。这其中都没有任何 特殊类型的函数2.3详细设计:根据题目分析，对于信息查询与修改功能，设计如下：1, 输入景点名称2, 从线性表头扫描到表尾，if(找到该景点)输出景点结构体信息 else输出提示信息找不到该顶点实现查找最短路

13、径，设计如下：景点名称根据输入的信息找到它们所在的线性表中的位置 调用Floyd算法找出最短路径输出信息1，2，3，4，实现增删景点功能，设计如下：1, 增加或者删除景点的名称2, if(输入景点)，将景点信息保存在相应的结构体中，并插入到线性表尾；if(删除景点)，找到景点在线性表中所在的位置，然后将景点信息从线性表中删除实现增删道路功能，设计如下：1,入增加或删除道路连接的两个景点的名称；2, 找到它们的相对位置；3, if(删除道路)，将连接它们的边置为 Maxweight ;if(增加道路)，将输入的边值赋给相应的邻接矩阵表;3, 调试分析:1，调试过程中遇到的问题与解决方案：1, 关

14、于最短路径的输出问题。在进行最短路径输出时，我刚开始时只能正序输出， 具体的描述为：比如，我要查寻从东区到东湖的最短路径，那么它能正确输出结果，他的形式为：东区一一 主楼 一一 西体育馆 一一 隧道 一一 北大门 一一 东湖。但是，当我逆 向输出时，得到的结果却有点问题，经过分析调试后，找到了错误的所在。在找最短路径的时候我用的是Floyd算法，在这个算法中有三重循环，形式均为：for(k=0;kn;k+)，它们都是从零开始的，所以在顺序输出时没问题，但是逆序的时候就需要进行一个判断，正序与逆序循环输出是相反的。输出的最短路Floyd算法那,，由于2,关于新增加景点后再找最短路径问题。比如我再

15、新增一个景点，如北区食堂，并 输入相关信息，然后插入到线性表尾，当我再找从东区到东湖的最短距离时，径将变为：东区一一 食堂 一一 东湖。经过分析调试后，其原因也是出在在 Floyd 算法中，有这么一个判断if(weightijweightik+weightkj)我在输入新景点信息时并没有建立它与其它景点之间的连接信息，所以在图中，该新景点与其它景点之间的边得连接信息是空的，也就是说在邻接矩阵中，它的边得信息是空的， 那么在进行 if(weightijweightik+weightkj)判断时 weight新增景点序号其它景点序号的值将是一个很大的负数，所以最短路径将会出错。解决这个问题的方 法

16、就是在增加新景点时就将它与其它景点之间的边(距离)设置为MaxWeight，这时如果再用Floyd函数进行最短路径的求解时就不会再出现问题了。不过都比较容易解决，这里我就另外，在做这个题时也还出现过一些其他的小问题， 不再列出了2,算法的时空复杂度分析对应题目的要求，我总共提供了八个选项操作对于每一个操作的分析如下：1，相关信息的查询。在这个操作中允许使用者输入一个景点名称，然后再根据景点名称来或取其相关的信息，这个操作要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(n);2, 最短路径查询。实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为 o(n人3

17、)，空间复杂度为o(1);3, 修改景点信息。要修改信息，必须首先找到景点所在的存储位置，那么就需要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(1);4, 增加景点。增加景点信息时，直接将此景点结构体信息插入到线性表表尾，而不需要进行遍历，其时间复杂度与空间复杂度均为o(1);5, 删除景点。删除景点时必须找到所要删除景点所在的位置，这样就必须遍历线性表，除此之外，删除后线性表还要进行移动操作，其时间复杂度为o(n),空间复杂度为 0( n1);6, 增加道路。增加道路也要扫描线性表，找到要增加路的两景点的存储位置，然后再根据找到的存储位置去改变邻接矩阵的边的值，改变邻接矩阵的时间复杂

18、度为0(1),其总时间消耗在线性表的扫描上，故最终其时间复杂度为o( n)，空间复杂度为o(1);7, 删除道路。删除道路和增加道路类似，都是先找到存储位置，然后再改变邻接矩阵， 它的时空复杂度分别为 o(n) , o(1);8，浏览所有景点。浏览所有景点的实质就是从头到尾遍历线性表，然后输出遍历到的 节点的信息，其时间复杂度为0(n),空间复杂度为0(1)。4, 用户手册：使用说明：当用户将程序经过编译，连接后，点击运行，在DOS环境里面将看到一个操作。选项菜单，菜单里面提供了 8种操作，同时输出了一行提示信息：请选择您想进行的操作。 然后用户可以输入一个 18之间的数字进行选择性的操作，例

19、如，您想进行信息的查询 操作，您可以从键盘输入数字 1'当然，一般而言先应该进行 “浏览所有景点名称”如果您选择了浏览所有景点名称操作，在屏幕上将会显示出10个景点的名称，这些景点是事先加进去的，用户可以对这些景点进行任何程序所提供的操作。菜单将会继续显示出来，为下面，我将详细介绍本程序的使用方法：在浏览景点后， 您提供操作选择。1',然后程序将会提醒您输入查2'，然后程序将会提醒您输入 要注意的是景点名称间如果您想进行“相关信息的查询”操作，输入数字 询景点的名称，在您输入景点名称后回车即可。如果您想进行“最短路径查询”操作，首先输入数字 查询的景点的名称，您输入按要

20、求输入所提供的两个景点名称即可， 以空格隔开，最后程序就会告诉您最短的路径，以及最短路的长度。如果您想修改景点的信息，同样先输入数字3然后程序就会提醒您输入所要修改景点的名称，您可以根据要求输入一个景点的名称，然后回车，之后屏幕上就会显示您所输入的景点的所有信息，同时会有三个修改选项供用户选择，然后您可以输入13之间的一个数字进行选择性的修改。比如，您可以输入1'对景点名称进行修改，修改完后又会返回到菜单项继续选择。如果您想进行“增加景点”操作，可以输入数字4',然后程序就会提示您输入新增加的景点的名称，代号，信息简介，各种输入之间以空格隔开。当输入完毕后回车，景点也 就成功加

21、入了，然后用户可以再次选择第八项操作浏览所有景点名称，检测新输入的景点是否已经成功添加。如果您想进行“删除景点”操作，可以输入数字5'，回车后系统将会提示您输入要删除的景点的名称，您可以输入您想要删除的景点的名称，然后回车，这样删除景点的操作就已经完成，您同样可以选择第八项操作，检测是否成功删除了景点。如果您想进行“增加道路”操作，您可以输入数字 6'，然后回车，系统将会提示您 输入增加道路所连接的两个景点的名称， 输入两景点名称后回车， 然后系统又会提示输入增 加道路的长度，输入后回车，这时增加道路操作也就完了。 用户如果想要检查道路是否增加 成功可以进行“最短路径查询”操作

22、。如果您想进行“删除道路”操作，您可以输入数字 7'，然后系统就会提示您输入删 除道路所连接的两景点的名称， 输入名称后回车即可，当然，如果您想检测删除是否成功您 可以选择“最短路径查询”操作。备注：经过测试，本程序的所有操作都能正常执行，您可以选择性的对他进行操作， 同时也可以混合着操作，混合操作是检测错误的最好的一个方法。-/5, 测试数据及测试结果:菜单显示为:*单 *1, 相关信息查询2, 最短路径查询3, 修改景点信息4, 增加景点5, 删除景点6, 增加道路7, 删除道路8, 浏览所有景点名称幵*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*2,8请选择您想进行的操作:4

23、请选择您想进行的操作： 东区 博物馆主楼 北大门东湖8图书馆西体育馆隧道 北综北体育馆请选择您想进行的操作：请输入您所想要查询的景点的名称: 您输入的景点的名称是： 您输入的景点的代码为： 您输入的景点的相关信息有：博物馆博物馆11有各种化石请选择您想进行的操作：请输入你要查询的两景点的名称：最短路径为：108从东区点到东湖景点的最短路径为：东区一一 主楼一一 西体育馆一一 隧道一一 北大门一一 东湖东区东湖请选择您想进行的操作： 您想修改的景点的名称为： 您输入的景点的名称是： 您输入的景点的代码为： 您输入的景点的相关信息有:3隧道隧道15自主修建您想修改什么信息？1,名称;请输入要修改的

24、的景点的新名称： 请选择您想进行的操作： 东区 博物馆主楼 体育馆 北大门东湖代号；3，信息简介：1 地大隧道图书馆西体育馆地大隧道北综 北-/请输入增加节点的名称，代号，信息简介北一楼34教师办公室请选择您想进行的操作：1请输入您所想要查询的景点的名称： 您输入的景点的名称是：北一楼您输入的景点的代码为：34您输入的景点的相关信息有：教师办公室北一楼请选择您想进行的操作：5请输入您要删除景点的名称：北一楼请选择您想进行的操作： 东区 博物馆主楼 体育馆北大门东湖8图书馆西体育馆地大隧道北综 北请选择您想进行的操作：输入您要增加的道路链接的两个景点名称: 输入您要增加的道路的长度：50 请选择

25、您想进行的操作：2请输入你要查询的两景点的名称： 最短路径为：50从东区点到北综景点的最短路径为: 东区 > 北综东区东区北综请选择您想进行的操作：7输入您要删除的道路链接的两个景点名称： 请选择您想进行的操作：2请输入你要查询的两景点的名称： 最短路径为：103 从东区点到北综景点的最短路径为： 东区 > 主楼 > 西体育馆 > 地大隧道东区东区北综北综北综>北大门一一 >北综6,源程序清单:school.c PPAdjMGra ph.hAdjMGra phCreat.hSeqList.hFloyd.hOp erati on.hIn quiry.h/程序源

26、文件/图的相关操作头文件/创建图的头文件线性表操作头文件/Floyd算法头文件/自己所定义的一些操作的头文件/查询信息包含的头文件II 详细 school.cpp程序源文件#i nclude <stdio.h>#in elude <stri ng.h>#in elude <malloc.h>#defi ne MaxSize 20#defi ne MaxVertices 20#defi ne MaxWeight 1000/线性表的最大数组空间/景点个数所允许的最大值/无穷边权值#i nclude "Floyd.h"#i nclude &qu

27、ot;AdjMGra phCreat.h"#in clude "I nqu iry.h"AdjMGra ph G;#in elude "Op eratio n.h" void mai n()/初始景点信息DataType a="东区",10,"研究生院”博物馆",11,"有各种化石”主楼",12,"学 校的标志建筑" ,"图书馆",13,"藏书50万册","西体育馆",14,"主要供西区学 生使用

28、","隧道",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,3

29、0,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;int n=10,e=28;/景点数与边数Creat(&G,a,rcw, n,e);构造图menu();/详细Floyd.h头文件void Floyd(i nt costMaxVertices,i nt n,i nt weightMaxVertices,i nt p athMaxVertices) /初始化int i,j,k;for(i=0;i< n; i+)f

30、or(j=0;j< n;j+)weightij=costij; p athij=-1;/n次递推 for(k=0;k< n; k+) for(i=0;i <n ;i+)for(j=0;j< n;j+)if(weightij>weightik+weightkj)weightij=weightik+weightkj; pathij=k;头文件/详细void In formati on( AdjMGra ph G , char sce nery)In quiry.hint i;for(i=0;i<G .vertices.size;i+)if(strcmp(G .v

31、,scenery)=0) printf(”您输入的景点的名称是： printf(”您输入的景点的代码为： printf(”您输入的景点的相关信息有： break;%sn"Gvertices.listi. name);%dn",G.vertices.listi.code);%snn",G.vertices.listi.i ntroductio n);-/if(i=G.vertices.size)nrr);printf("您所查询的景点不在我们所提供的范围内!void P ath(AdjMGra ph G,char sce

32、neryn ame, char sceneryn ame1) int i,j,k ,n, m,co un t=0;n=G.vertices.size;int weightMaxVerticesMaxVertices, pathMaxVerticesMaxVertices;int valueMaxVertices;for(i=0;i<G .vertices.size;i+)if(strcmp(G .,sceneryname)=0)j=i;if(strcmp(G .,sceneryname1)=0)k=i;Floyd

33、(G.Edge ,n, weight, path);m=p athjk;printf(” 最短路径为：%dn”,weightjk);if(m=-1)printf(” 从 %s 点到 %s 景点的最短路径为：n”,seeneryname,sceneryname1);prin tf("%s>%sn ”,see neryn ame,sce neryn ame1);else while(m!=-1)valueco un t=m; if(j<k) k=m; else j=m;m=p athjk; coun t+;printf(” 从 %s 点到 %s 景点的最短路径为：n”,see

34、neryname,sceneryname1);prin tf("%s>",sce neryn ame);if(j<k)for(i=co un t-1;i>=0;i-)prin tf("%s>",G.vertices.listvaluei. name); prin tf("%sn",sce neryn ame1);elsefor(i=0;i<co un t;i+)prin tf("%s>",G .vertices.listvaluei. name);prin tf("%s

35、n",sce neryn ame1);/详细Operation.h头文件 void menu();/查询景点信息的函数void In formati on 1()char sceneryn ame20;”);”);printf(”请输入您所想要查询的景点的名称: sca nf("%s",sce neryn ame);In formati on(G ,sce neryn ame);menu();/查询最短路径的函数void P ath1()char sceneryn ame20,sce neryn ame120;printf(”请输入你要查询的两景点的名称：sca

36、nf("%s%s",sce neryn ame,sce neryn ame1);P ath(G,sce neryn ame,sce neryn ame1);menu();prin tf("n");-/修改景点信息的函数void ModifyOchar sceneryn ame20;int i,x;printf(”您想修改的景点的名称为：sca nf("%s",sce neryn ame);Information(G ,sceneryname);for(i=0;i<G .vertices.size;i+)if(strcmp(G .

37、,sceneryname)=0) printf(”您想修改什么信息？1,名称；2，scan f("%d"，& x);if(x=1)printf("请输入要修改的的景点的新名称：sca nf("%s",G.vertices.listi. name); break;if(x=2)printf("请输入要修改的的景点的新代号： scanf("%d",&(G .vertices.listi.code);break;if(x=3)printf("请输入要修改的的

38、景点的新信息简介: sca nf("%s",G.vertices.listi.i ntroduct ion);break;menu();”);代号；3,信息简介：");”);");");/增加景点的函数void AddVertic()int i,k;DataT ype ver;printf(”请输入增加节点的名称，代号，信息简介:n");sca nf("%s%d%s",ver. name,&( ver.code),ver.i ntroduct ion);ListInsert(&(G .vertice

39、s), G.vertices.size, ver); k= G.vertices.size-1;for(i=0;i<G .vertices.size;i+)if(k!=i)G.Edgeki=MaxWeight;G.Edgeik=MaxWeight;else G.Edgeki=0;menu();void DeleteVertic()DataT ype x;char n ame20;int i,k;”);printf(”请输入您要删除景点的名称：sca nf("%s", name);for(i=0;i<G.vertices.size;i+)if(strcmp(G .

40、,name)=0) k=i;ListDelete(&(G .vertices),k，&x);for(i=0;i<G .vertices.size;i+)if(k!=i)G.Edgeki=MaxWeight;G.Edgeik=MaxWeight;else G.Edgeki=0;menu();删除景点的函数void AddRoad()char name20, name120;int len gth,i,j,k;printf("输入您要增加的道路链接的两个景点名称:sca nf("%s%s", name ,n