logo资料库

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

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.81M 资料格式：doc 举报 版权申诉
第1页 / 共36页
第2页 / 共36页
第3页 / 共36页
第4页 / 共36页
第5页 / 共36页
第6页 / 共36页
第7页 / 共36页
第8页 / 共36页
资料共36页，剩余部分请下载后查看
    第一章 需求分析
    1.1 题目的内容与要求
    1.2 程序实现的功能
    第二章 概要设计
    2.1 算法思想
    2.2 系统功能模块结构图
    第三章 详细设计
    2.2 系统流程设计
    3.2 数据结构
    3.2.1 图
    3.2.2 栈
    3.3 具体实现函数
    3.3.1 程序所需头文件及全局变量
    3.3.2 栈的操作
    3.3.2 有向图(DAG)邻接表存储结构(ALG)的操作
    3.3.3 拓扑排序
    3.3.4 简单绘图函数
    第四章 调试分析
    4.1 调试数据及结果
    4.2 遇到的困难、错误及修改
    第五章 用户使用说明与执行结果
    参考文献
    附 录（关键部分程序清单）
    xxxxxxx大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：有向图的拓扑排序 院（系）：计算机学院 专 班 学 姓 业：计算机科学与技术 级： 号： 名： 指导教师：
    xxxxxxxx 大学课程设计报告 目 录 XXXXXXXX 大学..........................................................................................................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 I
    xxxxxxxx 大学课程设计报告 第五章 用户使用说明与执行结果.......................................................................12 参考文献.................................................................................................................21 附 录（关键部分程序清单）...........................................................................22 II
    xxxxxxx 大学课程设计报告 第一章 需求分析 1.1 题目的内容与要求 本程序要求用合适方便的方式输入一个有向图，而且该有向图在程序中采用 邻接表的存储结构存储，然后对该有向图进行拓扑排序。 如果输入的有向图有环存在，程序需要给出图中有环的结果，否则，程序需 要输出对图进行拓扑排序的结果。 要求有向图的输入要尽量的简单、简便，能用图形形象的显示出输入的有向 图，使其可以形象方便的观察。能够用动态图形形象的演示拓扑排序的具体过程。 1.2 程序实现的功能 1.简便的输入一个有向图。 2.在图形界面上显示出有向图。 3.在图形界面上形象的用动态图形演示拓扑排序的具体过程。 4.程序可以判断输入的有向图是否有环。有环时，输出有环无法排序的结果； 无环时，输出拓扑排序的结果。 1
    xxxxxxx 大学课程设计报告 第二章 概要设计 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
    xxxxxxx 大学课程设计报告 2.2 系统功能模块结构图 本程序共分为 4 大模块，有向图创建模块、拓扑排序模块、拓扑排序核心算 法模块、绘图模块。 有向图创建模块 输入有向图的信息 将有向图信息存入邻 在屏幕上输出有向图 接表中 图 3.1.1 有向图创建模块图 拓扑排序模块 拓 扑 排 序 核 心 算 在 屏 幕 上 动 态 演 判断是否有环 法模块 示排序 图 3.1.2 拓扑排序模块图 3
    xxxxxxx 大学课程设计报告 绘图模块 画圆函数 画线函数 图 3.1.3 绘图模块图 拓 扑 排 序 核 心 算 法模块 栈操作 求顶点入度 0 入度出栈，其余 顶点入度减 1 图 3.1.4 拓扑排序核心算法模块图 4
    xxxxxxx 大学课程设计报告 第三章 详细设计 2.2 系统流程设计 开始 输入顶点及弧的信息 否 输入符合条件？ 是 根据输入信息建立邻接表，建立有向 图，并在图形界面上绘制出有向图。 建立栈 在邻接表中寻找入度为 0 的顶点，将其顺序入栈 进行拓扑排序，将栈顶元素出栈，并在图形界面当中演 示排序过程；将与栈顶元素邻接的顶点的入度减一 否 判断栈是否为空 是 结束 图 2.1 系统流程图 5
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料