数据结构旅游区导航图课程设计.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;/将找到的顶点加入到集合S中for(w=0;w<g->vexnum;w+)/修改集合T中顶点的距离值if(!Sw&&distancew>distancek+g->adjkw)distancew=distancek+g->adjkw;prew=k;Printf("查询结果:n");for(j=0;j<g->vexnum;j+)输出结果if(prej!=-l)(Printf("从景点c到景点c”,G->AdjListvO.data,g->vexsj);p=prej;Printf("的最短距离是：%d*,distancej);PrintfC途中通过的景点有：")；while(p!=-l)(printf("%c*,g->vexsp);p=prep;printf(*n*);elseif(j!=v)Printf("n%c到c:nopath*,g->vexsj,g->vexsv);景点路线综合查询：关于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。voidDijkstra_Two(ALGraph*G,MGraph*g,intv,intdistance,intpre)/带权图G从顶点v到其他定点的最短距离distance与最短路径前驱结点的下标preintw;intS30,i,j,k,p,min,d;Printf(“你所要开始查询的开始景点是:cnn",G->AdjListv.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+)Diin=INFINITY;for(j=0;j<g->vexnum;j+)if(!SjAAdistancej<min)(min=distancej;k=j;Sk=l;/将找到的顶点加入到集合S中for(w=0;w<g->vexnum;w+÷)/修改集合T中顶点的距离值if(!SwAAdistancew>distancek+g->adjkw)(distancew=distancek+g->adjkw;prew=k;Printf("输入你要查询的另外一个景点(下标值)：);scanf(*%d*,&d);Printf("你要查询的另外一个景点是:cn”,g->vexsd);PrintfCn查询结果:n)；输出结果if(pred!=-l)(Printf("从景点c到景点c",G->AdjListvO.data,g->vexsd);p=pred;Printf("的最短距离是：%d*,distanced);PrintfC途中通过的景点有:")；while(p!=-l)printf("%c*,g->vexsp);p=prep;最小的路径长度distancew是否大于distancew+边adjkw的值从VO出发到W的最短距离distancew=从VO出发到W的最短距离distancek+边adjkw的权值最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路务必通过所有的旅游景点(有些景点能够重复通过)且走的路最短。voiddfs_path(ALGraph*g,intsrc,intcur,intvis,GPath*cur_path,GPath*min_path)(if(vissrc)(if(cur-path->count=g->vexnum)(if(cur_path->value<min_path->value)(memcpy(min_path,cur_path,sizeof(GPath);/*由CUr_Path所指内存区域复制SiZeOf(GPath)个字节到min,path所指内存区域*/return;return;ArcNode*node=g->AdjListcur.firstare;for(;node!=NULL;node=node->nextarc)/起始条件为node=g->AdjListcur.firstarc*/charadj=node->adjvex;intIndex=LocateVex(g,adj);if(visindex=0)cur_path->vertexcur_path->count+=index;cur_path->value+=node->info;visindex=l;dfs_path(g,src,index,vis,cur_path,min_path);cur_path->count;cur-path->value-=node->info; visindex=O;voidbest_path(ALGraph*g,intsrc)(intvisMAXVEX;memset(vis,0,sizeof(vis);GPathcur_path,min_path;memset(&cur_path,0,SiZeOf(GPath);/*将cur_path所指向的某一块内存中的每个字节的内容全部设置为O指定的ASCII值，块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作，其返回值为指向CUr_Path的指针。*/memset(&min_path,O,SiZeof(GPath);/*将min_path所指向的某一块内存中的每个字节的内容全部设置为O指定的ASCII值，块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作，其返回值为指向Inin-Path的指针。*/min_path.Value=INFINITY;dfs_path(g,src,src,vis,&cur_path,&min_path);if(min_path.value!=INFINITY)inti=0;printfn最佳旅游路线景点下标值是:n");for(i=0;i<min_path.count;i+)(printf(*%d->”,min_path.vertexi);printf(*n*);printf(*n最佳旅游路线景点是:n");for(i=0;i<min_path.count;i+)(printf(*%c->”,g->AdjListmin_path.vertexi.data);printf(*n*);else(Printf("建立的图中没有最佳路径n");主函数voidmain()(intn,opse,v,i;intdistanceMAXVEX,pre2*MAXVEX,pathMAXVEX;ALGraph*G;MGraph*M;doprintf(11n请选择对图的操作要求:nr);for(n=0;n<=30;n+)printf('*');printf(*n*);PrintfCl一一建立图的邻接矩阵”);PrintfC2图的邻接矩阵的输出”)；printf("*n");printf(*n*");printfC3图的邻接链表的输出“)；printf4相邻景点查询“)；printf("*n*);printfCn*");printfC5一一从某点出发到另外所有点最短简单路径及距离printf("*n*);printfCn*");printfC6一一两个景点之间的最短距离(下标值)printf("*n*);printfCn*");printfC7一一最佳路径”)；printf(*8退出“)；printf("*n*);for(n=0;n<=30;n+)printf('*");printfCnnO;doscanf("%d”,feopse);while(opse<lopse>8);switch(opse)(case 1:M=(MGraph*)malIoc(sizeof(MGraph);M=create_graph();Printf(“nn");break;case 2:Printf("n您所建立的图是：n*);output_graphic(M);break;case 3:printf(图G的邻接矩阵转换成邻接表:n");G=MGraphToALGraph(M,G);OUtPUt_graphic_c(M,G);break;case 4:(Printf("n相邻景点是：n");output_Find_ALGraph(G);break;case 5:Printf("n最短简单路径及距离是：n");scanf("%d*,&vO);Dijkstra_One(G,M,v,distance,pre);break;case 6:(Printf("两个景点之间的最短距离(下标值)：“)；scanf("%d*,&v0);Dijkstra_Two(G,M,v,distance,pre);break;case 7:(Printf("最佳路径(下标值)：")；Dijkstra(M,0,distance,path);PrintfC从结点%c到其他各结点的最短距离为:n",M->vexsO);for(i=l;i<M->vexnum;i÷+)printf("到结点c的最短距离为d:n*,M->vexsi,distancei);printf从结点c到其他各结点最短路径的前一结点为:n”,M->vexs0);for(i=l;i<M->vexnum;i+)if(pathi!=-l)printfC到结点c的前一结点为c:n*,M->vexsi,M->vexspathi);break;while(opse!=8);调用OUtPUt_graphic()邻接矩阵的输出4.每个题目都务必有运行时的输入数据（随机产生的数据要求输出显示），运行的输出结果。建立邻接矩阵:请选择对图的操作要求：1二二图的邻接矩阵2一一图的邻接矩阵的输出- 3-图的邻接槌表的输出4一一相邻景点查询（下标值）*- 5从某点出发到另外所有点最短简单路径及距离<下标值）*- 6-一两个景点之间的最短距离（下标值>>"7最佳路径8退出"营先进行图的初始化H请以顶点.顶点,权值的形式输入图的边（或弧，第一个顶点是?表示结束：ab1请继续输入下一条边（或弧ae2语继续输入下一条边（或瓠>，？be3请继续输入下一条边（或弧>，bc4请继续输入下一条边<或弧）”c5请继续输入下一条边<或弧X?Cd6请继续输入下一条边或弧）”d7请继续输入下一条边或弧？邻接矩阵输出:请选择对图的操作要求：“J二莹之图的邻接矩阵2-图的邻接矩阵的输出*”3一一图的邻接链表的输出4一一相邻景点查询<下标值>"“5-从某点出发到另外所有点最短简单路径及距离<下标值>"* 6-两个景点之间的最短距离<下标值)* 7-最佳路径8-退出*“XXXXX2您所建立的图是：图的顶志如下，abecd图的邻接矩阵如下：£2M*M1 W*34*2 3*S7*45*6>MM<M?6*邻接链表输出:请选择对图的操作要求：* 7二港W图的邻接矩阵2图的邻接矩阵的输出* 3一一图的邻接链表的输出4相邻景点查询<下标值* 5一一从某点出发到另外所有点最短简单路径及距离下标值* 6一两个景点之间的最短距离<下标值)* 7最佳路径8退出*XXX兴XX3图G的邻接矩阵转换成邻接表：a-><b,l>-><e,2>b-><a,l>-><e,3>-><c,4>e-><a,2>-><b,3>-><c,5>>><d,7>c->(b,4)-><e,5>-><d,6>d-><e,7>-><c,6>相邻景点查询:点选择对图的操作要求：* M兴X兴兴* 1一一建立图的邻接矩阵2一一图的邻接矩阵的输出*3图的邻接链表的输出4相邻景点查询<下标值）*5一一从某点出发到另外所有点最短简单路径及距离<下标值）*6一两个景点之间的最短距离下标值）*7最佳路径8退出*>>通通BUBW77fjPtfnYK-道道一(zl点两两<<12Bl-=一的的be点aa点点从某点出发到另外所有点最短简单路径及距离:请选择对图的操作要求：:&W图的邻接矩阵2图的邻接矩阵的输出* 3图的邻接链表的输出4相邻景点查询<下标值）* 5-从某点出发到另外所有点最短简单路径及距离（下标值* 6一两个景点之间的最短距离（下标值* 7最佳路径8退出*5输入一个顶点是：点点点l= 离离离离 -=一 OOO4Q 短短短短 中«.:皆“ b e C d 点点点占 旦s置邕12 5 9有有有有 i点占点 Sss 过过过过 经经经经 口口m口 途途途途两个景点之间的最短距离:请选择对图的操作要求：* :二%妄图的邻接矩阵2一一图的邻接矩阵的输出* 3图的邻接链表的输出4相邻景点查询下标值* 5一从某点出发到另外所有点最短简单路径及距离（下标值* 6一两个景点之间的最短距离（下标值）* 7最佳路径8退出*共X*XXX器所要开始查询的开始景点是：次要查询的另外一个景点是：C查询结果：从到景点C的最短距离是：5途巾经过的景点有：ba最佳路径:F：相展学习DebugTe×tlexe:“I二二壹3图的邻接矩阵* 3一一图的邻接链表的输出2图的邻接矩阵的输出4相邻景点查询 下标值）,5一一从某点出发到另外所有点最短简单路径及距离（下标值）8退出；6两个景点之间的最短距离<下标值）*7最佳路径7输入你要查询的开始景点:a最佳旅游路线景点下标值是:1->3->4->2->0->最佳旅游路线景点是:b->c->d->e->a->请选择对图的操作要求:* * X * X :1一一建立图的邻接矩阵* 3图的邻接链表的输出2一一图的邻接矩阵的输出4-相邻景点查询下标值）8退出F5一一从某点出发到另外所有点最短简单路径及距离下标值）*6一一两个景点之间的最短距离<下标值）*7一一最佳路径*X兴头头7输入你要查询的开始景点:b最佳旅游路线景点下标值是:0->2->4->3->1->5.每个函数中应给出尽可能全面的中文注释。（源程序-全）#include*stdio.h*#include*malloc.h*#include"string,h”#defineINFINITY32767/最大值8*/*根据图的权值类型，分别定义为最大整数或者实数*/#defineMAXVEX30/*最大顶点数目*/邻接矩阵结构体typedefstructcharvexl,vex2;/*弧或者边所依附的两个顶点/intArcVal./弧或者边的权值*/ArcType;/*弧或者边的结构定义/typedefstruct(intvexnum,arcnum;/*图的当前顶点数与弧数/charvexsMAXVEX;/*顶点向量/intadjMAXVEXMAXVEX;MGraph;/*图的结构定义/typedefstructPath(intvertexMAXVEX;intvalue;intcount;GPath;邻接链表结构体typedefstructANode弧的结点结构类型intadjvex;/邻接点在头结点数组中的位置（下标）intinfo;该弧的有关信息,这里用于存放权值structANode*nextarc;指向下一条弧的指针ArcNode;typedefstructVnode邻接表头结点的类型(chardata;顶点信息ArcNode*firstarc;指向第一条弧VNode;typedefstruct(VNodeAdjListMAXVEX;邻接表数组intvexnum,arcnum;图中顶点数n与边数eALGraph;图的邻接表类型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=0;G->arcnum=O;/*初始化顶点数*/return(G)intLocateVex(MGraph*G,charvp)/*图中顶点的定位，若图中有顶点vp,返回其在顶点数组的下标值*/(intk;for(k=0;k<=G->vexnum;k+)if(G->vexsk=vp)return(k);return(-1);*图中无此顶点/intLocateVexx(ALGraph*G,charvp)/*图的顶点定位(图的顶点定位实际上是确定一个顶点在AdjList数组中的某个元素的data域内容。)*/(intk;for(k=0;k<G->vexnum;k+)if(G->AdjListk.data=vp)return(k);*假如存在此顶点返回顶点数组下标值*/return(-1);/*假如没有则返回T(图中无此顶点)*/voidAddVertex(MGraph*G,charvp)*往图的顶点数组中增加顶点*/(intk,j;if(G->vexn三>=MAXVEX)Printf("图中顶点数已达到最多！n");else(if(LocateVex(G,vp)=-l)图中无此顶点(k=G->vexnum;G->vexsG->vexnum+=vp;for(j=0;j<G->vexnum;j+)(G->adjjk=INFINi;G->adjkj=INFINi;/*是带权的有向图或者无向图*/voidAddArc(MGraph*G,ArcType*arc)/*往图的邻接矩阵中添加边(弧)*/intk=0,j=0;R=LocateVex(G,arc->vexl);J=LocateVex(G,arc->vex2);(G->arcnum+;G->adjkj=arc->ArcVal;G->adjjk=arc->ArcVal;/*是无向图或者带权的无向图,需对称赋值*/voidoutput_graphic(MGraph*G)/*输出图的顶点矩阵与邻接矩阵*/(intk,j;Printf("图的顶点如下：n");for(k=0;k<G->vexnum;k+)printfC%4c*,G->vexsk);printfCnn*);Printf("图的邻接矩阵如下：n);for(k=0;k<G->vexnum;k+)(for(j=0;j<G->vexnum;j+)if(G->adjkj=INFINITY)printf("%4s","*")elseprintf(*%4d*,G->adjkj);printfCnn*);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)malIoc(sizeof(ArcType);printf(n请以(顶点,顶点,权值)的形式输入图的边(或者弧),第一个顶点是?表示结束：不);while(l)(scanf(*%s*,inchar);fvex=incharO;/*输入第一个顶点，？结束*/if(fvex=三,?')break;else(AddVertex(G,fvex);scanf("%s”,enchar);lvex=enchar0;AddVertex(G,lvex);/*输入第二个顶点与权值*/scanf(*%d*,&weight);arc->vexl=fvex;arc->vex2=lvex;arc->ArcVal=weight;AddArc(G,arc);printfCn请继续输入下一条边(或者弧)