数据结构实验报告图与景区

1、WORD格式学生学号实验课成绩学生实验报告书实验课程名称数据构造与算法综合实验开课学院计算机科学与技术学院指导教师*学生*学生专业班级2021-2021学年第2学期专业资料整理WORD格式1专业资料整理WORD格式实验课程名称：数据构造与算法综合实验实验工程名称图与景区信息管理系统实践报告成绩实验者专业班级组别同组者完成日期2021年 5月 23 日第一局部：实验分析与设计可加页一、实验目的和要求1. 目的掌握图的定义和图的存储构造。掌握图的创立方法和图的应用使用 C+语言，定义图的数据构造， 结合迭代开发思路实现“景区信息管理系统 。掌握图的两种遍历方法和应用。使用 C+语言和深度优先算法实

2、现“旅游景点导航功能开发。掌握迪杰斯特拉算法和应用。使用 C+语言和迪杰斯特拉算法实现“搜索最短路径功能开发。理解最小生成树的概念，掌握普里姆算法和应用。使用 C+语言和最小生成树算法实现“铺设电路规划功能开发。2. 要求开发景区信息管理系统，对景区的信息进展管理。使用图的数据构造来保存景区景点信息，为用户提供创立图、查询景点信息、旅游景点导航、搜索最短路径、铺设电路规划等功能。二、分析与设计(1) 创立工程读取文件信息，创立图，输出周边景点信息读取景区信息文件，采用图的存储构造，创立景区景点图，查询景点信息。(2) 迭代开发，进展深度优先搜索，实现旅游景点导航。(3) 继续迭代，采用迪杰斯特

3、拉算法、普里姆算法，实现搜索最短路径和电路铺设，开发景区信息管理系统。专业资料整理WORD格式1专业资料整理WORD格式1. 数据构造的设计记录顶点信息的构造体structVexintnum; / 景点编号char name20;/ 景点名字char desc1024;/ 景点介绍;记录边的信息的构造体structEdgeintvex1; / 边的第一个顶点intvex2; / 边的第二个顶点intweight;/ 权值;用来保存路径的链表的构造体typedefstructPathintvexs20;/ 保存一条路径Path *next;*PathList;CGraph类用来实现相应功能的方法

4、classCGraphprivate:intm_aAdjMatrix2020;/ 邻接矩阵Vex m_aVexs20;/ 顶点信息数组intm_nVexNum;/ 当前图的顶点个数public:voidInit( void );bool InsertVex(Vex sVex);bool InsertEdge(Edge sEdge);Vex GetVex( int nVex);intGetVexnum( void );intFindEdge(intnVex,Edge aEdge);voidDFS(intnVex, boolaVisited,int &nIndex,PathList &pList)

5、;voidDFSTraverse(int nVex,PathList &pList);intFindShortPath(intnVexStart, intnVexEnd,Edge aPath);voidFindMinTree(Edge aPath);专业资料整理WORD格式2专业资料整理WORD格式2. 核心算法设计（ 1输出周边景点信息 Input: 操作表号与景点编号 Output: 输入景点的周边景点信息Process:intCGraph:FindEdge(intnVex,Edge aEdge)intk=0;for ( inti=0;ivexsnIndex+=nVex;/ 访问顶点/ 判

6、断是否所有节点都已访问过intnVexNum=0;for ( inti=0;inext=(PathList)malloc(sizeof (Path);for ( inti=0;inext-vexsi=pList-vexsi;专业资料整理WORD格式3专业资料整理WORD格式pList=pList-next;pList-next=NULL;else/ 按顶点的存储顺序，查找当前顶点相连的的顶点for ( inti=0;i0)/ 以该顶点为起点遍历剩下的顶点DFS(i,aVisited,nIndex,pList);aVisitedi=false ; / 访问状态置空nIndex-;/ 回溯void

7、 CGraph:DFSTraverse(intnVex,PathList &pList)intnIndex=0;bool aVisitedMAX_VERTEX_NUM=false ;DFS(nVex,aVisited,nIndex,pList);（ 3 Dijkstra 算法搜索最短路径Input: 操作表号与起始景点编号Output: 从起始顶点到终点的最短路径Process:intCGraph:FindShortPath(intnVexStart,intnVexEnd,Edge aPath)int nShortPathMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 保存最短路

8、径 int nShortDistanceMAX_VERTEX_NUM;/ 保存最短距离bool aVisitedMAX_VERTEX_NUM;/ 判断某顶点是否已经参加到最短路径/ 初始化intv;for (v=0;vm_nVexNum;v+)aVisitedv=false ;if (m_aAdjMatrixnVexStartv!=0)/ 初始化该顶点到其他顶点的最短距离，默认为两点间的距离nShortDistancev=m_aAdjMatrixnVexStartv;专业资料整理WORD格式4专业资料整理WORD格式else/ 如果顶点 i 和 nVexStart 不相连，那么最短距离设为最大

9、值nShortDistancev=0x7FFFFFFF;nShortPathv0=nVexStart;/ 起始点为 nVexStartfor ( intj=1;jm_nVexNum;j+)nShortPathvj=-1;/ 初始化最短路径/ 初始化， nVexStart 顶点参加到集合中aVisitednVexStart=true ;intmin;for ( inti=1;im_nVexNum;i+)min=0x7FFFFFFF;bool bAdd=false ; / 判断是否还有顶点可以参加到集合中for ( intj=0;jm_nVexNum;j+)if (aVisitedj=false

10、)if (nShortDistancejmin)v=j; /j顶点离 nVexStart 顶点最近min=nShortDistancej;/j到 nVexStart 的最短距离为 minbAdd=true ; / 如果没有顶点可以参加到集合，那么跳出循环if (bAdd=false )break ;aVisitedv=true ; / 将顶点 j 参加到集合nShortPathvi=v;/ 将顶点 j 保存到 nVexStart 到j 的最短路径里for ( intw=0;wm_nVexNum;w+)/ 将w作为过度顶点计算 nVexStart 通过 w到每个顶点的距离if (aVisited

11、w=false &(min+m_aAdjMatrixvwnShortDistancew)&m_aAdjMatrixvw!=0)/ 更新当前最短路径及距离nShortDistancew=min+m_aAdjMatrixvw;for ( inti=0;im_nVexNum;i+)专业资料整理WORD格式5专业资料整理WORD格式/ 如果通过 w到达顶点 i 的距离比较短，那么将 w的最短路径复制给 i nShortPathwi=nShortPathvi;intnIndex=0;intnVex1=nVexStart;/ 将最短路径保存为边的构造体数组for ( inti=1;im_nVexNum;i

12、+)if (nShortPathnVexEndi!=-1)aPathnIndex.vex1=nVex1;aPathnIndex.vex2=nShortPathnVexEndi;aPathnIndex.weight=m_aAdjMatrixaPathnIndex.vex1aPathnIndex.vex2; nVex1=nShortPathnVexEndi;nIndex+;returnnIndex;（ 4普里姆算法构建最小生成树Input: 输入操作编号Output: 得到最小生成树的路径Process:void CGraph:FindMinTree(Edge aPath)bool aVisite

13、dMAX_VERTEX_NUM;/ 判断某顶点是否在最小生成树顶点集合里 for ( int i=0;iMAX_VERTEX_NUM;i+)aVisitedi=false ;aVisited0=true ; /0 顶点参加到集合中intmin;intnVex1,nVex2;for ( intk=0;km_nVexNum-1;k+)min=0x7FFFFFFF;for ( inti=0;im_nVexNum;i+)if (aVisitedi)/ 从集合中取一个顶点专业资料整理WORD格式6专业资料整理WORD格式for ( intj=0;jm_nVexNum;j+)if (!aVisitedj)

14、/ 从不在集合的顶点中取出一个顶点if (m_aAdjMatrixijmin)&(m_aAdjMatrixij!=0)nVex1=i;nVex2=j;min=m_aAdjMatrixij;/ 找出最短的边/ 保存最短边的两个顶点aPathk.vex1=nVex1;aPathk.vex2=nVex2;aPathk.weight=m_aAdjMatrixnVex1nVex2;/ 将两个顶点参加到集合aVisitednVex1=true ;aVisitednVex2=true ;3. 测试用例设计使用实验所要求的图创立两个文本文件，对文件进展读取，观察其相关功能的实现。三、主要仪器设备及耗材1. 安

15、装了 Windows 10 或其它版本的Windows操作系统的 PC机 1 台2.PC 机系统上安装了 Microsoft Visual Studio 2021开发环境专业资料整理WORD格式7专业资料整理WORD格式第二局部：实验过程和结果可加页一、实现说明使用 Mircosoft Visual Studio 2021开发工具，创立一个空的控制台工程。利用图的存储构造来保存景区景点图，使用C+语言开发景区信息管理系统，工程名为 GraphCPro。1添加 Graph.h 文件，用来定义图的数据构造，实现图的相关操作。2添加 Tourism.h 文件，用来实现景区信息管理系统的相关功能。 T

16、ourism.h 存放与 Tourism.cpp 相关函数的数据类型的定义，函数原型的声明等。3添加 Main.cpp 文件，在文件中创立程序入口函数 int main void 。调用 Tourism.h 中的相关函数实现相应功能。二、调试说明调试手段、过程及结果分析调试的主要内容为编写程序的语法正确性与否，程序逻辑的正确性与否。调试手段主要采用了 Mircosoft Visual Studio 2021集成开发环境中的“开场执行 Ctrl+F5 运行并测试，和 F11“逐语句调试、 F12“逐过程调试、F9“切换断点、 ctrl+B “新建断点等。三、软件测试测试效果 . 界面、综合分析和结论1测试效果界面专业资料整理WORD格式8专业资料整理WORD格式9专业资料整理WORD格式2综合分析和结论由于上一次的哈夫曼树没有写很好所以我回去以后有好