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

《数据结构旅游区导航图课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、--《数据结构课程设计》报告题目旅游区导游图专业计算机科学与技术班级（2）班学生###--优质---13旅游区导游图题目容问题描述：设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m

2、旅游景点图。⑵相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。⑶--优质---景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。⑷景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。⑸最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。⑹设计一个菜单，上述操作要求都作为菜单中的主要菜单项

3、。⒈本人完成的工作完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。⒉所采用的数据结构邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）数据结构的定义//邻接矩阵结构体typedefstruct{charvex1,vex2;/*弧或边所依附的两个顶点*/intArcVal;/*弧或边的权值*/}ArcType;/*弧或边的结构定义*/typedef

4、struct{intvexnum,arcnum;/*图的当前顶点数和弧数*/--优质---charvexs[MAXVEX];/*顶点向量*/intadj[MAXVEX][MAXVEX];}MGraph;/*图的结构定义*///邻接链表结构体typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置intinfo;//该弧的相关信息,这里用于存放权值structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVnode//邻接表头结点的类型{cha

5、rdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefstruct{VNodeAdjList[MAXVEX];intvexnum,arcnum;//图中顶点数n和边数e}ALGraph;//图的邻接表类型⒈所设计的函数--优质---对于每个主要函数必须给出所采用的算法思想和程序框图；邻接矩阵和邻接链表初始化函数MGraph*Init_MGraph()/*图的初始化*/{MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));G->vexnum=0;G-

6、>arcnum=0;/*初始化顶点数、边数*/return(G);}ALGraph*Init_ALGraph()/*图的初始化*/{ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));G->vexnum=0;G->arcnum=0;/*初始化顶点数*/return(G);}图中顶点定位的函数，判断顶点是否重复输入了intLocateVex(MGraph*G,charvp)/*图中顶点的定位，若图中有顶点vp，返回其在顶点数组的下标值*/{intk;for(k=0;k<=G->vexnum;

7、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("图中顶点数已达到最多!");else{if(LocateVex(G,vp)==-1){k=G->vexnum;G->vexs[G->v

8、exnum++]=vp;for(j=0;jvexnum;j++){G->adj[j][k]=INFINITY;G->adj[k][j]=INFINITY;/*是带权的有向图或无向图*/开始把这个点跟其他所有点建立关系，为INFINITY，表示不存在连通关