校园导航系统-修订编选.pdf

1 题号：第七题题号：第七题 题目：校园导航问题题目：校园导航问题 1，需求分析：，需求分析： 设计你的学校的平面图，至少包括 10 个以上的景点（场所），每两个景点间可以有不 同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径） 要求：要求： （1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路 径，存放路径长度等有关信息 （2）为来访客人提供图中任意景点相关信息的查询 （3） 为来访客人提供任意景点的问路查询， 即查询任意两个景点之间的一条最短路径 （4）修改景点信息 实现提示： 一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网顶点和边均 含有相关信息 选做内容： （1）提供图的编辑功能：增、删景点；增、删道路；修改已有信息等 （2）校园导游图的仿真界面 2，设计：，设计： 2.1 设计思想：设计思想： ，数据结构设计，数据结构设计： （1）图采用邻接矩阵存储，其中图所用到的结构体为： typedef struct SeqList vertices; //表示图中的顶点 int EdgeMaxVerticesMaxVertices; //表示图中的边 int numOfEdge; //表示图中边的数目 AdjMGraph; （2）景点。

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

其中 menu()函数就是一个菜单供使用者来选择他所要进行的相关操作，比如 信息的查询，最短路径查询之类 对于要求 1：以图中顶点表示校园内各景点，存放景点名称、代号、简介等信 息；以边表示路径，存放路径长度等有关信息图的创建设计流程图为： Creat()函数原型为：函数原型为： void Creat(AdjMGraph *G, DataType v, RowColWeight E, int n,int e) 其中，G 为所创建的图结构体对象，v 为所有顶点的集合，它是 DataType 型，这个类型前面已经介绍过 ； E 存放着各顶点之间的连接关系，它是 RowColWeight 型， 前面也介绍过；n 表示顶点的个数；e 表示边数 Creat()函数的功能就是实现图的创建，将已知的景点的一些信息，转换成图的 信息，并进行存储 对于要求 2：为来访客人提供图中任意景点相关信息的查询流程图为： menu()函数的原型为：函数的原型为： main() Creat()menu() main()Creat() menu()Information1()Information() 3 void menu() 他就是一个菜单，供用户选择他们所要进行的操作。

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

Floyd()函数原型为：函数原型为： void Floyd (int cost MaxVertices,int n,int weightMaxVertices,int pathMaxVertices) 其中参数 cost MaxVertices即是图中边的邻接存储矩阵， weightMaxVertices用来存放经 此算法后的各顶点间的最短路径的值，pathMaxVertices就是每两个顶点之间最短路径中 到达目的顶点的前一个顶点的位置Path()函数中的输出信息就是据此而来 对于要求 4：修改景点信息流程图为： Modify()函数原型为：函数原型为： void Modify() 它不带任何参数，功能是通过手动输入景点名称，然后找到景点的 存储空间，然后在修改相应的信息 对于选做要求：增加景点其工作流程图为： AddVertic()函数原型为：函数原型为： void AddVertic() 他不带任何参数，该函数的功能是在这个函数里面输入景点的信 息，然后调用 ListInsert()函数，将所要增加的顶点信息插入到线性表中 ListInsert()函数原型为：函数原型为： void ListInsert(SeqList *L, int i, DataType x) 参数 L 表示顶点存储的线性表，i 表示 要插入的位置,x 表示要插入的景点的信息。

同时我在插入顶点时也将他与其他顶点之间的距 离设置为 MaxWeight，这样做主要是为了方便在 Floyd 函数里面求最短路径 对于选做要求：删除景点其工作流程图为 menu()Path1()Path() menu()Modify() menu()AddVertic() menu()DeleteVertic() Floyd() ListInsert() ListDelete () 4 DeleteVertic()函数原型为：函数原型为： void DeleteVertic() 他不带任何参数， 该函数的功能就是在函数体里面输入要删除的景 点的名称，然后根据名称找到该景点性表中的存储位置，然后调用线性表中的 ListDelete ()函数进行相应顶点的删除 ListDelete ()函数原型为：函数原型为： ListDelete(SeqList *L, int i, DataType *x) 其中参数 L 为存放顶点信息的线性表，i 表示 要删除顶点性表中的存放位置，,x 就是要删除的那一个景点 它的功能就是从线性表中 删除指定的顶点 对于选做要求：增、删道路，流程图为： AddRoad()和和 DeleteRoad()两函数原型为：两函数原型为： void AddRoad()和 void DeleteRoad()。

这两个函数都不带参数，它们的功能就是在这两 个函数里面输入要删除要增加或者的边连接的两个景点的名称， 然后性表中找到这两个 景点的相对存储空间，最后调用 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 就是增加的边的权值 函数接口说明函数接口说明 我所设计整个程序就是一些子函数的集合，每个功能都对应一个或者几个子函数， 他们之间可以没有任何限制，只要能保证程序正确运行就可以调用，特别是 AdjMGraph.h , AdjMGraph.h 和 SeqList.h 头文件之中的函数，他们被很多函数调用过这其中都没有任何 特殊类型的函数 2.3 详细设计：详细设计： 根据题目分析，对于信息查询与修改功能，设计如下： 1，输入景点名称 2，从线性表头扫描到表尾， if(找到该景点) 输出景点结构体信息 else 输出提示信息找不到该顶点 实现查找最短路径，设计如下： 1， 景点名称 2，根据输入的信息找到它们所在的线性表中的位置 3，调用 Floyd 算法找出最短路径 4，输出信息 实现增删景点功能，设计如下： 1，增加或者删除景点的名称 2，if(输入景点)，将景点信息保存在相应的结构体中，并插入到线性表尾； if(删除景点)，找到景点性表中所在的位置，然后将景点信息从线性表中删除 实现增删道路功能，设计如下： menu()AddRoad() DeleteRoad() InsertEdge () DeleteEdge () 5 1，入增加或删除道路连接的两个景点的名称； 2，找到它们的相对位置； 3，if(删除道路)，将连接它们的边置为 MaxWeight； if(增加道路)，将输入的边值赋给相应的邻接矩阵表； 3，调试分析：3，调试分析： ，调试过程中遇到的问题与解决方案： ，调试过程中遇到的问题与解决方案： 1, 关于最短路径的输出问题。

在进行最短路径输出时，我刚开始时只能正序输出， 具体的描述为 ： 比如，我要查寻从东区到东湖的最短路径，那么它能正确输出结果，他的形 式为 ： 东区 主楼 西体育馆 隧道 北大门 东湖但是，当我逆向 输出时，得到的结果却有点问题，经过分析调试后，找到了错误的所在在找最短路径的时 候我用的是 Floyd 算法，在这个算法中有三重循环，形式均为 ： for(k=0;k食堂 东湖经过分析调试后，其原因也是出在 Floyd 算法那， 在 Floyd 算法中， 有这么一个判断if(weightijweightik+weightkj)， 由于 我在输入新景点信息时并没有建立它与其它景点之间的连接信息， 所以在图中， 该新景点与 其它景点之间的边得连接信息是空的，也就是说在邻接矩阵中，它的边得信息是空的，那么 在进行 if(weightijweightik+weightkj)判断时 weight新增景点序号其 它景点序号的值将是一个很大的负数，所以最短路径将会出错解决这个问题的方法就是 在增加新景点时就将它与其它景点之间的边 （距离） 设置为 MaxWeight， 这时如果再用 F。