公园导游图课程设计.doc

《公园导游图课程设计.doc》由会员分享，可在线阅读，更多相关《公园导游图课程设计.doc（15页珍藏版）》请在三一办公上搜索。

1、学号： 课 程 设 计题目公 园 导 游 图教学院计 算 机 学 院专业计算机网络技术班级09网络技术（1）姓名指导老师冯 珊 、熊敬一2010年12月30日 课程设计任务书 20092010学年第 1学期学生姓名： 何雪梅 专业班级： 09网络技术 指导教师： 冯姗、熊敬一 工作部门： 计算机学院 一、课程设计题目: 公园导游图二、课程设计内容给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。三、进度安排1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个

2、数；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主要

3、数据结构63.2 主要函数说明63.3主要算法说明63.3.1数组表示法63.3.2Floyd算法64 心得体会7附录一：源程序8附录三：参考文献14摘 要 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的

4、插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种 运算的算法。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) ，其中每

5、条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.1单源最短路径问题Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。. 求最小生成树对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：Te,W(u , v)TE表示T的边集w(u，v)表示边(u，v)的权

6、。权最小的生成树称为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

7、; /顶点类型应由用户定义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

8、-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 g

9、raph:creatp(graph &t)；void graph:floyd(graph &t,const int n)；void graph:bfs(graph t)3.3主要算法说明3.3.1无向网的建立由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储 区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示 图是自然的事，它是一种最简单的这式映像结构，聚聚以一个由一个数据域和多个指针域存储该顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针.3.3.2数组表示法用两个数组

10、分别存储数据元素的信息和数据元素这间的关系的信息。以二维数组表示有N个顶点的图时，需存放N个顶点信息和N2个弧信息的存储量。3.3.3Floyd算法Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。4.心得体会当今世界，C

11、语言作为国际上广泛流行的通用程序设计语言，在计算机的研究和应用中已展现出强大的生命力。C语言兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。而数据结构-作为C语言使用的途径学科,也是计算机学科的一门核心课程.虽然我们学C语言和数据结构已快一年了，但一直都注重理论概念，而实际上机操作却不多.很感谢这次的课程设计，它使我更加深刻地体会到多看专业书、多学习专业知识的重要性，只有掌握了一定量的专业知识才能得心应手地解决诸多问题；另外，在课程设计过程中，我遇到了很多棘手的问题，好几次都差点放弃了，但最终还是坚持下来了，所以我懂得了，做任

12、何事都要有耐心，不要一遇到困难就退缩；当遇到那么多的问题时，我自己能解决的并不多，大部分都是通过和小组同学讨论而解决的。所以，在学习和工作中要时刻谨记“团结”二字，它好比通向成功的铺路石，不可或缺。在编程过程中，有编得很顺利的，也有很多不顺利的，正如人生的道路是曲折的，但正是因为曲折人生才光彩夺目，在人生的路上，总遇到重重困难，但正是因为这些困难我们才变的更加坚强，才能够不断地提高自己，充实自己，最后达到我们理想的彼岸。感谢冯老师在授课期间对我们严厉的态度和严格的管理，才造就了今天的我们。在课程设计过程中，我们几乎每个小组都遇到了不同程度的问题，但老师都细心指导，耐心地为我们讲解。老师认真负责

13、的工作态度，对我们这次的课程设计得以顺利完成发挥了不可估量的作用。最后，再一次感谢在这次课程设计中对我给予帮助的老师和同学。通过这次课程设计，我们不光收获了知识，还收获了友谊和欢乐。附录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 in

14、t 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

15、 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; c

16、out5.公园出口 距离为：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

17、; 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+) 待添加的隐藏文字内容3 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.

18、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

19、-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) cout *退出程序*endl; cout 欢迎下次再来endl; break; else break; int main()graph t;t.picture();t.creatp(t);t.floyd(t,n);t.bfs(t);附录二：测试数据图11图12参考文献1 严蔚敏 吴伟民著 数据结构（C 语言版） 清华大学出版 1999年 第一版 2 谭浩强著C程序设计 清华大学出版社 1999年 第二版 课程设计成绩评定表姓 名性 别专业班级课程设计题目：课程设计答辩或质疑记录：成绩评定依据：最终评定成绩（以优、良、中、及格、不及格评定） 指导教师签字： 年 月 日