数据结构课程设计-拓扑排序备课讲稿

数据结构课程设计——拓扑排序精品文档课程设计任务书学生姓名： 专业班级：指导教师： 工作单位： 计算机科学系题 目: 拓扑排序初始条件：1）采用邻接表作为有向图的存储结构；2）给出所有可能的拓扑序列。（3）测试用例见严蔚敏《数据结构习题集 (C语言版)》p48题7.9图要求完成的主要任务 :（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用 A4纸打印（书写），并应包含如下内容：问题描述简述题目要解决的问题是什么。设计存储结构设计、主要算法设计（用类 C/C++语言或用框图描述）、测试用例设计；调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。经验和体会（包括对算法改进的设想）附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。说明：设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以 0分记。时间安排：1．第17周完成，验收时间由指导教师指定2．验收地点：实验中心3．验收内容：可执行程序与源代码、课程设计报告书。指导教师签名：2013年6月14日收集于网络，如有侵权请联系管理员删除精品文档系主任（或责任教师）签名： 年 月 日拓扑排序目录问题描述具体设计2.1存储结构设计2.2主要算法设计拓扑排序的算法总体设计将有向图表示为邻接表拓扑排序函数的设计顺序表的运算设计2.3测试用例设计调试报告3.1设计和编码的分析3.2调试过程问题及解决经验与体会用户使用说明参考文献收集于网络，如有侵权请联系管理员删除精品文档附录源代码与运行结果问题描述题目：拓扑排序如果用有向图表示一个工程，在这种有向图中，用顶点表示活动，用有向边<vi,vj>表示活动vi必须先于活动 vj进行，这种有向图叫做顶点表示活动的网络，记作AOV网络。对一个有向无环图 G进行拓扑排序，是将 G中所有顶点排成一个线性序列，使得AOV网络中的所有应存在前驱和后继的关系都能得到满足，这种构造 AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序。在AOV-网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，若网中所有顶点都在它的拓扑有序序列中，则该 AOV-网必定不存在环。进行拓扑排序步骤如下：1、输入AOV网络即有向图。令 n为顶点个数。2、从有向图上选择一个没有入度的节点并输出。3、从网中删去该点，同时删去从该顶点发出的全部有向边。4、重复上述2，3，直到1）、全部顶点均已输出，拓扑有序序列形成，拓扑排序完成。2）、图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了，这时AOV网络中必定存在有向环。要求：1）、采用邻接表作为有向图的存储结构；2）、给出所有可能的拓扑序列。具体设计2.1存储结构设计本问题中，我将采用三种数据结构：邻接表，顺序表和数组。<1>邻接表：邻接表是图的链式存储结构，在邻接表的存储结构中，图中的每个收集于网络，如有侵权请联系管理员删除//邻接表类型精品文档顶点对应一个单链表。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和边的操作、恢复顶点和顶点前驱入度的操作。所以，可以采用邻接表作为有向无环图的存储结构。为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域into）”用来指示顶点当前的入度。当into域的值为0时，表明该顶点没有前驱，可以加入到结果序列中。而删除顶点及以它为起点的边操作时，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复则入度域加一。邻接表的定义如下：typedefstructARCNODE{ //表结点intadjvex; //邻接点的位置ARCNODE*nextarc;//指向下一个结点}ARCNODE; //邻接表中的结点类型typedefstructVEXNODE{ //头结点intvexdata; //顶点信息intinto; //每个顶点的入度ARCNODE*firstarc;//指向第一个邻接结点}VEXNODE,AdjList[MAX];//邻接表的表头结点类型typedefstruct{AdjListvexs; //表头结点数组intvexnum,arcnum;//顶点数、边数}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主要算法设计拓扑排序的算法总体设计因为这个课程设计题目是让AOV网络产生所有的拓扑排序，所以我想必然要用到递归或者回溯的思想。考虑到要不断的对数据进行删除，恢复，所以考虑了顺序表，单链表，堆栈，发现用顺序表删除和插入都很简单，好实施，只要在表尾插入或是删除即可。在整个过程中主要用到三部分：一、从图中删除，添加到顺序表中；二、递归；三、把删除的顶点和边恢复到图中并从顺序表中删除。首先，在整个图中搜索即没有被访问过而且入度为 0的顶点Vi，进行拓扑排序。在拓扑排序的函数里，首先将这个顶点加入到顺序表中，然后将这个顶点标志为被访问过，即Visited[i]=1。把以这个顶点为起点的邻接点的入度均减1.然后，判断顺序表的表长是否等于图的顶点数。如果不相等的话，则继续判断图中是否还存在满足拓扑排序条件的顶点，若存在就再次调用拓扑排序函数。接下来，就是使刚排序过的顶点Vi的标志恢复到原始状态0，每个以Vi为起点的邻接点的入度加1，恢复到原来的状态。把顶点Vi从顺序表中删除。如果，顺序表的表长等于图的顶点数，那么就输出这一种拓扑排序序列。计数器count加1之后，就是采用递归，不断的调用拓扑排序函数，不断的恢复、删除，直到排出所有的拓扑序列。最后，如果 count大于0的话，那么就输出有 count种拓扑排序。否则，输出此图不是AOV网，无拓扑排序序列产生。收集于网络，如有侵权请联系管理员删除精品文档开始置空顺序表A，表长赋初值用邻接表建立图 G，调用i赋初值0初始化标志数组，visited[i]置0i的值递增1Yi<G.顶点NJ赋初值0NVisited[j]=0 且Vj入度为0？Y调用函数Topusort(G,L,i);j的值递增1Yj<G.顶点数？NYCount>0？N此图不是AOV网，无拓扑排序该图有count种排序结束收集于网络，如有侵权请联系管理员删除精品文档将有向图表示为邻接表在产生拓扑排序的算法设计中，首先要将有向图用邻接表表示，主要流程如下：开始定义表头结点数组 al输入顶点数n和边数e初始化al的各项值：al[i].vexdata=i;al[i].into=0;al[i].firstarc=NULL;（i=0to图的顶点数）输入e条边的起点值j和终点值将Vk的入度加一，并将结点Vk加入到链表中；边数从0到e定义图algn=alg.vexnum顶点数；e=alg.arcnum边数i赋初值0将al[]中的值、入度、指针分别赋给图alg中数组vexs[]的.各的值递增1Yi<结点数N结束收集于网络，如有侵权请联系管理员删除精品文档拓扑排序函数的设计开始插入SqLinsert(L,vexs[i])标志数visited[i]赋初值Vi指向第一个结点指针 PP!=NULL？YNP指向顶点Vj顺序表长=顶点Vj的入度减1数？P指向链表下一结点输出Output(L)计数器Count加K赋初值0Visited[k]==0且Vk入度为0？调用函数Topusort(L,G,k);K的值递增1Yk<顶点数？N收集于网络，如有侵权请联系管理员删除精品文档Vi指向的第一个结点的指针 PYP！=NULL？N P指向顶点VjVj的入度加1P指向链表下一结点调用删除函数SqLdelete(L,vexs[i])结束顺序表的运算设计收集于网络，如有侵权请联系管理员删除精品文档开始定义顺序表A顺序表置空：setnull()表长L->last+1赋初值0插入：SqLinsert(L,vexs[i])

输出：output(L);

删 除：SqLdelete(L,vexs[i表长加1

I赋初值0即L->last+1输出Vi把结点X赋给顺序表I的值递增1最后一位L->r[L-Yi<表长?N结束

表长减1；L->last-1收集于网络，如有侵权请联系管理员删除精品文档2.3测试用例设计21 43图121 43图231 46725图3收集于网络，如有侵权请联系管理员删除1

精品文档32 456图4调试报告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<<"该图的所有拓扑排序为： "<<endl;for(i=1;i<=G.vexnum;i++)if((G.vexs[i].into==0)&&(visited[i]==0))收集于网络，如有侵权请联系管理员删除精品文档topusort(L,G,i);if(count<=0)cout<<"您输入的图不是有向无环图，故无拓扑排序序列产生 ."<<endl;else{cout<<"此图有"<<count<<"种拓扑排序\n\n";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为头的终止结点入度减 1P=P->nextarc;}for(k=1;k<=G.vexnum;k++)if((visited[k]==0)&&(G.vexs[k].into==0))// 如果Vk在此轮中未被访问过且入度为 0topusort(L,G,k);if(L->last==G.vexnum) //判断顺序表中一种拓扑排序完成{output(L);cout<<endl;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(i<L->last)收集于网络，如有侵权请联系管理员删除精品文档cout<<"V"<<L->data[i].vexdata<<"----->";elsecout<<"V"<<L->data[i].vexdata;}cout<<endl<<endl;}3.2调试过程问题及解决在调试的过程中出现了很多语法错误，如：开始没有申明 iostream头文件，导致所有的<<，>>输入输出流都是错误的，还有errorC2562:'main':'void'functionreturningavalue，发现main函数被我定义为了void返回类型，可是我在函数语句里又使用了return0；把main函数的返回值改成int即可，还有其他的语法错误都根据提示一一改进了。接着，我发现无论如何输出的结果都是零种排序，于是找到了 ALGraphcreatGraph()函数的一组赋值语句，开始我是这样写的“G.vexs=al;”后来改成for(i=0;i<alg.vexnum;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.arcnum=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<<endl;count++;}收集于网络，如有侵权请联系管理员删除精品文档topusort(L,G,k);}改成如下代码即可：for(k=1;k<=G.vexnum;k++)if((visited[k]==0)&&(G.vexs[k].into==0))// 如果Vk在此轮中未被访问过且入度为 0topusort(L,G,k);if(L->last==G.vexnum) //判断顺序表中一种拓扑排序完成{output(L);cout<<endl;count++;}经验与体会此次课程设计为拓扑排序，利用c++语言实现的，此算法还有多发面可以改进，比如图的表示利用的是邻接表，还可以在代码中增加邻接矩阵的表示方法，使得对于两种形式表示的图都可以进行拓扑排序，还有在代码中并没有把邻接表很直观的输出给用户，如果可以编写代码把邻接表很直观的输出，会更有可读性。在执行的过程中发现对于大量的数据，比如边比较复杂的情况，程序执行就有可能会崩溃，说明程序的健壮性还有待提高。通过五天的课程设计，我巩固了以前学过的知识，懂得了理论与实际相结合的重要性，只有理论知识是远远不够的，理论知识是为将来的实践服务的，理论知识很重要，实践活动更重要。通过课程设计我看到自己实际操作能力的严重不足，知识理解不够深刻，掌握不够牢固，编程基础薄弱，没有耐心。在同学和相关资料的帮助下，最终完成了代码。通过这次设计，我看到自身学习方法存在很多错误，我决心在以后的学习过程中，要多锻炼自己处理实际问题的能力，要提高独立分析问题和解决问题的能力，多动手多上机操作。并且利用假期时间进一步巩固数据结构课程与C++语言基础，为今后的学习打下比较坚实的基础。收集于网络，如有侵权请联系管理员删除精品文档用户使用说明运行后，根据提示，“请输入结点数”,即输入图的顶点数目，“请入边总数数”，即输入图的边数；接着依次输入每条边的起始点序号和终止点序号即可，输出结果就可以一目了然。例如：请输入顶点数：4请输入弧数：4请输入边的信息：请输入第一条边：12请输入第二条边：13请输入第三条边：23请输入第四条边：346参考文献：严蔚敏，吴伟民。数据结构题集(c语言)。清华大学出版社，2011年11月。殷人昆。数据结构(用面向对象方法与C++语言描述)(第2版)。清华大学出版社，2007年6月附录源代码与运行结果源程序代码（c++语言）#include<stdio.h>#include<string.h>#include<malloc.h>#include<iostream.h>#defineNULL0收集于网络，如有侵权请联系管理员删除精品文档#definemaxlen100typedefstructARCNODE//表结点{intadjvex;//接邻点的位置ARCNODE*nextarc;//指向下一个结点}ARCNODE; //邻接表中的结点类型typedefstructVEXNODE//头结点{intvexdata;//顶点的位置intinto;//顶点的入度ARCNODE*firstarc;//指向第一个邻接结点}VEXNODE,AdjList[maxlen];// 表头结点类型typedefstruct{AdjListvexs;//表头结点数组intvexnum,arcnum;//顶点数、边数}ALGraph;//邻接表类型typedefstruct{VEXNODEdata[maxlen];intlast;}Sequenlist; //顺序表类型typedefstruct{intdata[maxlen];intlast;}Seqlist;//顺序表收集于网络，如有侵权请联系管理员删除精品文档ALGraphcreatGraph(){intn,e,i,j,k;ARCNODE*p;AdjListal;cout<<endl;cout<<"------------------------拓扑排序----------------------"<<endl<<endl;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<<"请依次输入边的信息:"<<endl;for(i=1;i<=e;i++){cout<<"请输入第"<<i<<"条边:";cin>>j>>k; //依次读入边的信息p=(ARCNODE*)malloc(sizeof(ARCNODE));p->adjvex=k;al[k].into++; //把终止结点的入度加 1p->nextarc=al[j].firstarc; //用头插法把p插入到链表中al[j].firstarc=p;}cout<<endl;ALGraphalg;alg.vexnum=n;收集于网络，如有侵权请联系管理员删除精品文档alg.arcnum=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(i<L->last)cout<<"V"<<L->data[i].vexdata<<"----->";elsecout<<"V"<<L->data[i].vexdata;收集于网络，如有侵权请联系管理员删除精品文档}cout<<endl<<endl;}ARCNODE*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->adjv