张倩组拓扑排序课程设计实验报告.docx

《张倩组拓扑排序课程设计实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东北大学信息科学与工程学院数据结构课程设计报告题目基于紧缩图的拓扑排序（B）课题组长张倩课题组成员王静怡崔贤哲专业名称物联网工程班级物1201指导教师孟凡荣2014年7月课程设计任务书题目：基于紧缩图的拓扑排序问题描述：紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，…，n-1的邻接顶点。向量单元h[i]存储顶点i的邻接表在向量list中的起始位置。设计要求：设计基于紧缩图的邻接表的拓扑排序程序。（1）采用STL的图、栈等数据结构。（2）实现STL的紧缩

2、邻接表结构图类。（3）实现紧缩图的邻接表结构的拓扑排序。　　　　　　　　　　　　指导教师签字：2014年7月17日目录1课题概述11.1课题任务11.2课题原理11.3相关知识12需求分析12.1课题调研22.2用户需求分析23方案设计23.1总体功能设计23.2数据结构设计23.3函数原型设计23.4主算法设计24方案实现34.1开发环境与工具34.2程序设计关键技术34.3个人设计实现（按组员分工）4.3.1崔贤哲设计实现34.3.2王静怡设计实现44.3.3张倩设计实现55测试与调试65.1组装与系统测

3、试65.2系统运行76课题总结76.1课题评价76.2团队协作86.3个人设计小结（按组员分工）96.3.1张倩设计小结96.3.2王静怡设计小结96.3.3崔贤哲设计小结97附录A课题任务分工10A-1课题程序设计分工10A-2课题报告分工10附录B课题设计文档（光盘）B-1课程设计报告（电子版）B-2源程序代码（*.H，*.CPP）B-3工程与可执行文件）B-4屏幕演示录像文件（可选）521课题概述1.1课题任务以STL类模板实现紧缩图邻接表的拓扑排序1.2课题原理将图的结点存入两个向量之中，List用以

4、存放全部结点，H用以存放结点间的相互关联关系，通过输入一系列结点信息及其发出弧的信息，确定每个结点的入度，进行拓扑排序序列的输出。拓扑排序算法boolTopo(ALGraphG)中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。该算法大体思想为：1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈；2)栈非空时，输出一个顶点，并对输出的顶点数计数；3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈；4)重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则

5、图中有环。1.3相关知识STL中的向量模板，通过栈实现图的拓扑排序。2需求分析2.1课题调研简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序（PartialOrder）,如果对每个x,y属于X必有xRy或yRx，则称R是集合X上的全序关系。比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。2.2用户需求分

6、析（1）用户可以通过输入每个结点和弧的信息讲结点放入图中，再通过栈实现拓扑排序序列的输出；（2）可以在拓扑排序时同时输出结点信息；（3）该程序应该有对用户错误输入的辨别纠错功能；（4）程序应具有演示功能和调试功能。（5）程序应能友好的展现结果。3方案设计3.1总体功能设计拓扑排序3.2数据结构设计向量结构，用以存储结点顺序及关系；图类结构，主要用以对用户输入的结点信息进行存储；栈结构，用来根据图的入度机型拓扑排序输出。3.3函数原型设计函数原型参数说明功能描述voidtopsort图的邻接表矩阵在函数中实现拓

7、扑排序，返回是否存在环intCreaten代表定点数，m代表边数邻接表创建3.4主算法设计在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。 （1）、查邻接表中入度为零的顶点，并进栈。 （2）、当栈为空时，进行拓扑排序。 （a）、退栈，输出栈顶元素V。 （b）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。 （3）、若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入

8、度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。4方案实现4.1开发环境与工具主要编程环境：MicrosoftVisualStudioC++6.0编程工具：C++。4.2程序设计关键技术基于紧缩图的拓扑排序：拓扑排序算法voidToport()中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现