校园导航问题

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()依次调用以下个函数#i nclude "AdjMGra ph.h"#i nclude "Dijkstra.h"(2) 函

3、数接口规格说明 调用库函数为#i nclude <stdio.h>#i nclude <stdlib.h>#in clude <malloc.h>调用自定义函数为#i nclude "AdjMGra ph.h"#i nclude "Dijkstra.h"各函数说明否则返回void ListI ni tiate(SeqList *L) /*初始化顺序表 L*/int ListLength(SeqList L) /*返回顺序表L的当前数据元素个数*/int ListI nsert(SeqList *L, int i, Da

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

5、ra ph *G)判断顶点vertex是否是有向图G的顶点，是则返回顶点在顶点顺序表中的序号， -1。int lsVertex(AdjMGraph *G QataType vertex)/在带权有向图 G中插入顶点vertex。如果图中已经有顶点vertex,则图不变void InsertVertex(AdjMGraph *G ,DataType vertex)v2个顶点，权值为weight的有向边。*如果v1和v2有一个不是图中的顶点，则图不变;如果 v1和v2相等，则图不变。*如果图已经包含该边，则边的权值更改为新的权值,*/void In sertEdge(AdjMGra ph *G,i

6、 nt v1,i nt v2,i nt weight) 判断第v1个顶点到第v2个顶点的边是否是有向图 回0.时间复杂度O(1)。int IsEdge(AdjMGraph *G ,int v1,int v2)/*在带权有向图G中删除一条第v1个顶点指向第 *如果v1和v2有一个不是图中的顶点，则图不变;时间复杂度:0(1)。G的边，是则返回1,否则返v2个顶点的有向边。如果 v1和v2相等，则图不/*在带权有向图G中插入一条第v1个顶点指向第变。：0(1)。*如果v1,v2不是图的边，则图不变。时间复杂度*/void DeleteEdge(AdjMGraph *G ,int v1,int v2

7、)/在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在， 则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度：O(n)。int GetFirstVex(AdjMGraph G ,int v)/创建有向图G，通过在空图 G中插入n个顶点和 e条边实现。时间复杂度:0(nA2+e)。void Grap hCreat(AdjMGra ph *G,DataTy pe v,i nt n ,RowColWeight W,i nt e)2.3详细设计(1)数据结构设计(包括逻辑结构设计和存储结构设计)程序启动检测SU視初优图理结构(2 )算法设计基本数据结构为：typ edef st

8、ructDataTy pe listMaxSize;int size ;SeqList;/*初始化顺序表L*/初始化顺序表void ListI ni tiate(SeqList *L)L->size = 0;/*返回顺序表L的当前数据元素个数*/int ListLe ngth(SeqList L)return L.size;int ListI nsert(SeqList *L, int i, DataT ype x)/*/*在顺序表L的第i(0 <= i = size)个位置前插入数据元素值x*/插入成功返回1，插入失败返回0*/int j;if(L->size >=

9、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;/元素个数加1L->size+;return 1;int ListDelete(SeqList *L, i nt i, DataTy pe *x)/*删除顺序

10、表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->listi;/*保存删除的元素到x中*/*依次前移*/for(j = i+1; j <= l_->size-1; j+)L-&g

11、t;listj-1 = l_->listj;L->size-;/元素个数减1return 1;int ListGet(SeqList L, i nt i, DataTy pe *x)/*取顺序表L中第i个数据元素存于x中，成功返回1,失败返回0*/if(i < 0 II i > L.size-1)printf("参数i不合法!n");return 0; else*x = L.listi; return 1; 基本函数为Dijkstra 算法算法具体步骤（1） 初始时，S只包含源点，即 S=, v的距离为0。U包含除v外的其他顶点，U中顶 点U距离为边

12、上的权（若 v与U有边）或）（若U不是v的出边邻接点）。（2） 从U中选取一个距离 v最小的顶点k,把k,加入S中（该选定的距离就是v到k 的最短路径长度）。（3） 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点U （ U U ）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点 U的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在三. 调试分析把图中顶点集合V分成两组，第S中只有一个源点，以后每求得一S中，算法就结束了），第二U表示），按最短路径长度的递增次序依次把第v到S中各顶点的最短路径长度不S中的顶点Dijkst

13、ra算法思想为：设 G=（V,E）是一个带权有向图， 一组为已求出最短路径的顶点集合（用 S表示，初始时 条最短路径，就将加入到集合S中，直到全部顶点都加入到 组为其余未确定最短路径的顶点集合（用v到此顶点只包括 S二组的顶点加入 S中。在加入的过程中，总保持从源点 大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离, 的距离就是从 v到此顶点的最短路径长度，U中的顶点的距离，是从中的顶点为中间顶点的当前最短路径长度。空间复杂度度Dijkstra算法的时间复杂度为0（n人2）0( nA2)四.用户手册1.首先选择要进行的操作2选3. 选4. 选4.选空间复杂度取决于存储方式，

14、邻接矩阵为1、2、3、4分别为查询景点信息、问路查询、修改景点信息、退出。1输入景点代号即可进行信息查询。2输入两景点代号即可进行问路查询。并输出最短路径长度以及两路径的景点。3输入景点代号即可进行修改。5选4退出五.测试数据及测试结果中国地质大学、地图信息驭教一楼1.教二搂2.教三楼3.主楼4.图书馆5.北一楼氣北二楼 J北三楼8、北综沢北区图书馆二、可供操作校园内各景点2.问路查询3修改景点信息现在请选择相关操作:号 :代 作点 关的 择畫 选要 现请吓如息言地点为=王楼 楼层为汐 救室数为汚D理套请选操佞MW-：2:豔瀬离为如从教二楼到北区图书馆路程为;教二楼一教三楼一北三搂一北区图书馆

15、地点为：3,弘毅堂 楼层为:丄教室数为洱现在谙选择相关操作：4Press any k亡y to continue六.源程序清单typ edef structDataTy pe listMaxSize; int size ;SeqList;IIIII初始化顺序表void ListI ni tiate(SeqList *L)L->size = 0;int ListLe ngth(SeqList L)return L.size;int ListI nsert(SeqList *L, int i, DataT ype x)在顺序表L的第i(0 <= i = size)个位置前插入数据元素值

16、x*I插入成功返回1，插入失败返回/*初始化顺序表L*/*返回顺序表L的当前数据元素个数*/I*I*0*1int j;if(L->size >= MaxSize)>=printf（"顺序表已满无法插入 return 0;!n");else if(i < 0 | i > L->size)printf("参数i不合法!n"); return 0;elseI*为插入做准备*Ifor(j = L->size; j > i; j-)L->listj = L->listj-1; L->listi =

17、x;L->size+;return 1;II元素个数加1int ListDelete(SeqList *L, i nt i, DataTy pe *x)I*删除顺序表L中位置为i(0 <= i = size-1)的数据元素并存放到x中*II*删除成功返回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

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

19、sti; return 1; #i nclude "SeqList.h"/邻接矩阵实现图的存储类型定义typ edef structSeqList vertices;/存放顶点的顺序表int edgeMaxVerticesMaxV ertices; / 存放边的邻接矩阵 int numOfEdges;边的数目AdjMGraph;/图的结构体定义 typ edef structint row; /行下标 int col; 列下标 int weight;权值RowColWeight;/边信息结构体定义 struct massageschar n ame20;int num;in

20、t cen;massage10="教一楼",50,7,"教二楼",50,7,"教三楼",50,7,"主楼",50,7,"图书馆 ",50,"北一楼",50,7,"北二楼",50,7,"北三楼",50,7,"北综",50,7,"北区图书馆",50,7;置带权有向图G为空图，时间复杂度:O(1)。void Grap hI nitiate(AdjMGra ph *G)int i,j;for(i=0;i&

21、lt;MaxVertices;i+)for(j=0;j<MaxVertices;j+)if(i=j) G->edgeij=0;else G->edgeij=MaxWeight; /MaxWeight 表示权值无穷大G-> num OfEdges=0;边的条数置为 0ListI ni tiate(&G->vertices);/ 顶点顺序表初始化int lsVertex(AdjMGraph *G QataType vertex)int i;for (i=O;i<G->vertices.size;i+)if(G->vertices.listi=

22、vertex) break;if (i=G->vertices.size)return -1;elsereturn i;void In sertVertex(AdjMGra ph *G,DataTy pe vertex) if(IsVertex(G,vertex)<0)if(ListI nsert(&G->vertices,G->vertices.size,vertex)=0)/在顶点顺序表的表尾插入顶点 vertexprintf（”插入顶点时空间已满无法插入！"）;exit（1）;void InsertEdge(AdjMGraph *G ,int v

23、1,int v2,int weight)DataT ype x; if(v1!=v2)if(ListGet(G->vertices,v1, &x)=0)|(ListGet(G->vertices,v2, &x)=0) printf(”插入边时参数 v1和v2越界出错！n");exit(1);G->edgev1v2=weight;G-> num OfEdges+;int IsEdge(AdjMGra ph *G,i nt v1,i nt v2)DataT ype x;if(ListGet(G->vertices,v1, &x)=0)

24、 | (ListGet(G->vertices,v2, &x)=0)printf（"边的参数v1和v2越界出错！n”）;return 0;if(G->edgev1v2 = MaxWeight | v1=v2) printf("该边不存在！n");return 0;return 1;void DeleteEdge(AdjMGra ph *G,i nt v1, in t v2)if (IsEdge(G,v1,v2)=0)printf("删除边时出错！"); exit(1);elseG->edgev1v2=MaxWeight

25、;G->num OfEdges-;计算带权有向图 G中第v个顶点的入度，时间复杂度:O(n)。 int InDegree(AdjMGraph *G ,int v)/在此插入你第二步的代码，替换掉下面的语句 int din=O,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)/在此插入你第二步的代码，

26、替换掉下面的语句 int dou=0,j;for(j=0;j<G->vertices.size;j+)if(G->edgejv!=0&&G->edgevj!=MaxWeight) dou+;return dou;计算带权有向图G中第v个顶点的度，时间复杂度：O(n)。int Degree(AdjMGra ph *G,i nt v)return(I nDegree(G ,v)+OutDegree(G ,v);在带权有向图G中删除第v个顶点，时间复杂度：O(n人2)。 void DeleteVertex(AdjMGraph *G ,int v)/在此插入你第

27、一步的代码int j=0,i;if(v>G->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<

28、;G->vertices.size-1;j+)G->vertices.listj=G->vertices.listj+1;G->vertices.size-;在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该 顶点在顶点顺序表的序号，否则返回-1.时间复杂度：0(n)。int GetFirstVex(AdjMGraph G ,int v)int coIQataT ype 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;DataT ype x;if(ListGet(G.vertices,v1, &x)=0)|(ListGet

30、(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 col;return -1;创建有向图

31、G,通过在空图G中插入n个顶点和e条边实现。时间复杂度：0(nZ+e)。void GraphCreat(AdjMGraph *G QataType v,int n,RowColWeight W,int e)int i,k;Graphin itiate(G);for(i=0;i< n; i+)In sertVertex(G,vi);for(k=0;k<e;k+)In sertEdge(G,Wk.row,Wk.col,Wk.weight);void Dijkstra(AdjMGraph G ,int v0,int distance,int path) int n=G.vertices.

32、size;int *s=(i nt *)malloc(sizeof( in t)* n);int min Dis,i,j,u;for (i=0;i <n ;i+)dista ncei=G .edgev0i;si=0;if (i!=v0&&dista ncei<MaxWeight) p athi=v0;else p athi=-1;sv0=1;for (i=0;i <n ;i+)min Dis=MaxWeight;for (j=0;j< n;j+)if (sj=0&&dista ncej<mi nDis) u=j;min Dis=di

33、sta ncej;if (mi nDis=MaxWeight)return;su=1;for (j=0;j< n;j+)if (sj=0&&G .edgeuj<MaxWeight&&distanceu+G.edgeuj<distancej) distancej=distanceu+G .edgeuj;p athj=u;#i nclude <stdio.h>#i nclude <stdlib.h>#i nclude <malloc.h> typ edef int DataT ype; #defi ne MaxS

34、ize 100 #defi ne MaxVertices 15 #defi ne MaxWeight 10000 #i nclude "AdjMGra ph.h"#i nclude "Dijkstra.h" void mai n()int p 10;int flog=0;AdjMGra ph g;int i,j,k,o,l, n=10,e=30,t;int dista nce10, path10;DataT ype a=0,1,2,3,4,5,6,7,8,9;RowColWeight rcw=0,3,20,0,4,15,1,2,30,2,1,30,2,3

35、,50,2,4,65,2,7,653,2,8,700,3,0,20,3,2 ,50,3,4,6,4,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 out pu t(i nt t);Grap hCreat(&g,a, n,rcw,e);Dijkstra(g,0,dista nce,p ath);printf("nnntt 中国地质大学 nn”)； printf("t 一、地图信息 nrr);printf("t0、教一楼 1、教二楼2、教三楼printf("nt5、北一楼6、北二楼7、北三楼printf("t 二、可供操作 nn");printf("t1、校园内各景点 nn");printf("t2、问路查询 nn");printf("t3、修改景点信息