公园导游图课程设计.doc

学号： 课 程 设 计题目公 园 导 游 图教学院计 算 机 学 院专业计算机网络技术班级09网络技术（1）姓名指导老师冯 珊 、熊敬一2010年12月30日 课程设计任务书 20092010学年第 1学期学生姓名： 何雪梅 专业班级： 09网络技术 指导教师： 冯姗、熊敬一 工作部门： 计算机学院 一、课程设计题目: 公园导游图二、课程设计内容给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。三、进度安排1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；3 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。四、基本要求1. 界面友好，函数功能要划分好2. 总体设计应画一流程图3. 程序要加必要的注释4. 要提供程序测试方案5. 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 教研室主任签名： 年 月 日目 录摘要 1 问题描述31.1图、无向图31.1.1图的存储结构31.1.2 图的邻接矩阵表示法31.2算最短路径41.3无向图遍历41.4广度优先搜索42.系统分析52.1系统流程图53 系统设计53.1主要数据结构63.2 主要函数说明63.3主要算法说明63.3.1数组表示法63.3.2floyd算法64 心得体会7附录一：源程序8附录三：参考文献14摘 要 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种 运算的算法。1.问题描述.图的存储结构 图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用c语言描述，以下假定顶点序号从0开始，即图g的顶点集的一般形式是v(g)=v 0 ，v i ，v n-1 。1.1.1 图的邻接矩阵表示法（）用邻接矩阵表示顶点之间的相邻关系；（）用一个顺序表来储存顶点信息1.1.2图的邻接矩阵(adacency matrix)设g=(v，e)是具有n个顶点的图，则g的邻接矩阵是具有如下性质的n阶方阵：若是网络，则邻接矩阵可定义为： .求最短路径给定一个带权有向图 g=(v,e) ，其中每条边的权是一个非负实数。另外，还给定 v 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.1单源最短路径问题dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。. 求最小生成树对于连通的带权图(连通网)g，其生成树也是带权的。生成树t各边的权值总和称为该树的权，记作：te,w(u , v)te表示t的边集w(u，v)表示边(u，v)的权。权最小的生成树称为g的最小生成树(minimum spanning tree)。最小生成树可简记为mst。最小生成树性质：设g=(v，e)是一个连通网络，u是顶点集v的一个真子集。若(u，v)是g中一条“一个端点在u中(例如：uu)，另一个端点不在u中的边(例如：vv-u)，且(u，v)具有最小权值，则一定存在g的一棵最小生成树包括此边(u，v)。.系统分析. 系统流程本系统主要是实现图的最短路径问题图2-12.2系统相关抽象数据类型2.2.1图的邻接矩阵存储结构形式说明#define maxvertexnum l00 /最大顶点数，应由用户定义typedef char vertextype; /顶点类型应由用户定义typedef int edgetype; /边上的权值类型应由用户定义typedef structvextextype vexsmaxvertexnum /顶点表edetype edgesmaxvertexnummaxvertexnum;/邻接矩阵，可看作边表int n，e; /图中当前的顶点数和边数mgragh;2.2.2建立无向网络的算法void createmgraph(mgraph *g)/建立无向网的邻接矩阵表示int i，j，k，w;scanf(%d%d，&g-n，&g-e); /输入顶点数和边数for(i=0;in;i+) /读人顶点信息，建立顶点表g-vexsi=getchar();for(i=0;in;i+)for(j=0;jn;j+)g-edgesij=0; /邻接矩阵初始化for(k=0;ke;k+)/读入e条边，建立邻接矩阵scanf(%d%d%d，&i，&j，&w);/输入边(v i ,v j )上的权wg-edgesij=w;g-edgesji=w;/createmgraph3.系统设计3.1系统功能 提供无向图的生成，并保证了该无向图为一个无向网，同时也提供了计算最短距离的迪杰斯特拉算法，以及图的遍历。3.2主要函数说明 本系统用了一个类来实现程序，里面包含了4个对象，即void graph:picture()；void graph:creatp(graph &t)；void graph:floyd(graph &t,const int n)；void graph:bfs(graph t)3.3主要算法说明3.3.1无向网的建立由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储 区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示 图是自然的事，它是一种最简单的这式映像结构，聚聚以一个由一个数据域和多个指针域存储该顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针.3.3.2数组表示法用两个数组分别存储数据元素的信息和数据元素这间的关系的信息。以二维数组表示有n个顶点的图时，需存放n个顶点信息和n2个弧信息的存储量。3.3.3floyd算法floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。floyd算法适用于apsp(all pairs shortest paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|v|次dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。4.心得体会当今世界，c语言作为国际上广泛流行的通用程序设计语言，在计算机的研究和应用中已展现出强大的生命力。c语言兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。而数据结构-作为c语言使用的途径学科,也是计算机学科的一门核心课程.虽然我们学c语言和数据结构已快一年了，但一直都注重理论概念，而实际上机操作却不多.很感谢这次的课程设计，它使我更加深刻地体会到多看专业书、多学习专业知识的重要性，只有掌握了一定量的专业知识才能得心应手地解决诸多问题；另外，在课程设计过程中，我遇到了很多棘手的问题，好几次都差点放弃了，但最终还是坚持下来了，所以我懂得了，做任何事都要有耐心，不要一遇到困难就退缩；当遇到那么多的问题时，我自己能解决的并不多，大部分都是通过和小组同学讨论而解决的。所以，在学习和工作中要时刻谨记“团结”二字，它好比通向成功的铺路石，不可或缺。在编程过程中，有编得很顺利的，也有很多不顺利的，正如人生的道路是曲折的，但正是因为曲折人生才光彩夺目，在人生的路上，总遇到重重困难，但正是因为这些困难我们才变的更加坚强，才能够不断地提高自己，充实自己，最后达到我们理想的彼岸。感谢冯老师在授课期间对我们严厉的态度和严格的管理，才造就了今天的我们。在课程设计过程中，我们几乎每个小组都遇到了不同程度的问题，但老师都细心指导，耐心地为我们讲解。老师认真负责的工作态度，对我们这次的课程设计得以顺利完成发挥了不可估量的作用。最后，再一次感谢在这次课程设计中对我给予帮助的老师和同学。通过这次课程设计，我们不光收获了知识，还收获了友谊和欢乐。附录1 源程序#include const int n=5; /n表示公园图中顶点个数const int e=7; /e表示公园图中路径bool visitedn+1; #define max 32767class graph public: 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 9 endl; cout 2 *-*4 endl; cout | /| endl; cout | 4 5/ | endl; cout | / | endl; cout 3 | / | 2 endl; cout | * 3 | endl; cout | / | endl; cout | /10 3| endl; cout 1 * / * 5 endl; cout 入口 出口 endl; cout下面是景点与景点之间的距离和介绍：endl; cout2.水族馆 距离为：3endl; cout3.摩天轮 距离为：10endl; cout4.动物园 距离为：9endl; cout3.摩天轮 距离为：4endl; cout4.动物园 距离为：5endl; cout5.公园出口 距离为：2endl; cout5.公园出口 距离为：3endl;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.ij if(i!=j)&(aijmax) 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.akjt.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; couti; while(i=5) if(i=1)cout这里就是你要去的地方拉!endlendl; else for(j=1;j=n;j+) if(i!=j) cout距离为t.aij: ; int next=t.pathij; coutj; while(next!=i) cout-next; next=t.pathinext; cout-iendl; coutch; if(ch=y) if(i=2) cout2-3-5endl; if(i=3) cout3-5endl; if(i=4) cout4-5endl; cout请问你想去游览公园全景吗(y/n)：ch;if(ch=y)cout请走1-2-3-4-5路线endl;coutch; if(ch=y) couti; if(ch!=y)