1、 课程设计说明书 课 程 名 称: 数据结构 课 程 代 码: 题 目: 拓扑排序 年级/专业/班:10 级计算机科学与技术软件工程二班 第 1 页 目目 录录 摘 要 1 一、引 言 3 二、设计目的与任务 3 1、课程设计目的 . 3 2、课程设计的任务 . 3 三、设计方案 3 1、需求分析 . 3 2、概要设计 . 3 3、详细设计 . 7 四、调试分析与体会 . 20 五、运行结果 . 21 六、结 论 . 22 七、致 谢 . 22 八、参考文献 . 23 第 2 页 摘摘 要要 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序(Topolo
2、gical 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 arbitra
3、ry graph, makes a pair of vertices u and V, if 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 + +; 第 3 页 数据结构课程设计数据结
4、构课程设计 -拓扑排序拓扑排序 一、引引 言言 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且 已成为其他理工专业的热门选修课。 采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。 用邻接表构造图 然后进行拓扑排序，输出拓扑排序序列。 二、设计目的与任务二、设计目的与任务 1、课程设计目的、课程设计目的 1、选择合适的存储结构，建立有向无环图，并输出该图； 2、实现拓扑排序算法； 3、运用拓扑排序实现对教学计划安排的检验。 2、课程设计的任务、课程设计的任务 在 AOV 网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序 即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安 排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序 执行后会给出符合拓扑排序的课程安排计划。 三
