1、华北科技学院课程设计说明书 华 北 科 技 学 院 数据结构课程设计说明书 班级 计算 B121 小组成员 : 成绩 : 小组成员 : 成绩 : 小组成员 : 成绩 : 设计题目 : 教学计划编制问题 设计时间 : 2014.6.23 至 2014.6.27 指导教师 : 评 语 : 评阅教师 : _ 华北科技学院课程设计说明书 I 目 录 设计总说明 .1 第 1 章 绪论 .2 第 2 章 教学计划编制问题陈述及需求分析 .3 2.1 教学计划编制问题陈述 .3 2.2 功能需求分析 .3 第 3 章 系统设计 .4 3.1 总体设计 .4 3.2 主要模块简介 .6 第 4 章 详细设计
2、 .7 4.1 数据结构 .7 4.3 设计说明 .9 4.4 算法说明 .9 第 5 章 编码与调试 . 13 5.1 教学计划编制问题实例 . 13 5.2 程序运行结果 . 15 第 6 章 总结 . 19 参考文献 . 20 附录 源程序 . 21 华北科技学院课程设计说明书 第 1 页 共 29 页 教学计划编制问题 设计总说明 根据任务要求及对实际情况的了解，可知设计中需要定义先修关系的 AOV 网图中的顶点及弧 边的结构体，采用邻接表存储结构，利用栈作辅助结构，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题 输出每学期的课程。 整个系统从符合操作简便、界面简
3、洁、灵活、实用、安全的要求出发，完成教学计划编制问题的全过程，包括创建三个数据结构（邻接表存储结构、栈、拓扑排序）、数据的处理与计算、数据的分析、结果的输出。本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词： 教学计划编 制问题；数据结构；邻接表存储结构； 栈；拓扑排序 华北科技学院课程设计说明书 第 2 页 共 29 页 第 1 章 绪论 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练培养分析和编程
4、等实际动手能力，系统掌握数据结构这门课程的主要内容。本次课程设计的内容是 教学计划编制 问题，邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 iv 的边。栈是一种限定性的线性表，它只允许在表尾插入元素或删除元素，所以栈具有后进先出的特性。拓扑排序是由某个集合上的一个偏序得到该集合上的一个全序。而 教学计划编制 问题就是对排序问题的应用，通过这个设计事例，我们有理由相信至此以后，我们对邻接表、栈和拓扑排序的理解将会是更上一层楼。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系
5、统分析、编码设计以及调试分析，熟练掌握数据结构的选择、设计、实现以及 操作方法，为进一步的应用开发打好基础。 华北科技学院课程设计说明书 第 3 页 共 29 页 第 2 章 教学计划编制问题陈述及需求分析 2.1 教学计划编制问题陈述 大学中每个专业都有固定的教学计划，任何专业的学习年限是固定的，每年两个学期，每个专业开设的课程是确定的，而课程之间的开设时间是必须满足先修关系的。每们课可以有多门先修课，也可以没有。以本科四年为准，要求设计一个教学计划。 输入学期总数，一学期的学分上限，每门课的课程号、学分和直接先修课的课程号。一是使学生在各学期中的学习负担尽量均匀；二是 使课程尽可能地集中在
6、前几个学期中。 输出教学 计划到用户指定的文件中，计划表格格式自行设计，若无结果可报告适当的信息。 2.2 功能需求分析 本 系统主要实现对大学中 每个专业的教学计划进行设计，需要实现以下几个方面的功能： （ 1）创建存储结构：创建邻接表。 （ 2）数据的输入：学期总数，课程数，一学期的学分上限，每门课的课程号（固定占 2位的数字串）、学分和直接先修课的课程号。 （ 3）数据的处理：对输入的数据进行计算。 （ 4）结果的输出：输出各门课程所对应的学分，以及每学期各门课程的安排。 华北科技学院课程设计说明书 第 4 页 共 29 页 第 3 章 系 统设计 3.1 总体设计 允许用户指定下列两种
7、编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。采用第二种策略，使课程尽可能地集中在前几个学期中，根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体，创建图 ， 结合先修关系的 AOV 网，采用邻接链表存储和使用前插法，通过菜单显示代号所对应课程及课程的先修课程，运用拓扑排序将课程排序后并决定出每学期所学课程，最后输出图 G 的信息，将图的顶点和弧边输出。具体流程图如图 3.1 所示。 图 3.1 系统功能结构图 开始 管理员：输入用户名和密码 创建图 CreateGraph（） ：结合先修关系的 AOV网，采用邻接表存储 菜单 OUTPUT
8、()：显示课程代码、课程名称及先修课程 输出图 G 的信息 Display( )：输出图的顶点和弧边 拓扑排序 TopoSort( )：将课程排序后，编制出每学期所学的课程 结束 前插法 使课程尽可能地集中在前几个学期中 华北科技学院课程设计说明书 第 5 页 共 29 页 首先，初始化栈，构造一个空栈 S，判定这个栈是否为空栈，如果是，则进行下一步操作，否则，返回错误；接下来对各个顶点求入度，将入度为零的顶点存入数组，当所有入度为零的顶点都存入数组后，执行完毕。具体流程图如图 3.2 所示。 Y N N Y 图 3.2 拓扑排序流程图 初始化栈 InitStack(S) 对各顶点求入度，并存
9、入数组InDegreei中 （ i=0n ） 依次将入度为 0 的顶点存入栈中 推出栈顶的一个元素（入度为零的顶点号）至 i，输出 i，计数器加 1（ Count+） 对以 i 号顶点为尾弧的每个邻接点的入度减 1，并将入度减 1 后为零的顶点号压入栈中，输出 i，计数器加 1(Count+) n 个顶点全输出 Return ERROR Return OK 栈是否为空？ 华北科技学院课程设计说明书 第 6 页 共 29 页 3.2 主要模块简介 1、管理员 要进入管理员界面，首先需要输入用户名和密码。输入正确的用户名和密码后，即可进入管理员界面；若输入错误，则提示输入正确的用户名或密码。 2、
10、 主函数 本程序主要调用两个模块：主程序模块 -拓扑排序模块，调用关系简单，通过主函数主要调用 TopoSort（）输出 G 顶点的拓扑排序， Display（）输出图的邻接矩阵， CreateGraph（） 生成图，用来实现对教学计划的编制。 3、拓扑排序 利用课程之间的先修关系，运用拓扑排序进行学期课程安排（ 4 个学期），每学期都有学分上限，而每学期应学课程的学分应在学分上限内，超过学分上限后，将移到下一学期课程安排中。在满足课程先修关系和各学期课程安排的情况下，如果某门课程的学分超过该学期的学分上限，则系统返回值为 Error，提示错误，需要进行修改，必须保证该学期的各课程学分不会超过
11、学分上限 ，这时系统返回值为 OK。 华北科技学院课程设计说明书 第 7 页 共 29 页 第 4 章 详细设计 4.1 数据结构 1、图的数据结构 typedef struct ArcNode /表结点 int adjvex; /该弧所指向的顶点的位置，弧的节点结构 struct ArcNode *nextarc; /指向下一条弧的指针 ArcNode; /链表结点 typedef struct VNode /头结点 VertexType data; /顶点信息 int grades; /存储学分信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,Adj
12、ListMAX_VERTEX_NUM; typedef struct /图的数据结构 AdjList vertices; /vertices 存储课程名 int vexnum,arcnum; /图的当前顶点数和弧数 ALGraph; 2、栈的数据结构 typedef struct SqStack SElemType *base; SElemType *top; int stacksize; /分配的存储空间 SqStack; 4.2 抽象数据类型的定义 1、图的抽象数据类型定义 ADT Graph 数据对象 V： V 是具有相同特性的数据元素的集合，称为顶点集。 数据关系 R: R=VR VR
13、=|v,wV 且 P（ v,w),表示从 v 到 w 的弧， 谓词 P(v,w)定义了弧 的意义或信息 基本操作 P： CreateGraph（ &G,V,VR)； 初始条件： V 是图的顶点集， VR 是图中弧的集合。 操作结果：按 V 和 VR 的定义构造图 G。 LocateVex（ G， u） 初始条件：图 G 存在， u 和 G 中顶点有相同特征。 华北科技学院课程设计说明书 第 8 页 共 29 页 操作结果：若 G 中存在顶点 u，则返回该顶点在图中位置；否则返回其他信息。 ADT Graph 2、栈的抽象数据类型定义 ADT Stack 数据对象： D= ia | ia Ele
14、mSet,i=1,2,.,n,n 0 数据关系： R1=| 1ia , ia D,i=2,.,n 约定 na 端为栈顶， 1a 端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE,否则 FALSE。 Pop(&S,&e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 Push(&S,e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 ADT Stack 基本操作： int LocateVex(ALG
15、raph G,VertexType u) /*查找图中某个顶点位置 */ int CreateGraph(ALGraph &G) /*采用邻接表存储结构 */ void Display(ALGraph G) /*输出图 G 的信息 */ void FindInDegree(ALGraph G,int indegree) /*求顶点的入度 */ int InitStack(SqStack &S) /*栈的初始化 */ int StackEmpty(SqStack S) /*判空 */ int Pop(SqStack &S,SElemType &e) /*出栈 */ int Push(SqStack &S,SElemType e) /*入栈 */
