《数据结构实验报告图与景区》由会员分享，可在线阅读，更多相关《数据结构实验报告图与景区（11页珍藏版）》请在金锄头文库上搜索。
1、学生学号 实验课成绩学 生 实 验 报 告 书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名学生姓名学生专业班级2017-2018学年第2学期实验课程名称： 数据结构与算法综合实验 实验项目名称图与景区信息管理系统实践报告成绩实验者专业班级组别同组者 完成日期2018年5月23日第一部分：实验分析与设计（可加页）一、 实验目的和要求1. 目的=掌握图的定义和图的存储结构。=掌握图的创建方法和图的应用=使用C+语言，定义图的数据结构，结合迭代开发思路实现“景区信息管理系统”。=掌握图的两种遍历方法和应用。=使用C+语言和深度优先算法实现“旅游景点导航”功能开发。=掌握
2、迪杰斯特拉算法和应用。=使用C+语言和迪杰斯特拉算法实现“搜索最短路径”功能开发。=理解最小生成树的概念，掌握普里姆算法和应用。=使用C+语言和最小生成树算法实现“铺设电路规划”功能开发。2.要求=开发景区信息管理系统，对景区的信息进行管理。=使用图的数据结构来保存景区景点信息，为用户提供创建图、查询景点信息、旅 游景点导航、搜索最短路径、铺设电路规划等功能。二、 分析与设计(1) 创建工程读取文件信息，创建图，输出周边景点信息读取景区信息文件，采用图的存储结构，创建景区景点图，查询景点信息。(2)迭代开发，进行深度优先搜索，实现旅游景点导航。(3)继续迭代，采用迪杰斯特拉算法、普里姆算法，实
3、现搜索最短路径和电路铺 设，开发景区信息管理系统。1. 数据结构的设计=记录顶点信息的结构体struct Vexint num;/景点编号char name20;/景点名字char desc1024;/景点介绍;=记录边的信息的结构体struct Edgeint vex1;/边的第一个顶点int vex2;/边的第二个顶点int weight;/权值;=用来保存路径的链表的结构体typedef struct Pathint vexs20;/保存一条路径Path *next;*PathList;=CGraph类用来实现相应功能的方法class CGraphprivate:int m_aAdjMa
4、trix2020;/邻接矩阵Vex m_aVexs20;/顶点信息数组int m_nVexNum;/当前图的顶点个数public: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,Path
5、List &pList);int FindShortPath(int nVexStart,int nVexEnd,Edge aPath);void FindMinTree(Edge aPath);2.核心算法设计（1）输出周边景点信息Input:操作表号与景点编号Output:输入景点的周边景点信息Process:int CGraph:FindEdge(int nVex,Edge aEdge)int k=0;for(int i=0;ivexsnIndex+=nVex;/访问顶点/判断是否所有节点都已访问过int nVexNum=0;for(int i=0;inext=(PathList)mal
6、loc(sizeof(Path);for(int i=0;inext-vexsi=pList-vexsi;pList=pList-next;pList-next=NULL;else/按顶点的存储顺序，查找当前顶点相连的的顶点for(int i=0;i0)/以该顶点为起点遍历剩下的顶点DFS(i,aVisited,nIndex,pList);aVisitedi=false;/访问状态置空nIndex-;/回溯void CGraph:DFSTraverse(int nVex,PathList &pList)int nIndex=0;bool aVisitedMAX_VERTEX_NUM=false
7、;DFS(nVex,aVisited,nIndex,pList);（3） Dijkstra算法搜索最短路径Input: 操作表号与起始景点编号Output: 从起始顶点到终点的最短路径Process:int CGraph:FindShortPath(int nVexStart,int nVexEnd,Edge aPath)int nShortPathMAX_VERTEX_NUMMAX_VERTEX_NUM;/保存最短路径int nShortDistanceMAX_VERTEX_NUM;/保存最短距离bool aVisitedMAX_VERTEX_NUM;/判断某顶点是否已经加入到最短路径/初始
8、化int v;for(v=0;vm_nVexNum;v+)aVisitedv=false;if(m_aAdjMatrixnVexStartv!=0)/初始化该顶点到其他顶点的最短距离，默认为两点间的距离nShortDistancev=m_aAdjMatrixnVexStartv;else/如果顶点i和nVexStart不相连，则最短距离设为最大值 nShortDistancev=0x7FFFFFFF;nShortPathv0=nVexStart;/起始点为nVexStartfor(int j=1;jm_nVexNum;j+)nShortPathvj=-1;/初始化最短路径/初始化，nVexSt
9、art顶点加入到集合中aVisitednVexStart=true;int min;for(int i=1;im_nVexNum;i+)min=0x7FFFFFFF;bool bAdd=false;/判断是否还有顶点可以加入到集合中for(int j=0;jm_nVexNum;j+)if(aVisitedj=false)if(nShortDistancejmin)v=j;/j顶点离nVexStart顶点最近min=nShortDistancej;/j到nVexStart的最短距离为minbAdd=true;/如果没有顶点可以加入到集合，则跳出循环if(bAdd=false)break;aVis
10、itedv=true;/将顶点j加入到集合nShortPathvi=v;/将顶点j保存到nVexStart到j的最短路径里for(int w=0;wm_nVexNum;w+)/将w作为过度顶点计算nVexStart通过w到每个顶点的距离if(aVisitedw=false&(min+m_aAdjMatrixvwnShortDistancew)&m_aAdjMatrixvw!=0)/更新当前最短路径及距离nShortDistancew=min+m_aAdjMatrixvw;for(int i=0;im_nVexNum;i+)/如果通过w到达顶点i的距离比较短，则将w的最短路径复制给inShort
11、Pathwi=nShortPathvi;int nIndex=0; int nVex1=nVexStart;/将最短路径保存为边的结构体数组for(int i=1;im_nVexNum;i+)if(nShortPathnVexEndi!=-1)aPathnIndex.vex1=nVex1;aPathnIndex.vex2=nShortPathnVexEndi;aPathnIndex.weight=m_aAdjMatrixaPathnIndex.vex1aPathnIndex.vex2;nVex1=nShortPathnVexEndi;nIndex+;return nIndex;（4）普里姆算法构建最小生
