教学计划编制问题.docx

1、教学计划编制问题一、设计内容：问题描述大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。1、基本要求（1）.输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3

2、）若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。2、测试数据学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图7.26。3、输出输入要求输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。4、实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立

3、内部课程号与课程号之间的对应关系。二、 概要设计1、抽象数据类型图的定义如下: ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R: R=VR VR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P:LocateVex（ALGraph G,VertexType u）：图的邻接表存储的基本操作CreateGraph（ALGraph *G）：构造生成树Display（ALGraph G）：输出图的邻接矩阵FindInDegree（ALGraph G,int indegree）：求顶点的入度TopologicalSort（ALGraph G

4、）：有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。ADT Graph2、栈的定义:ADT Stack数据对象:D=ai|aiElemSet,i=1,2,n,n=0 数据关系:R1=ai-1 ai|ai-1,aiD,i=2,n基本操作D： InitStack (SqStack *S); 初始化一个空栈SStackEmpty(SqStack S); 若栈S为空栈，则返回TRUE，否则返回FALSEPush(SqStack *S,SElemType *e ); 插入元素e为新的栈顶元素Pop(SqStack *S,SElemType *e); 若

5、栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORADT Stack3、主程序void main() ALGraph f;printf(教学计划编制问题的数据模型为拓扑排序AOV-网结构。n);printf(以下为教学计划编制问题的求解过程:n);printf(请输入学期总数:);scanf(%d,&xqzs);printf(请输入学期的学分上限:);scanf(%d,&xfsx);CreateGraph(&f);Display(f);TopologicalSort(f);4、本程序只有两个模块,调用关系简单. 主程序模块 拓扑排序模块三、 详细设计1、顶点、边、图类型#

6、define MAX_VERTEX_NUM 100typedef int pathoneMAXCLASS;typedef int pathtwoMAXCLASS; typedef enumDGGraphKind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 网的权值指针）*/ ArcNode; /* 表结点*/ typedef struct VertexType data;

7、/* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM; /* 头结点*/ typedef struct AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ ALGraph;2、图的基本操作int InitGraph(ALGraph &G);初始化邻接多重表，表示一个空图。int LocateVex(ALGraph G,VertexType u)； 若G中

8、存在顶点u,则返回该顶点在图中位置;否则返回-1。Status CreateGraph(ALGraph *G)；采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图。void Display(ALGraph G)；输出图的邻接矩阵G。void FindInDegree(ALGraph G,int indegree)；求顶点的入度，算法调用。Status TopologicalSort(ALGraph G)；有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR3、栈类型#define STACK_INIT_SIZE 10 /* 存储空间初

9、始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ SqStack; /* 顺序栈*/4、栈的基本操作Status InitStack(SqStack *S)；初始化void ClearStack(SqStack *S)；清空栈的操作Status StackEmpty(SqStack S)；

10、 若栈S为空栈，则返回TRUE，否则返回FALSEStatus Pop(SqStack *S,SElemType *e)；若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status Push(SqStack *S,SElemType e)；插入元素e为新的栈顶元素5、部分操作代码如下：int LocateVex(ALGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征*/ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;iG.vexnum;+i) if(strc

11、mp(u,G.verticesi.data)=0) return i; return -1;Status CreateGraph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图) */ int i,j,k; VertexType va,vb; ArcNode *p; printf(请输入教学计划的课程数: ); scanf(%d,&(*G).vexnum); printf(请输入拓扑排序所形成的课程先修关系的边数: ); scanf(%d,&(*G).arcnum); printf(请输入%d个课程的代表值(%d个字符):n,(*G).vexnum

12、,MAX_NAME); for(i=0;i(*G).vexnum;+i) /* 构造顶点向量*/ scanf(%s,(*G).verticesi.data); (*G).verticesi.firstarc=NULL; printf(请输入%d个课程的学分值(%d个字符):n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;+i) /* 构造顶点向量*/ scanf(%s,(*G).verticestwoi.data); printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n); for(k=0;kadjvex=j; p-info=NUL

13、L; /* 图*/ p-nextarc=(*G).verticesi.firstarc; /* 插在表头*/ (*G).verticesi.firstarc=p; return OK; void Display(ALGraph G) /* 输出图的邻接矩阵G */ int i; ArcNode *p; switch(G.kind) case DG: printf(有向图n); printf(%d个顶点：n,G.vexnum); for(i=0;iG.vexnum;+i) printf(%s ,G.verticesi.data); printf(n%d条弧(边):n,G.arcnum); for

14、(i=0;iadjvex.data); p=p-nextarc; printf(n); void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用*/ int i; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; /* 赋初值*/ for(i=0;iadjvex+; p=p-nextarc; Status InitStack(SqStack *S) /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemTy

15、pe); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK;void ClearStack(SqStack *S) /清空栈的操作 S-top=S-base;Status StackEmpty(SqStack S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE;Status Pop(SqStack *S,SElemType *

16、e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status Push(SqStack *S,SElemType e) /* 插入元素e为新的栈顶元素*/ if(*S).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间*/ (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT) *sizeof(SElemT

17、ype); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; Status TopologicalSort(ALGraph G) /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */ /* 否则返回ERROR。*/ int i,k,j=0,count,indegreeMAX_VERTEX_NUM; bool has=false; SqS

18、tack S; pathone a; pathtwo b; ArcNode *p; FindInDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ InitStack(&S); /* 初始化栈*/ for(i=0;iG.vexnum;+i) /* 建零入度顶点栈S */ if(!indegreei) Push(&S,i); /cout*G.verticesi.datanextarc) /* 对i号顶点的每个邻接点的入度减*/ k=p-adjvex; if(!(-indegreek) /* 若入度减为,则入栈*/ Push(&S,k); /co

19、ut*G.verticesi.dataendl; if(countG.vexnum) printf(此有向图有回路n); return ERROR; else printf(为一个拓扑序列。n); has=true; FindInDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ ClearStack(&S); cout=课程计划如下= endl; int qq=1; /学期数 int xxf; while(qq=xqzs) int result20; int rtop=0; int nn=0; /int ccount=0; / 学期学分计算

20、 xxf=0; for(i=0;ixfsx) break; indegreei-; for(p=G.verticesi.firstarc;p;p=p-nextarc) /* 对i号顶点的每个邻接点的入度减*/ k=p-adjvex; indegreek-; /* if(!(-indegreek) 若入度减为,则入栈 Push(&S,k); */ resultrtop=i; rtop+; cout第qq个学期的课程为：endl; for(nn=0;nnrtop;nn+) cout课程G.verticesresultnn.dataendl; qq+; return OK;6、主函数：int mai

21、n() ALGraph f; printf(教学计划编制问题的数据模型为拓扑排序AOV-网结构。n); printf(以下为教学计划编制问题的求解过程:n); printf(请输入学期总数:); scanf(%d,&xqzs); printf(请输入学期的学分上限:); scanf(%d,&xfsx); CreateGraph(&f); Display(f); TopologicalSort(f);四、调试分析1、实验过程中出现的问题及解决方法我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经

22、过请教同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。2、实验体会:经过此次课程设计，我认识到了理论与实践结合的重要性，仅仅只是从课本上学到算法原理是远远不够的。在实践中，我们总会出现许多错误。这就要求我们以一个脚踏实地的态度来处理问题。我们深刻地认识到自己写程序的不足，使我们学到了好多有用的知识，让我们明白了C语言的语句用法。五、用户手册及测试结果输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对学分值输入完成后执行可得到每个学期的课程结果六、附录（程序源代码）#include #include #include

23、/ malloc()等 #include / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi()52 #include / eof() #include / floor(),ceil(),abs() #include / exit() #include / cout,cin / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; / Status是函数的类型,其值是函数结

24、果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 10 /* 顶点字符串的最大长度*/ #define MAXCLASS 100 int Z=0; int X=0; int xqzs,q=1,xfsx; typedef int InfoType; typedef char VertexTypeMAX_NAME; /* 字符串类型*/ /* 图的邻接表存储表示*/ #define MAX_VERTEX_NUM 100 typedef enumDGGraphKind; /* 有向图,有向网,无

25、向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 网的权值指针）*/ ArcNode; /* 表结点*/ typedef struct VertexType data; /* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM; /* 头结点*/ typedef struct AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ ALGraph;/* 图的邻接表存储的基本操作*/int LocateVex(ALGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征*/ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.verticesi.data)=0) return i; retur