数据结构课程的设计拓扑排序.docVIP

数据结构 课程设计报告 题目：XXXXXXXXXXXXXX 院（系）：专 业： 班 级： 学 号：姓 名： 指导教师： 2013年月 （自动生成） 1介绍 2 需求分析 3 总体设计（概要设计） 4详细设计 5调试（测试） 6课程设计总结 参考文献 1 课程设计介绍 1 1.1 课程设计目的 1 1.2 课程设计内容 1 1.2 课程设计要求 1 2 需求设计 3 2.1 课设题目粗略分析 3 2.2 原理图介绍 4 2.2.1 功能模块图 4 2.2.2 流程图分析 4 3 需求分析 6 3.1 存储结构 6 3.2 算法描述 6 4.调试与分析 10 （1）调试过程 10 （2） 程序执行过程 10 参考文献 12 总结 13 附 录（关键部分程序清单） 14 1 课程设计介绍 1.1 课程设计目的 熟悉使用c语言编码程序，解决实际问题； 了解数据结构与算法的设计方法，具备初步的独立分析和设计能力。 初步掌握软件开发过程的分析能力，系统设计，程序编码，测试等基本能力。 提高综合运用的能力，运用所学理论知识与独立分析能力。 1.2 课程设计内容 编写算法，编写函数实现图的拓扑排序： 求所有顶点的入度 实现进栈与处栈 找相邻的顶点 1.2 课程设计要求 上交的成果的内容必须由以下四个部分组成，缺一不可 　　1． 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）； 　　2． 上交程序的说明文件：（保存在.中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明； 　　3． 课程设计报告：（保存在word 文档中，文件名要求 按照姓名-学号-课程设计报告起名，如文件名为张三-001-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成； 　　其中包括: 　　 　　)概要设计 　　在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。 　　）详细设计 　　各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现） 　　源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 　　）调试分析 　　测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 　　4. 课设总结： （保存在word 文档中）总结可以包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 .2 原理图介绍 2.2.1 功能模块图 图2.1 功能模块图 2.2.2 流程图分析 根据程序的总的步骤，拟将整个流程分为三个模块。三个模块既相互独立又相互联系。具体分析如下： 1. 图像输入，根据题目要求，要能够建立一个有向无环图，这就要我们在程序中去建立。考虑到输入方式要尽量方便全面，采用输入弧的方式，输入每条弧的链接的两个结点，当输入-1时结束输入。这样再输入的时候，与相邻的两个结点的邻接矩阵对应的位置也做相应改变。 2. 判断图是不是有向无环图。当图为有向无环图时，则挑选完毕后，队列应该是满的，进行后续步骤。对于结点入队列的顺序，需要借助于数组。选取入度为零的结点，入队列，调整数组，循环进行。若队列不满，则输入的图不符合要求，应该重新输入。在程序中应做适当提醒，然后自动转模块1.，进行图的重新编辑。 3. 拓扑排序。此时，所输入的弧应该是有向无环图了，下面进行拓扑排序。在判断它是否为无环图的过程中已经形成了一个满队列。接下来所要做的事情就是循环出队列，按照队列固有的顺序进行输出即可，排序完成。 图2.2 程序流程图 3 需求分析 3.1 存储结构 一个无环的有向图叫做有向无环图，简称DAG图。本算法首先要建立一个有向五环图，即通过输入各边的数据，搭建图的结构。 对于图的存储，用到邻接表，是一种链式存储结构。 typedef struct Node { int data; struct Node *next; }GraphNode; GraphNode vexs[maximum]; 对于用来排序的队列，则用到了顺序存储结构的队列，用数组表示。 int Queue[maximum]; 3.2 算法描述 1. 邻接表的构造： 本算法借用图的邻接矩阵构造邻接表，其