拓扑排序数据结构课程设计报告图形演示

简单图形输出有向图,简单演示拓扑排序的具体过程

xxxxxxx大学

课 程 设 计 报 告

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

院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师：

课程设计名称： 课程设计题目：

简单图形输出有向图,简单演示拓扑排序的具体过程

目 录

沈阳航空航天大学 ................................................................................................... I

第一章 需求分析 .................................................................................................... 1 1.1 题目的内容与要求 ...................................................................................... 1 1.2 程序实现的功能 .......................................................................................... 1 第二章 概要设计 .................................................................................................... 2 2.1 算法思想 ........................................................................................................ 2 2.2 系统功能模块图 ............................................................................................ 3 第三章 详细设计 .................................................................................................... 5 2.2 系统流程设计 ................................................................................................ 5 3.2 数据结构 ........................................................................................................ 6 3.2.1 图 ............................................................................................................. 6 3.2.2 栈 ............................................................................................................. 6 3.3 具体实现函数 .............................................................................................. 7 3.3.1 程序所需头文件及全局变量 ................................................................. 7 3.3.2 栈操作 ..................................................................................................... 7 3.3.2 有向图(DAG)邻接表存储结构(ALG)的操作 ....................................... 8 3.3.3 拓扑排序 ................................................................................................. 8 3.3.4 简单绘图函数 ......................................................................................... 9 第四章 调试分析 .................................................................................................. 10 4.1 调试数据及结果 ........................................................................................ 10 4.2 遇到的困难、错误及修改 ......................................................................... 11

简单图形输出有向图,简单演示拓扑排序的具体过程

第五章 用户使用说明与执行结果 ...................................................................... 12 参考文献 ................................................................................................................ 21

附 录（关键部分程序清单） .......................................................................... 22

简单图形输出有向图,简单演示拓扑排序的具体过程

第一章 需求分析

1.1 题目的内容与要求

本程序要求用合适方便的方式输入一个有向图，而且该有向图在程序中采用邻接表的存储结构存储，然后对该有向图进行拓扑排序。

如果输入的有向图有环存在，程序需要给出图中有环的结果，否则，程序需要输出对图进行拓扑排序的结果。

要求有向图的输入要尽量的简单、简便，能用图形形象的显示出输入的有向图，使其可以形象方便的观察。能够用动态图形形象的演示拓扑排序的具体过程。

1.2 程序实现的功能

1.简便的输入一个有向图。 2.在图形界面上显示出有向图。

3.在图形界面上形象的用动态图形演示拓扑排序的具体过程。

4.程序可以判断输入的有向图是否有环。有环时，输出有环无法排序的结果；无环时，输出拓扑排序的结果。

简单图形输出有向图,简单演示拓扑排序的具体过程

第二章 概要设计

2.1 算法思想

1采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。

2 拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。

3 拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈； 2)栈非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈； 4)重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。

5)重复2)、3)、4)直到序列中所有元素均被遍历，则该序列是拓扑序列，

否则不是拓扑序列。

4 算法的时间复杂度和空间复杂度

拓扑排序实际是对邻接表表示的图G进行遍历的过程，每次访问一个入度为零的顶点，若图G中没有回路，则需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D需访问表头向量中的所有边结点，算法的时间复杂度为O(n+e)。

简单图形输出有向图,简单演示拓扑排序的具体过程

2.2 系统功能模块结构图

本程序共分为4大模块，有向图创建模块、拓扑排序模块、拓扑排序核心算法模块、绘图模块。

图3.1.1 有向图创建模块图

图3.1.2 拓扑排序模块图

简单图形输出有向图,简单演示拓扑排序的具体过程

图3.1.3 绘图模块图

图3.1.4 拓扑排序核心算法模块图

简单图形输出有向图,简单演示拓扑排序的具体过程

第三章 详细设计

2.2

图2.1 系统流程图

否

简单图形输出有向图,简单演示拓扑排序的具体过程

3.2 数据结构

3.2.1 图

typedef char VertexType[MAX_NAME]; // 字符串类型 typedef struct ArcNode {

int adjvex;

// 该弧所指向的顶点的位置

struct ArcNode *nextarc; // 指向下一条弧的指针

}ArcNode; // 表结点 typedef struct VNode {

VertexType data; ArcNode *firstarc;

// 顶点信息

// 第一个表结点的地址,指向第一条依附该

顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];// 头结点 typedef struct {< …… 此处隐藏：5254字，全部文档内容请下载后查看。喜欢就下载吧 ……