成绩
14信计20152016（一）
数据结构课程设计
设计题目设计时间学生姓名学生学号所在班级指导教师
拓扑排序20161112016115冯佳君2014040110514信计1刘风华
徐州工程学院数学与物理科学学院一、需求分析
f1问题描述本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序列。拓扑排序的基本思想为：1从有向图中选一个无前驱的顶点输出；2将此顶点和以它为起点的弧删除；3重复1、2直到不存在无前驱的顶点；4若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。2拓扑排序有向图拓朴排序算法的基本步骤如下：1）从图中选择一个入度为0的顶点，输出该顶点；2）从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度1）；3）重复执行1）、2）直到所有顶点均被输出，拓朴排序完成或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）。3．基本要求1输入的形式和输入值的范围；首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。2输出的形式；首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。3程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。
二、概要设计
f1算法中用到的所有各种数据类型的定义在该程序中用邻接表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。2各程序模块之间的层次调用关系第一部分，vr