数据结构课程设计-拓扑排序

《数据结构课程设计-拓扑排序》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湖南人文科技学院湖南人文科技学院计算机科学技术系课程设计说明书课程名称:数据结构课程代码:题目:拓扑排序年级/专业/班:10级计算机科学与技术软件工程二班学生姓名:刘玄郑晴李坤洪毅唐宏峰曾齐学号:104362011043620210436203104362041043620510436234指导教师:易叶青开题时间:2012年3月8日完成时间:2012年4月8日第24页湖南人文科技学院目录摘要2一、引言3二、设计目的与任务31、课程设计目的32、课程设计的任务3三、设计方案31、需求分析32、概要设计43、详细设

2、计5四、调试分析与体会26五、运行结果27六、结论27七、致谢28八、参考文献28第24页湖南人文科技学院摘要对一个有向无环图(DirectedAcyclicGraph简称DAG)G进行拓扑排序(TopologicalSort),是将G中所有顶点排成一个线性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序(TopolgicalOrder)的序列,简称拓扑序列。关键词：拓扑；数据结构；C；C++；AbstractForadirectedac

3、yclicgraph(DirectedAcyclicGraphDAG)Gtopologicalsort(TopologicalSort),Gisallverticesintoalinearsequenceofarbitrarygraph,makesapairofverticesuandV,ifE(G),uinlinearoccurinthesequencebeforev.Usuallysuchlinearsequencescalledmeetthetopologicalorder(TopolgicalOr

4、der)sequences,referredtoasthetopologicalsequence.Keywords:Topology;datastructure;C;C++;第24页湖南人文科技学院《数据结构》课程设计----拓扑排序一、引言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。用邻接表构造图然后进行拓扑排序，输出拓扑排序序列。二、设计目的与任务1、课程设计目的1、

5、选择合适的存储结构，建立有向无环图，并输出该图；2、实现拓扑排序算法；3、运用拓扑排序实现对教学计划安排的检验。2、课程设计的任务在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。三、设计方案1、需求分析1)问题描述本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序

6、列拓扑排序的基本思想为：1).从有向图中选一个无前驱的顶点输出；2).将此顶点和以它为起点的弧删除；3).重复1),2)直到不存在无前驱的顶点；4).若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。2)基于邻接表的存储结构入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放各顶点入度的数组indegree[]，于是有1）找G中无前驱的顶点——查找indegree[i]为零的顶点vi；第24页湖南人文科技学院2）删除以i为起点的所有弧——对链在顶点i后面的所有邻

7、接顶点k，将对应的indegree[k]减1。为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一入度为0的顶点时，便将它从栈中删3)基本要求1)首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。2)输出的形式；首先输出建立的邻接表，然后是

8、最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。3)程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。2、概要设计1)抽象数据类型