数据结构课程设计_拓扑排序

1、课程设计任务书学生： 专业班级：指导教师： 工作单位：计算机科学系题目：拓扑排序 初始条件：（1 ）采用邻接表作为有向图的存储结构；（2）给出所有可能的拓扑序列。（3）测试用例见严蔚敏数据结构习题集 （C语言版）p48题7.9图要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用 A4纸打印（书写），并应包含如下容：1问题描述简述题目要解决的问题是什么。2. 设计存储结构设计、主要算法设计（用类C/C+语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4. 经验和体会（包括对算法改

2、进的设想）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.

3、2.3 拓扑排序函数的设计2.2.4 顺序表的运算设计2.3 测试用例设计3 调试报告3.1 设计和编码的分析3.2 调试过程问题及解决4 经验与体会5 用户使用说明6 参考文献7 附录源代码与运行结果1 问题描述题目：拓扑排序如果用有向图表示一个工程， 在这种有向图中， 用顶点表示活动，用有向边 <vi,vj> 表示活动 vi 必须先于活动 vj 进行，这种有向图叫做顶点表示活动的网络，记作 AOV 网络。对一个有向无环图 G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得 AOV网络中的所有应存在前驱和后继的关系都能得到满足，这种构造AOV网络全部顶点的拓扑有序序列的

4、运算叫做拓扑排序。在AOV网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，若网中 所有顶点都在它的拓扑有序序列中，则该 AOV网必定不存在环。进行拓扑排序步骤如下：1、输入AOV网络即有向图。令n为顶点个数。2、从有向图上选择一个没有入度的节点并输出。3、从网中删去该点，同时删去从该顶点发出的全部有向边。4、重复上述 2， 3，直到（1）、全部顶点均已输出，拓扑有序序列形成，拓扑排序完成。（2）、图中还有未输出的顶点， 但已跳出处理循环。 这说明图中还剩下一些顶点， 它们都有直接前驱，再也找不到没有前驱的顶点了，这时AOV网络中必定存在有向环。要求：（1）、采用邻接表作为有向图的存储

5、结构；（2）、给出所有可能的拓扑序列。2 具体设计2.1 存储结构设计本问题中，我将采用三种数据结构：邻接表，顺序表和数组。<1>邻接表：邻接表是图的链式存储结构，在邻接表的存储结构中，图中的每个顶点对应一个单链表。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检 查顶点的前驱以及作删除顶点和边的操作、恢复顶点和顶点前驱入度的操作。所以， 可以采用邻接表作为有向无环图的存储结构。为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域（ into ） 用来指示顶点当前的入度。当 into 域的值为 0 时，表明该顶点没有前驱，可以加入到 结果序列中。而删除顶点及以它为

6、起点的边操作时，可以通过把该顶点的所有邻接点 的入度域减一来完成，恢复则入度域加一。邻接表的定义如下：typedef struct ARCNODE / 表结点int adjvex; / 邻接点的位置ARCNODE *nextarc;/ 指向下一个结点ARCNODE; / 邻接表中的结点类型typedef struct VEXNODE / 头结点int vexdata; / 顶点信息int into; / 每个顶点的入度ARCNODE *firstarc; / 指向第一个邻接结点VEXNODE,AdjListMAX;/ 邻接表的表头结点类型typedef structAdjList vexs;

7、/表头结点数组int vexnum,arcnum;/ 顶点数、边数 ALGraph;/邻接表类型<2>顺序表：在整个拓扑排序的过程中，把满足条件（在此轮中未访问过 visitedi=0 以及入度为 0）的顶点加入到顺序表的末尾，使 last 加 1。当一轮排序 结束后，输出顺序表中的排序。接着，是恢复部分，每恢复一步，都要把 visiti 置 0 并且相应的入度加 1 ，把这个顶点从顺序表中删除，重新加入到图中，进行下一轮的 拓扑排序。邻接表的顺序表定义如下：typedef struct VEXNODE dataMAX;int last;Sequenlist; / 顺序表类型<

8、;2>数组：产生所有的拓扑排序是一个递归 （回溯）过程。其中，定义的 visitedMAX 数组是一个辅助变量， 数组元素的初值为 0，当第 i 个顶点被访问后， 便置 visitedi 为 1. 记录该顶点是否被访问过。VisitedMAX ；2.2 主要算法设计拓扑排序的算法总体设计因为这个课程设计题目是让 AOV网络产生所有的拓扑排序，所以我想必然要用到递 归或者回溯的思想。考虑到要不断的对数据进行删除，恢复，所以考虑了顺序表，单链表，堆栈，发 现用顺序表删除和插入都很简单，好实施，只要在表尾插入或是删除即可。在整个过程中主要用到三部分：一、从图中删除，添加到顺序表中；二、递归；

9、三、把删除的顶点和边恢复到图中并从顺序表中删除。首先，在整个图中搜索即没有被访问过而且入度为0的顶点Vi，进行拓扑排序。在拓扑排序的函数里，首先将这个顶点加入到顺序表中，然后将这个顶点标志为被访 问过，即 Visitedi=1 。把以这个顶点为起点的邻接点的入度均减 1.然后，判断顺序表的表长是否等于图的顶点数。如果不相等的话，则继续判断图 中是否还存在满足拓扑排序条件的顶点，若存在就再次调用拓扑排序函数。接下来， 就是使刚排序过的顶点 Vi 的标志恢复到原始状态 0，每个以 Vi 为起点的 邻接点的入度加 1，恢复到原来的状态。把顶点 Vi 从顺序表中删除。如果，顺序表的表长等于图的顶点数，

10、那么就输出这一种拓扑排序序列。计数器 count 加 1 之后，就是采用递归，不断的调用拓扑排序函数，不断的恢复、删除，直到 排出所有的拓扑序列。最后，如果 count 大于 0 的话，那么就输出有 count 种拓扑排序。否则，输出 此图不是AOV网，无拓扑排序序列产生。YNNYi)YNYCou nt > 0 ?N结束i<G.顶点数？Visitedj=O 且 Vj 入度为 0 ?调用函数 Topusort(G, L,j<G.顶点数?此图不是AOV网，无拓扑排序序列该图有count种排序J赋初值0用邻接表建立图G，调用G=creat_AdjlistGraph();初始化标志数

11、组，visitedi置0置空顺序表A，表长赋初值0i的值递增1i赋初值0开始j的值递增1222将有向图表示为邻接表在产生拓扑排序的算法设计中，首先要将有向图用邻接表表示，主要流程如下:结束223拓扑排序函数的设计224顺序表的运算设计开始结束2.3测试用例设计图1图33调试报告3.1设计和编码的分析1、邻接表实现拓扑序列shixia n()在本函数里，首先定义一个顺序表，然后把它置空。接着，以邻接表创建一个图，并且把它赋给图G接着，把全局变量数组visited初始化。对于整个图中，没被访问过的而且入度为0的顶点进行拓扑排序。如果常量count等于0的话，说明图有回路，不能拓扑排序。否则，在拓扑

12、排序函数中会输出所有的拓扑排序序列。void shixia n()Seque nl ist A,*L=&A;L=(Seque nlist *)malloc(sizeof(Seque nlist);Set null(L);ALGraph G;G=creatGraph();for(i nt n=1; n<=G.vex num;n+)visited n=0;int i;cout<<"该图的所有拓扑排序为："<<e ndl;for(i=1;i<=G.vex nu m;i+)if(G.vexsi.i nto=0)&&(vis

13、itedi=0)topusort(L,G,i);if(count<=0)cout<<" 您输入的图不是有向无环图，故无拓扑排序序列产生 ."<<endl; else cout<<" 此图有 "<<count<<" 种拓扑排序 nn"count=0;2、邻接表的主要算法拓扑排序 topusort() void topusort(Sequenlist *L,ALGraph G,int i) 把顶点 Vi 加入到顺序表中把排序过的点标记把以 Vi 为头的终止结点入度减 1in

14、t j,k;SqLinsert(L,G.vexsi); /P=G.vexsi.firstarc; visitedi=1; / while(P!=NULL)j=P->adjvex;G.o-; /P=P->nextarc;for(k=1;k<=G.vexnum;k+)if(visitedk=0)&&(G.o=0)/如果 Vk 在此轮中未被访问过且入度为 0判断顺序表中一种拓扑排序完成topusort(L,G,k);if(L->last=G.vexnum) / output(L); cout<<endl;coun

15、t+;使 Vi 恢复为未访问 visitedi=0; / while(P!=NULL)j=P->adjvex;使 Vj 的入度恢复G.o+; /P=P->nextarc;SqLdelete(L,G.vexsi);3、顺序表函数在这个设计中，只有顺序表的简单应用，置空，插入，删除和输出。插入和删除都只是在表尾插入 和删除。即只要把表长加 1 或是减 1.Sequenlist *Setnull(Sequenlist *L)/顺序表置空L->last=0;return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/在顺序表尾

16、插入新接点L->last=L->last+1;L->dataL->last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/删除顺序表中的最后一个节点L->last=L->last-1;int count=0;void output(Sequenlist *L) / 输出顺序表中的元素int i;for(i=1;i<=L->last;i+)if(i<L->last)cout<<"V"<<L->datai.vexdata<<"&g

17、t;"else cout<<"V"<<L->datai.vexdata;cout<<endl<<endl;3.2 调试过程问题及解决在调试的过程中出现了很多语法错误，如：开始没有申明 iostream 头文件，导致所有的 <<，>>输 入输出流都是错误的，还有 error C2562: 'main' : 'void' function returning a value，发现 main函数被我定义为了 void 返回类型，可是我在函数语句里又使用了 ret

18、urn 0 ；把 main 函数的返回值改 成 int 即可，还有其他的语法错误都根据提示一一改进了。接着，我发现无论如何输出的结果都是零种排序，于是找到了 ALGraph creatGraph() 函数的一组 赋值语句，开始我是这样写的“ G.vexs=al; ”后来改成for(i=0;i<alg.vexnum;i+)alg.vexsi.vexdata=ali.vexdata;alg.vexsi.indegree=ali.indegree; alg.vexsi.firstarc=ali.firstarc;再次运行时，输出结果还是不对。最后发现在 for 语句前少了 alg.vexnum

19、=n;alg.arcnum=e; 赋值 语句。在 topusort 函数中下列语句使得运行结果一直为您输入的图不是有向无环图，故无拓扑排序序列 产生 .for(k=1;k<=G.vexnum;k+)if(visitedk=0)&&(G.o=0)/ 如果 Vk 在此轮中未被访问过且入度为 0if(L->last=G.vexnum) / 判断顺序表中一种拓扑排序完成output(L);cout<<endl;count+;topusort(L,G,k);改成如下代码即可：for(k=1;k<=G.vexnum;k+)if(visited

20、k=0)&&(G.o=0)/ 如果 Vk 在此轮中未被访问过且入度为 0 topusort(L,G,k);if(L->last=G.vexnum) / 判断顺序表中一种拓扑排序完成output(L);cout<<endl;count+;4 经验与体会此次课程设计为拓扑排序，利用 C+语言实现的，此算法还有多发面可以改进，比如图的表示利用 的是邻接表， 还可以在代码中增加邻接矩阵的表示方法， 使得对于两种形式表示的图都可以进行拓扑排 序，还有在代码中并没有把邻接表很直观的输出给用户，如果可以编写代码把邻接表很直观的输出， 会更有可读性。 在执行

21、的过程中发现对于大量的数据， 比如边比较复杂的情况， 程序执行就有可能会崩溃， 说明程序的健壮性还有待提高。通过五天的课程设计， 我巩固了以前学过的知识， 懂得了理论与实际相结合的重要性， 只有理论知 识是远远不够的，理论知识是为将来的实践服务的，理论知识很重要，实践活动更重要。通过课程设计我看到自己实际操作能力的严重不足，知识理解不够深刻，掌握不够牢固，编程基础薄弱，没有耐心。 在同学和相关资料的帮助下，最终完成了代码。通过这次设计，我看到自身学习方法存在很多错误，我决心在以后的学习过程中， 要多锻炼自己处理实际问题的能力， 要提高独立分析问题和解决问题的能力， 多动手多上机操作。并且利用假

22、期时间进一步巩固数据结构课程与C+语言基础，为今后的学习打下比较坚实的基础。5 用户使用说明运行后，根据提示， “请输入结点数” ,即输入图的顶点数目， “请入边总数数” ，即输入图的边数；接着依次输入每条边的起始点序号和终止点序号即可，输出结果就可以一目了然。 例如：请输入顶点数： 4 请输入弧数： 4 请输入边的信息： 请输入第一条边： 1 2 请输入第二条边： 1 3 请输入第三条边： 2 3 请输入第四条边： 3 46 参考文献 ：1. 严蔚敏，吴伟民。 数据结构题集 （c 语言）。 清华大学， 2011 年 11月。2007 年 6月2.殷人昆。 数据结构（用面向对象方法与 C+语言

23、描述）（第2版）。清华大学,7 附录源代码与运行结果源程序代码（C+语言）#include <stdio.h>#inClude <string.h>#inClude <malloC.h>#inClude <iostream.h>#define NULL 0#define maxlen 100typedef struCt ARCNODE / 表结点int adjvex;/接邻点的位置ARCNODE *nextarc;/ 指向下一个结点ARCNODE; / 邻接表中的结点类型typedef struct VEXNODE /头结点int vexdata

24、;/ 顶点的位置int into; / 顶点的入度ARCNODE *firstarc;/指向第一个邻接结点VEXNODE,AdjListmaxlen;/ 表头结点类型typedef structAdjList vexs;/ 表头结点数组int vexnum,arcnum;/ 顶点数、边数ALGraph;/ 邻接表类型typedef structVEXNODE datamaxlen;int last;Sequenlist; / 顺序表类型typedef structint datamaxlen;int last;Seqlist; / 顺序表ALGraph creatGraph()int n,e,

25、i,j,k;ARCNODE *p;AdjList al;cout<<endl;cout<<" 拓扑排序 "<<endl<<endl;cout<<" 请输入结点数 : "cin>>n;for(i=1;i<=n;i+) / 初始化表头结点数组ali.vexdata=i;o=0;ali.firstarc=NULL;cout<<" 请输入边总数 : "cin>>e;cout<<" 请依次输入边的信息 :&q

26、uot;<<endl;for(i=1;i<=e;i+)cout<<" 请输入第 "<<i<<" 条边 :"cin>>j>>k; / 依次读入边的信息 p=(ARCNODE *)malloc(sizeof(ARCNODE);p->adjvex=k;o+; / 把终止结点的入度加 1p->nextarc=alj.firstarc; / 用头插法把 p 插入到链表中 alj.firstarc=p;cout<<endl;ALGraph alg;al

27、g.vexnum=n;alg.arcnum=e;for(i=1;i<=alg.vexnum;i+) / 把头结点表头数组的值赋给邻接表表头数组 alg.vexsi.vexdata=ali.vexdata;o=o;alg.vexsi.firstarc=ali.firstarc;return alg;Sequenlist *Setnull(Sequenlist *L)/顺序表置空L->last=0;return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/在顺序表尾插入新接点L->last=L-&g

28、t;last+1;L->dataL->last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/删除顺序表中的最后一个节点L->last=L->last-1;int count=0;void output(Sequenlist *L) / 输出顺序表中的元素int i;for(i=1;i<=L->last;i+)if(i<L->last)cout<<"V"<<L->datai.vexdata<<">"else cout<

29、;<"V"<<L->datai.vexdata;cout<<endl<<endl;ARCNODE *P;int n;int visitedmaxlen;void topusort(Sequenlist *L,ALGraph G,int i)int j,k;SqLinsert(L,G.vexsi); /把顶点 Vi 加入到顺序表中P=G.vexsi.firstarc;visitedi=1;/把排序过的点标记while(P!=NULL)j=P->adjvex;G.o-; /把以 Vi 为头的终止结点入度减 1P=P->nextarc;for(k