数据结构基于紧缩图的邻接表的拓扑排序.doc

东北大学信息科学与工程学院 数据结构课程设计报告 题目 基于紧缩图的邻接表的拓扑排序 课题组长 宋振 课题组成员 常玉颖 于红爽 专业名称 计算机科学与技术 班级 计1307 指导教师 杨雷 2015 年 1月 课程设计任务书 题目： 基于紧缩图的拓扑排序 问题描述： 紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，…，n-1的邻接顶点。向量单元h[i]存储顶点i的邻接表在向量list中的起始位置。 设计要求： 设计基于紧缩图的邻接表的拓扑排序程序。 （1）采用STL的图、栈等数据结构。 （2）实现STL的紧缩邻接表结构图类。 （3）实现紧缩图的邻接表结构的拓扑排序。 　　　　　　　　　　　　 指导教师签字： 年　　月　　日 目录 1 课题概述 1.1 课题任务 1.2 课题原理 1.3 相关知识 2 需求分析 2.1 课题调研 2.2 用户需求分析 3 方案设计 3.1 总体功能设计 3.2 数据结构设计 3.3 函数原型设计 3.4 主算法设计 3.5 用户界面设计 4 方案实现 4.1 开发环境与工具 4.2 程序设计关键技术 4.3 个人设计实现（按组员分工） 4.3.1 宋振设计实现 5 测试与调试 5.1 个人测试（按组员分工） 5.1.1 宋振测试 5.2 组装与系统测试 5.3 系统运行 6 课题总结 6.1 课题评价 6.2 团队协作 6.3 团队协作 6.4 个人设计小结（按组员分工） 6.4.1 宋振设计小结 7 附录A 课题任务分工 A-1 课题程序设计分工 A-2 课题报告分工 附录B 课题设计文档（光盘） B-1课程设计报告（电子版） B-2源程序代码（*.H，*.CPP） B-3工程与可执行文件） B-4屏幕演示录像文件（可选） 附录C 用户操作手册（可选） C.1 运行环境说明 C.2 操作说明 1课题概述 课题任务 基于紧缩图的邻接表的拓扑排序问题 【问题描述】 紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，…，n-1的邻接顶点。向量单元h[i]存储顶点i的邻接表在向量list中的起始位置。 【设计要求】 设计基于紧缩图的邻接表的拓扑排序程序。 （1）采用STL的图、栈等数据结构。 （2）实现STL的紧缩邻接表结构图类。 （3）实现紧缩图的邻接表结构的拓扑排序。 课题原理 将图的结点存入两个向量之中，List用以存放全部结点，H用以存放结点间的相互关联关系，通过输入一系列结点信息及其发出弧的信息，确定每个结点的入度，进行拓扑排序序列的输出。拓扑排序算法bool TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。该算法大体思想为： ①遍历有向图各顶点的入度，将所有入度为零的顶点入栈； ②栈非空时，输出一个顶点，并对输出的顶点数计数； ③该顶点的所有邻接点入度减一，若减一后入度为零则入栈； ④重复②、③，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。 1.3相关知识 数据结构：栈，拓扑排序。 程序语言：C++。 STL中的向量模板。 2需求分析 2.1课题调研 对一个有向无环图 G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序 2.2 用户需求分析 拓扑排序在大型工程中有广泛的应用拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。 3.1 总体功能设计 第一部分是根据输入的边的信息情况对各个点进行入度统计；第二部分是实现拓扑排序 功能设计的流程图如下： 3.2 数据结构设计 向量结构，用以存储结点顺序及关系； 图类结构，主要用以对用户输入的结点信息进行存储； 栈结构，用来根据图的入度机型拓扑排序输出。 3.3 函数原型设计 函数原型 参数说明 功能描述 bool TopologicalSort(Graph v