欢迎来到天天文库
浏览记录
ID:41029948
大小:17.50 KB
页数:7页
时间:2019-08-14
《2019最短距离问题数据结构课程设计报告》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、最短距离问题数据结构课程设计报告 数据结构课程设计报告 题目:北海公园主要游览景点之间最短距离问题 一、课程设计题目:北海公园主要游览景点之间最短距离问题二、问题定义: 图的最短路径问题是指从指定的某一点v开始,求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求 解外,还能对该图进行修改,如顶点以及边的增删、边上权值的修改等。 三、需求分析 1、设计北海公园的平面图。选取若干个有代表性的景点抽象成一个无向带权图,以图 中顶点表示公园内各景点,边上的权值表示两景点之间的距离。 2、输入的形式:整型数字
2、输入值的范围:0-10 3、输出的形式:二元组表示以邻接矩阵存储的图 4、程序所能达到的功能; 输出顶点信息:将公园内各景点输出。 输出边的信息:将公园内每两个位置的距离输出。 修改:修改两个位置的距离,并重新输出每两个位置的距离; 求最短路径:输出给定两点之间的最短路径的长度及途经的地点,输出任意 一点与其他各点的最短路径。删除:删除任意一条边。插入:插入任意一条边。5、算法涉及的基本理论分析:定义邻接矩阵adjmatrix;自定义顶点结构体VertexType; 定义邻接表中的边结点类型edgenode;switch算法; 狄克斯特拉法求任意两结点之
3、间的最短路径;6、题目研究和实现的价值。 四、算法设计 1、概要设计 存储结构设计 本系统采用图结构类型存储抽象北海公园地图的信息。其中:各景点间的 邻接关系用图的邻接矩阵类型存储;景点信息用结构数组存储,其中每个数组元素是一个结构变量,包含景点编号、景点名称两个分量;图的顶点个数分量MaxVertexNum表示,它是整型数据。 主界面设计 为了实现公园导游系统各功能的管理,首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能,方便用户使用本系统。 系统功能设计 a学校景点介绍 公园景点介绍函数PrintMatrix根据邻接矩阵输出二元组表
4、示实现。当用户选择该功能,系统即能输出全部景点的信息:包括景点编号、景点名称。b查看浏览路线 查看浏览路线采用狄克斯特拉算法实现。当用户选择该功能,系统能根据用户所在门起始编号,求出从该门到其它景点的最短路径线路。c更改图的信息 更改图的信息功能主调函数change函数完成,可以实现图的若干基本操作。例如:插入、删除边,重建图等。 2、主程序的流程以及各程序模块之间的层次(调用)关系。公园抽象图设计 567843120 模块设计 本程序包含3个模块:主程序模块、工作区模块和无向网操作模块。 主程序模块工作区模块无向网操作模块 3、详细设计 实现概要设计中
5、定义的所有数据类型; //邻接矩阵的结构体 constintMaxVertexNum=9; constintMaxEdgeNum=16300;typedefintWeightType;constWeightTypeMaxValue=28;//顶点结构体structVertexType{ intnum_d;//顶点代号charname[20];//顶点名称}; typedefVertexTypevexlist[MaxVertexNum]; typedefintadjmatrix[MaxVertexNum][MaxVertexNum];//定义邻接表中的边结点类型
6、structedgenode{ intadjvex; WeightTypeweight; edgenode*next;}; 所有函数的接口描述; //将二维数组里的数据传输给邻接矩阵voidInitMatrix() //将景点名称数据传输给顶点结构体voidInitVT() //邻接矩阵的二元组表示voidPrintMatrix()//PATHvoidPATH() //最短路径:狄克斯特拉voidDijkstra()//输出最短路径voidPrint()//插入路径问题 voidchange() 所有函数的算法描述; //将二维数组data[]的数据
7、传输给邻接矩阵GAvoidInitMatrix(adjmatrix&GA,intdata[9][9]){ } GA[i][j]=data[i][j]; //将景点名称数据a传输给顶点结构体VTvoidInitVT(VertexTypeVT[9],char*a[9]){strcpy(VT[i].name,a[i]); } //邻接矩阵的二元组表示 voidPrintMatrix(adjmatrixGA,VertexTypeVT[9]){ cout'adjvex].name>chose1;switch(chose
此文档下载收益归作者所有