数据结构教学计划编制问题课程设计报告.doc

武汉纺织大学数学与计算机学院 数据结构课程设计报告 设计题目 教学计划编制问题 学生姓名： 易 爽 学 号： 1304240717 班 级： 计科1301 指导老师： 马宁 报告日期： 2015.1.20 1 题目与要求 1.1 问题提出 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。 1.2 本系统涉及的知识点 图的存储结构邻接表 对AOV-网构造其定点的拓扑有序序列 1.3 功能要求 （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。 （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程可能地集中在前几个学期中。 （3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。 [测试数据] 学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下： 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1，C2 C4 汇编语言 C1 C5 语言的设计和分析 C3，C4 C6 计算机原理 C11 C7 编译原理 C5，C3 C8 操作系统 C3，C6 C9 高等数学 无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C9，C10，C1 2 功能设计 2.1 数据结构定义 1．头结点，表结点，邻接表的定义 #define MAX_VERTEX_NUM 100 //最大课程总数 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ char name[24]; //课程名 int classid; //课程号 int credit; //课程的学分 int indegree; //该结点的入度 int state; //该节点的状态 ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VEXTEX_NUM]; typedef struct{ AdjList vertices; int vexnum, arcnum; }ALGraph; 邻接表的基本操作： void CreatGraph(ALGraph *); 创建邻接表 void FindInDegree(ALGraph , int * ); 求一个结点的入度 void TopologicalSort_1(ALGraph G,int numterm,int maxcredit); 拓扑排序来编排课程 void TopologicalSort_2(ALGraph G,int numterm,int maxcredit); 2．栈的定义： #define STACk_INIT_SIZE 100 //存储空间的初时分配量 #define STACKINCREMENT 10 //存储空间的分配增量 typedef int ElemType; typedef struct{ AdjList vertices; int vexnum, arcnum; }ALGraph; 基本操作： void InitStack (SqStack *S); 栈的初始化 int StackEmpty(SqStack S); 判断栈是否为空 void Push(SqStack *S, int ); 入栈操作 int Po