图的遍历与最小生成树的实现.doc
《图的遍历与最小生成树的实现.doc》由会员分享,可在线阅读,更多相关《图的遍历与最小生成树的实现.doc(45页珍藏版)》请在咨信网上搜索。
1、图的遍历与最小生成树的实现 作者: 日期:42 个人收集整理 勿做商业用途数学与计算机学院课程设计说明书课 程 名 称:数据结构与算法课程设计 课 程 代 码: 题 目:图的遍历和最小生成树 年级/专业/班: 2011级软工一班 学 生 姓 名: 学 号: 开 始 时 间: 2012 年 12 月 24 日完 成 时 间: 2012 年 1 月 3 日课程设计成绩:学习态度及平时成绩(30)技术水平与实际能力(20)创新(5) 说明书(计算书、图纸、分析报告)撰写质量(45)总 分(100)指导教师签名: 年 月 日目 录 (小三黑体,居中)引言11 需求分析2 概要设计3详细设计4调试分析5
2、用户使用说明6测试结果7结论致谢参考文献(目录左对齐,所有的均为1。5倍行距,未具体指明使用字体的均为小四宋体,以下同) (目录中最多放二级标题。注意看页面的规范要求。尤其注意页眉。页眉从目录开始) 摘 要 图是一种比线形表和树更为复杂的数据结构.在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法,邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词:图;存储结构;遍历 引 言 数据结构是计算机存储、组织数据的方式,是指相互之间
3、存在一种或多种特定关系的数据元素的集合.利用数据结构能解决许多实际问题,在各个方面都有非常不错的成就.通过本项课程设计,培养学生独立思考、综合运用所学有关相应知识的能力,使学生巩固数据结构课程学习的内容,掌握工程软件设计的基本方法,强化上机动手编程能力,闯过理论与实践相结合的难关;为了培养学生综合运用所学知识、独立分析和解决实际问题的能力,培养创意识和创新能力,使学生获得科学研究的基础训练。为后续各门计算机课程的学习和毕业设计打下坚实基础.同时,可以利用这次机会来检验自己的c+数据结构水平,提高自己的写作水平,锻炼自己的动手能力。而此次课程设计的任务和意义在于:增强自己的动手能力,利用VC+6
4、.0等专业软件编程实现图各种遍历的算法,以及最小生成树算法,增强自己的调试程序和测试程序的能力.1 需求分析 1。1任务与分析 1. 由键盘向程序输入相关数据;2. 程序处理输入数据,以十字链表,邻接矩阵和邻接链表的形式输出;3. 根据已建成的图,程序实现图的深度优先遍历,广度优先遍历;4. 显示图的最小生成树,连同分量的实现;5. 采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储.1.2测试数据 1. 邻接矩阵测试数据:6 6 a b c d e f a b 2 a e 6 a d 5 b d 4 b c 1 b f 3 2. 邻接链表测试数据:7 8 a b c d e f g
5、 a b a e a c a f b g b d d g c f3. 十字链表测试数据:4 5 3 2 2 5 4 3 99 3 4 662 概要设计 2.1 ADT描述 ADT Graph 数据对象:V具有相同特征的数据元素,即V顶点集数据关系:EVR VR=v,wv,wV,v。w表示顶点v和顶点w之间的边;基本操作:初始化空图; 输入建立图; 广度优先遍历; 深度优先遍历; 最小生成树; ADT Graph2.2程序模块结构 根据本系统对功能实现的要求,主要可以分为一下三个大的模块:1. 邻接矩阵存储结构;2. 邻接链表存储结构;3. 十字链表存储结构;其中每个模块又包涵其它相应的子功能模
6、块.则根据以上可以得到本系统的概要设计图 图的遍历与最小生成树退出系统十字链表存储结构邻接链表存储结构邻接矩阵存储结构2.3各功能模块(四号黑体) 2。3.1在邻接矩阵(AdjMWGraph)类中 void kruscal_arc(); /克鲁斯卡尔算法 AdjMWGraph(); /构造函数 void CreatG(int n,int e); /建立一个图的邻接矩阵 void DepthF(); /连通分量的实现 void BoradF(); /连通分量的实现 void PrintOut(); /输出图的信息 void Prim (); /普里姆算法 void kruscal_arc();
7、/克鲁斯卡算法 void DepthM(); /深度非递归优先遍历 void Borad(int v,int visited); /广度非递归优先遍历 void Depth(int v,int visited); /深度递归优先遍历2.3.2在邻接链表( AdjTWGraph)类中 void Prim (); /普里姆算法 void CreatG(int n,int e); /建立一个图的邻接表 void kruscal_arc(); /克鲁斯卡算法 void DepthF() /连通分量的实现 void BoradF() /连通分量的实现 void PrintOut(); /输出图的信息 v
8、oid Borad(int v,int visited); /广度非递归优先遍历 void Depth(int v,int visited); /深度非递归优先遍历 void DepthM(int v,int visited);/深度递归优先遍历2.3.3在十字链表( Linkedmat )类中 void Creat(); /创建一个十字链表 void Show(); /输出显示十字链表void zh(); /十字链表转换为邻接矩阵void Depth(int v,int visited);/深度递归优先遍历void Borad(int v,int visited);/广度非递归优先遍历voi
9、d DepthF(); /连通分量的实现void BoradF(); /连通分量的实现void Prim (); /普里姆算法 void kruscal_arc(); /克鲁斯卡尔算法3详细设计3。1结构体定义struct Node int row; int col; Node *down; Node *right; union Nodenext; ElemType val; ;;struct Edgeint dest;ElemType weight;Edge next;struct item ElemType data;Edge *adj;;struct MinSpanTree ElemTy
10、pe begin,end; ElemType length; ;3。2 初始化(四号黑体)3.2。1邻接矩阵的初始化AdjMWGraph() for ( int i=0; iMaxVertices; i+ ) for ( int j=0; jMaxVertices; j+ ) if( i=j ) Edgeij=0; else Edgeij=MaxWeight; numE=0; numV=0;3.2.2邻接链表的初始化AdjTWGraph:AdjTWGraph()for(int i=0;iMaxVertices;i+)Verticesi.data=0;Verticesi.adj=NULL;num
11、V=0;numE=0;3。2。3十字链表的初始化LinkeDmat() *hm=null;3。3 图的创建(四号黑体)3。3.1创建图的邻接矩阵void AdjMWGraph::CreatG(int n,int e)int vi,vj,w,i; numE=e; numV=n; cout”n 输入顶点的信息(整型):” ; for (i=0; inumV; i+ ) cout”n ”i+1Verticesi; for (i=0; inumE; i+ ) coutvivjw; Edgevi1vj-1=w; 3.3.2创建图的邻接链表void AdjTWGraph::CreatG(int n,int
12、 e)int vi,vj;DistT w;numE=e;numV=n;coutn输入顶点信息:endl;for(int i=0;inumV;i+)cout”ni+1Verticesi。data;for(int j=0;jvivjw;if(vi1|vinumV|vjnext=NULL;if(Verticesvi-1.adj=NULL)Verticesvi1.adj=q;elseEdge curr=Verticesvi1.adj,pre=NULL;while(curr!=NULLcurr-destnext=pre-next;prenext=q; Edge *p=new Edge;p-dest=vi
13、1;p-weight=w;p-next=NULL;if(Verticesvj1。adj=NULL)Verticesvj1.adj=p;elseEdge *curr=Verticesvj1.adj,*pre=NULL;while(curr!=NULL&currdestvi1)pre=curr;curr=currnext;if(pre=NULL)p-next=Verticesvj-1。adj;Verticesvj1。adj=p;elsepnext=pre-next;pre-next=p;3.3.3创建图的十字链表void Linkedmat::Creat()int m,n,r,c,v,s;Node
14、 p,q,*h10;cout请输入您要创建的矩阵维数”endlendl;coutm;coutn;s=mn?m:n;if(mn) k=n;else k=m;p=new Node;p-row=m;p-col=n;hm=p;h0=p;for(int i=1;irow=0;pcol=0;hi=p;pright=p;pdown=p;hi1next=p;hsnext=hm;coutendl”注意:endl;cout”最大行坐标:”mendl;cout最大列坐标:nendl;cout”三元组最多个数:m*nendl;cout”若输入不在此范围内的数据将丢失!endl;int t;coutt;cout”请输入
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遍历 最小 生成 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。