公园导游图课程设计.doc

1、课程设计（论文）目 录摘要 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），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质

2、是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种 运算的算法。1.问题描述.图的存储结构 图的存储方式很多，这里用的是邻接矩阵的方式。为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)=v 0 ，v i ，V n-1 。1.1.1 图的邻接矩阵表示法（）用邻接矩阵表示顶点之间的相邻关系；（）用一个顺序表来储存

3、顶点信息1.1.2图的邻接矩阵(Adacency Matrix)设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：若是网络，则邻接矩阵可定义为： .求最短路径给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.1单源最短路径问题Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，

4、直到从源点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)。.系统分析. 系统流

5、程本系统主要是实现图的最短路径问题图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建立无向网络的算法

6、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系统功能

7、提供无向图的生成，并保证了该无向图为一个无向网，同时也提供了计算最短距离的迪杰斯特拉算法，以及图的遍历。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无向网的建立由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储 区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据

8、类型表示元素之间的关系。另一方面，用多重链表表示 图是自然的事，它是一种最简单的这式映像结构，聚聚以一个由一个数据域和多个指针域存储该顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针.3.3.2数组表示法用两个数组分别存储数据元素的信息和数据元素这间的关系的信息。以二维数组表示有N个顶点的图时，需存放N个顶点信息和N2个弧信息的存储量。3.3.3Floyd算法Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。

9、此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。4.心得体会当今世界，C语言作为国际上广泛流行的通用程序设计语言，在计算机的研究和应用中已展现出强大的生命力。C语言兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。而数据结构-作为C语言使用的途径学科,也是计算机学科的一门核心课程.虽然我们学C语言和数据结构已快一年了，但一直都注重理论概念，而实际上机操作却不多.很感谢这次的课

10、程设计，它使我更加深刻地体会到多看专业书、多学习专业知识的重要性，只有掌握了一定量的专业知识才能得心应手地解决诸多问题；另外，在课程设计过程中，我遇到了很多棘手的问题，好几次都差点放弃了，但最终还是坚持下来了，所以我懂得了，做任何事都要有耐心，不要一遇到困难就退缩；当遇到那么多的问题时，我自己能解决的并不多，大部分都是通过和小组同学讨论而解决的。所以，在学习和工作中要时刻谨记“团结”二字，它好比通向成功的铺路石，不可或缺。在编程过程中，有编得很顺利的，也有很多不顺利的，正如人生的道路是曲折的，但正是因为曲折人生才光彩夺目，在人生的路上，总遇到重重困难，但正是因为这些困难我们才变的更加坚强，才能

11、够不断地提高自己，充实自己，最后达到我们理想的彼岸。感谢孙老师在授课期间对我们严厉的态度和严格的管理，才造就了今天的我们。在课程设计过程中，我们几乎每个小组都遇到了不同程度的问题，但老师都细心指导，耐心地为我们讲解。老师认真负责的工作态度，对我们这次的课程设计得以顺利完成发挥了不可估量的作用。最后，再一次感谢在这次课程设计中对我给予帮助的老师和同学。通过这次课程设计，我们不光收获了知识，还收获了友谊和欢乐。附录1 源程序#include const int n=5; /n表示公园图中顶点个数const int e=7; /e表示公园图中路径bool visitedn+1; #define ma

12、x 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() /公园图 void graph:picture() /公园图 cout -滨大公园导游图- endl; cout 以下是滨大公校的景点 endl; cout - endl; cout 丨 1.公园入口 2

13、.海盗船 丨 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; c

14、out下面是景点与景点之间的距离和介绍：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时

15、 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!=

16、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=

17、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) 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年 第二版 课程设计成绩评定表姓 名性 别专业班级课程设计题目：课程设计答辩或质疑记录：成绩评定依据：最终评定成绩（以优、良、中、及格、不及格评定） 指导教师签字： 年 月 日13