教学计划编制.doc

(完整word版)教学计划编制教学计划编制问题问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求：（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据：学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。#include #include#include#define null 0#define MAXNODE 64 /最大课程个数typedef struct char c3; cid; /课程号typedef struct Course cid id3; /课程号 char name30; /课程名 float xf; /学分 Course; /课程typedef struct PreCourse int adjvex; /课程在数组中的下标struct PreCourse *pre; /指向下一先修的课程节点PreCourse;/先修的课程节点typedef structCourse course;/课程PreCourse *firstnext; /指向第一个先修的课程节点CourseNode;/课程节点typedef structCourseNode coursesMAXNODE; /邻接表int xqs;/学期总数int num; /课程的数目float xfsx;/学分上限AlGraph;/课程图typedef struct int dataMAXNODE;/队中元素int f,r;/队头r 队尾fqueue;int IsCricle=0;/判断是否环 1表示是 0表示不是int jxq;/用于计算学期的/void queueinit(queue *q)/队初始化q-f=q-r=0;void queuein(queue *q,int x)/入队if(q-r+1)%MAXNODE=q-f)printf(队满n);exit(0);q-r=(q-r+1)%MAXNODE;q-dataq-r=x;int queueout(queue *q)/出队if(q-f=q-r)printf(队空n);exit(0);q-f=(q-f+1)%MAXNODE;return q-dataq-f;int queueempty(queue *q)/队判空 1为空if(q-f=q-r)return 1;else return 0;void creatpre(AlGraph *CGraph)/建立先修关系system(cls);/用来清屏int choice;fflush(stdin);/清空输入流int i,j,n;/临时变量PreCourse *p,*q;/临时变printf(n建立先修关系:n);printf(n请输入每一门课程号的编号：);for(i=0;inum;i+)if(i%4=0)printf(n);printf(%d) ,i+1);printf(%st,CGraph-coursesi.course.id);printf(n请根据以上的编号，输入每一门课程的先修课程（输入0 表示没有或结束）：n);for(i=0;inum;i+)printf(%s的先修课程:,CGraph-coursesi.course.id);scanf(%d,&j);n=0;while(j)while(jCGraph-num|j=i+1)if(j=i+1)printf(先修课程号不能是本课程号);elseprintf(输入的先修课程号不在该专业开设的课程序列中);fflush(stdin);/清空输入流printf(重新输入:);scanf(%d,&j);p=(PreCourse *)malloc(sizeof(PreCourse);p-adjvex=j-1;p-pre=null;if(n=0)CGraph-coursesi.firstnext=p;q=CGraph-coursesi.firstnext;n+;elseq-pre=p;q=p;n+;scanf(%d,&j);printf( 1)重新建立先修关系 2)确定n);printf(请选择:);scanf(%d,&choice);if(choice=1)creatpre(CGraph);jxq=0;AlGraph input()/输入并建立课程图AlGraph CGraph;int xqzs=0,kczs=0;/学期总数:xqzs 专业共开设课程数:kczsint i,j;/临时变量float xf,xfsx=0;/临时变量xf 学分上限:xfsxprintf(教学计划编制nn);printf(输入参数:n);printf(1、学期总数:);scanf(%d,&xqzs);CGraph.xqs=xqzs;printf(2、专业共开设课程数:);scanf(%d,&kczs);CGraph.num=kczs;/课程数printf(3、学分上限(每个学期的学分上限都一样):);scanf(%f,&xfsx);CGraph.xfsx=xfsx;printf(4、每门课的课程号(固定占3位的字母数字串)、课程名、学分:n);for(i=0;ixfsx|xf=0)printf(本课程学分大于学期学分上限或小于等于零，请重新输入学分:);fflush(stdin);/清空输入流scanf(%f,&xf);CGraph.coursesi.course.xf=xf;CGraph.coursesi.firstnext=null;creatpre(&CGraph);/建立先修关系return CGraph;void output(AlGraph CGraph)/输出先修关系int i,j,n;/临时变量PreCourse *p;/临时变量printf(先修关系如下：nn);printf(课程编号t课程名称tt 先决条件n);for(i=0;iadjvex;printf(%s ,CGraph.coursesn.course.id);p=p-pre;j+;if(j=0)printf(无);printf(n);void findoutdegree(AlGraph *CGraph,int outdegree)/找出度数，即找出每一门课程的先修课数int i;PreCourse *p;for(i=0;inum;i+)outdegreei=0;p=CGraph-coursesi.firstnext;while(p)outdegreei+;p=p-pre;void judgingcricle(AlGraph *CGraph,queue *q2)/判断是否有环int outdegreeMAXNODE;/出度int i,m,j,pd=0;float xf=0;PreCourse *p;queue q;queueinit(&q);/队初始化findoutdegree(CGraph,outdegree);/找出度for(i=0;inum;i+)if(outdegreei=0&(xf+CGraph-coursesi.course.xf)xfsx)/出度为零的，并且学分还没达到学分上限的入队，即没有先修课的课程入队queuein(&q,i);outdegreei-;xf+=CGraph-coursesi.course.xf;m=0;xf=0;queuein(&q,-1);jxq+;while(1)i=queueout(&q);queuein(q2,i);if(i!=-1)m+;for(j=0;jnum;j+)if(j!=i)if(outdegreej=0&(xf+CGraph-coursesj.course.xf)xfsx)/将之前因学分上限受制的出度为零的入队，即没有先修课的课程入队queuein(&q,j);outdegreej-;xf+=CGraph-coursesj.course.xf;elsep=CGraph-coursesj.firstnext;while(p)if(p-adjvex=i)outdegreej-;if(outdegreej=0&(xf+CGraph-coursesi.course.xf)xfsx)/出度为零的入队queuein(&q,j);outdegreej-;pd=1;xf+=CGraph-coursesi.course.xf;p=p-pre;elseif(pd)pd=0;queuein(&q,-1);jxq+;xf=0;else break;if(jxqCGraph-xqs)printf(n错误报告：n在%d学期内是无法修完这些课程n,CGraph-xqs);exit(0);if(mnum)printf(n错误报告：n);for(i=0;inum;i+)if(outdegreei0)printf(%s ,CGraph-coursesi.course.id);printf(存在循环，因此课程安排不了n);IsCricle=1;void layout1(AlGraph *CGraph,queue *q)/编排1/printf(n学生在各学期中的学习负担尽量均匀:nn);int i,j,xq=1,cxq=CGraph-xqs-jxq,ck20;float xf,m=CGraph-num/CGraph-xqs*1.0f;/m是每学期要学的课程数queue q1=*q;/while(!queueempty(&q1)for(i=0;i20;i+)cki=-1;for(i=0;icoursesj.course.id);i+;xf+=CGraph-coursesj.course.xf;while(cki!=-1); printf(获得学分是%.2fn,xf);void layout2(AlGraph *CGraph,queue *q)/编排2printf(n课程尽可能地集中在前几个学期中:nn); int i,j,xq=1;float xf;printf(n第%d学期学：,xq+);xf=0;queue q1=*q;/for(i=0;inum;)j=queueout(&q1);if(j!=-1)printf( %s ,CGraph-coursesj.course.id);i+;xf+=CGraph-coursesj.course.xf;else printf(获得学分是%.2fn第%d学期学：,xf,xq+);xf=0;while(xqxqs)printf(获得学分是%.2fn第%d学期学：无t,xf,xq+);xf=0;printf(获得学分是%.2fn);void main()int choice;queue q;/用来存放已编排好的课程queueinit(&q);/队初始化AlGraph CGraph;/课程图fflush(stdin);/清空输入流CGraph=input();/输入并建立课程图system(cls);/用来清屏output(CGraph);/输出先修关系printf(nn);fflush(stdin);/清空输入流judgingcricle(&CGraph,&q);/判断是否有环if(!IsCricle)printf(请选择编排策略:n);printf(1.使学生在各学期中的学习负担尽量均匀;n);printf(2.使课程尽可能地集中在前几个学期中。n);printf(请选择:);/scanf(%d,&choice);/fflush(stdin);/清空输入流/if(choice=1) layout1(&CGraph,&q);/编排1/else layout2(&CGraph,&q);/编排2