数据结构-实验5-图的应用.doc

《数据结构-实验5-图的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告开课学院及实验室：年月日学院年级、专业、班姓名学号　实验课程名称数据结构　成绩　实验项目名称实验5图的应用指导教师　一实验目的1、掌握图的基本概念和基本存储方法；2、掌握有关图的操作算法，并用高级语言实现；3、熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构及算法有着密切联系；4、熟悉如何用图结构解决实际应用问题；5、培养数据抽象的设计能力和实际动手的综合能力，并进一步掌握完整应用系统的设计过程和方法。二实验原理图形结构是一种应用非常广泛的数据结构，它的应用已经渗透到语言学

2、、逻辑学、物理、化学、电子、通信、数学、计算机科学等诸多学科领域。最短路径是指路径长度（即路劲上边的权值之和）最小的路径，一般讨论带权有向图，在实际应用中经常用于解决城市节点间运输代价最少或运输时间最短等问题。三实验内容请为珠江三角洲城市间设计与实现一个简单的交通咨询系统。基本要求：（1）设计简单的珠江三角洲城市间道路通行平面图，所含城市不少于10个。以图中顶点表示城市节点，存放城市名称、代号、简介等信息；以边表示通行道路，存放道路的路径长度。（2）提供图中任意城市的相关信息查询。（3）提供图中任意城市间的

3、最短路径查询。四实验步骤1将珠江三角洲城市间的交通图抽象为无向带权图。（要求给出一个设计方案）2设计求图中任意结点间最短路径的算法。3编程实现。五实验方法1对问题进行需求分析，选取具体城市结点，通过调研获取城市间的交通网络，选取主要的通行道路抽象为图的无向带权边。2进行概要设计和详细设计，形成模块间的调用结构图和模块的算法。3编写程序，设计测试用例进行测试。4完成开发文档。六实验结果1需求分析：在中国城市，电子地图的认知度和使用率正在飞快递增，随着用户量不断增加，纸质地图逐渐被电子地图取而代之。在大中型城市

4、，电子地图已经成为绝大多数用户出行前首选的参照工具和查询途径。电子地图强调准确性、简单易用以及查询速度。电子地图的另外一个特点是使用方便，无论是通过互联网还是手机都能够方便接触到并使用。出行前用电脑通过互联网地图规划路线、查找目的地，路上则可以用手机连接无线网络，通过手机地图随时修正路线和辨识方向。2概要设计：3详细设计：4编程遇到的问题和调试分析：5用户手册：概述：简单的交通咨询系统功能：1.珠三角地区交通查询；2.珠三角地区各城市信息查询。使用说明：1.打开方法：打开命令行窗口，进入map.exe文件所

5、在目录（如：cde:/map），输入map，进入程序。2.构造地图信息，按提示输入map.txt.3.交通查询功能的使用：输入1进入查询，按要求输入起点城市编号和终点城市编号，回车即可。4.城市信息查询功能的使用：输入2进入查询，按要求输入城市编号，回车即可。6测试结果：7附录（源程序清单）#defineMAX_NAME9//顶点字符串的最大长度#defineMAX_INFO20//相关信息字符串的最大长度#defineMAX_MES300//顶点城市信息的最大长度typedefintVRType;stru

6、ctVertexType{charname[MAX_NAME];//城市名字charmes[MAX_MES];//城市信息};typedefcharInfoType;//c1.h(程序名)#include#include//malloc()等#include//INT_MAX等#include//EOF(=^Z或F6),NULL#include//eof()//函数结果状态代码#defineTRUE1#defineFA

7、LSE0typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE#defineINFINITYINT_MAX//用整型最大值代替∞#defineMAX_VERTEX_NUM26//最大顶点个数enumGraphKind{DG,DN,UDG,UDN};//{有向图,有向网,无向图,无向网}typedefstruct{VRTypeadj;//顶点关系类型。对无权图，//用1(是)或

8、0(否)表示相邻否；//对带权图，则为权值InfoType*info;//该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组structMGraph{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量,原程序放城市名字,现在加上城市信息AdjMatrixarcs;//邻接矩阵intvexnum,arc