数据结构拓扑排序课程设计_第1页
数据结构拓扑排序课程设计_第2页
数据结构拓扑排序课程设计_第3页
数据结构拓扑排序课程设计_第4页
数据结构拓扑排序课程设计_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、课题二拓扑排序1问题的提出2.1问题的提出任务：编写函数实现图的拓扑排序。程序所实现的功能：建立对应的邻接表，对该图进行拓扑排序，并显示排序结果。输入：顶点数,边数及各顶点信息（数据格式为整形）输出：拓扑排序结果。2.2概要设计1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。2解决拓扑排序的方法如下：（1）在有向图中选一个没有前驱的顶点且输出之。（2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者

2、当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。3构造邻接表图：邻接表图4.为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedefstructstack栈的结构，存储图的顶点序号4源代码/采用尾插法创的邻接图栈的结构，存储图的顶点序号弧结点顶点数组指向与顶点邻接的第一条弧邻接表图请输入图的顶点数和弧数且顶点数不能超过请输入顶点值输入图的顶点输入图的弧请输入请输入第条1弧的弧尾和弧头求每个顶点的入度值入度顶点入栈记求每个顶点的入度值入度顶点入栈记+录+输;出/的/顶点数把与顶点把与顶点相/邻接的顶点的入度拓扑排序不成功

3、拓扑排序成功结果与分析2.4.它的时间复杂度是O(G.vexnum+G.arcnum)。2.整个程序的关键就是采用尾插法创的邻接表图，运用栈来实现各个数值的输入输出及存储。3注意*的使用，并不是什么情况下都用*，它有时候会造成数据破坏，利用破坏的值进行运算，结果可想而知，所以，如果没返回值时，一般不要用。4为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点，此程序段书写如下：建零入度顶点栈入度为者进栈对输出顶点计数输出号顶点并计数对号顶点的每个邻接点的入度减1一旦入度为0则入栈5测试的数据如下：第一组结果（有向无环图）C:FilesMicriosuftVisualStu

4、diaByProjectslC:FilesMicriosuftVisualStudiaByProjectsl1123Debug：123.虞输入圉的顶*裁和切庶卞且顶点谿卜能赳出恥加输入顶点值：1234G晴输入第1条弧的弧尼和弧头:12笹入影条弧的弧尾和弧头:舍输入第3条弧的弧尾和弧头:脣输入第4茶弧的弧尾和弧头=51情嗡入第E条弧的弧尾和弧头:52i青愉入第6条弧的弧匡和弧头；B31234师扑排序成功tPressanyJceitocontinueB第二组结果（有向有环图）：诵输入圏的顶点数和弧数V且顶点数不能超过阴请输.入顶点值:1M输入第丄条弧的弧尾和弧头晴输入第2条弧的弧尾和弧头情输入第5条弧的弧尾和弧头情输入第6条弧的弭层和弧头障输入第?条弧的弧足

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论