数据结构课程设计-有向图的拓扑排序

《数据结构课程设计-有向图的拓扑排序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：有向图的拓扑排序院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告此页为任务书33沈阳航空航天大学课程设计报告目录沈阳航空航天大学II第一章需求分析11.1题目的内容与要求11.2程序实现的功能1第二章概要设计22.1算法思想22.2系统功能模块图3第三章详细设计52.2系统流程设计53.2数据结构63.2.1图63.2.2栈63.3具体实现函数73.3.1程序所需头文件及全局变量73.3.2

2、栈操作73.3.2有向图(DAG)邻接表存储结构(ALG)的操作83.3.3拓扑排序83.3.4简单绘图函数9第四章调试分析104.1调试数据及结果104.2遇到的困难、错误及修改1133沈阳航空航天大学课程设计报告第五章用户使用说明与执行结果12参考文献21附录（关键部分程序清单）2233沈阳航空航天大学课程设计报告第一章需求分析1.1题目的内容与要求本程序要求用合适方便的方式输入一个有向图，而且该有向图在程序中采用邻接表的存储结构存储，然后对该有向图进行拓扑排序。如果输入的有向图有环存在，程序需要给出图中有

3、环的结果，否则，程序需要输出对图进行拓扑排序的结果。要求有向图的输入要尽量的简单、简便，能用图形形象的显示出输入的有向图，使其可以形象方便的观察。能够用动态图形形象的演示拓扑排序的具体过程。1.2程序实现的功能1.简便的输入一个有向图。2.在图形界面上显示出有向图。3.在图形界面上形象的用动态图形演示拓扑排序的具体过程。4.程序可以判断输入的有向图是否有环。有环时，输出有环无法排序的结果；无环时，输出拓扑排序的结果。33沈阳航空航天大学课程设计报告第二章概要设计2.1算法思想1采用邻接表存储结构实现有向图；有向

4、图需通过顶点数、弧数、顶点以及弧等信息建立。2拓扑排序算法voidTopologicalSort(ALGraphG)中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。3拓扑排序算法voidTopologicalSort(ALGraphG)，大体思想为：1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈；2)栈非空时，输出一个顶点，并对输出的顶点数计数；3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈；4)重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，

5、否则图中有环。5)重复2)、3)、4)直到序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。4算法的时间复杂度和空间复杂度拓扑排序实际是对邻接表表示的图G进行遍历的过程，每次访问一个入度为零的顶点，若图G中没有回路，则需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D需访问表头向量中的所有边结点，算法的时间复杂度为O(n+e)。33沈阳航空航天大学课程设计报告2.2系统功能模块结构图本程序共分为4大模块，有向图创建模块、拓扑排序模块、拓扑排序核心算法模块、绘图模块。有向图创建模块输入有向图的

6、信息将有向图信息存入邻接表中在屏幕上输出有向图图3.1.1有向图创建模块图拓扑排序模块拓扑排序核心算法模块在屏幕上动态演示排序判断是否有环图3.1.2拓扑排序模块图33沈阳航空航天大学课程设计报告绘图模块画圆函数画线函数图3.1.3绘图模块图拓扑排序核心算法模块栈操作求顶点入度0入度出栈，其余顶点入度减1图3.1.4拓扑排序核心算法模块图33沈阳航空航天大学课程设计报告第三章详细设计否开始输入顶点及弧的信息输入符合条件？根据输入信息建立邻接表，建立有向图，并在图形界面上绘制出有向图。建立栈在邻接表中寻找入度为0

7、的顶点，将其顺序入栈进行拓扑排序，将栈顶元素出栈，并在图形界面当中演示排序过程；将与栈顶元素邻接的顶点的入度减一判断栈是否为空结束是否是2.2系统流程设计图2.1系统流程图33沈阳航空航天大学课程设计报告3.2数据结构3.2.1图typedefcharVertexType[MAX_NAME];//字符串类型typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;//表结点typedefstruct

8、VNode{VertexTypedata;//顶点信息ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph3.2.