欢迎来到沃文网! | 帮助中心 分享知识,传播智慧!
沃文网
换一换
首页 沃文网 > 资源分类 > DOCX文档下载
 

数据结构设计无向图

  • 资源ID:20041       资源大小:120.31KB        全文页数:22页
  • 资源格式: DOCX        下载权限:游客/注册会员/VIP会员    下载费用:10积分 【人民币10元】
快捷注册下载 游客一键下载
会员登录下载
三方登录下载: QQ登录   微博登录  
下载资源需要10积分 【人民币10元】
邮箱/手机:
温馨提示:
支付成功后,系统会自动生成账号(用户名和密码都是您填写的邮箱或者手机号),方便下次登录下载和查询订单;
支付方式: 微信支付    支付宝   
验证码:   换一换

加入VIP,免费下载资源
 
友情提示
2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

数据结构设计无向图

无向图学校专业班级姓名学号任课教师数据结构课程设计题目3以邻接链表的方式确定一个无向网,完成⑴建立并显示出它的邻接矩阵;⑵对该图进行广度优先遍历,显示遍历的结果,(并随时显示队列的入、出情况);⑶普里姆算法构造其最小生成树,随时显示其构造的过程;⑷用克鲁斯卡尔算法构造其最小生成树,随时显示其构造的过程。一、需求分析1.运行环境MicrosoftVisualStudio20122.程序所实现的功能a建立并显示图的邻接矩阵;b广度优先遍历该图,显示遍历结果;c用普里姆算法构造该图的最小生成树,显示构造过程;d用克鲁斯卡尔算法构造该图的最小生成树,显示构造过程。3.程序的输入,包含输入的数据格式和说明a输入顶点数,及各顶点信息数据格式为整形;b输入弧以及其权值数据格式为整形。1.程序的输出,程序输出的形式a输出图的邻接矩阵;b广度优先遍历结果;c普里姆算法构造最小生成树的结果;d克鲁斯卡尔算法构造最小生成树的结果。2.测试数据,如果输入的数据量较大,需要给出测试数据a顶点个数5b各个顶点为ABCDEc输入所有的弧(格式为“顶点顶点权值”)为AB10AC4BD3CD5BE6DE9二、设计说明算法设计的思想建立图类,建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。在本次的设计中,我采用的是多文件的编程方式。每个类写成了一个头文件。这样有助于阅读和查看源程序。1.邻接链表邻接链表是一种链式存储结构。在邻接链表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由3个域组成,其中邻接点域指示与顶点Vi邻接的点在图中的位置,链域指示下一条边或弧的结点;数据域存储和边或弧相关的信息,如权值等。所以一开始必须先定义邻接链表的边结点类型以及邻接链表类型,并对邻接链表进行初始化,然后根据所输入的相关信息,包括图的顶点数、边数、是否为有向,以及各条边的起点与终点序号,建立图的邻接链表。2.邻接矩阵图的邻接矩阵存储表示即是数组存储表示,在邻接矩阵中,我们定义两个数组分别存储数据元素的信息和数据元素之间的关系(边或弧)的信息,以二维数组表示有n个顶点的图时,需存放n个顶点信息和n的平方个弧信息的存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连,并容易求得各个顶点的度。故在建立邻接矩阵之前,必须先定义顶点关系类型和相关指针指示弧的信息。3.广度优先遍历假设从图总某顶点出发,在访问了v之后依次访问v的各个未曾访问到的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的邻接点”先于“后被访问的邻接点”被访问,直至图中所有已被访问的邻接点都被访问到。若此时图中尚有顶点未被访问到,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程是以v为起始点,由近及远,依次访问饿v有路径相通且路径长度为1,2.的顶点。和深度优先搜索类似,在遍历过程中也需要一个访问标志数组。并且,为了顺次访问路径长度为2,3的顶点,需附设队列以存储已被访问的路径长度为1,2.的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列,并定义队首与队尾指针,同时也要定义一个标志数组以标记结点是否被访问。同样,也是从初始点出发开始访问,访问初始点,标志其已被访问,并将其入队。当队列非空时进行循环处理。当结点被访问时对其进行标志,并入队列。通过while()循环,并以是否被访问为控制条件,访问所有结点,完成图的广度优先遍历。4.普里姆算法假设NV,{E}是连通网,TE是N上最小生成数中边的集合。算法从U{U0},TE{}开始,重复执行如下操作;在所有的边(u,v)中找一条代价最小的边(u0,v0)并入集合TE,同时V0并入U,直到UV为止。此时TE中必有n-1条边,则,TV,{TE}为N的最小生成树。5.克鲁斯卡尔算法假设连通网NV,{E},则令最小生成树的初始状态为只有n个顶点且无边的非连通图TV,{},图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直到T中的所有顶点都在同一个连通分量上为止。主要的数据结构设计说明图的邻接矩阵、邻接表的建立。图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树。程序的主要流程图程序的主要模块,要求对主要流程图中出现的模块进行说明用邻接链表的方式确定一个无向图,以邻接矩阵的方式输出,再进行图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树并输出。程序的主要函数说明intlocatepointstring;定位节点位置无向网邻接表方式确定输出邻接矩阵普里姆算法克鲁斯卡尔算法广度优先遍历voidBreadth_traversal;广度优先遍历voidprintgragh;邻接矩阵的输出voidprim;普里姆算法voidktus;克鲁斯卡尔算法三、上机结果及体会1.上机过程中出现的问题及其解决方案。问题刚开始编译没有错误,但结果有问题。在其中的普里姆算法和克鲁斯卡尔算法的循环过程中,对循环控制变量设置不当,导致程序陷入死循环之中。解决方案调整改变循环控制变量。2.程序中可以改进的地方说明程序中的广度优先遍历,可以考虑用循环来做,也可以用栈来实现。在本程序中,两个没有联系的顶点之间的权值的无穷大我是用“0”来表示的。可以考虑用一个特殊字符来实现。四、实验源程序*******************************************************************************头文件node_linklist.hifndefNODE_LINKLISTdefineNODE_LINKLISTclassnode_array;//邻接链表链结点classnode_linklist{publicintposition;intweight;node_linklist*next;node_linklistinta,intb{positiona;weightb;nextNULL;}node_linklist{positionNULL;weightNULL;nextNULL;}node_linklist{}};endif*******************************************************************************头文件node_array.hifndefNODE_ARRAYdefineNODE_ARRAY//邻接链表数组结点classnode_array{publicnode_linklist*next;stringdata;node_array{data\0;nextNULL;}node_array{}};endif*******************************************************************************头文件tu_matrix.hifndefTU_MATRIXdefineTU_MATRIX//图类classtu_matrix{privateintmatrix[MAX][MAX];stringtoppoint[MAX];intnumpoint;node_arrayvertices[MAX];publictu_matrix{}voidcreat;intlocatepointstring;//返回这个顶点的位置voidBreadth_traversal;voidprintgragh;voidprim;voidktus;};inttu_matrixlocatepointstringb{inti0;for;inumpoint;//输入顶点couttoppoint[i];}//以邻接链表确定无向网node_linklist**endnewnode_linklist*[numpoint];//指向数组链表的最后一个节点指针数组int*ppnewint[numpoint];//辅助数组,当其中的值不为0时,表示该数组节点后面已经有至少一个链表节点,否则表示没有链表节点forinti0;idata1data2num;nlocatepointdata1;mlocatepointdata2;ifn-1m-1{ifpp[n]//如果该数组节点后面没有链表节点{pppnewnode_linklistm,num;end[n]vertices[n].nextppp;pp[n]1;}else{end[n]-nextnewnode_linklistm,num;end[n]end[n]-next;}ifpp[m]//如果该数组节点后面没有链表节点{pppnewnode_linklistn,num;end[m]vertices[m].nextppp;pp[m]1;}else{end[m]-nextnewnode_linklistn,num;end[m]end[m]-next;}}}whiledata10//根据邻接链表建立邻接矩阵node_linklist*p;forinti0;iposition;mp-weight;pp-next;matrix[i][n]m;};}deleteend;}voidtu_matrixprintgragh//打印无向网的邻接矩阵{cout\t\tincludedefineMAX40usingnamespacestd;includenode_linklist.hincludenode_array.hincludetu_matrix.hvoidmain{intk1;tu_matrix*graph;whilek{coutcreat;graph-printgragh;graph-Breadth_traversal;graph-ktus;graph-prim;deletegraph;coutk;}systempause;}五、输出结果显示六、收获及体会在这次的上机实验中,我更深入地学习了图的相关算法思想及其实现过程,用C++语言实现了算法。其中的数据元素为node_linklist*类型的一个数组指针的用法我颇费心思,蒋经国一翻认真思考及改正之后,终于正确地实现了我预想中的结果。这使我再一次正确地复习了一遍指针及指针数组的用法。编程过程中,程序一度在克鲁斯卡尔算法和普里姆算法中陷入了死循环,我运用设置断点,逐过程执行的方法找到了死循环的位置,通过认真分析,找出了陷入死循环的原因,并予以了改正。这使我更好地掌握了一种编程中排查错误的方法。有助于在以后的编程过程中更快得找到错误。这次试验,我不尽系统地复习了数据结构这门课程,而且付诸了实践,而且学会了排查错误的方法。这次实验收获颇丰。一定会给我今后的学习带来很大的便利。最后,我十分感谢王老师的辛勤教导,帮助我学到了不少知识。这是我今后的学习生活中十分宝贵财富。七、参考文献缪淮扣,顾训穰,沈俊.数据结构C++实现.科学出版社,2011年修订忽略此处..

注意事项

本文(数据结构设计无向图)为本站会员(星星008)主动上传,沃文网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知沃文网(发送邮件至2622162128@qq.com或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给沃文网发消息,QQ:2622162128 - 联系我们

版权声明:以上文章中所选用的图片及文字来源于网络以及用户投稿,由于未联系到知识产权人或未发现有关知识产权的登记,如有知识产权人并不愿意我们使用,如有侵权请立即联系:2622162128@qq.com ,我们立即下架或删除。

Copyright© 2017-2019 www.wodocx.com ,All Rights Reserved |陕ICP备19002583号  

陕公网安备 61072602000132号     违法和不良信息举报:0916-4228922