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

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

《拓扑排序课程设计报告.docx》由会员分享，可在线阅读，更多相关《拓扑排序课程设计报告.docx（20页珍藏版）》请在冰点文库上搜索。

拓扑排序课程设计报告

沈阳航空航天大学

课程设计报告

课程设计名称：

数据结构课程设计

课程设计题目：

拓扑排序算法

院（系）：

计算机学院

专业：

计算机科学与技术（嵌入式系统方向）

班级：

班

学号：

姓名：

王芃然

指导教师：

丁一军

目录

课程设计介绍

课程设计内容

由某个集合上的一个偏序得到该集合上的一个全序这个操作称之为拓扑排序。

若在图一的有向图上人为的加一个表示的弧表示领先于则图一表示的亦为全序且这个全序称为拓扑有序而由偏序定义得到拓扑有序的操作便是拓扑排序。

在网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。

编写算法建立有向无环图，主要功能如下：

1.能够求解该有向无环图的拓扑排序并输出出来；

2.拓扑排序应该能处理出现环的情况；

3.顶点信息要有几种情况可以选择。

课程设计要求

1.输出拓扑排序数据外，还要输出邻接表数据；

2.参考相应的资料，独立完成课程设计任务；

3.交规范课程设计报告和软件代码。

课程设计原理

课设题目粗略分析

本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的有向图，是一类较有向图更一般的特殊有向图。

其功能要求及个人在写程序时对该功能的实现作如下分析：

将图以合适的方式存储起来。

图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接表。

本人在构思时使用邻接表来建立有向无环图，将其存储起来；

求解该有向无环图的拓扑排序，并将其输出出来。

若通过构造，建立了一个有向无环图，那么一定可以求出其拓扑排序，其原理比较简单。

即统计每个节点的入度，将入度为的结点提取出来，然后再统计剩下的结点的入度，再次将入度为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图的拓扑排序序列；

拓扑排序算法应能够处理出现环的情况。

个人在写程序时，考虑到构造图时，会有构造成有向有环图的情况，应该在运行程序时，试着统计依次按照入读为零的节点输出的节点数是否为整个节点的总数，如果是，那么拓扑排序成功，输出拓扑排序的结果，否者输出有环出现；

输出除拓扑排序外，还要求输出邻接表数据。

由于图是用邻接表存储的，所以将邻接表按照顺序依次打印输出。

原理图介绍

功能模块图

图功能模块图

流程图分析

1.如图所示，根据题目要求建立一个有向无环图，按照提示，依次输入节点数和变数，然后输入两个联通的节点，前者指向后者，当输入边数为所要输入的数目时，输入结束，有向图建立完成（未判断是否有环）。

开始

建立有向无环图

结束

输入节点数，边数，

输入确定弧的两点

图建立有向无环图

2.如图所示，判断有向图是否为有向无环图。

按照输入的有向图建立一个邻接表，将图储存在邻接表中，并将邻接表打印，然后对该邻接表进行拓扑排序，依次取入度为零的节点，入栈，并删除该节点和该节点有关的所边，若入栈节点个数与节点数相同，则全部入栈，该图为无环图，可以进行拓扑排序，若该图节点数大于入栈节点数，则该图为有环图。

建立邻接表并打印

取入度为零的节点入栈，删除该节点，继续遍历其他节点

入栈节点数等于节点总数

该图为无环图

该图为有环图

结束

图判断是否为无环图

3.此时该图为有向无环图，可进行拓扑排序，在上一过程中，所有节点已经入栈，将栈顶弹出进入另一个空栈，，然后依次输出栈顶，拓扑排序成功。

如图所示。

开始

将栈顶依次输出

拓扑排序成功

结束

将弹出的栈顶进入新的空栈

输出栈顶元素

图输出拓扑排序结果

4.具体内容

-

-图拓扑排序

数据结构分析

存储结构

一个无环的有向图叫做有向无环图，简称图。

本算法首先要建立一个有向无环图，即通过输入各边的数据，搭建图的结构。

对于图的存储，用到邻接表，是一种链式存储结构。

弧结点结构类型：

该弧指向的顶点的位置

指向下一条弧的指针

邻接表头结点类型：

顶点信息

指向第一条依附于该点的弧的指针

算法描述

邻接表的构建

创建一个邻接表，首先要输入节点数和边数，然后输入确定一条边的两个节点，通过输入顺序来确定边的方向，构成有向图，具体方法如下：

初始化头结点

编写顶点的位置序号

先将头结点清零，编写顶点位置序号。

输入确定弧的两点，如果输入数字大于节点数或者小于零，则输出错误信息，并重新输入一组节点，申请新的节点来储存新的节点信息，该弧指向位置编号为的节点，下一条弧指向的是依附于的第一条弧，最后打印生成的邻接表。

输入确定弧的两个顶点，

输入的顶点序号不正确请重新输入

开辟新的弧结点

该弧指向位置编号为的结点

建立的邻接表为打印生成的邻接表（以一定的格式）

邻接表构建完成。

入栈操作

在本算法中栈主要用来构造拓扑排序序列。

由于栈具有先入后出的特点，所以，将每次选择入度为零的结点入栈，这样当结点都入栈的时候，再依次出栈，进入另一个新栈，这样，排序序列显而易见。

它将图这样的非线性结构转化为栈这样的线性结构。

建立空栈

栈底指针

栈顶指针

初始化栈

存储分配失败

入栈操作，压入新的元素为栈顶，为新的栈顶元素。

压入新的元素为栈顶

拓扑排序

本程序的拓扑排序，必须在图的邻接表已知的情况下。

它还有另外一个功能：

判断一个图是不是无环图。

确切的说，不能单纯的叫拓扑排序，但考虑它主要的作用，在不引起误解的情况下就叫拓扑排序算法。

判断一个图是否为有向无环图并进行拓扑排序，对于本题目来说，由于本题要求是对有向无环图进行拓扑排序，其主要方法是将入度为零的结点依次输出出来，知道图的所有定点全部输出为止。

那么若图为有环图，在环上的结点在其他结点都选择出来后，入度都不为零，即无法被输出出来。

那么就可以认为按照拓扑排序的方法输出结点后，若不是将节点全部输出出来的，则此图为有环图。

输出有向图有环，拓扑排序失败。

若无环，则进行拓扑排序。

通过入栈出栈的操作来完成拓扑排序。

主要算法如下：

初始化输出计数器

入度为的入栈

拓扑排序序列为

栈不为空

弹出栈顶

输出栈顶并计数

若入度减为零，则再入栈

有向图中有环

排序成功

调试与分析

调试过程

在调试程序是主要遇到一下几类问题：

1.数组的数据容易出现混乱，比如节点用数字标识，数组结点的位置是从开始，而标识符往往从开始，这在程序的开始就应该注意到；

2.各函数的形参和实参的区别，全局变量，局部变量的区别，特别是在做大型程序的时候，如果多个函数都要用到一个变量，那么就应把该变量定义为全局变量，若错误的定义为局部变量，很容易出现错误；

3.程序应该调理清晰，结构明朗，各个函数代表各个模块，起到不同的作用，并协调运作，形成含有不同功能的程序。

开始时因为程序的结构混乱而导致很难调试，无法找到错误的根源。

程序执行过程

系统使用说明：

1.图的创建；

打印邻接表；

进行拓扑排序；

退出程序。

具体内容：

输入边数及节点数，如图所示

图主菜单

图的创建，如图所示：

图图的创建

打印邻接表，如图所示：

图打印邻接表

进行拓扑排序，如图所示：

图进行拓扑排序

退出程序，如图所示：

图退出程序

参考文献

严蔚敏，吴伟民数据结构北京：

清华大学出版社，

张长海，陈娟程序设计北京：

高等教育出版社，

谭浩强程序设计北京：

清华大学出版社，

严蔚敏数据结构（语言版）清华大学出版社，

高婷杨明莉实用数据结构习题与实践北京：

清华大学出版社

殷人昆数据结构（用面向对象方法与描述）北京：

清华大学出版社

宁正元算法与数据结构习题精解和实验指导北京：

清华大学出版社

附录（关键部分程序清单）

程序代码

弧结点结构类型

该弧指向的顶点的位置

指向下一条弧的指针

邻接表头结点类型

顶点信息

指向第一条依附于该点的弧的指针

为邻接表类型

创建一个图的邻接表

输入顶点数

输入边数

初始化各顶点

编写顶点的位置序号

记录图中由两点确定的弧

输入确定弧的两个顶点，

输入的顶点序号不正确请重新输入

申请新的弧结点来存储用户输入的弧信息

该弧指向位置编号为的结点

下一条弧指向的是依附于的第一条弧

请输入指令：

进行拓扑排序

建立的邻接表为打印生成的邻接表（以一定的格式）

请输入指令：

感谢您的使用

进行拓扑排序

指令错误

栈的存储结构

栈底指针

栈顶指针

初始化栈

存储分配失败

压入新的元素为栈顶

追加新空间

存储分配失败

作为新的栈顶元素