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

东北大学信息科学与工程学院数据结构课程设计报告题目 基于紧缩图的邻接表的拓扑排序课题组长 宋振课题组成员 常玉颖 于红爽专业名称 计算机科学与技术班级 计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(); if(b0) v.NodeNum=b; break; else cout请重新输入大于0的数字endl; else cout请输入数字Node; for(i=0;iv.NodeNum;i+) string temp; cout请输入第i+1个节点的信息temp; if(temp=0) break; n.vernum=temp; v.Node.push_back(n); num=v.Node.size(); for(i=0;inum;i+) string n; cout第i+1条边所发出的弧,输入0结束该节点的输入n; if(IsDigit(n) int b=atoi(n.c_str(); if(b=0) if(b!=i+1) for(countN=v.Hi;countNv.List.size();countN+) if(v.ListcountN=b-1) Numequal=true; if(!Numequal) if(b=0) break; b-; v.List.push_back(b); m+; else cout输入重复请重新输入endl; else cout请重新输入与本节点不同的节点编号endl; else cout请输入编号小于总结点数大于0的节点编号endl; else cout请输入数字endl; for(i=0;iv.Node.size();i+) int number=0; for(int j=0;jv.List.size();j+) if(v.Listj=i) number+; indegree.push_back(number); if(TopologicalSort(v,indegree) coutendl; cout正常完成！endl; else cout该有向图有回路！endl; system(pause); / 结束前暂停 return 0;4.3.2常玉颖设计实现拓扑排序函数stack s;bool TopologicalSort(Graph v,vector indegree) int i,k,m,n=0; for(i=0;iindegree.size();i+) if(!indegreei)s.push(i); cout结果为：endl; fopen(result.txt,+w); while(!s.empty() i = s.top(); s.pop(); couti+1; cout|; coutv.Nodei.vernum; if(n!=v.Node.size()-1) cout; n+; if(i=indegree.size()-1) for(m=v.Hi;mv.List.size();m+) k=v.Listm; indegreek-; if(!indegreek) s.push(k); else for(m=v.Hi;mv.Hi+1;m+) k=v.Listm; indegreek-; if(!indegreek) s.push(k); if(nindegree.size() return false; return true;4.3.3于红爽设计实现判断输入是否为数字bool IsDigit(string &str) bool flag=true; for(unsigned int i=0 ;istr.length();i+) if(!isdigit(stri) flag=false; break; return flag;5 测试与调试5.1 个人测试（按组员分工）5.1.1宋振个人测试#include #include #include #include #include using namespace std;struct Vnode string vernum;struct Graph vectorNode; vector List; vector H; int NodeNum;int main() static int m; class Graph v; Vnode n; int num;int i,j,countN; string Node; vector indegree; cout请输入节点的总数v.NodeNum; for(i=0;iv.NodeNum;i+) string temp; cout请输入第i+1个节点的信息temp; if(temp=0) break; n.vernum=temp; v.Node.push_back(n); num=v.Node.size(); for(i=0;inum;i+) string n; cout第i+1条边所发出的弧,输入0结束该节点的输入n; int b=atoi(n.c_str(); if(b=0) break; b-; v.List.push_back(b); m+; for(i=0;iv.Node.size();i+) int number=0; for(j=0;jv.List.size();j+) if(v.Listj=i) number+; indegree.push_back(number); int q; for(q=0;qv.H.size();q+) coutv.Hqendl; for(q=0;qv.List.size();q+) coutv.Listqendl; for(q=0;qv.Node.size();q+) coutv.Nodeq.vernumendl; for(q=0;qindegree.size();q+) coutindegreeqendl; return 0;建图过程：5.1.2常玉颖个人测试#include #include #include #include #include using namespace std;struct Vnode string vernum;class Graphpublic:bool TopologicalSort(Graph v,vector indegree);vectorNode;vector List;vector H;int NodeNum;bool Graph:TopologicalSort(Graph v,vector indegree)stack s;int i,k,m,n=0;for(i=0;iindegree.size();i+)if(!indegreei)s.push(i);cout结果为：endl;while(!s.empty()i = s.top();s.pop();couti+1;cout|;coutv.Nodei.vernum;if(n!=v.Node.size()-1)cout;n+; if(i=indegree.size()-1)for(m=v.Hi;mv.List.size();m+)k=v.Listm;indegreek-;if(!indegreek) s.push(k); else for(m=v.Hi;mv.Hi+1;m+)k=v.Listm;indegreek-;if(!indegreek) s.push(k);if(nindegree.size() return false;return true;int main() static int m; class Graph v; Vnode n; int num;int i,j,countN; string Node; vector indegree; cout节点的总数：Node; int b=atoi(Node.c_str(); v.NodeNum=b; for(i=0;iv.NodeNum;i+) v.Node.push_back(n); num=v.Node.size(); for(i=0;inum;i+) string n; cout第i+1条边所发出的弧,输入0结束该节点的输入n; int b=atoi(n.c_str(); if(b=0) break;b-;v.List.push_back(b); m+; for(i=0;iv.Node.size();i+) int number=0; for(j=0;jv.List.size();j+) if(v.Listj=i) number+; indegree.push_back(number); if(v.TopologicalSort(v,indegree) cout正常完成！endl; else cout该有向图有回路！endl;return 0;通过入度进行拓扑排序，调试结果为：5.1.3于红爽个人调试输入 #include #include #include #include #include using namespace std; bool IsDigit(string &str) bool flag=true; for(unsigned int i=0 istr.length();i+) if(!isdigit(stri) flag=false; break; return flag; int main() string a=123w; string b=1; string c=apple w; if(IsDigit(a) coutyesendl; else coutnoendl; if(IsDigit(b) coutyesendl; else coutnoendl; if(IsDigit(c) coutyesendl; else coutnoendl; 判断123w，1，apple w是否为数字，结果如下：5.2 组装与系统测试将所有的函数组装好以后，进行测试，如下表5.2.1所示表5.2.1 二进制堆系统的测试记录操作名称具体操作操作结果和输出运行程序编译器运行DOS界面显示，显示制作人，同时提示输入节点数输入节点总数用户根据自己需求输入节点总数提示用户输入节点信息输入节点信息，即每个节点所代表的的事件用户根据自己需求输入节点信息提示用户输入节点发出的弧输入节点发出的弧用户根据自己需求输入节点的弧统计各个节点的入度情况进行拓扑排序无若无回路，则输出拓扑序列，显示正常完成，若有回路，则输出该有向图有回路5.3系统运行总体运行进入界面：输入节点数和节点信息输入节点的弧及输出拓扑序列6 课题总结6.1 课题评价按照课题的要求，我们组同学进行了分工，实现了其所规定的设计要求，并且有所拓展，运用课本上的知识及学习了一些本来未曾接触的知识，运用陌生的类模板实现了掌握较为熟练的功能。通过这次的实验设计后，大家各方面的能力都有所提高6.2 团队协作 由于需要学习新的知识-stl类，在完成项目过程中，我们进行了明确的分工，以确保高效，每个人对新知识的学习，之后汇总，按照所学分配任务，高效地完成了任务。6.3 下一步工作 下一步工作就是每个人根据自己的任务进行编程调试，更加透彻的理解拓扑排序，提高一种创新和应用的能力。6.4 个人设计心得（按组员分工）6.4.1宋振设计小结 紧缩图的拓扑排序，这个题目听起来还蛮简单的，因为在课上老师讲过关于拓扑排序的相关知识，就是流程的先后顺序，但是对于STL函数模板库我们却一无所知。于是便从各种搜索引擎中查找相关资料。了解的STL是什么东西，并且了解了它的运行机制之后，我们便开始具体的从中寻找我们能用到的数据结构。该实验让我收获颇丰，至少懂得了什么叫STL，还有就是关于栈的抽象数据类型里面有这么多我们可以使用的库函数，这为我们以后的编程提供的很大的帮助，提高了我们编程的效率。而且这也提醒我们，以后自己编写的函数块可以当作模板储存到自己的函数库里面，若下次程序设计有类似的算法，可以直接进行调用，这回大大提高我们编写程序的速度。 6.4.2常玉颖设计小结通过这次的数据结构课程设计实验，我对数据结构的算法有了更深的了解，也对以前学过的知识进行了巩固和提高。在这次实验过程中，虽然遇到了很多困难和新问题，但是我没有自暴自弃，一遍遍地调试程序，并主动地采取查阅课本及网上资料等方法自主学习，解决困难，把以前被动的学习过程变成了主动的探索研究的过程。在以后的学习过程中，我一定会多多实践，充分利用每一次做实验的机会，查漏补缺，培养自己编程的能力，养成严密周到、一丝不苟的编程习惯。同时，我也要认真地学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，与实践相结合。最后我想说，在学习和编程的过程中，知识和经验的积累是十分重要的，在每次的实践后，总结积累的过程是必不可少的，例如在编程调试的过程中，积累得多了，才更容易得到理想的效果，少走弯路。6.4.3于红爽设计小结 经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。这次课程设计使我收获了很多，不仅有技术上的，还有做事方面的，我学会了不骄不躁去完成好每一件事。