毕业设计-数据结构基于紧缩图的邻接表的拓扑排序.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课题概述
1.1 课题任务
基于紧缩图的邻接表的拓扑排序问题
【问题描述】
紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，…，n-1的邻接顶点。向量单元h[i]存储顶点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
栈不空
删除栈顶元素,赋给i
count++
将与第i个顶点链接的各顶点入度减1
输出第i个顶点值

顶点入度为0
顶点序号入栈
count<G.vexnum
输出“拓扑排序成功”
输出“拓扑排序不成功”
结束

3.2 数据结构设计
向量结构，用以存储结点顺序及关系；
图类结构，主要用以对用户输入的结点信息进行存储；
栈结构，用来根据图的入度机型拓扑排序输出。
3.3 函数原型设计
函数原型
参数说明
功能描述
bool TopologicalSort(Graph v,vector <int> indegree)

两向量存储的图v和存储入度indegree的向量
在函数中实现拓扑排序，返回是否存在环
bool IsDigit(string &str)

字符类型的&str
判断str是否为数字

3.4主算法设计
在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧<J,K>建立链表的一个结点，同时令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 <iostream>
#include <vector>
#include <stack>
#include <string>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

struct Vnode
{
string vernum;
};
struct Graph
{
vector<Vnode>Node;
vector<int> List; //存所有节点信息
vector<int> H; //存i的邻接节点
int NodeNum; //节点数
};

int main()
{
static int m;
Graph v;
Vnode n;
int num;
int countN,i,j;
string Node;
vector <int> indegree;
Clock *clock=new Clock();
cout<<"当前进行拓扑排序的时间为:"<<*clock<<endl;
cout<<"------------------------------拓扑排序---------------------------"<<endl;
cout<<"| |"<<endl;
cout<<"| 基于紧缩图的邻接表的拓扑排序问题 |"<<endl;
cout<<"| |"<<endl;
cout<<"| |"<<endl;
cout<<"| 制作人：宋振 常玉颖 于红爽 |"<<endl;
cout<<"| |"<<endl;
cout<<"|-------------------------请输入节点的总数----------------------|"<<endl;
cin>>Node;
while(1)
{
if(IsDigit(Node))
{
int b=atoi(Node.c_str());
if(b>0)
{
v.NodeNum=b;
break;
}
else
cout<<"请重新输入大于0的数字"<<endl;
}
else cout<<"请输入数字"<<endl;
cin>>Node;
}
for(i=0;i<v.NodeNum;i++)
{
string temp;
cout<<"~~~~~~~~~~~~~~~~请输入第"<<i+1<<"个节点的信息~~~~~~~~~~~~"<<endl;
cin>>temp;
if(temp=="0") break;
n.vernum=temp;
v.Node.push_back(n);
}
num=v.Node.size();
for(i=0;i<num;i++)
{

string n;
cout<<"第"<<i+1<<"条边所发出的弧,输入0结束该节点的输入"<<endl;
v.H.push_back(m);
for(j=0;;j++)
{
bool Numequal=false;
cin>>n;
if(IsDigit(n))
{
int b=atoi(n.c_str());
if(b<=v.Node.size()&&b>=0)
{
if(b!=i+1)
{
for(countN=v.H[i];countN<v.List.size();countN++)
if(v.List[countN]==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;i<v.Node.size();i++)
{
int number=0;
for(int j=0;j<v.List.size();j++)
if(v.List[j]==i)
number++;
indegree.push_back(number);
}

if(TopologicalSort(v,indegree))
{
cout<<endl;
cout<<"正常完成！"<<endl;
}

else cout<<"该有向图有回路！"<<endl;
system("pause"); // 结束前暂停
return 0;
}

4.3.2常玉颖设计实现
拓扑排序函数

stack <int> s;
bool TopologicalSort(Graph v,vector <int> indegree)
{
int i,k,m,n=0;
for(i=0;i<indegree.size();i++)
{
if(!indegree[i]){s.push(i);}
}
cout<<"结果为："<<endl;
fopen("result.txt","+w");
while(!s.empty())
{
i = s.top();
s.pop();
cout<<i+1;
cout<<"||";
cout<<v.Node[i].vernum;
if(n!=v.Node.size()-1)
cout<<"-->";
n++;
if(i==indegree.size()-1)
for(m=v.H[i];m<v.List.size();m++)
{
k=v.List[m];
indegree[k]--;
if(!indegree[k]) s.push(k);
}
else for(m=v.H[i];m<v.H[i+1];m++)
{
k=v.List[m];
indegree[k]--;
if(!indegree[k]) s.push(k);
}
}
if(n<indegree.size()) return false;
return true;
}
4.3.3于红爽设计实现
判断输入是否为数字

bool IsDigit(string &str)
{
bool flag=true;
for(unsigned int i=0 ;i<str.length();i++)
{
if(!isdigit(str[i]))
{
flag=false;
break;
}
}
return flag;
}
5 测试与调试
5.1 个人测试（按组员分工）
5.1.1宋振个人测试
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
struct Vnode
{
string vernum;
};
struct Graph
{
vector<Vnode>Node;
vector<int> List;
vector<int> H;
int NodeNum;
};
int main()
{
static int m;
class Graph v;
Vnode n;
int num;
int i,j,countN;
string Node;
vector <int> indegree;
cout<<"请输入节点的总数"<<endl;
cin>>v.NodeNum;
for(i=0;i<v.NodeNum;i++)
{
string temp;
cout<<"~~~~~~~~~~~~~~~~请输入第"<<i+1<<"个节点的信息~~~~~~~~~~~~"<<endl;
cin>>temp;
if(temp=="0") break;
n.vernum=temp;
v.Node.push_back(n);
}
num=v.Node.size();
for(i=0;i<num;i++)
{

string n;
cout<<"第"<<i+1<<"条边所发出的弧,输入0结束该节点的输入"<<endl;
v.H.push_back(m);
for(j=0;;j++)
{

cin>>n;
int b=atoi(n.c_str());
if(b==0)
{
break;
}
b--;
v.List.push_back(b);
m++;

}
}
for(i=0;i<v.Node.size();i++)
{
int number=0;
for(j=0;j<v.List.size();j++)
if(v.List[j]==i)
number++;
indegree.push_back(number);
}
int q;
for(q=0;q<v.H.size();q++)
{
cout<<v.H[q]<<endl;
}
for(q=0;q<v.List.size();q++)
{
cout<<v.List[q]<<endl;
}
for(q=0;q<v.Node.size();q++)
{
cout<<v.Node[q].vernum<<endl;
}
for(q=0;q<indegree.size();q++)
{
cout<<indegree[q]<<endl;
}
return 0;
}
建图过程：

5.1.2常玉颖个人测试
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <stdlib.h>
using namespace std;
struct Vnode
{
string vernum;
};
class Graph
{
public:
bool TopologicalSort(Graph v,vector <int> indegree);
vector<Vnode>Node;
vector<int> List;
vector<int> H;
int NodeNum;
};
bool Graph::TopologicalSort(Graph v,vector <int> indegree)
{
stack <int> s;
int i,k,m,n=0;
for(i=0;i<indegree.size();i++)
{
if(!indegree[i]){s.push(i);}
}
cout<<"结果为："<<endl;
while(!s.empty())
{
i = s.top();
s.pop();
cout<<i+1;
cout<<"||";
cout<<v.Node[i].vernum;

if(n!=v.Node.size()-1)
cout<<"-->";
n++;
if(i==indegree.size()-1)
for(m=v.H[i];m<v.List.size();m++)
{
k=v.List[m];
indegree[k]--;
if(!indegree[k]) s.push(k);
}
else for(m=v.H[i];m<v.H[i+1];m++)
{
k=v.List[m];
indegree[k]--;
if(!indegree[k]) s.push(k);
}
}
if(n<indegree.size()) return false;
return true;
}
int main()
{
static int m;
class Graph v;
Vnode n;
int num;
int i,j,countN;
string Node;
vector <int> indegree;
cout<<"节点的总数："<<endl;
cin>>Node;
int b=atoi(Node.c_str());
v.NodeNum=b;

for(i=0;i<v.NodeNum;i++)
v.Node.push_back(n);
num=v.Node.size();
for(i=0;i<num;i++)
{

string n;
cout<<"第"<<i+1<<"条边所发出的弧,输入0结束该节点的输入"<<endl;
v.H.push_back(m);
for(j=0;;j++)
{
cin>>n;
int b=atoi(n.c_str());
if(b==0)
{
break;
}
b--;
v.List.push_back(b);
m++;
}
}
for(i=0;i<v.Node.size();i++)
{
int number=0;
for(j=0;j<v.List.size();j++)
if(v.List[j]==i)
number++;
indegree.push_back(number);
}

if(v.TopologicalSort(v,indegree))
{
cout<<"正常完成！"<<endl;
}

else cout<<"该有向图有回路！"<<endl;
return 0;
}
通过入度进行拓扑排序，调试结果为：

5.1.3于红爽个人调试

输入
#include <string>
#include <cctype>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
bool IsDigit(string &str)
{
bool flag=true;
for(unsigned int i=0 i<str.length();i++)
{
if(!isdigit(str[i]))
{
flag=false;
break;
}
}
return flag;
}
int main()
{
string a="123w";
string b="1";
string c="apple w";
if(IsDigit(a))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
if(IsDigit(b))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
if(IsDigit(c))
cout<<"yes"<<endl;
else cout<<"no"<<endl; } 判断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于红爽设计小结
经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。这次课程设计使我收获了很多，不仅有技术上的，还有做事方面的，我学会了不骄不躁去完成好每一件事。 这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。
通过这次的程序设计，我也发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣，以前偷工减料的学习也不可能一下子写出一个程序出来，于是我就认真看老师写的程序，发现我们看懂了一个程序其实不难，难的是对于一个程序的思想的理解，我们要掌握一个算法，不仅仅限于读懂，主要的是要理解老师的思路，学习老师的解决问题的方法。

7 附录A 课题任务分工
课题程序设计分工
学号
姓名
程序设计函数原型、类
功能说明
20133986

宋振
main（）函数
图的结构
进行图的定义和输入向量
20134001

常玉颖

bool TopologicalSort(Graph v,vector <int> indegree)

拓扑排序算法
2013400