数据结构优秀课程设计有向图拓扑排序算法的实现.docx

数据结构课程设计设计说明书有向图拓扑排序算法实现学生姓名樊佳佳学号班级网络工程1301成绩指导老师申静数学和计算机科学学院1月4日课程设计任务书—第一学期课程设计名称：数据结构课程设计课程设计题目：图拓扑排序算法实现完成期限：自12月20日至1月3日共2周设计内容：1、设计任务（1）给出一个有向无环图，遍历全部节点；（2）能够实现对全部顶点拓扑；(3)界面友好，可操作性强。2、需求分析对系统功效及性能要求进行分析，写出需求规格说明书（可行性分析汇报、系统分层DFD图）。3、软件设计软件设计分两个阶段进行：总体设计和具体设计；总体设计：确定系统总体设计方案，完成系统模块结构图及模块功效说明；具体设计：对模块内部过程及数据结构进行设计，和进行数据库设计、用户界面设计等编写出该项目标具体设计汇报；4、具体编码编写程序，要求给出具体注释，包含：模块名、模块功效、中间过程功效、变量说明等。同时编写用户使用手册、程序模块说明等文档；5、软件测试全部测试过程要求采取综合测试策略：先作静态分析，再作动态测试。应事先制订测试计划，并要求保留全部测试用例，完成测试汇报。指导老师：申静教研室责任人：申静课程设计评阅评语：指导老师署名：年月日摘要设计了一个对有向图进行拓扑排序算法，该算法首先用邻接表结构有向图存放结构，然后对此有向图进行拓扑排序，输出拓扑排序结果。用VC++作为软件开发环境，以邻接表作为图存放结构，将图中全部顶点排成一个线性序列，输出拓扑排序结果。拓扑排序常见来确定一个依靠关系集中，事物发生次序。拓扑排序是对有向无环图顶点一个排序，它使得假如存在一条从顶点A到顶点B路径，那么在排序中B出现在A后面。关键词：邻接表；有向无环图；拓扑排序目录TOC\o"1-3"\u1课题描述PAGEREF_Toc\h12问题分析和任务定义PAGEREF_Toc\h23逻辑设计PAGEREF_Toc\h33.1程序模块功效图PAGEREF_Toc\h33.2抽象数据类型PAGEREF_Toc\h34具体设计PAGEREF_Toc\h44.1C语言定义相关数据类型PAGEREF_Toc\h44.2关键模块伪码算法PAGEREF_Toc\h44.2.1主函数伪码算法PAGEREF_Toc\h44.2.2邻接表伪码算法PAGEREF_Toc\h44.2.3拓扑排序伪码算法：PAGEREF_Toc\h54.3主函数步骤图PAGEREF_Toc\h65程序编码PAGEREF_Toc\h76程序调试和测试PAGEREF_Toc\h137结果分析PAGEREF_Toc\h168总结PAGEREF_Toc\h17参考文件PAGEREF_Toc\h181课题描述根依据设计要求利用C语言程序设计了一个对有向图进行拓扑排序算法，该算法首先用邻接表结构有向图存放结构，然后对此有向图进行拓扑排序，输出拓扑排序结果。如给定一个有向无环图图1.1所表示。在此图中，从入度为0顶点出发，删除此顶点和全部以它为尾弧；反复直至全部顶点均已输出；或当图中不存在无前驱顶点为止。23145图1.1有向无环图开发工具：VisualC++6.02问题分析和任务定义对一个有向无环图G进行拓扑排序，是将G中全部顶点排成一个线性序列，使得图中任意一对由某个集合上一个偏序得到该集合上一个全序，这个操作就称之为拓扑排序。偏序集合中仅有部分组员之间颗比较，而全序指集合中全体组员之间均可比较，而由偏序定义得到拓扑有序操作便是拓扑排序。一个表示偏序有向图可用来表示一个步骤图，经过抽象出来就是AOV-网，若从顶点i到顶点j有一条有向路径，则i是j前驱，j是i后继。若（i，j）是一条弧，则i是j直接前驱；j是i直接后继。在AOV-网中，不应该出现有向环，用拓扑排序就能够判定网中是否有环，若网中全部顶点全部在它拓扑有序序列中，则该AOV-网肯定不存在环。3逻辑设计主函数3.1程序模块功效图拓扑排序节点入度栈初始化创建邻接表有向图初始化图3.1程序模块功效图3.2抽象数据类型ADTALGraph｛数据对象：D={V|V是含有相同特征数据元素集合，即顶点集}数据关系：R={<v,w>|v,w∈V,<v,w>表示顶点v到顶点w弧}基础操作P:CreatGraphlist(ALGraph*G)初始条件：成对输入顶点集V中点。操作结果：结构图G邻接表。FindInDegree(ALGraphG,intindegree[])初始条件：图G邻接表中存在结点V。操作结果：找到图中入度为0结点。Initgraph()操作结果：完成图形初始化。TopologicalSort(ALGraphG)初始条件：结构有向图G已初始化。操作结果：对于