教学计划安排检验程序正文汇编.doc

目 录 1 实验目的 1 2 问题描述 1 3 需求分析 1 4 概要设计 2 4.1设计思想 2 4.2设计流程图 2 4.3 数据库设计 3 4.4函数及功能要求 3 4.5模块调用关系 4 5详细设计 4 5.1制定课程计划伪码 4 6 测试分析 8 7 使用说明 11 8 总结 12 9 参考文献 13 10 附录 14 教学计划安排检验 （德州学院计算机系，山东德州 253023） 1 实验目的 本次数据结构课程设计的主要目的是检验和巩固专业知识，提高综合素质和能力。并在实际操作中掌握： 1．邻接表的存储结构。 2．栈的基本操作。 3．拓扑排序的思想。 通过实习，可以将我们课堂上掌握的理论知识与处理数据的业务相结合，以检验我们掌握知识的宽度、深度及对知识的综合运用能力。 2 问题描述 针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。 3 需求分析 该程序的工作是制定课程安排计划，并满足各学期课程数大致相同。此程序规定： 1、输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符。 2、程序所能达到的功能：按照用户的输入，给出每学期应学的课程。 3、测试数据：输入：学期数：５，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11v6输出：第1学期应学的课程：v1 v9 第2学期应学的课程：v2 v4 v10 v11 第3学期应学的课程：v3 v6 v12 第4学期应学的课程：v5 v8 第5学期应学的课程：v7 4 概要设计 4.1设计思想 总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。 4.2设计流程图 图1 流程图 4.3 数据库设计 ADT Graph｛ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据系统用到的抽象数据类型定义： 1．关系R： R=｛VR｝ VR=｛v,w|v,w∈V且P(v,w),v,w表示从v到w的弧， 谓词P(v,w)定义了弧v,w的意义和信息 ｝ 基本操作： （1）Status CreateDG(ALGraphG)； （2）void FindInDegree(ALGraph G)； （3）Status TopologicalSort(ALGraph G)； ｝ADT Graph 2. ADT Stack｛ 数据对象：D={ai|ai∈ElemSet，i=1,2,…,n, n≥0} 数据关系：R1=｛ai-1，ai|ai-1，ai∈D,i=2,…，n｝ 约定an端为栈顶，a1端为栈底。 基本操作： （1）Status InitStack(SqStackS)； （2）Status Push(SqStackS,SElemType e)； （3）Status Pop(SqStackS,SElemTypee)； （4）Status StackEmpty(SqStack S)； ｝ADT Stack 4.4函数及功能要求 （1）Status InitStack(SqStackS)：构造一个空栈。 （2）Status Push(SqStackS,SElemType e)：插入元素e为新的栈顶元素。 （3）Status Pop(SqStackS,SElemTypee)：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。 （4）Status StackEmpty(SqStack S)：判断栈是否为空,为空返回TRUE,否则返回FALSE。 （5）Status CreateDG(ALGraphG)：建立邻接表。 （6）void FindInDegree(ALGraph G)：求图的入度。 （7）void print(int n[],ALGraph G)：排序输出顶