数据结构课程设计-图的遍历和生成树的求解实现.doc
《数据结构课程设计-图的遍历和生成树的求解实现.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计-图的遍历和生成树的求解实现.doc(22页珍藏版)》请在沃文网上搜索。
1、 目 录摘 要3前 言4正 文51.问题描述:52.采用类C语言定义相关的数据类型53各模块流程图及伪码算法64函数的调用关系图85调试分析91.调试中遇到的问题及对问题的解决方法92.算法的时间复杂度和空间复杂度96.测试结果10参考文献14摘 要图是一种复杂的非线性数据结构,一个图G(Grah)由两个集合V和E构成,图存在两种遍历方式,深度优先遍历和广度优先遍历,广度优先遍历基本思路是假设从图中某顶点U出发,在访问了顶点U之后依次访问U的各个未访问的领接点,然后分别从这些领接点出发依次访问他们的领接点,并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思
2、路是从某个顶点出发,访问此顶点,然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法KRUSKAL算法;可以对图形进行最小生成树的求解。主要问题是:(1)当给出一个表达式时,如何创建图所表达的树,即相应的逻辑结构和存储结构?(2)表达式建立好以后,如何求出其遍历?深度优先和广度优先遍历。(3)计算它的最小生成树?主要是prim算法和kruscal算法两种形式。前 言很多涉及图的操作的算法都是以图的遍历操作为基础,通过遍历的演示,方便在学习中更好的理解突地遍历的过程。通过对图的深度优先遍历和广度优先遍历的演示,分别两种遍历的不同与其优缺点。我们在对一些问题进
3、行求解时,会发现有些问题很难找到规律,或者根本无规律可寻。对于这样的问题,可以利用计算机运算速度快的特点,先搜索查找所有可能出现的情况,再根据题目条件从所有可能的情况中,删除那些不符合条件的解。在深度优先搜索算法中,是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索, 本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展, 也就是说先产生 的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。很多问题都可以用广度优先搜索进行处理,如翻币问题、最短路径问题等。在计算机中,有多种方法存储图的信息,由于图的结构复杂,使用广泛,一般应根据实际的应用,选
4、择适合的表示方法。常用的图的存储结构有邻接矩阵、邻接多重表和邻接表。在实际问题当中,经常遇到这类问题,为新建的某个机构进行选址,道路交通路线,如何走完所有路线,旅游线路等一系列问题都涉及到图的知识。图是一种复杂的非线性数据结构,一个图G(Grah)由两个集合V和E。构成,图存在两种遍历方式,深度优先遍历和广度优先遍历,广度优先遍历基本思路是假设从图中某顶点U出发,在访问了顶点U之后依次访问U的各个未访问的领接点,然后分别从这些领接点出发依次访问他们的领接点,并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发,访问此顶点,然后依次从V的未被
5、访问的领接点出发深度优先检索图。直至图中所有顶点都被访问到。PRIM算法KRUSKAL算法;可以对图形进行最小生成树的求解。树型结构是一种非线性结构,它用于描述数据元素之间层次关系,如人类社会的族谱等,树型结构的应用非常广泛,磁盘文件目录结构就是一个典型的例子。正 文1.问题描述:图是一种复杂的非线性数据结构,一个图G(Grah)由两个集合V和E构成,图存在两种遍历方式,深度优先遍历和广度优先遍历,广度优先遍历基本思路是假设从图中某顶点U出发,在访问了顶点U之后依次访问U的各个未访问的领接点,然后分别从这些领接点出发依次访问他们的领接点,并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有
6、领接点被访问到。深度优先的基本思路是从某个顶点出发,访问此顶点,然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法KRUSKAL算法;可以对图形进行最小生成树的求解。2.采用类c语言定义相关的数据类型#define int_max 10000 /定义邻接矩阵最大值10000为无穷大#define max 20 /最大顶点个数typedef struct /开始对 邻接表或图进行定义char vexs20; /顶点数的名称AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum /图中顶点数和边数int creatMGraph_L(M
7、Graph_L &G)/创建图用邻接矩阵表示int visitedmax; /访问标记typedef struct arcnode /弧结点int adjvex; /该弧指向的顶点的位置,即边或弧依赖的顶点序号char *info; / 该弧信息char data; /结点信息基本操作:int creatadj(algraph &gra,MGraph_L G)/用邻接表存储图int initqueue(linkqueue &q)/初始化队列int enqueue(linkqueue &q,int e)/入队int dequeue(linkqueue &q,int &e)/出队int queue
8、empty(linkqueue q)/判断队为空void bfstra(algraph gra)/广度优先遍历int bfstra_fen(algraph gra)/求连通分量3各模块流程图及伪码算法int prim(int gmax,int n) /最小生成树PRIM算法int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点int i,j,k,min; for(i=2;i=n;i+) /n个顶点,n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 low
9、cost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf;return f;void kruscal_arc(MGraph
10、_L G,algraph gra) edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi
11、.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; / coutxym;/ coutendl; buf=find(acrvisited,x); edf=find(acrvisited,y); / coutbuf edfendl; edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; 4函数的调用关系图函数调用关系如图4.1所示图4.1 函数调用关系图5调试分析1.调试中遇到的问题及对问题的解决方法解决Visual C+ 6.0不正确连接的问
12、题明明改动了一个文件,却要把整个项目全部重新编译链接一次。刚刚链接好,一运行,又提示重新编译链接一次。这是因为出现了未来文件(修改时间和创建时间比系统时间晚)的缘故。可以这样处理:找到工程文件夹下的debug目录,将创建和修改时间都比系统时间的文件全部删除,然后再从新“Rebuild All”一次。2.算法的时间复杂度和空间复杂度关于时间复杂度的计算是按照运算次数来进行的, 关于空间复杂度的计算是在程序运行过程所要借助的内容空间大小。即:空间复杂是储存空间的大小和变换等等决定的.时间复杂是逻辑比较、赋值等基本运算的次数决定的.prim算法的时间复杂度为O(n 2),kruskcal算法的时间复
13、杂度为O(eloge)prim的空间复杂度为O(n* prevex), kruskcal算法的空间复杂度为O(n)6.测试结果(1)输入图的顶点即弧度个数:(2)分别写出边的权值:邻接矩阵和邻接表创建成功,显示出菜单:菜单选择:输入0,显示邻接矩阵输出y 进行下一步操作,重新选择菜单,输出1显示邻接表:输出y 进行下一步操作,重新选择菜单,输出2显示广度优先遍历:输出y 进行下一步操作,重新选择菜单,输出3显示深度优先遍历:输出y 进行下一步操作,重新选择菜单,输出4,显示prim算法计算最小生成树:输出y 进行下一步操作,重新选择菜单,输出5,显示kruscal算法计算最小生成树:输出y 进
14、行下一步操作,重新选择菜单,输出6,计算出该图的连通分量:输出n,结束操作,退出运行: 设计总结在这三周的算法与数据结构课程设计中,我的题目是:图的遍历和生成树的求解实现,这三周课程设计中,通过该题目的设计过程,我加深了对图数据结构及队列的逻辑结构,存储结构及图的深度优先和广度优先遍历过程,Prim算法和Kruscal算法进行最小生成树求解过程的理解,对图数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展。在课程设
15、计时遇到了很多的问题,在老师的帮助,和对各种资料的查阅中,将问题解决,培养了我自主动手,独立研究的能力,为今后在学习工作中能更好的发展打下了坚实的基础。三周的课程设计很短暂,但其间的内容是很充实的,在其中我学习到了很多平时书本中无法学到的东西,积累了经验,锻炼了自己分析问题,解决问题的能力,并学会了如何将所学的各课知识融会,组织,来配合学习,三周中我收益很 大,学到很多。致 谢在本次算法与数据结构的课程设计中,我学到了很多的东西,同时也得到了很多人的帮助和指导。在此我非常的感谢他们,感谢他们这些天对我的帮助、感谢他们对我的悉心指导。其次,我更要感谢我们的指导老师王旭阳老师。谢谢她这三周以来对我
16、们的悉心指导和帮助。感谢她能在百忙中抽出时间,在机房高温之下还非常认真的为我们做课设指导,在此,我深深的感谢我的指导老师。最后,我还要感谢我们的学校以及学校领导,感谢他们能够给我们一个这么好的锻炼平台,让我们能够对自己所学的知识充分的利用和学习,让我的个人能力也有所提高。参考文献1. 严蔚敏,吴伟民, 数据结构(C语言版),北京:清华大学出版社,20032. 严蔚敏,吴伟民, 数据结构题集(C语言版),北京:清华大学出版社,20053. DATA STRUCTURE WITH C+,William Ford,William Tcpp,北京:清华大学出版社(影印版),20054. 谭浩强,C语言
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 遍历 生成 求解 实现