拓扑排序课程设计报告.doc

《拓扑排序课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、下载可编辑航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：拓扑排序算法院（系）：计算机学院专业：计算机科学与技术（嵌入式系统方向）班级：14010105班学号：2011040101221姓名：王芃然指导教师：丁一军.专业.整理.下载可编辑目录1课程设计介绍11.1课程设计容11.2课程设计要求12课程设计原理22.1课设题目粗略分析22.2原理图介绍22.2.1功能模块图22.2.2流程图分析33数据结构分析73.1存储结构73.2算法描述74调试与分析124.1调试过程124.2程序执行过程1

2、2参考文献14附录（关键部分程序清单）15.专业.整理.下载可编辑1课程设计介绍1.1课程设计容由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。若在图一的有向图上人为的加一个表示V2<=V3的弧(“<=”表示V2领先于V3)则图一表示的亦为全序且这个全序称为拓扑有序,而由偏序定义得到拓扑有序的操作便是拓扑排序。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。编写算法建立有向无环图，主要功能如下：1.能够求解该有向无环图的拓扑排序并输出出来；2.

3、拓扑排序应该能处理出现环的情况；3.顶点信息要有几种情况可以选择。1.2课程设计要求1.输出拓扑排序数据外，还要输出邻接表数据；2.参考相应的资料，独立完成课程设计任务；3.交规课程设计报告和软件代码。.专业.整理.下载可编辑2课程设计原理2.1课设题目粗略分析本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的有向图，是一类较有向图更一般的特殊有向图。其功能要求及个人在写程序时对该功能的实现作如下分析：1.将图以合适的方式存储起来。图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接

4、表。本人在构思时使用邻接表来建立有向无环图，将其存储起来；2.求解该有向无环图的拓扑排序，并将其输出出来。若通过构造，建立了一个有向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的入度，将入度为0的结点提取出来，然后再统计剩下的结点的入度，再次将入度为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图的拓扑排序序列；3.拓扑排序算法应能够处理出现环的情况。个人在写程序时，考虑到构造图时，会有构造成有向有环图的情况，应该在运行程序时，试着统计依次按照入读为零的节点输出的节点数是否

5、为整个节点的总数，如果是，那么拓扑排序成功，输出拓扑排序的结果，否者输出“有环出现”；4.输出除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的，所以将邻接表按照顺序依次打印输出。.专业.整理.下载可编辑2.2原理图介绍2.2.1功能模块图拓扑排序算法打印邻接表拓扑排序图的建立入读为零的依次输出邻接表有向无环图可进行邻接矩阵图2.1功能模块图2.2.2流程图分析1.如图2.2所示，根据题目要求建立一个有向无环图，按照提示，依次输入节点数和变数，然后输入两个联通的节点，前者指向后者，当输入边数为所要

6、输入的数目时，输入结束，有向图建立完成（未判断是否有环）。开始建立有向无环图输入节点数i，边数n，j=0.专业.整理.下载可编辑j

7、接表并打印取入度为零的节点入栈，删除该节点，继续遍历其他节点入栈节点数等于节点总数NY该图为有环图该图为无环图.专业.整理.下载可编辑结束图2.3判断是否为无环图1.此时该图为有向无环图，可进行拓扑排序，在上一过程中，所有节点已经入栈，将栈顶弹出进入另一个空栈，，然后依次输出栈顶，拓扑排序成功。如图2.4所示。.专业.整理.下载可编辑开始将栈顶依次输出拓扑排序成功结束将弹出的栈顶进入新的空栈输出栈顶元素图2.4输出拓扑排序结果1.具体容.专业.整理.下载可编辑开始符合条件？根据输入信息建立邻接表建栈寻找入度为零的节

8、点入栈弹出栈顶，打印，将与栈顶元素邻接的节点入度减一栈是否为空结束输入节点及弧的信息--图2.5拓扑排序.专业.整理.下载可编辑3数据结构分析3.1存储结构一个无环的有向图叫做有向无环图，简称DAG图。本算法首先要建立一个有向无环图，即通过输入各边的数据，搭建图的结构。对于图的存储，用到邻接表，是一种链式存储结构。弧结点结构类型：typedefstructA