(完整word版)数据结构实验报告图与景区(word文档良心出品)

1学生学号实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名学生姓名学生专业班级2017--2018学年第2学期1实验课程名称：数据结构与算法综合实验实验项目名称图与景区信息管理系统实践报告成绩实验者专业班级组别同组者完成日期2018年5月23日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的掌握图的定义和图的存储结构。掌握图的创建方法和图的应用使用C++语言，定义图的数据结构，结合迭代开发思路实现“景区信息管理系统”。掌握图的两种遍历方法和应用。使用C++语言和深度优先算法实现“旅游景点导航”功能开发。掌握迪杰斯特拉算法和应用。使用C++语言和迪杰斯特拉算法实现“搜索最短路径”功能开发。理解最小生成树的概念，掌握普里姆算法和应用。使用C++语言和最小生成树算法实现“铺设电路规划”功能开发。2.要求开发景区信息管理系统，对景区的信息进行管理。使用图的数据结构来保存景区景点信息，为用户提供创建图、查询景点信息、旅游景点导航、搜索最短路径、铺设电路规划等功能。二、分析与设计(1)创建工程读取文件信息，创建图，输出周边景点信息读取景区信息文件，采用图的存储结构，创建景区景点图，查询景点信息。(2)迭代开发，进行深度优先搜索，实现旅游景点导航。(3)继续迭代，采用迪杰斯特拉算法、普里姆算法，实现搜索最短路径和电路铺设，开发景区信息管理系统。21.数据结构的设计记录顶点信息的结构体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[]);};32.核心算法设计（1）输出周边景点信息Input:操作表号与景点编号Output:输入景点的周边景点信息Process:intCGraph::FindEdge(intnVex,EdgeaEdge[]){intk=0;for(inti=0;im_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;im_nVexNum;i++){if(aVisited[i])nVexNum++;}//所有顶点都被访问过if(nVexNum==m_nVexNum){//新增链表节点，保存本次遍历的路径pList-next=(PathList)malloc(sizeof(Path));for(inti=0;im_nVexNum;i++){pList-next-vexs[i]=pList-vexs[i];4}pList=pList-next;pList-next=NULL;}else{//按顶点的存储顺序，查找当前顶点相连的的顶点for(inti=0;im_nVexNum;i++){//既没有遍历过，又与当前顶点相连的顶点if(!aVisited[i]&&(m_aAdjMatrix[nVex][i]0)){//以该顶点为起点遍历剩下的顶点DFS(i,aVisited,nIndex,pList);aVisited[i]=false;//访问状态置空nIndex--;//回溯}}}}voidCGraph::DFSTraverse(intnVex,PathList&pList){intnIndex=0;boolaVisited[MAX_VERTEX_NUM]={false};DFS(nVex,aVisited,nIndex,pList);}（3）Dijkstra算法搜索最短路径Input:操作表号与起始景点编号Output:从起始顶点到终点的最短路径Process:intCGraph::FindShortPath(intnVexStart,intnVexEnd,EdgeaPath[]){intnShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//保存最短路径intnShortDistance[MAX_VERTEX_NUM];//保存最短距离boolaVisited[MAX_VERTEX_NUM];//判断某顶点是否已经加入到最短路径//初始化intv;for(v=0;vm_nVexNum;v++){aVisited[v]=false;if(m_aAdjMatrix[nVexStart][v]!=0)//初始化该顶点到其他顶点的最短距离，默认为两点间的距离nShortDistance[v]=m_aAdjMatrix[nVexStart][v];5else//如果顶点i和nVexStart不相连，则最短距离设为最大值nShortDistance[v]=0x7FFFFFFF;nShortPath[v][0]=nVexStart;//起始点为nVexStartfor(intj=1;jm_nVexNum;j++){nShortPath[v][j]=-1;//初始化最短路径}}//初始化，nVexStart顶点加入到集合中aVisited[nVexStart]=true;intmin;for(inti=1;im_nVexNum;i++){min=0x7FFFFFFF;boolbAdd=false;//判断是否还有顶点可以加入到集合中for(intj=0;jm_nVexNum;j++){if(aVisited[j]==false){if(nShortDistance[j]min){v=j;//j顶点离nVexStart顶点最近min=nShortDistance[j];//j到nVexStart的最短距离为minbAdd=true;}}}//如果没有顶点可以加入到集合，则跳出循环if(bAdd==false){break;}aVisited[v]=true;//将顶点j加入到集合nShortPath[v][i]=v;//将顶点j保存到nVexStart到j的最短路径里for(intw=0;wm_nVexNum;w++){//将w作为过度顶点计算nVexStart通过w到每个顶点的距离if(aVisited[w]==false&&(min+m_aAdjMatrix[v][w]nShortDistance[w])&&m_aAdjMatrix[v][w]!=0){//更新当前最短路径及距离nShortDistance[w]=min+m_aAdjMatrix[v][w];for(inti=0;im_nVexNum;i++)6{//如果通过w到达顶点i的距离比较短，则将w的最短路径复制给inShortPath[w][i]=nShortPath[v][i];}}}}intnIndex=0;intnVex1=nVexStart;//将最短路径保存为边的结构体数组for(inti=1;im_nVexNum;i++){if(nShortPath[nVexEnd][i]!=-1){aPath[nIndex].vex1=nVex1;aPath[nIndex].vex2=nShortPath[nVexEnd][i];aPath[nIndex].weight=m_aAdjMatrix[aPath[nIndex].vex1][aPath[nIndex].vex2];nVex1=nShortPath[nVexEnd][i];nIndex++;}}returnnIndex;}（4）普里姆算法构建最小生成树Input:输入操作编号Output:得到最小生成树的路径Process:voidCGraph::FindMinTree(EdgeaPath[]){boolaVisited[MAX_VERTEX_NUM];//判断某顶点是否在最小生成树顶点集合里for(inti=0;iMAX_VERTEX_NUM;i++){aVisited[i]=false;}aVisited[0]=true;//0顶点加入到集合中intmin;intnVex1,nVex2;for(intk=0;km_nVexNum-1;k++){min=0x7FFFFFFF;for(inti=0;im_nVexNum;i++){if(aVisited[i])//从集合中取一个顶点7{for(intj=0;jm_nVexNum;j++){if(!aVisited[j])//从不在集合的顶点中取出一个顶点{if((m_aAdjMatrix[i][j]min)&&(m_aAdjMatrix[i][j]!=0)){nVex1=i;nVex2=j;min=m_aAdjMatrix[i][j];//找出最短的边}}}}}//保存最短边的两个顶点aPath[k].vex1=nVex1;aPath[k].vex2=nVex2;aPath[k].weight=m_aAdjMatrix[nVex1][nVex2];//将两个顶点加入到集合aVisited[nVex1]=true;aVisited[nVex2]=true;}}3.测试用例设计使用实验所要求的图创建两个文本文件，对文件进行读取，观察其相关功能的实现。三、主要仪器设备及耗材1.安装了Windows10或其它版本的Windows操作系统的PC机1台2.PC机系统上安装了MicrosoftVisualStudio2010开发环境8第二部分：实验过程和结果（可加页）一、实现说明使用MircosoftVisualStudio2010开发工具，创建一个空的控制台工程。利用图的存储结构来保存景区景点图，使用C++语言开发景区信息管理系统，工程名为GraphCPro。（1）添加Graph.h文件，用来定义图的数据结构，实现图的相关操作。（2）添加Tourism.h文件，用来实现景区信息管理系统的相关功能。Tourism.h存放与Tourism.cpp相关函数的数据类型的定义，函数原型的声明等。（3）添加Main.