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

--------------------------校验:_____________--------------------------日期:_____________数据结构旅游区导航图课程设计《数据结构课程设计》报告题目旅游区导游图专业计算机科学与技术班级(2)班学生###13旅游区导游图题目内容问题描述:设某个旅游区共有n个旅游景点(n≥10),每个旅游景点都和相邻的m个旅游景点(m≥2,m<n)有直接的道路(有对应的距离)相通,请设计一个简易的旅游区导游系统。以(Vi,Vj,d)的形式从键盘输入建立该旅游区的旅游景点图,其中:Vi和Vj表示两个不同的旅游景点,d表示这两个景点之间的道路距离;该旅游景点图采用邻接矩阵存储结构(数组)。实现要求:⑴旅游景点图的输出:分别以邻接矩阵、邻接链表的方式输出该旅游景点图。⑵相邻景点查询:假设对于每个景点,设置有简易的信息查询,要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。⑶景点路线查询:假设对于每个景点,设置有景点路线查询,要求能给出从该景点出发到任一其它景点的最短简单路径及距离。⑷景点路线综合查询:对于该旅游区的任意两个景点,找出它们之间的最短简单路径及距离。⑸最佳旅游路线确定:假设该旅游区的入口也是出口,请确定一条最佳的旅游线路,该线路必须经过所有的旅游景点(有些景点可以重复经过)且走的路最短。⑹设计一个菜单,上述操作要求都作为菜单中的主要菜单项。本人完成的工作完成的工作:首先是用邻接矩阵的存储形式建立无向带权图,然后将邻接矩阵转换为邻接链表,最后用狄克斯特拉函数求出后面的三道有关最短路径的小题,设计主函数。所采用的数据结构邻接矩阵的数据结构,包括(弧/边的结构定义、图的结构定义)邻接链表的数据结构,包括(弧/边的结点定义、邻接表头结点定义、图的结构定义)数据结构的定义//邻接矩阵结构体typedefstruct{ charvex1,vex2;/*弧或边所依附的两个顶点*/intArcVal;/*弧或边的权值*/}ArcType;/*弧或边的结构定义*/typedefstruct{ intvexnum,um;/*图的当前顶点数和弧数*/ charvexs[MAXVEX];/*顶点向量*/ intadj[MAXVEX][MAXVEX];}MGraph;/*图的结构定义*///邻接链表结构体typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置intinfo;//该弧的相关信息,这里用于存放权值structANode*nextarc;//指向下一条弧的指针}ode;typedefstructVnode//邻接表头结点的类型{ chardata;//ode*firstarc;//指向第一条弧}VNode;typedefstruct{VNodeAdjList[MAXVEX];intvexnum,um;//图中顶点数n和边数e}ALGraph;//图的邻接表类型所设计的函数对于每个主要函数必须给出所采用的算法思想和程序框图;邻接矩阵和邻接链表初始化函数MGraph*Init_MGraph()/*图的初始化*/{ MGraph*G; G=(MGraph*)malloc(sizeof(MGraph)); G->vexnum=0;G->um=0;/*初始化顶点数、边数*/ return(G);}ALGraph*Init_ALGraph()/*图的初始化*/{ ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); G->vexnum=0; G->um=0;/*初始化顶点数*/ return(G);}图中顶点定位的函数,判断顶点是否重复输入了intLocateVex(MGraph*G,charvp)/*图中顶点的定位,若图中有顶点vp,返回其在顶点数组的下标值*/{ intk; for(k=0;k<=G->vexnum;k++) if(G->vexs[k]==vp)return(k);开始k=0返回-1k<=顶点总数?G->vexs[k]==vp?返回k结束k++ return(-1);/*图中无此顶点*/}NNYY往图中增加顶点的函数voidAddVertex(MGraph*G,charvp)/*往图的顶点数组中增加顶点*/{ intk,j; if(G->vexnum>=MAXVEX) printf("图中顶点数已达到最多!\n"); else { if(LocateVex(G,vp)==-1) { k=G->vexnum;G->vexs[G->vexnum++]=vp; for(j=0;j<G->vexnum;j++) { G->adj[j][k]=INFINITY; G->adj[k][j