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

《数据结构课程设计》报告
题 目 旅游区导游图
专 业 计算机科学与技术
班 级 （2）班
学 生 ###
13 旅游区导游图
题目容
问题描述：
设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。
以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构(数组)。
实现要求：
⑴ 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。
⑵ 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。
⑶ 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。
⑷ 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。
⑸ 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。
⑹ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。
本人完成的工作
完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。
所采用的数据结构
邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）
邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）
数据结构的定义
//邻接矩阵结构体
typedef struct
{ char vex1, vex2 ; /* 弧或边所依附的两个顶点 */
int ArcVal ; /* 弧或边的权值 */
}ArcType ; /* 弧或边的结构定义 */
typedef struct
{
int vexnum, arcnum ; /* 图的当前顶点数和弧数 */
char vexs[MAXVEX] ; /* 顶点向量 */
int adj[MAXVEX][MAXVEX];
}MGraph ; /* 图的结构定义 */
//邻接链表结构体
typedef struct ANode //弧的结点结构类型
{ int adjvex; //该弧的终点位置
int info; //该弧的相关信息,这里用于存放权值
struct ANode *nextarc; //指向下一条弧的指针
} ArcNode;
typedef struct Vnode //邻接表头结点的类型
{
char data; //顶点信息
ArcNode *firstarc; //指向第一条弧
} VNode;
typedef struct
{
VNode AdjList[MAXVEX];
int vexnum,arcnum; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
所设计的函数
对于每个主要函数必须给出所采用的算法思想和程序框图；
邻接矩阵和邻接链表初始化函数
MGraph *Init_MGraph()
/* 图的初始化 */
{
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)) ;
G->vexnum=0 ; G->arcnum=0 ; /* 初始化顶点数、边数 */
return(G) ;
}
ALGraph *Init_ALGraph()
/* 图的初始化 */
{
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph)) ;
G->vexnum=0 ;
G->arcnum=0; /* 初始化顶点数 */
return(G) ;
}
图中顶点定位的函