校园导航问题

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&q

3、uot;（ 2）函数接口规格说明调用库函数为#include <stdio.h>#include <stdlib.h>#include <malloc.h>调用自定义函数为#include "AdjMGraph.h"#include "Dijkstra.h".'.各函数说明void ListInitiate(SeqList *L)/*初始化顺序表L*/int ListLength(SeqList L)/*返回顺序表L 的当前数据元素个数*/int ListInsert(SeqList *L, int i, Da

4、taType x)int ListDelete(SeqList *L, int i, DataType *x)/* 删除顺序表L 中位置为i(0 <= i = size-1)的数据元素并存放到x 中 */* 删除成功返回1，删除失败返回0*/int ListGet(SeqList L, int i, DataType *x)/* 取顺序表L 中第 i 个数据元素存于x 中，成功返回1，失败返回0*/void Dijkstra(AdjMGraph G,int v0,int distance,int path)最短路径算法/置带权有向图G 为空图void GraphInitiate(AdjM

5、Graph *G)/判断顶点vertex 是否是有向图G 的顶点，是则返回顶点在顶点顺序表中的序号，否则返回 -1。int IsVertex(AdjMGraph *G,DataType vertex)/在带权有向图G 中插入顶点vertex。如果图中已经有顶点vertex, 则图不变void InsertVertex(AdjMGraph *G,DataType vertex)/* 在带权有向图G 中插入一条第v1 个顶点指向第v2 个顶点，权值为weight 的有向边。* 如果 v1 和 v2 有一个不是图中的顶点，则图不变；如果v1 和 v2 相等，则图不变。* 如果图已经包含该边，则边的权

6、值更改为新的权值，时间复杂度:O(1) 。*/void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/判断第 v1 个顶点到第v2 个顶点的边是否是有向图G 的边，是则返回1，否则返回 0.时间复杂度 O(1) 。int IsEdge(AdjMGraph *G ,int v1,int v2)/* 在带权有向图G 中删除一条第v1 个顶点指向第v2 个顶点的有向边。* 如果 v1 和 v2 有一个不是图中的顶点，则图不变；如果v1 和 v2 相等，则图不变。* 如果 <v1,v2> 不是图的边，则图不变。时间复杂度:O(1) 。*

7、/void DeleteEdge(AdjMGraph *G ,int v1,int v2)/在带权有向图G 中取第 v 个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度 :O(n) 。int GetFirstVex(AdjMGraph G ,int v)/ 创建有向图G ，通过在空图G 中插入n 个顶点和e 条边实现。时间复杂度:O(n2+e) 。void GraphCreat(AdjMGraph *G,DataType v,int n,RowColWeight W,int e)2.3 详细设计（ 1）数据结构设计(包括逻辑结构设计和存储

8、结构设计);.'.（ 2）算法设计基本数据结构为：typedef structDataType listMaxSize ;int size ;SeqList;/ 初始化顺序表void ListInitiate(SeqList *L)/* 初始化顺序表L*/L->size = 0;int ListLength(SeqList L)/*返回顺序表L 的当前数据元素个数*/return L.size;int ListInsert(SeqList *L, int i, DataType x)/* 在顺序表 L 的第 i(0 <= i = size) 个位置前插入数据元素值 x*/

9、/* 插入成功返回 1，插入失败返回 0*/ int j;if(L->size >= MaxSize)printf(" 顺序表已满无法插入!n");return 0;else if(i < 0 | i > L->size);.'.printf(" 参数 i 不合法 !n");return 0;else/* 为插入做准备 */for(j = L->size; j > i; j-)L->listj = L->listj-1;L->listi = x;L->size+;/ 元素个数加1r

10、eturn 1;int ListDelete(SeqList *L, int i, DataType *x)/* 删除顺序表 L 中位置为 i(0 <= i = size-1) 的数据元素并存放到 x 中 */ /* 删除成功返回 1，删除失败返回 0*/int j;if(L->size <= 0)printf(" 顺序表已空无数据元素可删!n");return 0;else if(i < 0 | i > L->size-1 )printf(" 参数 i 不合法 !n");return 0 ;else*x = L-&g

11、t;listi;/* 保存删除的元素到x 中 */* 依次前移 */for(j = i+1; j <= L->size-1; j+)L->listj-1 = L->listj;L->size-;/ 元素个数减1return 1;int ListGet(SeqList L, int i, DataType *x)/* 取顺序表L 中第 i 个数据元素存于x 中，成功返回1，失败返回0*/if(i < 0 | i > L.size-1)printf(" 参数 i 不合法 !n");.'.return 0;else*x = L.l

12、isti;return 1;基本函数为Dijkstra 算法算法具体步骤（ 1）初始时， S 只包含源点，即S=， v 的距离为0。 U 包含除 v 外的其他顶点，U 中顶点 u 距离为边上的权（若v 与 u 有边）或）（若 u 不是 v 的出边邻接点）。（ 2）从 U 中选取一个距离v 最小的顶点k，把 k，加入 S 中（该选定的距离就是v 到 k的最短路径长度）。（ 3）以 k 为新考虑的中间点，修改U 中各顶点的距离；若从源点v 到顶点 u（ u U ）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k 的距离加上边上的权。（ 4）重复步骤（

13、2）和（ 3）直到所有顶点都包含在S 中三调试分析Dijkstra 算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V 分成两组，第一组为已求出最短路径的顶点集合（用S 表示，初始时S 中只有一个源点，以后每求得一条最短路径, 就将加入到集合S 中，直到全部顶点都加入到S 中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S 中。在加入的过程中，总保持从源点v 到 S 中各顶点的最短路径长度不大于从源点v 到 U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从 v 到此顶点的最短路径

14、长度， U 中的顶点的距离，是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。空间复杂度度Dijkstra算法的时间复杂度为O(n2)空间复杂度取决于存储方式，邻接矩阵为O(n2)四用户手册1.首先选择要进行的操作2 选 1、 2、 3、4 分别为查询景点信息、问路查询、修改景点信息、退出。3.选 1 输入景点代号即可进行信息查询。4.选 2 输入两景点代号即可进行问路查询。并输出最短路径长度以及两路径的景点。4.选 3 输入景点代号即可进行修改。5选 4退出五测试数据及测试结果;.'.六源程序清单typedef structDataType listMaxSize

15、;int size ;SeqList;.'./ 初始化顺序表void ListInitiate(SeqList *L)/* 初始化顺序表L*/L->size = 0;int ListLength(SeqList L)/*返回顺序表L 的当前数据元素个数*/return L.size;int ListInsert(SeqList *L, int i, DataType x)/* 在顺序表 L 的第 i(0 <= i = size) 个位置前插入数据元素值 x*/ /* 插入成功返回 1，插入失败返回 0*/ int j;if(L->size >= MaxSize)

16、printf(" 顺序表已满无法插入!n");return 0;else if(i < 0 | i > L->size)printf(" 参数 i 不合法 !n");return 0;else/* 为插入做准备 */for(j = L->size; j > i; j-)L->listj = L->listj-1;L->listi = x;L->size+;/ 元素个数加1return 1;int ListDelete(SeqList *L, int i, DataType *x)/* 删除顺序表 L

17、中位置为 i(0 <= i = size-1) 的数据元素并存放到 x 中 */ /* 删除成功返回 1，删除失败返回 0*/ int j;if(L->size <= 0)printf(" 顺序表已空无数据元素可删!n");return 0;.'.else if(i < 0 | i > L->size-1 )printf(" 参数 i 不合法 !n");return 0 ;else*x = L->listi;/* 保存删除的元素到x 中 */* 依次前移 */for(j = i+1; j <= L-

18、>size-1; j+)L->listj-1 = L->listj;L->size-;/ 元素个数减1return 1;int ListGet(SeqList L, int i, DataType *x)/* 取顺序表L 中第 i 个数据元素存于x 中，成功返回1，失败返回0*/if(i < 0 | i > L.size-1)printf(" 参数 i 不合法 !n");return 0;else*x = L.listi;return 1;#include "SeqList.h"/邻接矩阵实现图的存储类型定义typed

19、ef structSeqList vertices;/ 存放顶点的顺序表int edgeMaxVerticesMaxV ertices; / 存放边的邻接矩阵int numOfEdges;/边的数目AdjMGraph;/ 图的结构体定义typedef structint row;/ 行下标int col;/ 列下标int weight;/权值;.'.RowColWeight;/ 边信息结构体定义struct massageschar name20;int num;int cen;massage10=" 教一楼 ",50,7," 教二楼 ",50,

20、7," 教三楼 ",50,7," 主楼 ",50,7," 图书馆 ",50," 北一楼 ",50,7," 北二楼 ",50,7," 北三楼 ",50,7," 北综 ",50,7," 北区图书馆 ",50,7; /置带权有向图 G 为空图，时间复杂度 :O(1) 。void GraphInitiate(AdjMGraph *G)int i,j;for(i=0;i<MaxVertices;i+)for(j=0;j<MaxVert

21、ices;j+)if(i=j) G->edgeij=0;elseG->edgeij=MaxWeight;/MaxWeight 表示权值无穷大G->numOfEdges=0;/边的条数置为0ListInitiate(&G->vertices);/ 顶点顺序表初始化int IsVertex(AdjMGraph *G,DataType vertex)int i;for (i=0;i<G->vertices.size;i+)if(G->vertices.listi=vertex)break;if (i=G->vertices.size)retur

22、n -1;elsereturn i;void InsertVertex(AdjMGraph *G,DataType vertex)if(IsVertex(G,vertex)<0);.'.if(ListInsert(&G->vertices,G->vertices.size,vertex)=0)/在顶点顺序表的表尾插入顶点 vertexprintf(" 插入顶点时空间已满无法插入！");exit(1);void InsertEdge(AdjMGraph *G ,int v1,int v2,int weight)DataType x;if(v1

23、!=v2)if(ListGet(G->vertices,v1,&x)=0)|(ListGet(G->vertices,v2,&x)=0)printf(" 插入边时参数v1 和 v2 越界出错！ n");exit(1);G->edgev1v2=weight;G->numOfEdges+;int IsEdge(AdjMGraph *G,int v1,int v2)DataType x;if(ListGet(G->vertices,v1,&x)=0) | (ListGet(G->vertices,v2,&x)=0

24、)printf(" 边的参数v1 和 v2 越界出错！ n");return 0;if(G->edgev1v2 = MaxWeight | v1=v2)printf(" 该边不存在！n");return 0;return 1;void DeleteEdge(AdjMGraph *G,int v1,int v2)if (IsEdge(G,v1,v2)=0)printf(" 删除边时出错！");exit(1);.'.elseG->edgev1v2=MaxWeight;G->numOfEdges-;/计算带权有向图

25、G 中第 v 个顶点的入度，时间复杂度:O(n) 。int InDegree(AdjMGraph *G,int v)/在此插入你第二步的代码，替换掉下面的语句int din=0,j;for(j=0;j<G->vertices.size;j+)if(G->edgevj!=0&&G->edgevj!=MaxWeight)din+;return din;/计算带权有向图G 中第 v 个顶点的出度，时间复杂度:O(n) 。int OutDegree(AdjMGraph *G ,int v)/在此插入你第二步的代码，替换掉下面的语句int dou=0,j;for(

26、j=0;j<G->vertices.size;j+)if(G->edgejv!=0&&G->edgevj!=MaxWeight)dou+;return dou;/计算带权有向图G 中第 v 个顶点的度，时间复杂度:O(n) 。int Degree(AdjMGraph *G,int v)return(InDegree(G,v)+OutDegree(G ,v);/在带权有向图G 中删除第v 个顶点，时间复杂度:O(n2) 。void DeleteVertex(AdjMGraph *G,int v)/在此插入你第一步的代码int j=0,i;if(v>G

27、->vertices.size);.'.printf(" 参数 v 出错！ n");return;for (j=v;j<G->vertices.size;j+)for (i=0;i<G->vertices.size;i+)G->edgeji=G->edgeji+1;for (j=v;j<G->vertices.size-1;j+)for (i=0;i<G->vertices.size;i+)G->edgeij=G->edgei+1j;for(j=v;j<G->vertices.

28、size-1;j+)G->vertices.listj=G->vertices.listj+1;G->vertices.size-;/在带权有向图G 中取第 v 个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度 :O(n) 。int GetFirstVex(AdjMGraph G ,int v)int col;DataType x;if(ListGet(G.vertices,v,&x)=0)printf(" 取第一个邻接顶点时参数v 越界出错！ n");exit(1);/寻找邻接矩阵 v 行中

29、从最左开始第一个值非零且非无穷大的权值对应的顶点 for(col=0;col<G .vertices.size;col+)if(G.edgevcol>0 && G.edgevcol < MaxWeight)return col;return -1;/在带权有向图G 中取第 v1 个顶点的继邻接结点第v2 个顶点之后的下一个邻接结点,时间复杂度 :O(n) 。int GetNextVex(AdjMGraph G ,int v1,int v2)int col;DataType x;.'.if(ListGet(G.vertices,v1,&x)=0)

30、|(ListGet(G.vertices,v2,&x)=0)printf(" 取下一邻接顶点时参数v1 和 v2 越界出错！ n");exit(1);if(G.edgev1v2=0)printf("v2不是 v1 的邻接顶点 n");exit(1);/寻找邻接矩阵 v 行中从第 v2+1 列开始的第一个值非零且非无穷大的权值对应的顶点 for(col=v2+1;col<G .vertices.size;col+)if(G.edgev1col>0 && G.edgev1col<MaxWeight)return co

31、l;return -1;/创建有向图G，通过在空图G 中插入 n 个顶点和e 条边实现。时间复杂度:O(n2+e) 。void GraphCreat(AdjMGraph *G ,DataType v,int n,RowColWeight W,int e)int i,k;GraphInitiate(G);for(i=0;i<n;i+)InsertVertex(G,vi);for(k=0;k<e;k+)InsertEdge(G,Wk.row,Wk.col,Wk.weight);void Dijkstra(AdjMGraph G,int v0,int distance,int path)

32、int *s=(int *)malloc(sizeof(int)*n);int minDis,i,j,u;for (i=0;i<n;i+)distancei=G .edgev0i;si=0;if (i!=v0&&distancei<MaxWeight)pathi=v0;else pathi=-1;sv0=1;for (i=0;i<n;i+)minDis=MaxWeight;.'.for (j=0;j<n;j+)if (sj=0&&distancej<minDis)u=j;minDis=distancej;if (minDis

33、=MaxWeight)return;su=1;for (j=0;j<n;j+)if (sj=0&&G.edgeuj<MaxWeight&&distanceu+G.edgeuj<distancej)distancej=distanceu+G .edgeuj;pathj=u;#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef int DataType;#define MaxSize 100#define MaxVertices 15#de

34、fine MaxWeight 10000#include "AdjMGraph.h"#include "Dijkstra.h"void main()int p10;int flog=0;AdjMGraph g;int i,j,k,o,l,n=10,e=30,t;int distance10,path10;DataType a=0,1,2,3,4,5,6,7,8,9;RowColWeightrcw=0,3,20,0,4,15,1,2,30,2,1,30,2,3,50,2,4,65,2,7,653,2,8,700,3,0,20,3,2,50,3,4,6,4,

35、0,15,4,2,65,4,3,6,5,6,10,5,9,20,6,5,10,6,7,10,6,9,30,7,2,653,7,6,10,7,8,50,7,9,20,8,2,700,8,7,50,8,9,40,9,5,20,9,6,30,9,7,20,9,8,40;.'.int output(int t);GraphCreat(&g,a,n,rcw,e);Dijkstra(g,0,distance,path);printf("nnntt 中国地质大学 nn");printf("t一、地图信息 nn");printf("t0、教一楼1、教二楼2、教三楼3、主楼4、图书馆 n");printf("nt5 、北一楼6、北二楼7、北三楼8、北综9、北区图书馆 nn");printf("t二、可供操作 nn");printf("t1、校园内各景点 nn");printf(&quo