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

数据结构旅游区导航图课程设计题目旅游区导游图专业计算机科学与技术班级（2）班学生向13旅游区导游图题目内容问题描述：设某个旅游区共有n个旅游景点（n>10）,每个旅游景点都与相邻的m个旅游景点（mN2,m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。以（M,Vj,d）的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi与Vj表示两个不一致的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图使用邻接矩阵存储结构（数组）。实现要求：旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。相邻景点查询：假设关于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点（有直接的道路相通）及对应的距离。景点路线查询：假设关于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。（4）景点路线综合查询：关于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路务必通过所有的旅游景点（有些景点能够重复通过）且走的路最短。（6）设计一个菜单，上述操作要求都作为菜单中的要紧菜单项。1 .本人完成的工作完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题,设计主函数。2 .所使用的数据结构邻接矩阵的数据结构，包含（弧/边的结构定义、图的结构定义）邻接链表的数据结构，包含（弧/边的结点定义、邻接表头结点定义、图的结构定义）数据结构的定义邻接矩阵结构体typedefstructcharvexl,vex2;/*弧或者边所依附的两个顶点/intArcVal;/*弧或者边的权值*/JArcType;/*弧或者边的结构定义*/typedefstruct（intvexnum,arcnum;/*图的当前顶点数与弧数*/charvexsMAXVEX;/*顶点向量/intadjMAXVEXMAXVEX;MGraph;/*图的结构定义/邻接链表结构体弧的结点结构类型typedefstructANodeintadjvex;该弧的终点位置intinfo;该弧的有关信息,这里用于存放权值structANode*nextarc;指向下一条弧的指针ArcNode;typedefstructVnode邻接表头结点的类型(chardata;顶点信息ArcNode*firstarc;指向第一条弧VNode;typedefstruct(VNodeAdjListtMAXVEX;intvexnum,arcnum;图中顶点数n与边数eALGraph;图的邻接表类型3 .所设计的函数关于每个要紧函数务必给出所使用的算法思想与程序框图；邻接矩阵与邻接链表初始化函数MGraph*Init_MGraph()/*图的初始化*/(MGraph*G;G=(MGraph*)malloc(sizeof(MGraph);G->vexnum=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(MGraph*G,charvp)*图中顶点的定位，若图中有顶点vp,返回其在顶点数组的下标值*/for(k=0;k<=G->vexnum;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;j<G->vexnum;j+)(G->adjjk=infinity；G->adjkj=infinity；*是带权的有向图或者无向图*/往图的邻接矩阵中添加边(弧)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)*输出图的顶点矩阵与邻接矩阵*/(intk,j;Printf("图的顶点如下：);for(k=0;k<G->vexnum;k+)printf("%4c”,G->vexsk);printfCnn*);Printf("图的邻接矩阵如下：n*);for(k=0;k<G->vexnum;k+)for(j=0;j<G->vexnum;j+)if(G->adjkj=INFINITY)以邻接矩阵作为图的存储结构建立图MGraph*create_graph()/*以邻接矩阵作为图的存储结构建立图*/(charinchar100,enchar100,fvex,Ivex;intcount=0;intweightMGraph*G;ArcType*arc;Printfc首先进行图的初始化！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*,&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;i<G->vexnum;i+)G->AdjListi.firstarc=NULL;for(i=O;i<n;i+)检查邻接矩阵中每个元素(for(j=n-l;j>=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;ArcNode*p;for(i=0;i<g->vexnum;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)(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;i<g->vexnum;i+)(distancei=g->adjvi;Si=0;if(distancei<INFINITY)prei=v;elseprei=-l;SvO=l;顶点v已加入到集合S中for(i=0;i<g->vexnum;i+)(min=INFINITY;for(j=0;j<g->vexnum;j+)(if(!Sj&&distancej<min)min=distancej;k=j;Sk=l;/将找到的