数据结构旅游区导航图课程设计.docx

《数据结构旅游区导航图课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构旅游区导航图课程设计.docx（57页珍藏版）》请在优知文库上搜索。

1、数据结构旅游区导航图课程设计题目旅游区导游图专业计算机科学与技术班级（2）班学生向13旅游区导游图题目内容问题描述：设某个旅游区共有n个旅游景点（n10）,每个旅游景点都与相邻的m个旅游景点（mN2,mvexnum=O;G-arcnum=O;/*初始化顶点数、边数*/return(G);ALGraph*Init_ALGraph()/*图的初始化*/ALGraph*G;G=(ALGraph)malIoc(sizeof(ALGraph);G-vexnum=O;G-arcnum=O;/*初始化顶点数*/return(G);图中顶点定位的函数，推断顶点是否重复输入了intLocateVex(MGrap

2、h*G,charvp)*图中顶点的定位，若图中有顶点vp,返回其在顶点数组的下标值*/for(k=0;kvexnum;if (G-vexsk=vp)return(k);往图中增加顶点的函数voidAddVertex(MGraph*G,charvp)结束/*往图的顶点数组中增加顶点*/intif(G-vexn三=MAXVEX)Printf(图中顶点数已达到最多！n);else(if(LocateVex(G,vp)=-1)(k=G-vexnum;G-vexsG-vexnum+=vp;for(j=0;jvexnum;j+)(G-adjjk=infinity；G-adjkj=infinity；*是带权

3、的有向图或者无向图*/往图的邻接矩阵中添加边(弧)voidAddArc(MGraph*G,ArcType*arc)/*往图的邻接矩阵中添加边(弧)/(intk=0,j=0;R=LocateVex(G,arc-vexl);J=LocateVex(G,arc-vex2);if(k=-lIIj=-l)Printf(边或者弧的顶点不存在，错误！n);elseG-arcnum+;G-adjkj=arc-ArcVal;G-adjjk=arc-ArcVal;/是无向图或者带权的无向图,需对称赋值/输出图的顶点矩阵与邻接矩阵voidoutput_graphic(MGraph*G)*输出图的顶点矩阵与邻接矩阵*

4、/(intk,j;Printf(图的顶点如下：);for(k=0;kvexnum;k+)printf(%4c”,G-vexsk);printfCnn*);Printf(图的邻接矩阵如下：n*);for(k=0;kvexnum;k+)for(j=0;jvexnum;j+)if(G-adjkj=INFINITY)以邻接矩阵作为图的存储结构建立图MGraph*create_graph()/*以邻接矩阵作为图的存储结构建立图*/(charinchar100,enchar100,fvex,Ivex;intcount=0;intweightMGraph*G;ArcType*arc;Printfc首先进行图

5、的初始化！nn);G=(MGraph*)malloc(sizeof(MGraph);G=Init_MGraph()arc=(ArcType*)malloc(sizeof(ArcType);printf(*n请以(顶点,顶点,权值)的形式输入图的边(或者弧)，第一个顶点是?表示结束：n*);while(l)(scanf(*%s*,inchar);fvex=inchar0;/*输入第一个顶点，？结束*/if(fvex=三,?)break;elseAddVertex(G,fvex);scanf(*%s*,enchar);lvex=encharO;AddVertex(G,lvex);scanf(*%d

6、*,&weight);*输入第二个顶点与权值*/arc-vexl=fvexarc-vex2=lvex;arc-ArcVal=weight;AddArc(G,arc);printf(*n请继续输入下一条边(或者弧)！n);)return(G);将邻接矩阵g转换成邻接表GALGraph+MGraphToALGraph(MGraph*g,ALGraph*G)(inti,j,n=g-vexnum;11为顶点数ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph);G-arcnum=g-arcnum;G-vexnum=g-vexnum;for(i=0;ivexnum;i

7、+)G-AdjListi.firstarc=NULL;for(i=O;i=0;j)if(g-adjij!=INFINITY)邻接矩阵的当前元素不为(P=(ArcNode*)malloc(sIzeof(ArcNode);创建一个结点*pG-AdjListj.data=g-vexsj;p-adjvex=g-vexsj;p-info=g-adjij;p-nextarc=G-AdjListi.firstarc;将*p链到链表后G-AdjListi.firstarc=p;returnG;邻接链表的输出voidoutput_graphic_c(MGraph*g,ALGraph*G)(inti;ArcNod

8、e*p;for(i=0;ivexnum;i+)(printf(%c”,G-AdjListi.data);p=G-AdjListi.firstarc;whiIe(p!=NULL)(printf(%s,-;printf(%c,%d)”,p-adjvex,p-info);p=p-nextarc;printfCnn*);相邻景点查询并输出voidoutput_Find_ALGraph(ALGraph*G)/*相邻景点查询并输出*/i11tj;ArcNode*p;PrintfC请输入你要查询的景点(下标值)：n);scanf(*%d*,&j);p=G-AdjListj.firstarc;while(p)

9、(Printf(景点%c到景点%c的距离是%d(该两个景点之间有直接的道路相通)n”,G-AdjListj.data,p-adjvex,p-info);p=p-nextarc;景点路线查询：假设关于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。voidDijkstra_One(ALGraph*G,MGraph*g,intv,intdistance,intpre)/带权图G从顶点v到其他定点的最短距离distance与最短路径前驱结点的下标preintw;intS30,i,j,k,p,min;Printf(你所要开始查询的景点是:cn”,G-AdjListvO.data);for(i=0;ivexnum;i+)(distancei=g-adjvi;Si=0;if(distanceiINFINITY)prei=v;elseprei=-l;SvO=l;顶点v已加入到集合S中for(i=0;ivexnum;i+)(min=INFINITY;for(j=0;jvexnum;j+)(if(!Sj&distancejmin)min=distancej;k=j;Sk=l;/将找到的