校园导航系统.doc

《校园导航系统.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、均含有相关信息。选做内容：（1）提供图的编辑功能：增、删景点；增、删道路；修改已有信息等。（2）校园导游图的仿真界面。2，设计：2.1设计思想：<1>，数据结构设计：（1）图。采用邻接矩阵存储，其中图所用到的结构体为：typedefstruct{SeqListvertices;//表示图中的顶点intEdge[MaxVertices][MaxVertices];//表示图中的边intnumOfEdge;//表示图中边的数目}AdjMGraph;（2）景点。用顺序表存储。所用到的结构体为：typedefstruct{charname

3、[20];//顶点名称intcode;//顶点代号charintroduction[50];//顶点信息简介}DataType;18（3）景点之间的连接描述，所用到的结构体为：typedefstruct{introw;intcol;intweight;}RowColWeight;用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其中包括景点的名称，代号，信息简介，以及其它的一些信息。这样就将对景点的操作，变成对图中各顶点的操作。<2>，算法设计：关于本课题的算法，很大部分来源于这学期数据结构课程的学习，其中包括：图的

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

5、n()Creat()函数原型为：voidCreat(AdjMGraph*G,DataTypev[],RowColWeightE[],intn,inte)其中，G为所创建的图结构体对象，v[]为所有顶点的集合，它是DataType型，这个类型前面已经介绍过；E[]存放着各顶点之间的连接关系，它是RowColWeight型，前面也介绍过；n表示顶点的个数；e表示边数。Creat()函数的功能就是实现图的创建，将已知的景点的一些信息，转换成图的信息，并进行存储。menu()对于要求2：为来访客人提供图中任意景点相关信息的查询。流程图为：

6、Information()Information1()menu()函数的原型为：18voidmenu()他就是一个菜单，供用户选择他们所要进行的操作。Information1()函数原型为：voidInformation1()它的功能就是输入查询景点的信息，并调用Information()Information()函数原型为：voidInformation(AdjMGraphG,charscenery[])G依然是所创建的图的结构体对象，后面所有的G都是表示这个意思；scenery[]是在Information1()中输入的景点的

7、名称。此函数的功能就是根据输入的景点的名称来查询其相关的信息。对于要求3：为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。流程图为：Floyd()Path()Path1()menu()Path1()函数原型为：voidPath1()它的功能就是输入查询景点的名称，并调用Path()Path()函数原型为：voidPath(AdjMGraphG,charsceneryname[],charsceneryname1[])其中sceneryname[],sceneryname1[]就是在Path1()函数中所输入

8、的景点的名称，这个函数的功能就是通过这两个景点的名称找到它们在线性表中的位置，然后调用Floyd()函数，查找出它们的最短路径，并输出所要的信息。Floyd()函数原型为：voidFloyd(intcost[][MaxVertices],intn,