学生学号实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名学生姓名学生专业班级20172018学年第2学期实验课程名称:数据结构与算法综合实验实验项目名称图与景区信息管理系统实践报告成绩实验者专业班级组别同组者完成日期2018年5月23日第一部分:实验分析与设计(可加页)实验目得与要求目得=掌握图得定义与图得存储结构。=掌握图得创建方法与图得应用=使用C++语言,定义图得数据结构,结合迭代开发思路实现“景区信息管理系统”。=掌握图得两种遍历方法与应用。=使用C++语言与深度优先算法实现“旅游景点导航”功能开发。=掌握迪杰斯特拉算法与应用。=使用C++语言与迪杰斯特拉算法实现“搜索最短路径”功能开发。=理解最小生成树得概念,掌握普里姆算法与应用。=使用C++语言与最小生成树算法实现“铺设电路规划”功能开发。2、要求=开发景区信息管理系统,对景区得信息进行管理。=使用图得数据结构来保存景区景点信息,为用户提供创建图、查询景点信息、旅游景点导航、搜索最短路径、铺设电路规划等功能。分析与设计(1)创建工程读取文件信息,创建图,输出周边景点信息读取景区信息文件,采用图得存储结构,创建景区景点图,查询景点信息。(2)迭代开发,进行深度优先搜索,实现旅游景点导航。(3)继续迭代,采用迪杰斯特拉算法、普里姆算法,实现搜索最短路径与电路铺设,开发景区信息管理系统。数据结构得设计=记录顶点信息得结构体structVex{intnum;//景点编号charname[20];//景点名字chardesc[1024];//景点介绍};=记录边得信息得结构体structEdge{intvex1;//边得第一个顶点intvex2;//边得第二个顶点intweight;//权值};=用来保存路径得链表得结构体typedefstructPath{intvexs[20];//保存一条路径Path*next;}*PathList;=CGraph类用来实现相应功能得方法classCGraph{private:intm_aAdjMatrix[20][20];//邻接矩阵Vexm_aVexs[20];//顶点信息数组intm_nVexNum;//当前图得顶点个数public:voidInit(void);boolInsertVex(VexsVex);boolInsertEdge(EdgesEdge);VexGetVex(intnVex);intGetVexnum(void);intFindEdge(intnVex,EdgeaEdge[]);voidDFS(intnVex,boolaVisited[],int&nIndex,PathList&pList);voidDFSTraverse(intnVex,PathList&pList);intFindShortPath(intnVexStart,intnVexEnd,EdgeaPath[]);voidFindMinTree(EdgeaPath[]);};2、核心算法设计(1)输出周边景点信息Input:操作表号与景点编号Output:输入景点得周边景点信息Process:intCGraph::FindEdge(intnVex,EdgeaEdge[]){intk=0;for(inti=0;i<m_nVexNum;i++){if(m_aAdjMatrix[nVex][i]!=0){aEdge[k]、vex1=nVex;aEdge[k]、vex2=i;aEdge[k]、weight=m_aAdjMatrix[nVex][i];k++;}}returnk;//返回边得条数}(2)深度优先搜索算法实现旅游景点导航Input:操作表号与景点编号Output:从输入景点出发走遍整个景区得各种路线方案Process:voidCGraph::DFS(intnVex,boolaVisited[],int&nIndex,PathList&pList){aVisited[nVex]=true;//改为已访问pList>vexs[nIndex++]=nVex;//访问顶点//判断就是否所有节点都已访问过intnVexNum=0;for(inti=0;i<m_nVexNum;i++){if(aVisited[i])nVexNum++;}//所有顶点都被访问过if(nVexNum==m_nVexNum)