校园导航系统

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

2、内容： （1）提供图的编辑功能：增、删景点；增、删道路；修改已有信息等。 （2）校园导游图的仿真界面。 2，设计： 设计思想： ，数据结构设计 ： （1）图。采用邻接矩阵存储，其中图所用到的结构体为： typedef struct /表示图中的顶点 /表示图中的边 /表示图中边的数目 SeqList vertices; int EdgeMaxVerticesMaxVertices; int numOfEdge; AdjMGraph; 2）景点。用顺序表存储。所用到的结构体为： typedef struct char name20;/顶点名称 int code;/顶点代号 char introd

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

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

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

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

7、har sceneryname, char sceneryname1) 其中seeneryname, seeneryname1就是在 Path1()函数中所输入的景点的名称，这 个函数的功能就是通过这两个景点的名称找到它们在线性表中的位置，然后调用Floyd() 函数，查找出它们的最短路径，并输出所要的信息。 Floyd()函数原型为： void Floyd (int cost MaxVertices,int n,int weightMaxVertices,int pathMaxVertices) 其中参数cost MaxVertices即是图中边的邻接存储矩阵，weightMaxVertic

8、es用来存放经 此算法后的各顶点间的最短路径的值，pathMaxVertices就是每两个顶点之间最短路径中 到达目的顶点的前一个顶点的位置。Path()函数中的输出信息就是据此而来。 对于要求4:修改景点信息。流程图为： Modify()函数原型为： void Modify()它不带任何参数，功能是通过手动输入景点名称，然后找到景点的 存储空间，然后在修改相应的信息。 对于选做要求：增加景点。其工作流程图为： AddVertic()函数原型为： void AddVertic()他不带任何参数，该函数的功能是在这个函数里面输入景点的信 息，然后调用ListInsert()函数，将所要增加的顶点

9、信息插入到线性表中。 List In sert()函数原型为： voidListInsert(SeqList *L, int i, DataType x) 参数 L 表示顶点存储的线性表，i 表示 要插入的位置,x表示要插入的景点的信息。同时我在插入顶点时也将他与其他顶点之间的距 离设置为MaxWeight，这样做主要是为了方便在Floyd函数里面求最短路径 对于选做要求：删除景点。其工作流程图为 DeleteVertic()函数原型为: void DeleteVertic()他不带任何参数，该函数的功能就是在函数体里面输入要删除的景 点的名称，然后根据名称找到该景点在线性表中的存储位置，然后

10、调用线性表中的 ListDelete ()函数进行相应顶点的删除。 ListDelete ()函数原型为： ListDelete(SeqList *L, int i, DataType *x)其中参数 L为存放顶点信息的线性表，i表示 要删除顶点在线性表中的存放位置，,x就是要删除的那一个景点。它的功能就是从线性表中 删除指定的顶点。 对于选做要求：增、删道路，流程图为： AddRoad()和 DeleteRoad()两函数原型为： void AddRoad()和void DeleteRoad()。这两个函数都不带参数，它们的功能就是在这两 个函数里面输入要删除要增加或者的边连接的两个景点的名

11、称，然后在线性表中找到这两个 景点的相对存储空间，最后调用InsertEdge ()或者DeleteEdge ()函数。 InsertEdge ()和 DeleteEdge ()两函数原型为： void InsertEdge(AdjMGraph *G , int v1, int v2, int weight) void DeleteEdge(AdjMGraph *G, int v1, int v2) 这两个函数中同名参数所代表的意义 是相同的，其中v1, v2是所输入景点在线性表中的相对位置；weight就是增加的边的权值 函数接口说明 我所设计整个程序就是一些子函数的集合，每个功能都对应一个

12、或者几个子函数， 他们之间可以没有任何限制，只要能保证程序正确运行就可以调用，特别是 ,和头文件之中的函数，他们被很多函数调用过。这其中都没有任何特殊类型的函数 详细设计： 根据题目分析，对于信息查询与修改功能，设计如下： 1, 输入景点名称 2, 从线性表头扫描到表尾， if(找到该景点)输出景点结构体信息 else输出提示信息找不到该顶点 实现查找最短路径，设计如下： 1，景点名称 2，根据输入的信息找到它们所在的线性表中的位置 3, 调用Floyd算法找出最短路径 4, 输出信息 实现增删景点功能，设计如下： 1, 增加或者删除景点的名称 2, if(输入景点)，将景点信息保存在相应的结

13、构体中，并插入到线性表尾； if(删除景点)，找到景点在线性表中所在的位置，然后将景点信息从线性表中删除 实现增删道路功能，设计如下： 1, 入增加或删除道路连接的两个景点的名称； 2, 找到它们的相对位置； 3, if(删除道路)，将连接它们的边置为MaxWeight ; if( 增加道路 )，将输入的边值赋给相应的邻接矩阵表； 3,调试分析： ,调试过程中遇到的问题与解决方案： 1, 关于最短路径的输出问题。在进行最短路径输出时,我刚开始时只能正序输出, 具体的描述为： 比如,我要查寻从东区到东湖的最短路径,那么它能正确输出结果,他的形 式为：东区 主楼 西体育馆 隧道 北大门 东湖。但是

14、, 当我逆 向输出时, 得到的结果却有点问题, 经过分析调试后,找到了错误的所在。 在找最短路径的 时候我用的是 Floyd 算法,在这个算法中有三重循环,形式均为： for(k=0;k食堂 东湖。经过分析调试后,其原因也是出在Floyd 算法那, 在 Floyd 算法中,有这么一个判断 if(weightijweightik+weightkj),由于 我在输入新景点信息时并没有建立它与其它景点之间的连接信息,所以在图中, 该新景点与 其它景点之间的边得连接信息是空的, 也就是说在邻接矩阵中, 它的边得信息是空的, 那么 在 进 行if(weightijweightik+weightkj)判

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

16、杂度为 o(n) ,空间复杂度为 o(n) ； 2, 最短路径查询。实现这个功能用到了Floyd算法，他用到了一个三重的for()循环， 故其时间复杂度为 o(nA3)，空间复杂度为0(1); 3, 修改景点信息。要修改信息,必须首先找到景点所在的存储位置,那么就需要扫描 线性表，其时间复杂度为o(n)，空间复杂度为o(1); 4, 增加景点。增加景点信息时,直接将此景点结构体信息插入到线性表表尾,而不需 要进行遍历,其时间复杂度与空间复杂度均为 o(1)； 5, 删除景点。 删除景点时必须找到所要删除景点所在的位置, 这样就必须遍历线性表, 除此之外，删除后线性表还要进行移动操作，其时间复杂

17、度为o(n),空间复杂度为 o( n1); 6, 增加道路。增加道路也要扫描线性表,找到要增加路的两景点的存储位置,然后再 根据找到的存储位置去改变邻接矩阵的边的值，改变邻接矩阵的时间复杂度为0(1),其总时 间消耗在线性表的扫描上，故最终其时间复杂度为o( n)，空间复杂度为o(1); 7, 删除道路。删除道路和增加道路类似,都是先找到存储位置,然后再改变邻接矩阵, 它的时空复杂度分别为 o(n) , o(1)； 8, 浏览所有景点。浏览所有景点的实质就是从头到尾遍历线性表,然后输出遍历到的 4，用户手册： 使用说明：当用户将程序经过编译,连接后,点击运行,在DOS 环境里面将看到一个 选项

18、菜单,菜单里面提供了 8 种操作,同时输出了一行提示信息：请选择您想进行的操作。 然后用户可以输入一个 18 之间的数字进行选择性的操作,例如,您想进行信息的查询 操作, 您可以从键盘输入数字 1；当然, 一般而言先应该进行 “浏览所有景点名称” 操作。 如果您选择了浏览所有景点名称操作,在屏幕上将会显示出10 个景点的名称,这些景点是 事先加进去的,用户可以对这些景点进行任何程序所提供的操作。 下面,我将详细介绍本程序的使用方法：在浏览景点后,菜单将会继续显示出来,为 您提供操作选择。 如果您想进行“相关信息的查询”操作,输入数字1,然后程序将会提醒您输入查 询景点的名称,在您输入景点名称后

19、回车即可。 如果 您想进行“最短路径查询”操作,首先输入数字 2,然后程序将会提醒您输入 查询的景点的名称, 您输入按要求输入所提供的两个景点名称即可, 要注意的是景点名称间 以空格隔开,最后程序就会告诉您最短的路径,以及最短路的长度。 如果 您想修改景点的信息,同样先输入数字 3,然后程序就会提醒您输入所要修改 景点的名称, 您可以根据要求输入一个景点的名称, 然后回车, 之后屏幕上就会显示您所输 入的景点的所有信息,同时会有三个修改选项供用户选择,然后您可以输入13之间的 一个数字进行选择性的修改。比如,您可以输入1对景点名称进行修改,修改完后又会 返回到菜单项继续选择。 如果 您想进行“

20、增加景点”操作,可以输入数字4,然后程序就会提示您输入新增 加的景点的名称,代号,信息简介,各种输入之间以空格隔开。当输入完毕后回车,景点也 就成功加入了, 然后用户可以再次选择第八项操作浏览所有景点名称,检测新输入的景点是 否已经成功添加。 如果 您想进行“删除景点”操作,可以输入数字5,回车后系统将会提示您输入要 删除的景点的名称, 您可以输入您想要删除的景点的名称, 然后回车, 这样删除景点的操作 就已经完成,您同样可以选择第八项操作,检测是否成功删除了景点。 如果 您想进行“增加道路”操作,您可以输入数字6,然后回车,系统将会提示您 输入增加道路所连接的两个景点的名称, 输入两景点名称

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

22、, 增加景点 5, 删除景点 6, 增加道路 7, 删除道路 8, 浏览所有景点名称 * 请选择您想进行的操作：8 东区 博物馆主楼 图书馆西体育馆隧道 北综北体育馆 北大门东湖 请选择您想进行的操作：1 请输入您所想要查询的景点的名称：博物馆 您输入的景点的名称是：博物馆 您输入的景点的代码为：11 您输入的景点的相关信息有： 有各种化石 请选择您想进行的操作：2 请输入你要查询的两景点的名称：东区 东湖 最短路径为：108 从东区点到东湖景点的最短路径为： 东区 主楼 西体育馆 隧道 北大门 东湖 请选择您想进行的操作：3 您想修改的景点的名称为： 隧道 您输入的景点的名称是： 隧道 您输

23、入的景点的代码为： 15 您输入的景点的相关信息有: 自主修建 您想修改什么信息？1,名称；2,代号；3,信息简介：1 请输入要修改的的景点的新名称： 地大隧道 请选择您想进行的操作： 8 东区博物馆主楼 图书馆 西体育馆地大隧道 北综 北 体育馆 北大门东湖 请选择您想进行的操作：4 请输入增加节点的 名称，代号，信息简介 北一楼34教师办公室 请选择您想进行的操作： 1 请输入您所想要查询的景点的名称： 北一楼 您输入的景点的名称是： 北一楼 您输入的景点的代码为： 34 您输入的景点的相关信息有： 教师办公室 请选择您想进行的操作： 5 请输入您要删除景点的名称： 北一楼 请选择您想进行

24、的操作： 8 地大隧道 北综 东区 博物馆 主楼 图书馆 西体育馆 体育馆 北大门 东湖 请选择您想进行的操作： 6 输入您要增加的道路链接的两个景点名称： 东区 北综 输入您要增加的道路的长度 : 50 请选择您想进行的操作： 2 请输入你要查询的两景点的名称： 东区 北综 最短路径为： 50 从 东区 点到 北综 景点的最短路径为： 东区 北综 请选择您想进行的操作： 7 输入您要删除的道路链接的两个景点名称： 东区 北综 请选择您想进行的操作： 2 请输入你要查询的两景点的名称： 东区 北综 最短路径为： 103 从 东区 点到 北综 景点的最短路径为： 东区 主楼 西体育馆 地大隧道

25、北大门 北综 6，源程序清单： /程序源文件 /图的相关操作头文件 /创建图的头文件 /线性表操作头文件 /Floyd 算法头文件 /自己所定义的一些操作的头文件 /查询信息包含的头文件 / 详细 程序源文件 #include #include /线性表的最大数组空间 /景点个数所允许的最大值 /无穷边权值 #include #define MaxSize 20 #define MaxVertices 20 #define MaxWeight 1000 #include #include #include AdjMGraph G; #include void main() /初始景点信息 Da

26、taType a= 东区 ,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

27、,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( /构造图 menu(); / 详细头文件 void Floyd(int costMaxVertices,int n,int weightMaxVertices,int pathMaxVertices) /初始化 int i,j,k; for(i=0;in;i+) for(j=0;jn;j+) weightij=costij; pathij=-1;

28、 /n 次递推 for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jweightik+weightkj) weightij=weightik+weightkj; pathij=k; /详细 头文件 void Information(AdjMGraph G , char scenery) int i; for(i=0;i if(strcmp printf( 您输入的景点的代 %snn, break; nn); printf( 您输入的景点的名称是： %sn, 码为： %dn,printf( 您输入的景点的相关信息有 if(i= printf( 您所查询的景点不在我们所提

29、供的范围内！ void Path(AdjMGraph G,char sceneryname, char sceneryname1) int i,j,k,n,m,count=0; n= int weightMaxVerticesMaxVertices,pathMaxVerticesMaxVertices; int valueMaxVertices; for(i=0;i%sn,sceneryname,sceneryname1); else while(m!=-1) valuecount=m; if(j,sceneryname); if(j=0;i-) printf(%s , printf(%sn,

30、sceneryname1); else for(i=0;i, printf(%sn,sceneryname1); /详细头文件 void menu(); /查询景点信息的函数 void Information1() char sceneryname20; printf( 请输入您所想要查询的景点的名称： ); scanf(%s,sceneryname); Information(G ,sceneryname); menu(); /查询最短路径的函数 void Path1() char sceneryname20,sceneryname120; printf( 请输入你要查询的两景点的名称： )

31、; scanf(%s%s,sceneryname,sceneryname1); Path(G,sceneryname,sceneryname1); menu(); printf(n); /修改景点信息的函数 void Modify() char sceneryname20; int i,x; printf( 您想修改的景点的名称为： ); scanf(%s,sceneryname); Information(G ,sceneryname); for(i=0;i if(strcmp printf( 您想修改什么信息？ 1，名称； 2，代号； 3，信息简介 : ); scanf(%d, if(x=

32、1) printf( 请输入要修改的的景点的新名称： ); scanf(%s, break; if(x=2) printf( 请输入要修改的的景点的新代号： ); scanf(%d, if(x=3) printf( 请输入要修改的的景点的新信息简介： ); scanf(%s, break; menu(); /增加景点的函数 void AddVertic() int i,k; DataType ver; printf( 请输入增加节点的 名称，代号，信息简介 :n); scanf(%s%d%s, ListInsert( k= for(i=0;i if(k!=i) ki=MaxWeight; ik=MaxWeight; else ki=0; menu(); void DeleteVertic() ); DataType x; char name20; int i,k; printf( 请输入您要删除景点的名称： scanf(%s,name); for(i=0;i if(strcmp k=i; ListDelete( for(i=0;i if(k!=i) ki=MaxW