校园导航问题

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)函数接口

3、规格说明调用库函数为# include<stdio.h># include<stdlib.h># inelude<malloc.h>调用自定义函数为include"AdjMGraph.h"# include"Dijkstra.h"各函数说明voidListlnitiate(SeqListWL)P初始化顺序表L7intListLength(SeqListL)/*返回顺序表L的当前数据元素个数7intListlnsert(SeqList*L,inti,DataTypex)intListDelete(SeqList*L,in

4、ti,DataType*x)r删除顺序表L中位置为i(0<=i=size-1)的数据元素并存放到x中*/r删除成功返回1，删除失败返回07intListGet(SeqListL,intitDataType*x)r取顺序表l中第i个数据元素存于x中，成功返回1，失败返回o*/voidDijkstra(AdjMGraphGJntvOjntdistanceQJntpathQ)最短路径算法置带权有向图G为空图voidGraphlnitiate(AdjMGraph*G)判断顶点vertex是否是有向图G的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1。intlsVertex(AdjMGrap

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

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

7、空图G中插入n个顶点和e条边实现。时间复杂度:0(nT+e)。voidGraphCreat(AdjMGraph*G,DataTypev,intn.RowColWeightW,inte)2.3详细设计(1)数据结构设计(包括逻辑结构设计和存储结构设计)程序总动检测员标，初始化图形结构irrrm显示果.返回主菜单形式(2)算法设计基本数据结构为：typedefstruct(DataTypelistMaxSize;intsize;JSeqList;voidListlnitiate(SeqList*L)初始化顺序表L7(L->size=0;)intListLength(SeqListL)/返回顺

8、序表L的当前数据元素个数"(returnL.size;)intListlnsert(SeqList*L,inti,DataTypex)在顺序表L的第i(0<=i=size)个位置前插入数据元素值x/，插入成功返回1，插入失败返回07(intj;if(L->size>=MaxSize)(printf("顺序表已满无法插入!n");return0;)elseif(i<0|i>L->size)printf(H参数i不合法!nu);return0;)else(/*为插入做准备*/for(j=L->size;j>i;j-)L-

9、>listO=L->listj-1；L->listi=x;L>size+;H元素个数加1return1;)intListDelete(SeqList*L,inti,DataType*x)删除顺序表L中位置为i(0<=i=size-1)的数据元素并存放到x中*/删除成功返回1，删除失败返回07(intj;if(L->size<=0)(printf("顺序表已空无数据元素可删!n")；return0;)elseif(i<0|i>L->size-1)(printf("参数i不合法!n")；return

10、0;)else(-x=L->listi;/*保存删除的元素到X中*/*依次前移*/for(j=i+1;j<=L->size-1;j+)L->listj-1=L->listj；L->size-;/元素个数减1return1;)intListGet(SeqListL,inti,DataType*x)取顺序表L中第i个数据元素存于x中，成功返回1，失败返回07if(i<0|i>L.size-1)(printf("参数i不合法!n")；return0;)else(*x=L.listi;return1;)基本函数为Dijkstra算法算

11、法具体步骤（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（uU）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在S中三调试分析Dijkstra算法思想为：设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一组为

12、已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。空间复杂度度Dijkstra算法的时间复杂度为O（M2）空间复杂度取决于存储方式，邻接矩阵为0（M

13、2）四用户手册1.首先选择要进行的操作2选1、2、3、4分别为查询景点信息'问路查询'修改景点信息'退出。3.选1输入景点代号即可进行信息查询。4.选2输入两景点代号即可进行问路查询。并输出最短路径长度以及两路径的景点。4.选3输入景点代号即可进行修改。5选4退出五测试数据及测试结果-、地图信息叭教楼-教二楼汉教三楼3.主楼4.图书馆X北一楼桑北二楼入北三楼取北综趴北区图书馆二'可供操作校园内各景点2.问路查询矢修改景点信息4、退出现在请选择相关操作：地点为：主楼楼层为浮教室数为污D现荏酒选择相关埋绿2请输入蓉香街的两小I地点;1,9委到北区图书毒最短宙离为：7

14、。3从教二楼到北区图书总路程为：北三楼一北区图书馆地点为汴，趾裁堂楼层为：_L教室数为洱现在请选择相关操作：4*fbssan!/keytncontinue六.源程序清单typedefstruct(DataTypelistfMaxSize;intsize;JSeqList;/初始化顺序表voidListlnitiate(SeqList*L)/*初始化顺序表L7<L->size=0;)intListLength(SeqListL)/返回顺序表L的当前数据元素个数*/<returnL.size;)intListlnsert(SeqListinti,DataTypex)r在顺序表L的

15、第i(0<=i=size)个位置前插入数据元素值x*/插入成功返回1，插入失败返回。/intj;if(L->size>=MaxSize)printf(“顺序表已满无法插入!n");return0;)elseif(i<0|i>L->size)printf("参数i不合法!n");return0;)elser为插入做准备7for(j=L->size;j>i;j-)L->listO=L->listj-1;L->list(i=x;L->size+;元素个数加1return1;)intListDelet

16、e(SeqList*L,inti,DataType*x)"删除顺序表L中位置为i(0<=i=size-1)的数据元素并存放到x中*/r删除成功返回1，删除失败返回。/intj;if(L->size<=0)printf("顺序表已空无数据元素可删return0;elseif(i<0|i>L->size-1)(printf。'参数i不合法!nH);return0;else(*X=L->listi;r保存删除的元素到X中/*依次前移/for(j=i+1；j<=L->size-1;j+)L->listg-1=L-&

17、gt;listj;L->size-1/元素个数减1return1;intListGet(SeqListL,intifDataType*x)/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回07(if(i<0|i>L.size-1)(printf("参数i不合法!n");return0;else(*x=L.listi;return1;/include,SeqList.hM邻接矩阵实现图的存储类型定义typedefstruct(SeqListvertices;/存放顶点的顺序表intedgeMaxVerticesMaxVertices;/存放边的邻接

18、矢巨阵intnumOfEdges;边的数目JAdjMGraph;/图的结构体定义typedefstruct(introw;/行下标intcol;/列下标intweight;权值RowColWeight;/边信息结构体定义structmassages(charname20;intnum;intcen;massage10="教一楼”,50,7,“教二楼150,7,“教三楼150,7,"主楼*50,7,“图书馆50,“北一楼*50,7,"北二楼,50,7,"北三楼北0,7,”北综*50,7),"北区图书馆北0,7;/置带权有向图G为空图，时间复杂度:

19、0(1)-voidGraphlnitiate(AdjMGraph*G)(inti,j;for(i=0;i<MaxVertices;i+)forO=0;j<MaxVertices;j+)(if(i=j)G->edgei0J=O;elseG->edgeij=MaxWeight;/MaxWeight表示权值无穷大G->numOfEdges=0;边的条数置为0Listlnitiate(&G->vertices);/顶点顺序表初始化,intlsVertex(AdjMGraph*G,DataTypevertex)<inti;for(i=O;i<G-&

20、gt;vertices.size;i+)(if(G->vertices.listi=vertex)break;)if(i=G->vertices.size)return-1;elsereturni;voidlnsertVertex(AdjMGraph*G,DataTypevertex)if(lsVertex(G,vertex)<0)if(Listlnsert(&G->vertices,G->vertices.size,vertex)=O)/在顶点顺序表的表尾插入顶点vertex(printf("插入顶点时空间已满无法插入！")；exit

21、(1);)voidlnsertEdge(AdjMGraph*GJntvljntv2Jntweight)(DataTypex;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->numOfEdges+;)intlsEdge(AdjMGraph*G,intv1,intv2)(DataTypex;if(ListGet(G->

22、;vertices,v1,&x)=0)|(ListGet(G->vertices1v2,&x)=0)(printf("边的参数v1和v2越界出错！nH);return0;)if(G->edgev1v2=MaxWeight|v1=v2)(printf("该边不存在!n");return0;return1;voidDeleteEdge(AdjMGraph*G,intv1,intv2)(if(lsEdge(G,v1,v2)=0)(printf("删除边时出错！");exit；)else(G->edgev1v2=Max

23、Weight;G->numOfEdges-;计算带权有向图G中第v个顶点的人度，时间复杂度：O(n)。intlnDegree(AdjMGraph*G,intv)(在此插入你第二步的代码，替换掉下面的语句intdin=O,j;for(j=0;j<G->vertices.size;j+)(if(G->edgevj!=O&&G->edgev0!=MaxWeight)din+;)returndin;计算带权有向图G中第v个顶点的出度，时间复杂度：O(n)。intOutDegree(AdjMGraph*GJntV)(在此插入你第二步的代码，替换掉下面的语句i

24、ntdou=0,j;for(j=0;j<G->vertices.size;j+)(if(G->edgejv!=O&&G->edgev0!=MaxWeight)dou+;returndou;计算带权有向图G中第v个顶点的度，时间复杂度：O(n)-intDegree(AdjMGraph*Gjntv)<retum(lnDegree(G,v)+OutDegree(G,v);在带权有向图G中删除第v个顶点，时间复杂度：0(世2)。voidDeleteVertex(AdjMGraph*G,intv)(在此插入你第一步的代码intj=O,i;if(v>G-

25、>vertices.size)(printf。参数v出错!nH);return;for(j=v;j<G->vertices.size;j+)(for(i=O;i<G->vertices.size;i+)(G->edgeji=G->edgeji+1;)for(j=v;j<G->vertices.size-1;j+)(for(i=O;i<G->vertices.size;i+)(G->edgei0=G->edgei+10；)for(j=v;j<G->vertices.size-1;j+)G->verti

26、ces.listO=G->vertices.listO+1；G->vertices.size-;在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回.时间复杂度：0(n)ointGetFirstVex(AdjMGraphG,intv)(intcol;DataTypex;if(ListGet(G.vertices,v,&x)=O)(printf("取第一个邻接顶点时参数v越界出错！n");exit(1);)寻找邻接矩阵V行中从最左开始第一个值非零且非无穷大的权值对应的顶点for(col=0;col&

27、lt;G.vertices.size;col+)if(G.edgevcol>0&&G.edgevcol<MaxWeight)returncol;return-1;在带权有向图G中取第v1个顶点的继邻接结点第v2个顶点之后的下一个邻接结点，时间复杂度：0(n)。intGetNextVex(AdjMGraphG,intv1,intv2)intcol;DataTypex;if(ListGet(G.vertices,v1,&x)=0)|(ListGet(G.vertices,v2,&x)=0)(printf("取下一邻接顶点时参数v1和v2越界出错

28、！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)returncol;return-1;)创建有向图G,通过在空图G中插入n个顶点和e条边实现。时间复杂度：0(M2+e)。voidGraphCreat(AdjMGraph*

29、G,DataTypev,intntRowColWeightWOJnte)<inti,k;Graphlnitiate(G);for(i=0;i<n;i+)lnsertVertex(G,vi);for(k=0;k<e;k+)lnsertEdge(G,Wk.row,Wk.col,Wk.weight);)voidDijkstra(AdjMGraphGJntvOjntdistance。,intpath)(intn=G.vertices.size;int*s=(int*)malloc(sizeof(int)*n);intminDisjju;for(i=0;i<n;i+)(dista

30、ncei=G.edgevOi;si=0;if(i!=vO&&distancei<MaxWeight)pathi=vO;elsepathi=-1;)sv0=1;for(i=0;i<n;i+)(minDis=MaxWeight;for(j=O;j<n;j+)(if(sj=O&&distancej<minDis)(u=j;minDis=distancej;)if(minDis=MaxWeight)return;su=1;for(j=O;j<n;j+)(if(sj=0&&G.edgeuO<MaxWeight&&

31、amp;distanceu+G.edgeuj<distancej)(distanceO=distanceu+G.edgeuj;pathO=u;/include<stdio.h>/include<stdlib.h>/include<malloc.h>typedefintDataType;#defineMaxSize100#defineMaxVertices15#defineMaxWeight10000/includeMAdjMGraph.h"/include“Dijkstra.h"voidmain()(intp10;intflog=0

32、;AdjMGraphg;inti,j,k,o,l,n=10,e=30,t;intdistance10,path10;DataTypea=0,1,2,3,4,5,67,8,9;RowColWeightrcw0=0,3,20l0,4l15l1,2l30l2,1l30,2l3l50,2,4,65,2,7,653,2,8,700,3l0,20,3,2,50,3,4,6,4,0,1与,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);intoutput(intt);GraphCreat(&gfa,n,rcw,e);Dijkstra(g,O,distance,path);printf(,rnnntt中国地质大学nnM);printf(%一、地图信息nnH);printf"tO、教一楼1、教二楼2、教三楼3、主楼4、图书馆n");printf("nt5、北一楼6、北二楼7、北三楼8、北综9、北区图书馆nn");printf("t二、可供操作nn-);printf(