数据结构与算法-拓扑排序算法实现

《数据结构与算法-拓扑排序算法实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构与算法拓扑排序算法实现1课程设计目标与任务11.1课程设计目标11.2课程设计任务12分析与设计2.1拓扑排序分析错误！未定义书签。2.2原理图介绍2・1・1功能模块图错误！未定义书签。2.2.2流程图分析32.3数据结构分析42.3.1存储结构2.3.2算法描述43程序清单9134测试4.1调试过程错误！未定义书签。4.2测试结果分析135总结156参考文献161课程设计目标与任务1.1课程设计目标编写算法，建立冇向无环图，系统主要功能如下：1.能够求解该有向无环图的拓扑排序并输出出来；2.拓扑排序应能够

2、处理出现环的情况。3.顶点信息要冇几种情况可以选择。1.2课程设计任务(1)选择合适的结构存储图，在此基础上实现拓扑排序算法。(2)输出除拓扑排序数据外，述耍求输出邻接表数据。2分析与设计2.1拓扑排序分析分析算法的实现过程，选用合适的数据结构，设计适合题目要求的算法。木课设题口要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的冇向图，是一类较冇向图更一般的特殊冇向图。其功能的实现作如下分析：1•将图以合适的方式存储起来。图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接表。2.求解该有向无

3、环图的拓扑排序，并将其输岀岀来。若通过构造，建立了一个有向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的入度，将入度为0的结点提取出来，然后再统计剩下的结点的入度，再次将入度为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图的拓扑排序序列。3•输岀除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的,所以很容易将其邻接表输出出来。2.2原理图介绍2.2.1功能模块图拓扑排序算法图的存储图的遍历环图无法齐历图2.1功能模块图2.2.2流程图分析根据程序的总的步骤，拟将整

4、个流程分为三个模块。三个模块既相互独立又相互联系。具体分析如下：1.图像输入，根据题目要求，要能够建立一个有向无环图，这就耍我们在程序中去建立。考虑到输入方式要尽量方便全面，采用输入弧的方式，输入每条弧的链接的两个结点，当输入吋结朿输入。这样再输入的吋候，与相邻的两个结点的邻接矩阵对应的位置也做相应改变。2.判断图是不是冇向无环图。当图为冇向无环图时，则挑选完毕后，队列应该是满的，进行后续步骤。对于结点入队列的顺序，需要借助于可曲M数组。选取入度为零的结点，入队列，调整数组，循环进行。3.拓扑排序。此吋，所输入的弧

5、应该是有向无环图了，下面进行拓扑排序。在判断它是否为无环图的过程中已经形成了一个满队列。接下来所要做的事情就是循环出队列，按照队列同冇的顺序进行输出即可，排序完成。图2.2程序流程图2・3数据结构分析2.3.1存储结构一个无环的冇向图叫做冇向无环图，简称DAG图。本算法首先要建立一个有向五环图，即通过输入各边的数据，搭建图的结构。对于图的存储，用到邻接表，是一种链式存储结构。typedefstructNode{intdata;structNode*next;}GraphNode;GraphNodevexs[maxi

6、mum];对于用来排序的队列Qllelle,则用到了顺序存储结构的队列，用数组表示。intQueue[maximum];2.3.2算法描述1.邻接表的构造：本算法借用图的邻接矩阵构造邻接表，其形式如下：intGraph[maximum][maximum];对于相邻的结点i和j,Graph[i][j]=l,若不相邻,则Graph[i][j]=O；对于邻接表的存储结构，上面已作说明，定义一个GraphNode类型的数组变量vexs[maximum]和一个GraphNode类型的指针变量*newnodeo若两个结点i和j

7、相邻(由i指向j,Graph[i][j]=l),则在vexs[maximum]第i行添加以j为值的newnode数据,即vexs[i.卜〉next=*newnode。其屮newnode->data=j,newnode->next=NULLo直到遍历完整个邻接矩阵，邻接表随即建立完成。简单算法说明如下：for(i=0;i

8、(入队操作)及出队操作在木算法中队列主要用来，构造拓扑排序序列。由于队列具有先入先出的特点，所以，将每次选择入度为零的结点入队，这样当结点都入队的时候，再依次出队，这样，排序序列显而易见。它将图这样的非线性结构转化为队列这样的线性结构。(1)队列初始化：voidaddqueue(int*queue,intx)//入队操作{if(rear==l-l){prin