数据结构拓扑排序.doc

湖南人文科技学院计算机科学技术系
课程设计说明书
课程名称: 数据结构
课程代码:
题目: 拓扑排序
年级/专业/班:10级计算机科学与技术软件工程二班
学生姓名: 刘玄郑晴李坤
洪毅唐宏峰曾齐
学号:

指导教师: 易叶青
开题时间: 2012 年 3 月 8 日
完成时间: 2012 年 4 月 8 日

目录
摘要 2
一、引言 3
二、设计目的与任务 3
1、课程设计目的 3
2、课程设计的任务 3
三、设计方案 3
1、需求分析 3
2、概要设计 4
3、详细设计 5
四、调试分析与体会 26
五、运行结果 27
六、结论 27
七、致谢 28
八、参考文献 28

摘要
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序(Topological Sort),是将G中所有顶点排成一个线性序列,使得对图中任意一对顶点u和v,若<u,v>∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。
关键词:拓扑;数据结构;C;C++;
Abstract
For a directed acyclic graph ( Directed Acyclic Graph DAG) G topological sort ( Topological Sort ), G is all vertices into a linear sequence of arbitrary graph, makes a pair of vertices u and V, if < u, V > E ( G ), u in linear occur in the sequence before v. Usually such linear sequences called meet the topological order ( Topolgical Order ) sequences, referred to as the topological sequence.
Keywords: Topology; data structure; C; C + +;

《数据结构》课程设计
----拓扑排序
一、引言
数据结构是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心课程,而且已成为其他理工专业的热门选修课。
采用邻接表存储结构实现有向图;有向图需通过顶点数、弧数、顶点以及弧等信息建立。
用邻接表构造图然后进行拓扑排序,输出拓扑排序序列。
二、设计目的与任务
1、课程设计目的
1、选择合适的存储结构,建立有向无环图,并输出该图;
2、实现拓扑排序算法;
3、运用拓扑排序实现对教学计划安排的检验。
2、课程设计的任务
在AOV网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排,根据课程之间的依赖关系,制定课程安排计划。按照用户输入的课程数,课程间的先后关系数目以及课程间两两间的先后关系,程序执行后会给出符合拓扑排序的课程安排计划。
三、设计方案
1、需求分析
1) 问题描述
本次课程设计题目是:用邻接表构造图然后进行拓扑排序,输出拓扑排序序列
拓扑排序的基本思想为:
1).从有向图中选一个无前驱的顶点输出;
2).将此顶点和以它为起点的弧删除;
3). 重复1),2)直到不存在无前驱的顶点;
4). 若此时输出的顶点数小于有向图中的顶点数,则说明有向图中存在回路,否则输出的顶点的顺序即为一个拓扑序列。
2) 基于邻接表的存储结构
入度为零的顶点即为没有前驱的顶点, 我们可以附设一个存放各顶点入度的数组indegree[ ],于是有
1)找G中无前驱的顶点——查找indegree[i]为零的顶点vi;
2)删除以i为起点的所有弧——对链在顶点i后面的所有邻接顶点k,将对应的indegree[k] 减1。
为了避免重复检测入度为零的顶点,可以再设置一个辅助栈,若某一顶点的入度减为0,则将它入栈。每当输出某一入度为0的顶点时,便将它从栈中删
3) 基本要求
1) 首先是输入要排序的顶点数和弧数,都为整型,中间用分隔符隔开;再输入各顶点的值,为正型,中间用分隔符隔开;然后输入各条弧的两个顶点值,先输入弧头,再输入弧尾,中间用分隔符隔开,输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确,请重新输入,只要继续输入正确的值就行。
2) 输出的形式;
首先输出建立的邻接表,然后是最终各顶