数据结构实验报告-景点导游系统.doc

精选优质文档-倾情为你奉上南阳理工学院数据结构大作业实践报告课题名称： 景点导游系统 专 业： 班 级： 姓 名： 学 号： 完成日期： 目录1.问题描述景点（园林）导游系统设计一个景点的导游图，可以得到两个景点之间的所有简单路径、相应路径的路程公里数。选择苏州的某个园林，创建一个至少有15个旅游景点的导游图。顶点代表景点，边表示两个景点之间可以直达，权值表示两个景点之间的路程（公里数），还可以表示景点之间的到达方法（步行和乘车或船.)。建立一个游客咨询系统。基本功能：创建景点景区分布图；输出景区景点分布图：选择一个景点后，可以显示景点的相关信息；可以查询两个景点之间的所有简单路径；可以查询两个景点之间的最短路径：可以查询两个景点之间的行走方法：可以从公园大门进入，选一条最佳路线，可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。设计一实用的查询界面和功能菜单。1.1进度安排1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2.完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；3.进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。1.2基本要求1.界面友好，函数功能要划分好2.总体设计应画一流程图3.程序要加必要的注释4.要提供程序测试方案5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。摘要计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问 题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法(Algorithm), 最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问 题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语 言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构, 数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应 的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定 义的各种运算的算法。2.问题分析2 . 1图的存储结构图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用c语言描述，以 下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G) = v 0 , v i , V n-1 o2.1.1图的邻接矩阵表示法(1)用邻接矩阵表示顶点之间的相邻关系；(2)用一个顺序表来储存顶点信息2.1. 2 图的邻接矩阵(Adacency Matrix)设G二(V, E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵: 若G是网络，则邻接矩阵可定义为2 . 2求最短路径给定一个带权有向图G=(V, E),其中每条边的权是一个非负实数。另外，还 给定V中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路 径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。2.2.1单源最短路径问题Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的 最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一 条最短路径，依次类推，直飒漏点)或到基富各岫的最短路径全部求出为止。2.3求最小生成树对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总 和称为该树的权，记作：Te,W(u , v)，TE表示T的边集W(u, v)表示边(u, v)的权。权最小的生成树称为G的最小生成树(Minimum Spanning Tree) o最小生成树 可简记为MST。最小生成树性质：设G=(V, E)是一个连通网络，U是顶点集V的一个真子集。若(u, v)是G中一 条“一个端点在U中(例如：uU),另一个端点不在U中的边(例如：vV-U),且 (u, V)具有最小权值，则一定存在G的一棵最小生成树包括此边(u, v)。3.设计3 . 1系统流程本系统主要是实现图的最短路径问题3. 2系统相关抽象数据类型3.2. 1图的邻接矩阵存储结构形式说明#define MaxVertexNum 100/最大顶点数，应由用户定义 typedef char VertexType; /顶点类型应由用户定义typedef int EdgeType; /边上的权值类型应由用户定义 typedef structVextexType vexs MaxVertexNum /顶点表EdeType edgesMaxVertexNumMaxVertexNum;/邻接矩阵，可看作边表 int n, e; /图中当前的顶点数和边数 MGragh;3. 2. 2建立无向网络的算法void GreateMGraph(MGraph *G)/建立无向网的邻接矩阵表示int i, j, k, w;scanf (“%d%d”,&G->n,&G->e); /输入顶点数和边数for(i=0;i<n; i+) /读人顶点信息,建立顶点表G->vexsi =getchar();for (i=0;i<n;i+)for(j=0;j<n;j+)G->edgesij=0; /邻接矩阵初始化for (k=0;ke;k+) /读入e条边，建立邻接矩阵scanf (“%d%d%d”&i,&j,&w);/输入边(v i , v j )上的权值G->edgesij二w;G->edgesji二w;/CreateMGraph3.3系统功能提供无向图的生成，并保证了该无向图为一个无向网，同时也提供了计算最短距 离的迪杰斯特拉算法，以及图的遍历。3.4主要函数说明本系统用了一个类来实现程序，里面包含了4个对象：void graph: :picture ()； void graph:creatp(graph &t)； void graph:floyd(graph &t,const int n)； void graph:bfs(graph t)4. 测试4.1 用户界面（包含路径图）4.2 用户输入想去的地点（系统自动生成各种方案，可供选择，另外系统会推荐出出最适合的路线，且每条路线都会显示距离！）4.3 人性化设置：系统提示：是否要去其他的地方，让使用者更加的方便，在询问后，系统会提供返回路线。5.总结与心得体会当今世界，C+语言作为国际上广泛流行的通用程序设计语言，在计算机的研究 和应用中已展现出强大的生命力。C+语言兼顾了诸多高级语言的特点，是一种典型 的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。而数据结构-作为C+语言使用的途径学科，也是计算机学科的一门核心课程.虽 然我们学C+语言和数据结构已快一年了，但一直都注重理论概念，而实际上机操作却不多.很感谢这次的课程设计，它使我更加深刻地体会到多看专业书、多学习专 业知识的重要性，只有掌握了一定量的专业知识才能得心应手地解决诸多问题；另外，在课程设计过程中，我遇到了很多棘手的问题，好几次都差点放弃了，但最终 还是坚持下来了，所以我懂得了，做任何事都要有耐心，不要一遇到困难就退缩； 当遇到那么多的问题时，我自己能解决的并不多，大部分都是通过和小组同学讨论 而解决的。所以，在学习和工作中要时刻谨记“团结”二字，它好比通向成功的铺 路石，不可或缺。在编程过程中，有编得很顺利的，也有很多不顺利的，正如人生 的道路是曲折的，但正是因为曲折人生才光彩夺日，在人生的路上，总遇到重重困 难，但正是因为这些困难我们才变的更加坚强，才能够不断地提高自己，充实自己, 最后达到我们理想的彼岸。感谢老师在授课期间对我们严厉的态度和严格的管理，才造就了今天的我 们。在课程设计过程中，我们几乎每个小组都遇到了不同程度的问题，但老师都细 心指导，耐心地为我们讲解。老师认真负责的工作态度，对我们这次的课程设计得 以顺利完成发挥了不可估量的作用。最后，再一次感谢在这次课程设计中对我给予 帮助的老师和同学。通过这次课程设计，我们不光收获了知识，还收获了友谊和欢乐。6.主要算法6.1主要算法说明6.1. 1无向网的建立由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据 元素在存储 区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结 构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示 图是自然的事，它是一种最简单的这式映像结构，聚聚以一个由一个数据域和多个 指针域存储该顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指。.6.1. 2数组表示法用两个数组分别存储数据元素的信息和数据元素这间的关系的信息。以二维数 组表示有N个顶点的图时，需存放N个顶点信息和N2个弧信息的存储量。6.1. 3Floyd算法Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶 点间最短路径的算法。Floyd算法适用于APSP(All Pairs Shortest Paths),是一种动态规划算法， 稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于 稠密图，效率要高于执行V次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。参考文献：1.用C+实现数据结构程序设计-清华大学出版社-马春江附录：源代码#include <iostream>using namespace std;const int n=5; /n表示景点图中顶点个数const int e=7; /e表示景点图中路径bool visitedn+1;#define max 32767class graphpublic:int arcsn+1n+1;/领接矩阵int an+1n+1;/距离int pathn+1n+1;/景点void floyd(graph &t,const int n);void picture();void creatp(graph &t);void bfs(graph t);void graph:picture() /景点图cout<<" -美丽公园导游图- "<<endl;cout<<" 以下是非常美丽的景点 "<<endl;cout<<"-"<<endl;cout<<"1.公园入口 2.海盗船 "<<endl;cout<<"3.方舟湖水 4.龙王山 "<<endl;cout<<"5.公园出口 "<<endl;cout<<"-"<<endl;cout<<" 以下是公园的路径图 "<<endl;cout<<" 2*4 "<<endl;cout<<" * * * * "<<endl;cout<<" * * * * "<<endl;cout<<" * * * * "<<endl;cout<<" * 3 * * "<<endl;cout<<" * * * * "<<endl;cout<<" * * * * "<<endl;cout<<" * * * "<<endl;cout<<" 1*5 "<<endl;cout<<" 入 口 出口 "<<endl;cout<<"下面是景点与景点之间的距离和介绍 "<<endl;cout<<"1.公园入口->2.海盗船距离为：3 "<<endl;cout<<"1.公园入口->3.方舟湖水距离为：10"<<endl;cout<<"2.水族馆->4.龙王山距离为：9 "<<endl;cout<<"2.水族馆->3.方舟湖水距离为：4 "<<endl;cout<<"3.摩天轮->4.龙王山距离为：5 "<<endl;cout<<"4.动物园->5.公园出口距离为：2 "<<endl;cout<<"3.摩天轮->5.公园出口距离为：3 "<<endl;void graph:creatp(graph &t)int i,j;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i=j)t.arcsij=0; /景点一样则距离为 0 else t.arcsij=max; /i 不等于 j 时t.arcs12=3;t.arcs21=3;t.arcs24=9;t.arcs42=9;t.arcs31=8;t.arcs13=8;t.arcs32=4;t.arcs23=4;t.arcs34=5;t.arcs43=5;t.arcs35=3;t.arcs53=3;t.arcs54=2;t.arcs45=2;/把景点跟距离用一个二围数组存储下来void graph:floyd(graph &t,const int n)for(int i=1;i<=n;i+)for(int j=1;j <=n ;j+)t.aij=t.arcsij;/把距离付值给 a.ijif(i!=j)&&(aij<max)t.pathij=i;else t.pathij=0;for(int k=1;k<=n;k+)for(int i=1;i<=n;i+)for(int j=1 ;j<=n ;j+)if(t.aik+t.akj<t.aij)t.aij=t.aik+t.akj;t.pathij=t.pathkj;void graph:bfs(graph t) /从顶点i出发实现广度搜索搜索n int j,i;/f, r分别为队列头，尾指针char ch;cout<<"请输入一个你想去的地方:"cin>>i;while(i<=5)if(i=1)cout<<"这里就是你要去的地方拉!"<<endl<<endl;elsefor(j=1;j<=n;j+)if(i!=j)cout<<"距离为"<<t.aij<<":"int next=t.pathij;cout<<j;while(next!=i)cout<<"-"<<next;next=t.pathi next;cout<<"-"<<i<<endl;cout<<"等我推荐一条最佳路径供你返回吧(y/n):"cin>>ch;if(ch='y')if(i=2) cout<<"2-3-5"<<endl;if(i=3) cout<<"3-5"<<endl;if(i=4) cout<<"4-5"<<endl;cout<<"请问你想去游览公园全景吗(y/n):"<<endl;cin>>ch;if(ch='y')cout<<"请走 1-2-3-4-5 路线"<<endl;cout<<"你还想去别的地方吗?(y/n)"cin>>ch;if(ch='y')cout<<"请输入一个你想去的地方:"cin>>i;if(ch!='y')cout<<"*退出程序*"<<endl;cout<<"欢迎下次再来"<<endl;break;else break;int main()graph t;t.picture();t.creatp(t);t.floyd(t,n);t.bfs(t);专心-专注-专业