《《教学计划编制问题》数据结构课程设计操作说明书》由会员分享，可在线阅读，更多相关《《教学计划编制问题》数据结构课程设计操作说明书（31页珍藏版）》请在金锄头文库上搜索。
1、华北科技学院课程设计说明书 华 北 科 技 学 院 数据结构课程设计说明书 班级 计算 B121 小组成员 成绩 小组成员 成绩 小组成员 成绩 设计题目 教学计划编制问题 设计时间 2014 6 23 至 2014 6 27 指导教师 评 语 评阅教师 华北科技学院课程设计说明书 目目 录录 设计总说明 1 第 1 章 绪论 2 第 2 章 教学计划编制问题陈述及需求分析 3 2 1 教学计划编制问题陈述 3 2 2 功能需求分析 3 第 3 章 系统设计 4 3 1 总体设计 4 3 2 主要模块简介 6 第 4 章 详细设计 7 4 1 数据结构 7 4 3 设计说明 9 4 4 算法说
2、明 9 第 5 章 编码与调试 13 5 1 教学计划编制问题实例 13 5 2 程序运行结果 15 第 6 章 总结 19 参考文献 20 附录 源程序 21 华北科技学院课程设计说明书 第 0 页 共 29 页 教学计划编制问题教学计划编制问题 设计总说明设计总说明 根据任务要求及对实际情况的了解 可知设计中需要定义先修关系的 AOV 网图中的顶 点及弧边的结构体 采用邻接表存储结构 利用栈作辅助结构 在运行结果中将图的信息显 示出来 利用先修关系将课程排序 最后解决问题 输出每学期的课程 整个系统从符合 操作简便 界面简洁 灵活 实用 安全的要求出发 完成教学计划编制问题的全过程 包 括
3、创建三个数据结构 邻接表存储结构 栈 拓扑排序 数据的处理与计算 数据的分析 结果的输出 本课程主要介绍了本课题的开发背景 所要完成的功能和开发的过程 重点说 明了系统的设计思路 总体设计 各个功能模块的设计与实现方法 关键词 关键词 教学计划编制问题 数据结构 邻接表存储结构 栈 拓扑排序 华北科技学院课程设计说明书 第 1 页 共 29 页 第第 1 1 章章 绪论绪论 数据结构是研究数据元素之间的逻辑关系的一门课程 以及数据元素及其关系在计算机 中的存储表示和对这些数据所施加的运算 该课程设计的目的是通过课程设计的综合训练培 养分析和编程等实际动手能力 系统掌握数据结构这门课程的主要内容
4、 本次课程设计的内 容是教学计划编制问题 邻接表是图的一种链式存储结构 在邻接表中 对图中每个顶点建 立一个单链表 第 i 个单链表中的结点表示依附于顶点的边 栈是一种限定性的线性表 i v 它只允许在表尾插入元素或删除元素 所以栈具有后进先出的特性 拓扑排序是由某个集合 上的一个偏序得到该集合上的一个全序 而教学计划编制问题就是对排序问题的应用 通过 这个设计事例 我们有理由相信至此以后 我们对邻接表 栈和拓扑排序的理解将会是更上 一层楼 通过该课程设计 能运用所学知识 能上机解决一些实际问题 了解并初步掌握设 计 实现较大程序的完整过程 包括系统分析 编码设计以及调试分析 熟练掌握数据结构
5、 的选择 设计 实现以及操作方法 为进一步的应用开发打好基础 华北科技学院课程设计说明书 第 2 页 共 29 页 第第 2 2 章章 教学计划编制问题陈述及需求分析教学计划编制问题陈述及需求分析 2 12 1 教学计划编制问题陈述教学计划编制问题陈述 大学中每个专业都有固定的教学计划 任何专业的学习年限是固定的 每年两个学期 每个专业开设的课程是确定的 而课程之间的开设时间是必须满足先修关系的 每们课可以 有多门先修课 也可以没有 以本科四年为准 要求设计一个教学计划 输入学期总数 一学期的学分上限 每门课的课程号 学分和直接先修课的课程号 一 是使学生在各学期中的学习负担尽量均匀 二是使课
6、程尽可能地集中在前几个学期中 输出 教学计划到用户指定的文件中 计划表格格式自行设计 若无结果可报告适当的信息 2 22 2 功能需求分析功能需求分析 本系统主要实现对大学中每个专业的教学计划进行设计 需要实现以下几个方面的功能 1 创建存储结构 创建邻接表 2 数据的输入 学期总数 课程数 一学期的学分上限 每门课的课程号 固定占 2 位的数字串 学分和直接先修课的课程号 3 数据的处理 对输入的数据进行计算 4 结果的输出 输出各门课程所对应的学分 以及每学期各门课程的安排 华北科技学院课程设计说明书 第 3 页 共 29 页 第第 3 3 章章 系统设计系统设计 3 1 总体设计总体设计
7、 允许用户指定下列两种编排策略之一 一是使学生在各学期中的学习负担尽量均匀 二 是使课程尽可能地集中在前几个学期中 采用第二种策略 使课程尽可能地集中在前几个学 期中 根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体 创建图 结合先 修关系的 AOV 网 采用邻接链表存储和使用前插法 通过菜单显示代号所对应课程及课程 的先修课程 运用拓扑排序将课程排序后并决定出每学期所学课程 最后输出图 G 的信息 将图的顶点和弧边输出 具体流程图如图 3 1 所示 图图 3 13 1 系统功能结构图系统功能结构图 开始 管理员 输入用户名和密码 创建图 CreateGraph 结合先修关系的 AO
8、V 网 采用邻接表存储 菜单 OUTPUT 显示课程代码 课程名称及 先修课程 输出图 G 的信息 Display 输出图的顶点和 弧边 拓扑排序 TopoSort 将课程排序后 编制出 每学期所学的课程 结束 前插法 使课程尽可能 地集中在前几 个学期中 华北科技学院课程设计说明书 第 4 页 共 29 页 华北科技学院课程设计说明书 第 5 页 共 29 页 首先 初始化栈 构造一个空栈 S 判定这个栈是否为空栈 如果是 则进行下一步操 作 否则 返回错误 接下来对各个顶点求入度 将入度为零的顶点存入数组 当所有入度 为零的顶点都存入数组后 执行完毕 具体流程图如图 3 2 所示 Y N
9、N Y 图图 3 23 2 拓扑排序流程图拓扑排序流程图 初始化栈 InitStack S 对各顶点求入度 并存入数组 InDegree i 中 i 0 n 依次将入度为 0 的顶点存入栈中 推出栈顶的一个元素 入度为零的顶点号 至 i 输出 i 计数器加 1 Count 对以 i 号顶点为尾弧的每个邻接点的入度减 1 并将入度减 1 后为零的顶点号压入栈中 输出 i 计数器加 1 Count n 个顶点全输 出 Return ERROR Return OK 栈是否为空 华北科技学院课程设计说明书 第 6 页 共 29 页 3 23 2 主要模块简介主要模块简介 1 管理员 要进入管理员界面
10、首先需要输入用户名和密码 输入正确的用户名和密码后 即可进 入管理员界面 若输入错误 则提示输入正确的用户名或密码 2 主函数 本程序主要调用两个模块 主程序模块 拓扑排序模块 调用关系简单 通过主函数 主要调用 TopoSort 输出 G 顶点的拓扑排序 Display 输出图的邻接矩阵 CreateGraph 生成图 用来实现对教学计划的编制 3 拓扑排序 利用课程之间的先修关系 运用拓扑排序进行学期课程安排 4 个学期 每学期都有 学分上限 而每学期应学课程的学分应在学分上限内 超过学分上限后 将移到下一学期课 程安排中 在满足课程先修关系和各学期课程安排的情况下 如果某门课程的学分超过
11、该学 期的学分上限 则系统返回值为 Error 提示错误 需要进行修改 必须保证该学期的各课 程学分不会超过学分上限 这时系统返回值为 OK 华北科技学院课程设计说明书 第 7 页 共 29 页 第第 4 4 章章 详细设计详细设计 4 14 1 数据结构数据结构 1 图的数据结构 typedef struct ArcNode 表结点 int adjvex 该弧所指向的顶点的位置 弧的节点结构 struct ArcNode nextarc 指向下一条弧的指针 ArcNode 链表结点 typedef struct VNode 头结点 VertexType data 顶点信息 int grade
12、s 存储学分信息 ArcNode firstarc 指向第一条依附该顶点的弧的指针 VNode AdjList MAX VERTEX NUM typedef struct 图的数据结构 AdjList vertices vertices 存储课程名 int vexnum arcnum 图的当前顶点数和弧数 ALGraph 2 栈的数据结构 typedef struct SqStack SElemType base SElemType top int stacksize 分配的存储空间 SqStack 4 24 2 抽象数据类型的定义抽象数据类型的定义 1 图的抽象数据类型定义 ADT Grap
13、h 数据对象数据对象 V V 是具有相同特性的数据元素的集合 称为顶点集 数据关系数据关系 R R VR VR v wV 且 P v w 表示从 v 到 w 的弧 谓词 P v w 定义了弧的意义或信息 基本操作基本操作 P P CreateGraph AdjList Temp printf0 struct Name name N 1 2 3 4 5 6 7 8 9 10 11 12 OUTPUT 华北科技学院课程设计说明书 第 10 页 共 29 页 printf 教学计划编制系统 n n printf 请输入学期的总数 scanf d printf 请输入学期的学分上限 scanf d C
14、reateGraph G Display G TopoSort G Temp name 2 各主要子函数的算法设计 1 邻接表存储结构 代码 int CreateGraph ALGraph VertexType va ArcNode p printf 请输入教学计划的课程数 scanf d printf 请输入各门课程的先修课程的总和 弧总数 scanf d printf 请输入 d 门课程的课程代码 最多 d 个字符 数字 G vexnum MAX NAME for i 0 i G vexnum i 构造头结点 scanf s G vertices i firstarc NULL for i
15、 0 iMaxScores G vertices i grades 0 printf 警告 学分必须是在 0 到最大限制 d 之间 请检查后再输入 n MaxScores 如果输入的学分大于上限或等于 0 会出现警告 printf 请输入第 d 门课程的学分值 i 1 scanf d 华北科技学院课程设计说明书 第 11 页 共 29 页 printf 请输入下列课程的先修课程 无先修课程输入 0 结束也输入 0 n for k 0 kadjvex j p nextarc G vertices i firstarc 插在表头 G vertices i firstarc p scanf s va
16、 system cls return OK 2 拓扑排序 代码 int TopoSort ALGraph G AdjList Temp struct Name name int i k j 0 count indegree MAX VERTEX NUM SqStack S ArcNode p FindInDegree G indegree 对各顶点求入度 InitStack S 初始化栈 for i 0 inextarc 对 i 号顶点的每个 邻接点的入度减 1 k p adjvex if indegree k 若入度减为 0 则入栈 华北科技学院课程设计说明书 第 12 页 共 29 页 Push S k if count G vexnum printf 此有向图有回路 无法完成拓扑排序 return ERROR else printf 为一个拓扑序列 printf n 华北科技学院课程设计说明书 第 13 页 共 29 页 第第 5 5 章章 编码与调试编码与调试 5 15 1 教学计划编制问题实例教学计划编制问题实例 针对大学各专业本科课程 根据课程之间的依赖关系制定课程安排计划
