旅游区导游图.docx

旅游区导游图

第一篇：旅游区导游图旅游区导游图题目内容：问题描述：设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m以(Vi,Vj,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点,d表示这两个景点之间的道路距离；该旅游景点图采用邻接链表存储结构。实现要求：⑴旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。⑵相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。⑶景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。⑷景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。⑸最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。⑹设计一个菜单，上述操作要求都作为菜单中的主要菜单项。代码如下：································#include“stdio.h”#include“malloc.h”#include“string.h”#defineINFINITY32767/*图的最大权值,32767是整数表示的最大值*/#defineMAX_VEX30/*最大顶点数目*/#defineMAX_VALUE999999999typedefintInfoType;typedefcharVexType;typedefenum{DG=1,AG=2,WDG=3,WAG=4}GraphKind;/*枚举常量定义旅游景点对应的图类型*/typedefstructPath{intvertex[MAX_VEX];intvalue;intcount;}GPath;typedefstructMGraph{charvexs[MAX_VEX];/*存放图的邻接矩阵的的顶点,顶点向量*/intarcs[MAX_VEX][MAX_VEX];/*存放图的邻接矩阵的边*/intvexnum,arcnum;/*图的当前顶点数和弧数*/}MGraph;/*图的邻接链表转换为矩阵后,图的结构定义*//*图的邻接矩阵存储结构中结点结构体的定义*/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////typedefstructLinknode{charadjvex;/*邻接点在头结点数组中的位置（邻接边的弧头顶点序号）*/InfoTypeinfo;/*与边或弧相关的信息,如权值*/structLinknode*nextarc;/*指向下一个表结点*/}LinkNode;/*邻接边单链表的结点结构体*//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////typedefstructVexNode{chardata;/*数据域存储顶点信息*/intindegree;/*顶点的度,有向图是入度或出度或没有*/LinkNode*firstarc;/*链域指向第一个表结点（邻接边头指针）*/}VexNode;/*顶点结点类型定义*/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////typedefstruct{GraphKindkind;/*图的种类标志*/intvexnum;/*顶点个数*/VexNodeAdjList[MAX_VEX];/*邻接表数组*/}ALGraph;/*图的结构定义*//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////ty