2022年校园导航系统.docx

《2022年校园导航系统.docx》由会员分享，可在线阅读，更多相关《2022年校园导航系统.docx（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、troduction50; /顶点信息简介 DataType; 1 名师归纳总结 - - - - - - -第 1 页,共 17 页精选学习资料 - - - - - - - - - （3）景点之间的连接描述,所用到的结构体为：typedef struct int row; int col; int weight; RowColWeight; 用图来存放所供应的全部景点,然后用线性表来存放每一个景点的信息,其 中包括景点的名称,代号,信息简介,以及其它的一些信息；这样就将对景点的 操作,变成对图中各顶点的操作；,算法设计：关于本课题的算法,很大部分来源于这学期数据结构课程的学习,其中包括：图的创

4、建,线性表的一些操作；对于具体的问题实现,都有不同的算法,在下面的分析中,我将具体说明2.2 设计表示：, 函数调用关系及函数说明：第一, main 函数调用 Creat函数,用来创建图,然后调用 menu函数来挑选用户所要进行的操作；其中 menu函数就是一个菜单供使用者来挑选他所要进行的相关操作,比如 信息的查询,最短路径查询之类；main Creat menu 对于要求 1：以图中顶点表示校内内各景点,存放景点名称、代号、简介等信 息；以边表示路径,存放路径长度等有关信息；图的创建设计流程图为：main Creat Creat 函数原型为：void CreatAdjMGraph *G,

5、DataType v, RowColWeight E, int n,int e 其中, G 为所创建的图结构体对象,v 为全部顶点的集合,它是 DataType 型,这个类型前面已经介绍过；E 存放着各顶点之间的连接关系,它是 RowColWeight 型,前面也介绍过；n 表示顶点的个数；e 表示边数；Creat 函数的功能就是实现图的创建,将已知的景点的一些信息,转换成图的信息,并进行储备；对于要求 2：为来访客人供应图中任意景点相关信息的查询；流程图为：menu Information1 Information menu 函数的原型为：2 名师归纳总结 - - - - - - -第 2

6、页,共 17 页精选学习资料 - - - - - - - - - void menu 他就是一个菜单,供用户挑选他们所要进行的操作；Information1 函数原型为：void Information1 它的功能就是输入查询景点的信息,并调用 Information Information 函数原型为：void InformationAdjMGraph G , char scenery G 依旧是所创建的图的结构体对象,后面全部的 G 都是表示这个意思；scenery 是在 Information1 中输入的景点的名称；此函数的功能就是依据输入的景点的名称来查询其相关的信息；对于要求 3：为

7、来访客人供应任意景点的问路查询,即查询任意两个景点之间的一条最短路径；流程图为：menu Path1 Path Floyd Path1 函数原型为：void Path1 它的功能就是输入查询景点的名称,并调用Path Path 函数原型为：void PathAdjMGraph G ,char sceneryname, char sceneryname1 其中 sceneryname, sceneryname1 就是在 Path1函数中所输入的景点的名称,这个函数的功能就是通过这两个景点的名称找到它们在线性表中的位置,然后调用 Floyd 函数,查找出它们的最短路径,并输出所要的信息；Floyd

8、 函数原型为：void Floyd int cost MaxVertices,int n,int weightMaxVertices,int pathMaxVertices 其中参数 cost MaxVertices 即是图中边的邻接储备矩阵,weightMaxVertices 用来存放经此算法后的各顶点间的最短路径的值,pathMaxVertices 就是每两个顶点之间最短路径中到达目的顶点的前一个顶点的位置；Path函数中的输出信息就是据此而来；对于要求 4：修改景点信息；流程图为：menu Modify Modify 函数原型为：void Modify 它不带任何参数,功能是通过手动输入

9、景点名称,然后找到景点的储备空间,然后在修改相应的信息；对于选做要求：增加景点；其工作流程图为：menu AddVertic ListInsert AddVertic 函数原型为：void AddVertic 他不带任何参数,该函数的功能是在这个函数里面输入景点的信息,然后调用 ListInsert 函数,将所要增加的顶点信息插入到线性表中；ListInsert 函数原型为：void ListInsertSeqList *L, int i, DataType x 参数 L 表示顶点储备的线性表,i 表示要插入的位置 ,x 表示要插入的景点的信息；同时我在插入顶点时也将他与其他顶点之间的距离设置

10、为 MaxWeight ,这样做主要是为了便利在 Floyd 函数里面求最短路径对于选做要求：删除景点；其工作流程图为menu DeleteVertic ListDelete 3 名师归纳总结 - - - - - - -第 3 页,共 17 页精选学习资料 - - - - - - - - - DeleteVertic 函数原型为：void DeleteVertic 他不带任何参数, 该函数的功能就是在函数体里面输入要删除的景点的名称,然后依据名称找到该景点在线性表中的储备位置,然后调用线性表中的ListDelete 函数进行相应顶点的删除；ListDelete 函数原型为：ListDelete

11、SeqList *L, int i, DataType *x 其中参数 L 为存放顶点信息的线性表,i 表示要删除顶点在线性表中的存放位置,x 就是要删除的那一个景点；它的功能就是从线性表中删除指定的顶点；对于选做要求：增、删道路,流程图为：menu AddRoad InsertEdge DeleteRoad DeleteEdge AddRoad 和 DeleteRoad 两函数原型为：void AddRoad 和 void DeleteRoad ；这两个函数都不带参数,它们的功能就是在这两个函数里面输入要删除要增加或者的边连接的两个景点的名称,然后在线性表中找到这两个景点的相对储备空间,最终

12、调用 InsertEdge 或者 DeleteEdge 函数；InsertEdge 和 DeleteEdge 两函数原型为：void InsertEdgeAdjMGraph *G , int v1, int v2, int weight void DeleteEdgeAdjMGraph *G, int v1, int v2 这两个函数中同名参数所代表的意义是相同的,其中v1, v2 是所输入景点在线性表中的相对位置；weight 就是增加的边的权值函数接口说明 我所设计整个程序就是一些子函数的集合,每个功能都对应一个或者几个子函数,他们之间可以没有任何限制,只要能保证程序正确运行就可以调用,特

13、殊是 AdjMGraph.h , AdjMGraph.h 和 SeqList.h 头文件之中的函数,他们被许多函数调用过；这其中都没有任何 特殊类型的函数2.3 具体设计：依据题目分析,对于信息查询与修改功能,设计如下：1,输入景点名称 2,从线性表头扫描到表尾,if 找到该景点 输出景点结构体信息 else 输出提示信息找不到该顶点 实现查找最短路径,设计如下：1,景点名称 2,依据输入的信息找到它们所在的线性表中的位置 3,调用 Floyd 算法找出最短路径 4,输出信息 实现增删景点功能,设计如下：1,增加或者删除景点的名称 2,if 输入景点 ,将景点信息储存在相应的结构体中,并插入到

14、线性表尾；if 删除景点 ,找到景点在线性表中所在的位置,实现增删道路功能,设计如下：1,入增加或删除道路连接的两个景点的名称；然后将景点信息从线性表中删除名师归纳总结 - - - - - - -第 4 页,共 17 页精选学习资料 - - - - - - - - - 2,找到它们的相对位置；3,if 删除道路 ,将连接它们的边置为 MaxWeight ；if 增加道路 ,将输入的边值赋给相应的邻接矩阵表；3,调试分析： ,调试过程中遇到的问题与解决方案： 1, 关于最短路径的输出问题；在进行最短路径输出时,我刚开头时只能正序输出,具体的描述为： 比如,我要查寻从东区到东湖的最短路径,那么它能

15、正确输出结果,他的形式为： 东区 主楼 西体育馆 隧道 北大门 东湖；但是, 当我逆向输出时, 得到的结果却有点问题,经过分析调试后,找到了错误的所在；在找最短路径的时候我用的是 Floyd 算法,在这个算法中有三重循环,形式均为：fork=0;k食堂 东湖；经过分析调试后,其缘由也是出在 Floyd 算法那,在 Floyd 算法中,有这么一个判定 ifweightijweightik+weightkj,由于我在输入新景点信息时并没有建立它与其它景点之间的连接信息,所以在图中, 该新景点与其它景点之间的边得连接信息是空的,也就是说在邻接矩阵中,它的边得信息是空的,那么在 进 行 ifweigh

16、tijweightik+weightkj 判 断 时 weight 新 增 景 点 序号 其它景点序号 的值将是一个很大的负数,所以最短路径将会出错；解决这个问题的方法就是在增加新景点时就将它与其它景点之间的边（距离）设置为 用 Floyd 函数进行最短路径的求解时就不会再显现问题了；MaxWeight,这时假如再另外, 在做这个题时也仍显现过一些其他的小问题,不过都比较简单解决,这里我就不再列出了 , 算法的时空复杂度分析对应题目的要求,我总共供应了八个选项操作对于每一个操作的分析如下： 1,相关信息的查询；在这个操作中答应使用者输入一个景点名称,然后再依据景点名称来或取其相关的信息, 这个

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

18、为on1；6,增加道路；增加道路也要扫描线性表,找到要增加路的两景点的储备位置,然后再依据找到的储备位置去转变邻接矩阵的边的值,转变邻接矩阵的时间复杂度为o1；o1,其总时间消耗在线性表的扫描上,故最终其时间复杂度为on,空间复杂度为7,删除道路；删除道路和增加道路类似,它的时空复杂度分别为 on ,o1；都是先找到储备位置,然后再转变邻接矩阵,名师归纳总结 - - - - - - -第 5 页,共 17 页精选学习资料 - - - - - - - - - 8,浏览全部景点；浏览全部景点的实质就是从头到尾遍历线性表,然后输出遍历到的节点的信息,其时间复杂度为on,空间复杂度为o1；4,用户手册

19、：使用说明：当用户将程序经过编译,连接后,点击运行,在DOS 环境里面将看到一个选项菜单,菜单里面供应了 8 种操作,同时输出了一行提示信息：请挑选您想进行的操作；然后用户可以输入一个 1 8 之间的数字进行挑选性的操作,例如,您想进行信息的查询操作, 您可以从键盘输入数字1 ；当然, 一般而言先应当进行“ 浏览全部景点名称”操作；假如您挑选了浏览全部景点名称操作,在屏幕上将会显示出10 个景点的名称,这些景点是事先加进去的,用户可以对这些景点进行任何程序所供应的操作；下面,我将具体介绍本程序的使用方法：在浏览景点后,菜单将会连续显示出来,为 您供应操作挑选；假如 您想进行“ 相关信息的查询”

20、 操作,输入数字询景点的名称,在您输入景点名称后回车即可；假如 您想进行“ 最短路径查询” 操作,第一输入数字1 ,然后程序将会提示您输入查2 ,然后程序将会提示您输入查询的景点的名称,您输入按要求输入所供应的两个景点名称即可,要留意的是景点名称间以空格隔开,最终程序就会告知您最短的路径,以及最短路的长度；假如 您想修改景点的信息,同样先输入数字景点的名称, 您可以依据要求输入一个景点的名称,3 ,然后程序就会提示您输入所要修改 然后回车, 之后屏幕上就会显示您所输入的景点的全部信息,同时会有三个修改选项供用户挑选,然后您可以输入 1 3 之间的一个数字进行挑选性的修改；比如,您可以输入1对景

21、点名称进行修改,修改完后又会返回到菜单项连续挑选；假如 您想进行“ 增加景点” 操作,可以输入数字4 ,然后程序就会提示您输入新增加的景点的名称,代号,信息简介,各种输入之间以空格隔开；当输入完毕后回车,景点也 就胜利加入了, 然后用户可以再次挑选第八项操作浏览全部景点名称,检测新输入的景点是 否已经胜利添加；假如 您想进行“ 删除景点” 操作,可以输入数字5 ,回车后系统将会提示您输入要删除的景点的名称,您可以输入您想要删除的景点的名称,然后回车, 这样删除景点的操作就已经完成,您同样可以挑选第八项操作,检测是否胜利删除了景点；假如 您想进行“ 增加道路” 操作,您可以输入数字6 ,然后回车

22、,系统将会提示您输入增加道路所连接的两个景点的名称,输入两景点名称后回车,然后系统又会提示输入增加道路的长度, 输入后回车, 这时增加道路操作也就完了；胜利可以进行“ 最短路径查询” 操作；假如 您想进行“ 删除道路” 操作,您可以输入数字用户假如想要检查道路是否增加7 ,然后系统就会提示您输入删除道路所连接的两景点的名称,输入名称后回车即可,当然, 假如您想检测删除是否胜利您可以挑选“ 最短路径查询” 操作；备注：经过测试,本程序的全部操作都能正常执行,您可以挑选性的对他进行操作,同时也可以混合着操作,混合操作是检测错误的最好的一个方法；6 名师归纳总结 - - - - - - -第 6 页

23、,共 17 页精选学习资料 - - - - - - - - - 5,测试数据及测试结果：菜单显示为：* 菜单 * 1,相关信息查询 2,最短路径查询 3,修改景点信息 4,增加景点 5,删除景点 6,增加道路 7,删除道路 8,浏览全部景点名称 * 请挑选您想进行的操作：8 隧道北综北体育馆东区博物馆主楼图书馆西体育馆北大门东湖请挑选您想进行的操作：1 请输入您所想要查询的景点的名称：博物馆您输入的景点的名称是：博物馆您输入的景点的代码为：11 您输入的景点的相关信息有：有各种化石请挑选您想进行的操作：2 请输入你要查询的两景点的名称：东区东湖最短路径为：108 从 东区 点到 东湖景点的最短

24、路径为：东区 主楼 西体育馆 隧道 北大门 东湖请挑选您想进行的操作：3 北综北您想修改的景点的名称为：隧道您输入的景点的名称是：隧道您输入的景点的代码为：15 您输入的景点的相关信息有：自主修建您想修改什么信息？1,名称； 2,代号； 3,信息简介 : 1 请输入要修改的的景点的新名称：地大隧道请挑选您想进行的操作：8 东区博物馆主楼图书馆西体育馆地大隧道体育馆北大门东湖请挑选您想进行的操作：4 7 名师归纳总结 - - - - - - -第 7 页,共 17 页精选学习资料 - - - - - - - - - 请输入增加节点的名称,代号,信息简介: 北一楼34 老师办公室北综地大隧道北综北

25、请挑选您想进行的操作：1 请输入您所想要查询的景点的名称：北一楼您输入的景点的名称是：北一楼您输入的景点的代码为：34 您输入的景点的相关信息有：老师办公室请挑选您想进行的操作：5 请输入您要删除景点的名称：北一楼请挑选您想进行的操作：8 东区博物馆主楼图书馆西体育馆体育馆北大门东湖请挑选您想进行的操作：6 输入您要增加的道路链接的两个景点名称：东区输入您要增加的道路的长度: 50 请挑选您想进行的操作：2 请输入你要查询的两景点的名称：东区北综最短路径为：50 从 东区 点到 北综景点的最短路径为：东区 北综请挑选您想进行的操作：7 东区北综输入您要删除的道路链接的两个景点名称：请挑选您想进

26、行的操作：2 北综请输入你要查询的两景点的名称：东区最短路径为：103 从 东区 点到 北综景点的最短路径为：东区 主楼 西体育馆 地大隧道 北大门 北综8 名师归纳总结 - - - - - - -第 8 页,共 17 页精选学习资料 - - - - - - - - - 6,源程序清单：school.cpp /程序源文件AdjMGraph.h /图的相关操作头文件AdjMGraphCreat.h /创建图的头文件SeqList.h /线性表操作头文件Floyd.h /Floyd 算法头文件Operation.h /自己所定义的一些操作的头文件Inquiry.h /查询信息包含的头文件/ 具体

27、school.cpp 程序源文件#include #include #include #define MaxSize 20 /线性表的最大数组空间#define MaxVertices 20 /景点个数所答应的最大值#define MaxWeight 1000 /无穷边权值#include Floyd.h #include AdjMGraphCreat.h #include Inquiry.h AdjMGraph G; #include Operation.h void main /初始景点信息DataType a= 东区 ,10, 讨论生院 , 博物馆 ,11, 有各种化石 , 主楼 ,12

28、, 学校的标志建筑 , 图书馆 ,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,

29、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; 9 名师归纳总结 - - - - - - -第 9 页,共 17 页精选学习资料 - - - - - - - - - / 具体 Floyd.h 头文件 void Floydint costMaxVertices,int n,int weightMaxVertices,int pathMaxVertices /初始化 int i,j,k; fori=0;in;i+ forj=0;

30、jn;j+ weightij=costij; pathij=-1; /n 次递推 fork=0;kn;k+ fori=0;in;i+ forj=0;jweightik+weightkj weightij=weightik+weightkj; pathij=k; /具体 Inquiry.h 头文件 void InformationAdjMGraph G , char scenery int i; fori=0;iG .vertices.size;i+ ifstrcmpG .vertices.listi.name,scenery=0 printf 您输入的景点的名称是：printf 您输入的景点的

31、代码为：%sn,G.vertices.listi.name; %dn,G.vertices.listi.code; printf 您输入的景点的相关信息有：%snn,G.vertices.listi.introduction; break; 10 名师归纳总结 - - - - - - -第 10 页,共 17 页精选学习资料 - - - - - - - - - ifi=G.vertices.size printf 您所查询的景点不在我们所供应的范畴内！nn; void PathAdjMGraph G,char sceneryname, char sceneryname1 int i,j,k,n

32、,m,count=0; n=G.vertices.size; int weightMaxVerticesMaxVertices,pathMaxVerticesMaxVertices; int valueMaxVertices; fori=0;i%sn,sceneryname,sceneryname1; else whilem.=-1 valuecount=m; ifj,sceneryname; ifj=0;i- n,sceneryname,sceneryname1; printf%s ,G.vertices.listvaluei.name; printf%sn,sceneryname1; el

33、se fori=0;i,G.vertices.listvaluei.name; printf%sn,sceneryname1; /具体 Operation.h 头文件 void menu; /查询景点信息的函数 void Information1 char sceneryname20; printf 请输入您所想要查询的景点的名称：; scanf%s,sceneryname; InformationG ,sceneryname; menu; /查询最短路径的函数 void Path1 char sceneryname20,sceneryname120; printf 请输入你要查询的两景点的名

34、称：; scanf%s%s,sceneryname,sceneryname1; PathG,sceneryname,sceneryname1; menu; printfn; 12 名师归纳总结 - - - - - - -第 12 页,共 17 页精选学习资料 - - - - - - - - - /修改景点信息的函数 void Modify char sceneryname20; int i,x; printf 您想修改的景点的名称为：; scanf%s,sceneryname; InformationG ,sceneryname; fori=0;iG .vertices.size;i+ ifs

35、trcmpG .vertices.listi.name,sceneryname=0 printf 您想修改什么信息？1,名称； 2,代号； 3,信息简介 : ; scanf%d,&x; ifx=1 printf 请输入要修改的的景点的新名称：; scanf%s,G.vertices.listi.name; break; ifx=2 printf 请输入要修改的的景点的新代号：; scanf%d,&G .vertices.listi.code; break; ifx=3 printf 请输入要修改的的景点的新信息简介：; scanf%s,G.vertices.listi.introduction

36、; break; menu; /增加景点的函数 void AddVertic int i,k; DataType ver; printf 请输入增加节点的名称,代号,信息简介:n; scanf%s%d%s,ver.name,&ver.code,ver.introduction; 13 名师归纳总结 - - - - - - -第 13 页,共 17 页精选学习资料 - - - - - - - - - ListInsert&G .vertices, G.vertices.size, ver; k= G.vertices.size-1; fori=0;iG .vertices.size;i+ ifk.=i G.Edgeki=MaxWeight; G.Edgeik=MaxWeight; else G.Edgeki=0; menu; void DeleteVertic DataType x; char name20; int i,k; printf 请输入您要删除景点的名称：; scanf%s,name; fori=0;iG.vertices.size;i+ ifstrcmpG .vertices.listi.na