数据结构课程设计报告拓扑排序.docx
《数据结构课程设计报告拓扑排序.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告拓扑排序.docx（24页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告拓扑排序
课程设计任务书
学生：
专业班级：
指导教师：
工作单位：
计算机科学系
题目:
拓扑排序
初始条件：
〔1〕采用邻接表作为有向图的存储构造；
〔2〕给出所有可能的拓扑序列。
〔3〕测试用例见严蔚敏?
数据构造习题集（C语言版）?
p48题7.9图
要求完成的主要任务:
〔包括课程设计工作量及其技术要求，以及说明书撰写等具体要求〕
课程设计报告按学校规定格式用A4纸打印〔书写〕，并应包含如下容：
1.问题描述
简述题目要解决的问题是什么。
2.设计
存储构造设计、主要算法设计〔用类C/C++语言或用框图描述〕、测试用例设计；
3.调试报告
调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4.经历和体会〔包括对算法改良的设想〕
5.附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据，那么运行结果要包含这些测试数据和运行输出。
说明：
1.设计报告、程序不得相互抄袭和拷贝；假设有雷同，那么所有雷同者成绩均为0分。
2.凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。
时间安排：
1．第17周完成，验收时间由指导教师指定
2．验收地点：
实验中心
3．验收容：
可执行程序与源代码、课程设计报告书。
指导教师签名：
2013年6月14日
系主任〔或责任教师〕签名：
年月日
拓扑排序
1问题描述
2具体设计
2.1存储构造设计
2.2主要算法设计
2.2.1拓扑排序的算法总体设计
2.2.2将有向图表示为邻接表
2.2.3拓扑排序函数的设计
2.2.4顺序表的运算设计
2.3测试用例设计
3调试报告
3.1设计和编码的分析
3.2调试过程问题及解决
4经历与体会
5用户使用说明
6参考文献
7附录源代码与运行结果
1问题描述
题目：
拓扑排序
如果用有向图表示一个工程，在这种有向图中，用顶点表示活动，用有向边表示活动vi必须先于活动vj进展，这种有向图叫做顶点表示活动的网络，记作AOV网络。
对一个有向无环图G进展拓扑排序，是将G中所有顶点排成一个线性序列，使得AOV网络中的所有应存在前驱和后继的关系都能得到满足，这种构造AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序。
在AOV-网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，假设网中所有顶点都在它的拓扑有序序列中，那么该AOV-网必定不存在环。
进展拓扑排序步骤如下：
1、输入AOV网络即有向图。
令n为顶点个数。
2、从有向图上选择一个没有入度的节点并输出。
3、从网中删去该点，同时删去从该顶点发出的全部有向边。
4、重复上述2，3，直到
〔1〕、全部顶点均已输出，拓扑有序序列形成，拓扑排序完成。
〔2〕、图中还有未输出的顶点，但已跳出处理循环。
这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了，这时AOV网络中必定存在有向环。
要求：
〔1〕、采用邻接表作为有向图的存储构造；
〔2〕、给出所有可能的拓扑序列。
2具体设计
2.1存储构造设计
本问题中，我将采用三种数据构造：
邻接表，顺序表和数组。
<1>邻接表：
邻接表是图的链式存储构造，在邻接表的存储构造中，图中的每个顶点对应一个单链表。
从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和边的操作、恢复顶点和顶点前驱入度的操作。
所以，可以采用邻接表作为有向无环图的存储构造。
为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域〔into〕〞用来指示顶点当前的入度。
当into域的值为0时，说明该顶点没有前驱，可以参加到结果序列中。
而删除顶点及以它为起点的边操作时，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复那么入度域加一。
邻接表的定义如下：
typedefstructARODE{//表结点
intadjvex;//邻接点的位置
ARODE*nextarc;//指向下一个结点
}ARODE;//邻接表中的结点类型
typedefstructVEXNODE{//头结点
intvexdata;//顶点信息
intinto;//每个顶点的入度
ARODE*firstarc;//指向第一个邻接结点
}VEXNODE,AdjList[MAX];//邻接表的表头结点类型
typedefstruct{
AdjListvexs;//表头结点数组
intvexnum,arum;//顶点数、边数
}ALGraph;//邻接表类型
<2>顺序表：
在整个拓扑排序的过程中，把满足条件〔在此轮中未访问过visited[i]=0以及入度为0〕的顶点参加到顺序表的末尾，使last加1。
当一轮排序完毕后，输出顺序表中的排序。
接着，是恢复局部，每恢复一步，都要把visit[i]置0并且相应的入度加1，把这个顶点从顺序表中删除，重新参加到图中，进展下一轮的拓扑排序。
邻接表的顺序表定义如下：
typedefstruct{
VEXNODEdata[MAX];
intlast;
}Sequenlist;//顺序表类型
<2>数组：
产生所有的拓扑排序是一个递归〔回溯〕过程。
其中，定义的visited[MAX]数组是一个辅助变量，数组元素的初值为0，当第i个顶点被访问后，便置visited[i]为1.记录该顶点是否被访问过。
Visited[MAX]；
2.2主要算法设计
2.2.1拓扑排序的算法总体设计
因为这个课程设计题目是让AOV网络产生所有的拓扑排序，所以我想必然要用到递归或者回溯的思想。
考虑到要不断的对数据进展删除，恢复，所以考虑了顺序表，单链表，堆栈，发现用顺序表删除和插入都很简单，好实施，只要在表尾插入或是删除即可。
在整个过程中主要用到三局部：
一、从图中删除，添加到顺序表中；二、递归；三、把删除的顶点和边恢复到图中并从顺序表中删除。
首先，在整个图中搜索即没有被访问过而且入度为0的顶点Vi，进展拓扑排序。
在拓扑排序的函数里，首先将这个顶点参加到顺序表中，然后将这个顶点标志为被访问过，即Visited[i]=1。
把以这个顶点为起点的邻接点的入度均减1.
然后，判断顺序表的表长是否等于图的顶点数。
如果不相等的话，那么继续判断图中是否还存在满足拓扑排序条件的顶点，假设存在就再次调用拓扑排序函数。
接下来，就是使刚排序过的顶点Vi的标志恢复到原始状态0，每个以Vi为起点的邻接点的入度加1，恢复到原来的状态。
把顶点Vi从顺序表中删除。
如果，顺序表的表长等于图的顶点数，那么就输出这一种拓扑排序序列。
计数器count加1之后，就是采用递归，不断的调用拓扑排序函数，不断的恢复、删除，直到排出所有的拓扑序列。
最后，如果count大于0的话，那么就输出有count种拓扑排序。
否那么，输出此图不是AOV网，无拓扑排序序列产生。
2.2.2将有向图表示为邻接表
在产生拓扑排序的算法设计中，首先要将有向图用邻接表表示，主要流程如下：
2.2.3拓扑排序函数的设计
2.2.4顺序表的运算设计
2.3测试用例设计
图1
图2
图3
图4
3调试报告
3.1设计和编码的分析
1、邻接表实现拓扑序列shixian（）
在本函数里，首先定义一个顺序表，然后把它置空。
接着，以邻接表创立一个图，并且把它赋给图G。
接着，把全局变量数组visited[]初始化。
对于整个图中，没被访问过的而且入度为0的顶点进展拓扑排序。
如果常量count等于0的话，说明图有回路，不能拓扑排序。
否那么，在拓扑排序函数中会输出所有的拓扑排序序列。
voidshixian（）
{
SequenlistA,*L=&A;
L=（Sequenlist*）malloc（sizeof（Sequenlist））;
Setnull（L）;
ALGraphG;
G=creatGraph（）;
for（intn=1;n<=G.vexnum;n++）
{visited[n]=0;}
inti;
cout<<"该图的所有拓扑排序为：
"<for（i=1;i<=G.vexnum;i++）
if（（G.vexs[i].into==0）&&（visited[i]==0））
topusort（L,G,i）;
if（count<=0）
cout<<"您输入的图不是有向无环图，故无拓扑排序序列产生."<else
{cout<<"此图有"<count=0;}
}
2、邻接表的主要算法拓扑排序topusort（）
voidtopusort（Sequenlist*L,ALGraphG,inti）
{
intj,k;
SqLinsert（L,G.vexs[i]）;//把顶点Vi参加到顺序表中
P=G.vexs[i].firstarc;
visited[i]=1;//把排序过的点标记
while（P!
=NULL）
{
j=P->adjvex;
G.vexs[j].into--;//把以Vi为头的终止结点入度减1
P=P->nextarc;
}
for（k=1;k<=G.vexnum;k++）
if（（visited[k]==0）&&（G.vexs[k].into==0））//如果Vk在此轮中未被访问过且入度为0
topusort（L,G,k）;
if（L->last==G.vexnum）//判断顺序表中一种拓扑排序完成
{
output（L）;
cout<count++;
}
visited[i]=0;//使Vi恢复为未访问
while（P!
=NULL）
{
j=P->adjvex;
G.vexs[j].into++;//使Vj的入度恢复
P=P->nextarc;
}
SqLdelete（L,G.vexs[i]）;
}
3、顺序表函数
在这个设计中，只有顺序表的简单应用，置空，插入，删除和输出。
插入和删除都只是在表尾插入和删除。
即只要把表长加1或是减1.
Sequenlist*Setnull（Sequenlist*L）//顺序表置空
{
L->last=0;
return（L）;
}
voidSqLinsert（Sequenlist*L,VEXNODEx）//在顺序表尾插入新接点
{
L->last=L->last+1;
L->data[L->last]=x;
}
voidSqLdelete（Sequenlist*L,VEXNODEx）//删除顺序表中的最后一个节点
{
L->last=L->last-1;
}
intcount=0;
voidoutput（Sequenlist*L）//输出顺序表中的元素
{
inti;
for（i=1;i<=L->last;i++）
{
if（ilast）
cout<<"V"<data[i].vexdata<<"----->";
elsecout<<"V"<data[i].vexdata;
}
cout<}
3.2调试过程问题及解决
在调试的过程中出现了很多语法错误，如：
开场没有申明iostream头文件，导致所有的<<，>>输入输出流都是错误的，还有errorC2562:
'main':
'void'functionreturningavalue，发现main函数被我定义为了void返回类型，可是我在函数语句里又使用了return0；把main函数的返回值改成int即可，还有其他的语法错误都根据提示一一改良了。
接着，我发现无论如何输出的结果都是零种排序，于是找到了ALGraphcreatGraph（）函数的一组赋值语句，开场我是这样写的“G.vexs=al;〞后来改成
for（i=0;i{
alg.vexs[i].vexdata=al[i].vexdata;
alg.vexs[i].indegree=al[i].indegree;alg.vexs[i].firstarc=al[i].firstarc;
}
再次运行时，输出结果还是不对。
最后发现在for语句前少了alg.vexnum=n;alg.arum=e;赋值语句。
在topusort函数中以下语句使得运行结果一直为您输入的图不是有向无环图，故无拓扑排序序列产生.
for（k=1;k<=G.vexnum;k++）
if（（visited[k]==0）&&（G.vexs[k].into==0））//如果Vk在此轮中未被访问过且入度为0
{if（L->last==G.vexnum）//判断顺序表中一种拓扑排序完成
{
output（L）;
cout<count++;
}
topusort（L,G,k）;
}
改成如下代码即可：
for（k=1;k<=G.vexnum;k++）
if（（visited[k]==0）&&（G.vexs[k].into==0））//如果Vk在此轮中未被访问过且入度为0
topusort（L,G,k）;
if（L->last==G.vexnum）//判断顺序表中一种拓扑排序完成
{
output（L）;
cout<count++;
}
4经历与体会
此次课程设计为拓扑排序，利用c++语言实现的，此算法还有多发面可以改良，比方图的表示利用的是邻接表，还可以在代码中增加邻接矩阵的表示方法，使得对于两种形式表示的图都可以进展拓扑排序，还有在代码中并没有把邻接表很直观的输出给用户，如果可以编写代码把邻接表很直观的输出，会更有可读性。
在执行的过程中发现对于大量的数据，比方边比拟复杂的情况，程序执行就有可能会崩溃，说明程序的强健性还有待提高。
通过五天的课程设计，我稳固了以前学过的知识，懂得了理论与实际相结合的重要性，只有理论知识是远远不够的，理论知识是为将来的实践效劳的，理论知识很重要，实践活动更重要。
通过课程设计我看到自己实际操作能力的严重缺乏，知识理解不够深刻，掌握不够结实，编程根底薄弱，没有耐心。
在同学和相关资料的帮助下，最终完成了代码。
通过这次设计，我看到自身学习方法存在很多错误，我决心在以后的学习过程中，要多锻炼自己处理实际问题的能力，要提高独立分析问题和解决问题的能力，多动手多上机操作。
并且利用假期时间进一步稳固数据构造课程与C++语言根底，为今后的学习打下比拟坚实的根底。
5用户使用说明
运行后，根据提示，“请输入结点数〞,即输入图的顶点数目，“请入边总数数〞，即输入图的边数；接着依次输入每条边的起始点序号和终止点序号即可，输出结果就可以一目了然。
例如：
请输入顶点数：
4
请输入弧数：
4
请输入边的信息：
请输入第一条边：
12
请输入第二条边：
13
请输入第三条边：
23
请输入第四条边：
34
6参考文献：
[1].严蔚敏，吴伟民。
数据构造题集（c语言）。
清华大学，2011年11月。
[2].殷人昆。
数据构造（用面向对象方法与C++语言描述）（第2版）。
清华大学，2007年6月
7附录源代码与运行结果
源程序代码〔c++语言〕
#include
#include
#include
#include
#defineNULL0
#definemaxlen100
typedefstructARODE//表结点
{
intadjvex;//接邻点的位置
ARODE*nextarc;//指向下一个结点
}ARODE;//邻接表中的结点类型
typedefstructVEXNODE//头结点
{
intvexdata;//顶点的位置
intinto;//顶点的入度
ARODE*firstarc;//指向第一个邻接结点
}VEXNODE,AdjList[maxlen];//表头结点类型
typedefstruct
{
AdjListvexs;//表头结点数组
intvexnum,arum;//顶点数、边数
}ALGraph;//邻接表类型
typedefstruct
{
VEXNODEdata[maxlen];
intlast;
}Sequenlist;//顺序表类型
typedefstruct
{
intdata[maxlen];
intlast;
}Seqlist;//顺序表
ALGraphcreatGraph（）
{
intn,e,i,j,k;
ARODE*p;
AdjListal;
cout<cout<<"------------------------拓扑排序----------------------"<cout<<"请输入结点数:
";
cin>>n;
for（i=1;i<=n;i++）//初始化表头结点数组
{
al[i].vexdata=i;
al[i].into=0;
al[i].firstarc=NULL;
}
cout<<"请输入边总数:
";
cin>>e;
cout<<"请依次输入边的信息:
"<for（i=1;i<=e;i++）
{
cout<<"请输入第"<";
cin>>j>>k;//依次读入边的信息
p=（ARODE*）malloc（sizeof（ARODE））;
p->adjvex=k;
al[k].into++;//把终止结点的入度加1
p->nextarc=al[j].firstarc;//用头插法把p插入到链表中
al[j].firstarc=p;
}
cout<ALGraphalg;
alg.vexnum=n;
alg.arum=e;
for（i=1;i<=alg.vexnum;i++）//把头结点表头数组的值赋给邻接表表头数组
{
alg.vexs[i].vexdata=al[i].vexdata;
alg.vexs[i].into=al[i].into;
alg.vexs[i].firstarc=al[i].firstarc;
}
returnalg;
}
Sequenlist*Setnull（Sequenlist*L）//顺序表置空
{
L->last=0;
return（L）;
}
voidSqLinsert（Sequenlist*L,VEXNODEx）//在顺序表尾插入新接点
{
L->last=L->last+1;
L->data[L->last]=x;
}
voidSqLdelete（Sequenlist*L,VEXNODEx）//删除顺序表中的最后一个节点
{
L->last=L->last-1;
}
intcount=0;
voidoutput（Sequenlist*L）//输出顺序表中的元素
{
inti;
for（i=1;i<=L->last;i++）
{
if（ilast）
cout<<"V"<data[i].vexdata<<"----->";
elsecout<<"V"<data[i].vexdata;
}
cout<}
ARODE*P;
intn;
intvisited[maxlen];
voidtopusort（Sequenlist*L,ALGraphG,inti）
{
intj,k;
SqLinsert（L,G.vexs[i]）;//把顶点Vi参加到顺序表中
P=G.vexs[i].firstarc;
visited[i]=1;//把排序过的点标记
while（P!
=NULL）
{
j=P->adjvex;
G.vexs[j].into--;//把以Vi为头的终止结点入度减1
P=P->nextarc;
}
for（k=1;k<=G.vexnum;k++）
if（（visited[k]==0）&&（G.vexs[k].into==0））//如果Vk在此轮中未被访问过且入度为0
topusort（L,G,k）;
if（L->last==G.vexnum）//判断顺序表中一种拓扑排序完成
{
output（L）;
cout<count++;
}
visited[i]=0;//使Vi恢复为未访问
while（P!
=NULL）
{
j=P->adjvex;
G.vexs[j].into++;//使Vj的入度恢复
P=P->nextarc;
}
SqLdelete（L,G.vexs[i]）;
}
voidshixian（）
{
SequenlistA,*L=&A;
L=（Sequenlist*）malloc（sizeof（Sequenlist））;
Setnull（L）;
ALGraphG;
G=creatGraph（）;
for（intn=1;n<=G.vexnum;n++）
{visited[n]=0;}
inti;
cout<<"该图的所有拓扑排序为：
"<for（i=1;i<=G.vexnum;i++）
if（（G.vexs[i].into==0）&&（visited[i]==0））
topusort（L,G,i）;
if（count<=0）
cout<<"您输入的图不是有向无环图，故无拓扑排序序列产生."<else
{cout<<"此图有"<count=0;}
}
intmain（）
{
shixian（）;
return0;
}
运行结果截图如下：
本科生课程设计成绩评定表
班级：
：
学号：
序号
评分工程
总分值
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
10
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规性
10
6
设计验收
10
总得分/等级
评语：
注：
最终成绩以五级分制记。
优〔90-100分〕、良〔80-89分〕、中〔70-79分〕、
及格〔60-69分〕、60分以下为不及格
指导教师签名：
201年 月 日
升级会员 