东北大学信息科学与工程学院数据结构课程设计报告题目 基于紧缩图的邻接表的拓扑排序课题组长 宋振课题组成员 常玉颖 于红爽专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015 年 1月课程设计任务书题目：基于紧缩图的拓扑排序问题描述：紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，n-1的邻接顶点。向量单元hi存储顶点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课题概述1.1 课题任务基于紧缩图的邻接表的拓扑排序问题【问题描述】紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，n-1的邻接顶点。向量单元hi存储顶点i的邻接表在向量list中的起始位置。【设计要求】设计基于紧缩图的邻接表的拓扑排序程序。（1）采用STL的图、栈等数据结构。（2）实现STL的紧缩邻接表结构图类。（3）实现紧缩图的邻接表结构的拓扑排序。1.2 课题原理将图的结点存入两个向量之中，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。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。用户需求如下：用户可以通过输入每个结点和弧的信息讲结点放入图中，再通过栈实现拓扑排序序列的输出；可以在拓扑排序时同时输出结点信息；该程序应该有对用户错误输入的辨别纠错功能；程序应具有演示功能和调试功能；程序应具有良好的人机接口。程序应能所见即所得的输入数据。这就如同在VS中可视化的开发图形界面一样。程序应能精确的输入数据。每一个点的坐标，每条弧的权值都应能由用户精确控制。程序应能友好的展现结果。程序应能显示制作者的信息。3方案设计3.1 总体功能设计第一部分是根据输入的边的信息情况对各个点进行入度统计；第二部分是实现拓扑排序功能设计的流程图如下：开始设辅助数组indegree记录图的各顶点的入度值，并将indegree数组各变量赋初值。输入图的顶点数、边数建立一个栈，存储图的顶点的序号用邻接表法建图，并计算出indegree数组中各变量值根据indegree数组将入度为0的顶点入栈count对输出顶点计数0=count栈不空删除栈顶元素,赋给icount+将与第i个顶点链接的各顶点入度减1输出第i个顶点值顶点入度为0顶点序号入栈countG.vexnum输出“拓扑排序成功”输出“拓扑排序不成功”结束3.2 数据结构设计向量结构，用以存储结点顺序及关系；图类结构，主要用以对用户输入的结点信息进行存储；栈结构，用来根据图的入度机型拓扑排序输出。3.3 函数原型设计函数原型参数说明功能描述bool TopologicalSort(Graph v,vector indegree)两向量存储的图v和存储入度indegree的向量在函数中实现拓扑排序，返回是否存在环bool IsDigit(string &str)字符类型的&str判断str是否为数字3.4主算法设计 在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧建立链表的一个结点，同时令k的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。 在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。（1） 查邻接表中入度为零的顶点，并进栈。（2） 当栈为空时，进行拓扑排序。 退栈，输出栈顶元素V。 在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。（3）若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。3.5 用户界面设计本程序使用控制台DOS设计:4 方案实现4.1 开发环境与工具主要编程环境：Code:Blocks ，Microsoft Visual Studio C+6.0编程工具：C+。4.2 程序设计关键技术基于紧缩图的拓扑排序：拓扑排序算法bool TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。该算法大体思想为：遍历有向图各顶点的入度，将所有入度为零的顶点入栈；栈非空时，输出一个顶点，并对输出的顶点数计数；该顶点的所有邻接点入度减一，若减一后入度为零则入栈；重复、，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。4.3 个人设计实现（按组员分工）4.3.1宋振设计实现主程序的实现，定义结构体，根据输入的信息计算节点的入度include #include #include #include #include #include using namespace std;struct Vnode string vernum;struct Graph vectorNode; vector List; /存所有节点信息 vector H; /存i的邻接节点 int NodeNum; /节点数;int main() static int m; Graph v; Vnode n; int num; int countN,i,j; string Node; vector indegree; Clock *clock=new Clock(); cout当前进行拓扑排序的时间为:*clockendl;cout-拓扑排序-endl;cout| |endl;cout| 基于紧缩图的邻接表的拓扑排序问题 |endl;cout| |endl; cout| |endl;cout| 制作人：宋振 常玉颖 于红爽 |endl;cout| |endl; cout|-请输入节点的总数-|Node; while(1) if(IsDigit(Node) int b=atoi(Node.c_str();