校园导航问题

《校园导航问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、括逻辑结构设计和存储结构设计)1.创建有向图G，在空图G中插入n个顶点和e条边。并实现最短路径算法。2.定义邻接矩阵实现图的存储类型定义。用来保存景点的数据信息，如景点间的距离。3.定义结构体数组实现景点信息的保存，如景点名称等（2）算法设计1.根据景点信息建立临接矩阵2.调用Dijkstra求出两景点的最短路径3.建立结构体数组存储数据4.将修改的信息直接写入数组中2.2设计表示（1）函数调用关系图主函数main()依次调用以下个函数#include"AdjMGraph.h"#include"Dijkstra.h"（2）函数接口规格说明调用库函数为#include

3、o.h>#include#include调用自定义函数为#include"AdjMGraph.h"#include"Dijkstra.h"各函数说明voidListInitiate(SeqList*L)/*初始化顺序表L*/intListLength(SeqListL)/*返回顺序表L的当前数据元素个数*/intListInsert(SeqList*L,inti,DataTypex)intListDelete(SeqList*L,inti,DataType*x)/*删除顺序表L中位置为i(0<=i=size-1)的数据元素并存放到x中*

4、//*删除成功返回1，删除失败返回0*/intListGet(SeqListL,inti,DataType*x)/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath[])最短路径算法//置带权有向图G为空图voidGraphInitiate(AdjMGraph*G)//判断顶点vertex是否是有向图G的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1。intIsVertex(AdjMGraph*G,DataTypevertex)//在带权有向图G中插入顶点

5、vertex。如果图中已经有顶点vertex,则图不变voidInsertVertex(AdjMGraph*G,DataTypevertex)/*在带权有向图G中插入一条第v1个顶点指向第v2个顶点，权值为weight的有向边。*如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。*如果图已经包含该边，则边的权值更改为新的权值，时间复杂度:O(1)。*/voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight)//判断第v1个顶点到第v2个顶点的边是否是有向图G的边，是则返回1，否则返回0.时间复杂度O(1)。i

6、ntIsEdge(AdjMGraph*G,intv1,intv2)/*在带权有向图G中删除一条第v1个顶点指向第v2个顶点的有向边。*如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。*如果不是图的边，则图不变。时间复杂度:O(1)。*/voidDeleteEdge(AdjMGraph*G,intv1,intv2)//在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度:O(n)。intGetFirstVex(AdjMGraphG,intv)//创建有向图G，通过

7、在空图G中插入n个顶点和e条边实现。时间复杂度:O(n^2+e)。voidGraphCreat(AdjMGraph*G,DataTypev[],intn,RowColWeightW[],inte)2.3详细设计（1）数据结构设计(包括逻辑结构设计和存储结构设计)（2）算法设计基本数据结构为：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;/////初始化顺序表voidListInitiate(SeqList*L)/*初始化顺序表L*/{L->si