AOV网拓扑序列生成-数据结构与算法课程设计报告

合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称AOV网拓扑序列生成学生姓名韩守飞学号0804012020专业班级08计科(2)指导教师王昆仑、张贯虹2010年6月一、问题分析和任务定义1、题目：对于给定的AOV网，要求实现所有的拓扑排序。2、要求和任务：任务：⑴通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。⑵深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。⑶在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。要求：按“课程设计教学大纲”的要求完成“数据结构与算法课程设计报告”。3、原始数据输入、输出格式：输入格式：原始数据要求输入顶点数目、边的数目、每条边的起始点和终点在邻接表中的位置。例如图1所示的菜单如下：-----欢迎进入AOV网所有拓扑序列生成的系统----\n);1--------------基于邻接表存储结构的AOV网--------------\n);2--------------基于邻接矩阵存储结构的AOV网------------\n);3-----------------退出该系统，谢谢使用----------------\n请输入你的选择：1请输入顶点数：5请输入弧数：4请输入边的信息：请输入第一条边：12请输入第二条边：14请输入第三条边：23请输入第四条边：34输出格式：输出的是所有拓扑排序的种数，和每种排序的具体情况。例如：该AOV网有5种拓扑排序序列。4、算法测试用例设计：1〉设计一个简单的AOV网，如图1：2〉设计一个有回路的图，如图2：3〉设计一个稍复杂的AOV网，如图3：图1.简单的AOV网测试用例图2。一个有回路的图图3.一个稍复杂的AOV网二、数据结构的选择和概要设计1、数据结构本问题中，我将采用三种数据结构，邻接表，顺序表，邻接矩阵和数组。1邻接表：邻接表是图的链式存储结构，在邻接表的存储结构中，图中的每个顶点对应一V1V2V3V4V5V6V7V8V1V2V3V4V5V1V2V3V4V5V0个单链表。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和弧的操作、恢复顶点和顶点前驱入度的操作。所以，可以采用邻接表作为有向无环图的存储结构。为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域（into）”用来指示顶点当前的入度。当into域的值为0时，表明该顶点没有前驱，可以加入到结果序列中。而删除顶点及以它为尾的弧的操作，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复则入度域加一。邻接表的定义如下：typedefstructARCNODE{intadjvex;//邻接点的位置ARCNODE*nextarc;//指向下一个结点}ARCNODE;//邻接表中的结点类型typedefstructVEXNODE{intvexdata;//顶点信息intinto;//每个顶点的入度ARCNODE*firstarc;//指向第一个邻接结点}VEXNODE,AdjList[MAX];//邻接表的表头结点类型typedefstruct{AdjListvexs;//表头结点数组intvexnum,arcnum;//顶点数、弧数}ALGraph;//邻接表类型2邻接矩阵：邻接矩阵是图的另一种存储结构，在邻接矩阵的存储结构中，图中的每个顶点对应一个非0元素。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和弧的操作、恢复顶点和顶点前驱入度的操作。所以，可以采用邻接矩阵作为有向无环图的存储结构。为了快速的判断顶点是否有前驱，可以定义一个数组入度域（into）”用来指示顶点当前的入度。当into域的值为0时，表明该顶点没有前驱，可以加入到结果序列中。而删除顶点及以它为尾的弧的操作，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复则入度域加一。邻接矩阵的定义如下：typedefstruct{intnum;intdata;}VERTEX;typedefstruct{intn;inte;VERTEXvexs[maxlen];intedges[maxlen][maxlen];}MGraph;3顺序表：在整个拓扑排序的过程中，把满足条件（在此轮中未访问过visited[i]=0以及入度为0）的顶点加入到顺序表的末尾，使last加1。当一轮排序结束后，输出顺序表中的排序。接着，是恢复部分，每恢复一步，都要把visit[i]置0并且相应的入度加1，把这个顶点从顺序表中删除，重新加入到图中，进行下一轮的拓扑排序。邻接表的顺序表定义如下：typedefstruct{VEXNODEdata[MAX];intlast;}Sequenlist;//顺序表类型邻接矩阵的顺序表定义如下：typedefstruct{intdata[maxlen]；intlast;}Seqlist;3数组：产生所有的拓扑排序是一个递归（回溯）过程。其中，定义的visited[MAX]数组是一个辅助变量，数组元素的初值为0，当第i个顶点被访问后，便置visited[i]为1.记录该顶点是否被访问过。Visited[MAX]；2、设计思想（以邻接表为例，邻接矩阵大致相同）因为这个课程设计题目是让AOV网产生所有的拓扑排序，所以我想必然要用到递归或者叫回溯的思想。于是，我上图书馆去找了一些有递归内容的书，好好的研究了一下。复习以前学过的一些有递归思想的例子，再回归到这个课题上，反反复复的举例子，最后发现，这个课题递归思想跟那些还是有些不一样。因为这个课题中的数据时时刻刻既要删除又要保留，因为它会反反复复的用到，不只是一次就可以结束。几天以后，大致的思想有了。但是，当时用的不是顺序表来存储要输出的顶点，一开始是用到堆栈，后来该为用链表，最后才发现，其实只要用顺序表就可以简单的解决这部分问题。用顺序表后的删除和插入都很简单，好实施，只要在表尾插入或是删除即可。主要用到三部分，一、从图中删除，添加到顺序表中；二、递归；三、把删除的顶点和边恢复到图中并从顺序表中删除。首先，在整个图中搜索即没有被访问过而且入度为0的顶点Vi，进行拓扑排序。在拓扑排序的函数里，首先将这个顶点加入到顺序表中，然后将这个顶点标志为被访问过。把以这个顶点为起点的邻接点的入度均减1.然后，判断顺序表的表长是否等于图的顶点数。如果不相等的话，则继续判断图中是否还存在满足拓扑排序条件的顶点，若存在就再次调用拓扑排序函数。接下来，就是使刚排序过的顶点Vi的标志恢复到原始状态0，每个以Vi为起点的邻接点的入度加1，恢复到原来的状态。把顶点Vi从顺序表中删除。如果，顺序表的表长等于图的顶点数，那么就输出这一种拓扑排序序列。计数器count加1.之后，就是采用递归，不断的调用拓扑排序函数，不断的恢复、删除，直到排出所有的拓扑序列。最后，如果count大于0的话，那么就输出有count中拓扑排序。否则，输出此图不是AOV网，无拓扑排序序列产生。3、AOV网产生拓扑序列流程图1以邻接表创建AOV网，creat_AdjlistGraph();2以邻接矩阵创建AOV网，creat();开始定义表头结点数组al输入顶点数n和边数e输入e条边的起点值j和终点值k将Vk的入度加一，并将结点Vk加入到链表中；边数从0到e初始化al的各项值：al[i].vexdata=i;al[i].into=0;al[i].firstarc=NULL;（i=0to图的顶点数）定义图algn=alg.vexnum顶点数；e=alg.arcnum边数i赋初值0将al[]中的值、入度、指针分别赋给图alg中数组vexs[]的.各值；i的值递增1i边数e？NY结束开始输入顶点数n和弧数e初始化各边的信息i赋初值0对邻接矩阵中的元素分别赋值i的值递增1i边数e？NY结束输入e条边的起点值j和终点值k3邻接表拓扑排序函数的流程图Topusort(G,L,I);开始插入SqLinsert(L,vexs[i])标志数visited[i]赋初值0Vi指向第一个结点指针PP!=NULL？P指向顶点VjVj的入度减1P指向链表下一结点顺序表长=顶点数？输出Output(L)计数器Count加1;K赋初值0Visited[k]==0且Vk入度为0？调用函数Topusort(L,G,k);K的值递增1k顶点数？NY3邻接表拓扑排序函数的流程图Topu(G,L,I);Vi指向的第一个结点的指针PP！=NULL？P指向顶点VjVj的入度加1P指向链表下一结点调用删除函数SqLdelete(L,vexs[i])结束YN开始插入SqLinsert(L,vexs[i])标志数visited[i]赋初值1元素是否为0P指向顶点VjVj的入度减1P指向链表下一结点顺序表长=顶点数？输出Output(L)计数器t加1;K赋初值0Visited[k]==0且Vk入度为0？调用函数Topu(L,G,k);K的值递增1k顶点数？NY4顺序表相关运算的流程图元素是否为0P指向顶点VjVj的入度加1P指向链表下一结点调用删除函数SqLdelete(L,vexs[i])结束YN4模块之间调用的流程图（以邻接表为例）开始定义顺序表A顺序表置空：setnull()表长L-last+1赋初值0插入：SqLinsert(L,vexs[i])删除：SqLdelete(L,vexs[i]);输出：output(L);表长加1即L-last+1递增1把结点X赋给顺序表最后一位L-r[L-last]表长减1；L-last+1减1I赋初值0输出ViI的值递增1i表长?结束NY开始置空顺序表A，表长赋初值0用邻接表建立图G，调用G=creat_AdjlistGraph();或者i赋初值0初始化标志数组，visited[i]置0i的值递增1iG.顶点数?J赋初值0Visited[j]=0且Vj入度为0？调用函数Topusort(G,L,i);j的值递增1jG.顶点数?Count0？此图不是AOV网，无拓扑排序序列结束YNNY该图有count种排序YNYN三、详细设计和编码1.主函数main()在main()函数里，主要实现了菜单的选择：voidmain(){intk;while(k){meun();printf(请输入你的选择:);scanf(%d,&k);switch(k){case1:shixian1();break;case2:shixian2();break;case3:return;}system(pause);system(cls);}}2.菜单函数meun()在本函数里，主要实现菜单：voidmeun(){printf(-----欢迎进入AOV网所有拓扑序列生成的系统----\n);printf(1--------------基于邻接表存储结构的AOV网--------------\n);printf(2--------------基于邻接矩阵存储结构的AOV网------------\n);printf(3-----------------退出该系统，谢谢使用----------------\n);}3.邻接表实现拓扑序列shixian1()在本函数里，首先定义一个顺序表，然后把它置空。接着，以邻接表创建一个图，并且把它赋给图G。接着，把全局变量数组visited[]初始化。对于整个图中，没被访问过的而且入度为0的顶点进行拓扑排序。如果常量count等于0的话，说明图有回路，不能拓扑排序。否则，在拓扑排序函数中会输出所有的拓扑排序序列。voidshixian1(){SequenlistA,*L=&A;L=(Sequenlist*)malloc(sizeof(Sequenlist));Setnull(L);ALGraphG;G=creatGraph();for(in