武汉理工大学数据结构与算法综合实验图与景区信息管理系统

学生学号 Xxxx 实验课成绩 学 生 实 验 报 告 书

实验课程名称 开课学院 指导教师姓名 学生姓名 学生专业班级

数据结构与算法综合实验 计算机科学与技术学院

xxx xxx xxxx

2015

-- 2016 学年 第 2 学期

1

实验课程名称： 数据结构与算法综合实验

实验项目名称 实验者 同组者 图与景区信息管理系统实践 xxx 专业班级 xxxx 报告成绩 组别 完成日期 2016年5月23日 第一部分：实验分析与设计（可加页） 一、 实验目的和要求 1.目的 ?掌握图的定义和图的存储结构。 ?掌握图的创建方法和图的应用 ?使用C++语言，定义图的数据结构，结合迭代开发思路实现“景区信息管理系统”。 ?掌握图的两种遍历方法和应用。 ?使用C++语言和深度优先算法实现“旅游景点导航”功能开发。 ?掌握迪杰斯特拉算法和应用。 ?使用C++语言和迪杰斯特拉算法实现“搜索最短路径”功能开发。 ?理解最小生成树的概念，掌握普里姆算法和应用。 ?使用C++语言和最小生成树算法实现“铺设电路规划”功能开发。 2.要求 ?开发景区信息管理系统，对景区的信息进行管理。 ?使用图的数据结构来保存景区景点信息，为用户提供创建图、查询景点信息、旅 游景点导航、搜索最短路径、铺设电路规划等功能。 二、 分析与设计 (1) 创建工程读取文件信息，创建图，输出周边景点信息读取景区信息文件，采用图的存储结构，创建景区景点图，查询景点信息。 (2)迭代开发，进行深度优先搜索，实现旅游景点导航。 (3)继续迭代，采用迪杰斯特拉算法、普里姆算法，实现搜索最短路径和电路铺 设，开发景区信息管理系统。 1.数据结构的设计 ?记录顶点信息的结构体 struct Vex { }; int num;//景点编号 char name[20];//景点名字 char desc[1024];//景点介绍 ?记录边的信息的结构体 struct Edge { 1

}; int vex1;//边的第一个顶点 int vex2;//边的第二个顶点 int weight;//权值 ?用来保存路径的链表的结构体 typedef struct Path { int vexs[20];//保存一条路径 Path *next; }*PathList; ?CGraph类用来实现相应功能的方法 class CGraph { private: }; int m_aAdjMatrix[20][20];//邻接矩阵 Vex m_aVexs[20];//顶点信息数组 int m_nVexNum;//当前图的顶点个数 void Init(void); bool InsertVex(Vex sVex); bool InsertEdge(Edge sEdge); Vex GetVex(int nVex); int GetVexnum(void); int FindEdge(int nVex,Edge aEdge[]); void DFS(int nVex,bool aVisited[],int &nIndex,PathList &pList); void DFSTraverse(int nVex,PathList &pList); int FindShortPath(int nVexStart,int nVexEnd,Edge aPath[]); void FindMinTree(Edge aPath[]); public: 2.核心算法设计 （1）输出周边景点信息 Input:操作表号与景点编号 Output:输入景点的周边景点信息 Process: int CGraph::FindEdge(int nVex,Edge aEdge[]) { int k=0; for(int i=0;i

} } aEdge[k].weight=m_aAdjMatrix[nVex][i]; k++; } return k;//返回边的条数 （2）深度优先搜索算法实现旅游景点导航 Input: 操作表号与景点编号 Output:从输入景点出发走遍整个景区的各种路线方案 Process: void CGraph::DFS(int nVex,bool aVisited[],int &nIndex,PathList &pList) { aVisited[nVex]=true;//改为已访问 pList->vexs[nIndex++]=nVex;//访问顶点 //判断是否所有节点都已访问过 int nVexNum=0; for(int i=0;i0)) { } 3

{ //新增链表节点，保存本次遍历的路径 pList->next=(PathList)malloc(sizeof(Path)); for(int i=0;inext; pList->next=NULL; pList->next->vexs[i]=pList->vexs[i]; //以该顶点为起点遍历剩下的顶点 DFS(i,aVisited,nIndex,pList); aVisited[i]=false;//访问状态置空 nIndex--;//回溯 } } } void CGraph::DFSTraverse(int nVex,PathList &pList) { } int nIndex=0; bool aVisited[MAX_VERTEX_NUM]={false}; DFS(nVex,aVisited,nIndex,pList); （3）Dijkstra算法搜索最短路径 Input: 操作表号与起始景点编号 Output: 从起始顶点到终点的最短路径 Process: int CGraph::FindShortPath(int nVexStart,int nVexEnd,Edge aPath[]) { for(int i=1;i

int nShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//保存最短路径 int nShortDistance[MAX_VERTEX_NUM];//保存最短距离 bool aVisited[MAX_VERTEX_NUM];//判断某顶点是否已经加入到最短路径 //初始化 int v; for(v=0;v