您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 数据结构实验报告-景点导游系统
第1页共22页南阳理工学院数据结构大作业实践报告课题名称:景点导游系统专业:班级:姓名:学号:完成日期:第2页共22页目录1.问题描述............................................................................................................31.1进度安排............................................................................31.2基本要求............................................................................4摘要......................................................................................................................52.问题分析............................................................................................................52.1图的存储结构..........................................................................................52.1.1图的邻接矩阵表示法.......................................................................62.1.2图的邻接矩阵(AdacencyMatrix)....................................................62.2求最短路径.............................................................................................62.2.1单源最短路径问题...........................................................................62.3求最小生成树...........................................................................................63.设计...................................................................................................................73.1系统流程.................................................................................................73.2系统相关抽象数据类型............................................................................83.2.1图的邻接矩阵存储结构形式说明...................................................83.2.2建立无向网络的算法.....................................................................83.3系统功能...................................................................................................93.4主要函数说明...........................................................................................94.测试..................................................................................................................94.1用户界面(包含路径图)....................................................................94.2用户输入想去的地点.............................................................................104.3人性化设置:........................................................................................115.总结与心得体会...............................................................................................126.主要算法..........................................................................................................136.1主要算法说明.........................................................................................136.1.1无向网的建立...............................................................................136.1.2数组表示法...................................................................................136.1.3Floyd算法......................................................................................14参考文献:.........................................................................................................14附录:源代码.....................................................................................................15第3页共22页1.问题描述景点(园林)导游系统设计一个景点的导游图,可以得到两个景点之间的所有简单路径、相应路径的路程公里数。选择苏州的某个园林,创建一个至少有15个旅游景点的导游图。顶点代表景点,边表示两个景点之间可以直达,权值表示两个景点之间的路程(公里数),还可以表示景点之间的到达方法(步行和乘车或船....)。建立一个游客咨询系统。基本功能:创建景点景区分布图;输出景区景点分布图:选择一个景点后,可以显示景点的相关信息;可以查询两个景点之间的所有简单路径;可以查询两个景点之间的最短路径:可以查询两个景点之间的行走方法:可以从公园大门进入,选一条最佳路线,可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。设计一实用的查询界面和功能菜单。1.1进度安排1.初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;2.完成最低要求:建立一个文件,包括5个景点情况,能完成遍历功能;3.进一步要求:进一步扩充景点数目,画出景点图,有兴趣的同学可以自己扩充系统功能。第4页共22页1.2基本要求1.界面友好,函数功能要划分好2.总体设计应画一流程图3.程序要加必要的注释4.要提供程序测试方案5.程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是没有价值的。第5页共22页摘要计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法(Algorithm),最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。计算机算法与数据的结构密切相关,算法无不依附于具体的数据结构,数据结构直接关系到算法的选择和效率。运算是由计算机来完成,这就要设计相应的插入、删除和修改的算法。也就是说,数据结构还需要给出每种结构类型所定义的各种运算的算法。2.问题分析2.1图的存储结构图的存储方式很多,这里用的是邻接矩阵的方式。为了适合用c语言描述,以下假定顶点序号从0开始,即图G的顶点集的一般形式是V(G)={v0,vi,・・・,Vn-1}o第6页共22页2.1.1图的邻接矩阵表示法(1)用邻接矩阵表示顶点之间的相邻关系;(2)用一个顺序表来储存顶点信息2.1.2图的邻接矩阵(AdacencyMatrix)设G二(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:若G是网络,则邻接矩阵可定义为2.2求最短路径给定一个带权有向图G=(V,E),其中每条边的权是一个非负实数。另外,还给定V中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。2.2.1单源最短路径问题Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直飒漏点)或到基富各岫的最短路径全部求出为止。2.3求最小生成树对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各第7页共22页边的权值总和称为该树的权,记作:Te,W(u,v),TE表示T的边集W(u,v)表示边(u,v)的权。权最小的生成树称为G的最小生成树(MinimumSpanningTree)o最小生成树可简记为MST。最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,V)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。3.设计3.1系统流程本系统主要是实现图的最短路径问题第8页共22页3.2系统相关抽象数据类型3.2.1图的邻接矩阵存储结构形式说明#defineMaxVertexNum100//最大顶点数,应由用户定义typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义typedefstruct{VextexTypevexs[MaxVertexNum]/∕顶点表EdeTypeedges[MaxVertexNum][MaxVertexNum];//邻接矩阵,可看作边表intn,e;//图中当前的顶点数和边数}MGragh;3.2.2建立无向网络的算法voidGreateMGraph(MGraph*G){//建立无向网的邻接矩阵表示inti,j,k,w;scanf(“%d%d”,&G-n,&G-e);//输入顶点数和边数f
本文标题:数据结构实验报告-景点导游系统
链接地址:https://www.777doc.com/doc-7364069 .html