文档介绍：《数据结构》课程设计报告内容及其格式《数据结构课程设计》报告题目旅游区导游图专业计算机科学与技术班级(2)班学生### 《数据结构》课程设计报告内容及其格式 13 旅游区导游图题目内容问题描述: 设某个旅游区共有 n 个旅游景点( n≥10), 每个旅游景点都和相邻的 m个旅游景点(m≥2, m<n )有直接的道路(有对应的距离)相通, 请设计一个简易的旅游区导游系统。以(V i,V j,d) 的形式从键盘输入建立该旅游区的旅游景点图,其中: V i和V j 表示两个不同的旅游景点,d表示这两个景点之间的道路距离;该旅游景点图采用邻接矩阵存储结构(数组)。实现要求: ⑴旅游景点图的输出:分别以邻接矩阵、邻接链表的方式输出该旅游景点图。⑵相邻景点查询:假设对于每个景点,设置有简易的信息查询,要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。⑶景点路线查询:假设对于每个景点,设置有景点路线查询,要求能给出从该景点出发到任一其它景点的最短简单路径及距离。⑷景点路线综合查询:对于该旅游区的任意两个景点,找出它们之间的最短简《数据结构》课程设计报告内容及其格式单路径及距离。⑸最佳旅游路线确定:假设该旅游区的入口也是出口,请确定一条最佳的旅游线路,该线路必须经过所有的旅游景点(有些景点可以重复经过)且走的路最短。⑹设计一个菜单,上述操作要求都作为菜单中的主要菜单项。⒈本人完成的工作完成的工作:首先是用邻接矩阵的存储形式建立无向带权图,然后将邻接矩阵转换为邻接链表,最后用狄克斯特拉函数求出后面的三道有关最短路径的小题, 设计主函数。⒉所采用的数据结构邻接矩阵的数据结构,包括(弧/ 边的结构定义、图的结构定义) 邻接链表的数据结构,包括(弧/ 边的结点定义、邻接表头结点定义、图的结构定义) 数据结构的定义// 邻接矩阵结构体 typedef struct { char vex1, vex2 ; /* 弧或边所依附的两个顶点*/ int ArcVal ; /* 弧或边的权值*/ }ArcType ; /* 弧或边的结构定义*/ typedef struct { int vexnum, um ; /* 图的当前顶点数和弧数*/ char vexs[MAXVEX] ; /* 顶点向量*/ int adj[MAXVEX][MAXVEX]; }MGraph ; /* 图的结构定义*/ // 邻接链表结构体《数据结构》课程设计报告内容及其格式 typedef struct ANode // 弧的结点结构类型{ int adjvex; // 该弧的终点位置 int info; // 该弧的相关信息, 这里用于存放权值 struct ANode *nextarc; // 指向下一条弧的指针} ode; typedef struct Vnode // 邻接表头结点的类型{ char data; // 顶点信息 ode *firstarc; // 指向第一条弧} VNode; typedef struct { VNode AdjList[MAXVEX]; int vexnum,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) ;} 图中顶点定位的函数,判断顶点是否重复输入了 int LocateVex(MGraph *G, char vp) /* 图中顶点的定位,若图中有顶点 vp ,返回其在顶点数组的下标值*/ { int k; for (k=0; k<=G->vexnum; k++) if (G->vexs[k]==vp) return(k) ; return(-1) ; /* 图中无此顶点*/ }N N YY 往图中增加顶点的函数 void AddVertex(MGraph *G, char vp) /* 往图的顶点数组中增加顶点*/ 开始 k=0 返回-1 k<= 顶点总数? G->vexs[k]==vp ? 返回 k 结束 k++ 《数据结构》课