实验5教学计划编制问题预习报告.doc

实验5教学计划编制问题预习报告 实验5教学计划编制问题一.需求分析 （1）实验内容和实验目的1.大学的每个专业都要编制教学计划。 假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。 每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。 每个课程的先修关系都是确定的，可以有任意多门，也可以没有。 每一门课程恰好一个学期。 试在这样的情况下设置一个教学计划编制程序。 2.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.3.本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程. （2）测试数据学期总数6；学分上限10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。 先修关系见教科书图726。 二.概要设计1.抽象数据类型图的定义:ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P: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);ADT Graph 2、抽象数据类型栈的定义:ADT Stack数据对象:D=ai|aiElemSet,i=1,2,n,n=0数据关系:R1=ai-1ai|ai-1,aiD,i=2,n基本操作:void InitStack(SqStack*S);int StackEmpty(SqStack S);void Push(SqStack*S,int);int Pop(SqStack*S,int*e);ADT Stac3.本程序只有两个模块,调用关系简单.主程序模块拓扑排序模块三详细设计1头结点，表结点，邻接表的定义#define MAX_VERTEX_NUM100/最大课程总数typedef struct ArcNodeint adjvex;structArcNode*nextarc;ArcNode;typedef structVNodechar name24;/课程名int classid;/课程号int credit;/课程的学分int indegree;/该结点的入度int state;/该节点的状态ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices;int vexnum,arum;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_SIZE100/存储空间的初时分配量#define STACKINCREMENT10/存储空间的分配增量typedef intElemType;typedef structAdjList vertices;int vexnum,arum;ALGraph;栈的基本操作void InitStack(SqStack*S);/栈的初始化int StackEmpty(SqStack S);/判断栈是否为空void Push(SqStack*S,int);/入栈操作int Pop(SqStack*S,int*e);/出栈操作3主程序和其他算法int main()/主函数int numterm;/学期总数int uplcredit;/一个学期的学分上限int selectway;ALGraph G;printf(请输入学期总数:n);scanf(%d,&numterm);printf(请输入一个学期的学分上限:n);scanf(%d,&uplcredit);CreatGraph(&G);printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布n);scanf(%d,&selectway);if(selectway=1)TopologicalSort_1(G,numterm,uplcredit);if(selectway=2)TopologicalSort_2(G,numterm,uplcredit);system(pause);return0;4.时空分析时间复杂度O（n）；空间复杂度O（n）；四调试分析 （1）实验过程中出现的问题及解决方法我们在实验过程中遇到的最大难题是两个课程排序算法的编写。 刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。 经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。 经过三天的修改，终于写出了符合要求的排序算法。 五用户使用和说明要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步