教学计划编制问题#include<string.h>#include<stdio.h>#include<stdlib.h>#define null 0#define MAXNODE 64 //最大课程个数typedef struct{char c[3];}cid; //课程号typedef struct Course{cid id[3]; //课程号char name[30]; //课程名float xf; //学分}Course; ////////////////////////////////////////////////课程typedef struct PreCourse{int adjvex; //课程在数组中的下标struct PreCourse *pre; //指向下一先修的课程节点}PreCourse;/////////////////////////////////////////////////先修的课程节点typedef struct{Course course;//课程PreCourse *firstnext; //指向第一个先修的课程节点}CourseNode;////////////////////////////////////////////////////////////课程节点typedef struct{CourseNode courses[MAXNODE]; //邻接表int xqs;//学期总数int num; //课程的数目float xfsx;/////学分上限}AlGraph;///////////////////////////////////////////////////////////////课程图typedef struct{int data[MAXNODE];//队中元素int f,r;//队头r 队尾f}queue;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->data[q->r]=x;}int queueout(queue *q)//出队{if(q->f==q->r){printf("队空\n");exit(0);}q->f=(q->f+1)%MAXNODE;return q->data[q->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;i<CGraph->num;i++){if(i%4==0)printf("\n");printf("%d) ",i+1);printf("%s\t",CGraph->courses[i].course.id);}printf("\n请根据以上的编号，输入每一门课程的先修课程（输入0 表示没有或结束）：\n");for(i=0;i<CGraph->num;i++){printf("%s的先修课程:",CGraph->courses[i].course.id);scanf("%d",&j);n=0;while(j){while(j<1||j>CGraph->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->courses[i].firstnext=p;q=CGraph->courses[i].firstnext;n++;}else{q->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("教学计划编制\n\n");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;i<kczs;i++){j=0;fflush(stdin);/////////////////////////////////////////////清空输入流printf("课程号:");scanf("%s",CGraph.courses[i].course.id);fflush(stdin);/////////////////////////////////////////////清空输入流printf("课程名:");scanf("%s",CGraph.courses[i]);fflush(stdin);/////////////////////////////////////////////清空输入流printf("学分:");scanf("%f",&xf);fflush(stdin);/////////////////////////////////////////////清空输入流while(xf>xfsx||xf<=0){printf("本课程学分大于学期学分上限或小于等于零，请重新输入学分:");fflush(stdin);/////////////////////////////////////////////清空输入流scanf("%f",&xf);}CGraph.courses[i].course.xf=xf;CGraph.courses[i].firstnext=null;}creatpre(&CGraph);///////////////建立先修关系return CGraph;}void output(AlGraph CGraph)///////////////输出先修关系{int i,j,n;//////临时变量PreCourse *p;//////临时变量printf("先修关系如下：\n\n");printf("课程编号\t课程名称\t\t 先决条件\n");for(i=0;i<CGraph.num;i++){printf("%s\t\t%s\t\t",CGraph.courses[i].course.id,CGraph.courses[i]);j=0;p=CGraph.courses[i].firstnext;while(p){n=p->adjvex;printf("%s ",CGraph.courses[n].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;i<CGraph->num;i++){outdegree[i]=0;p=CGraph->courses[i].firstnext;while(p){outdegree[i]++;p=p->pre;}}}void judgingcricle(AlGraph *CGraph,queue *q2)////////判断是否有环{int outdegree[MAXNODE];/////////出度int i,m,j,pd=0;float xf=0;PreCourse *p;queue q;queueinit(&q);///////////////队初始化findoutdegree(CGraph,outdegree);/////////找出度for(i=0;i<CGraph->num;i++)if(outdegree[i]==0&&(xf+CGraph->courses[i].course.xf)<=CGraph->xfsx)/////////出度为零的，并且学分还没达到学分上限的入队，即没有先修课的课程入队{queuein(&q,i);outdegree[i]--;xf+=CGraph->courses[i].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;j<CGraph->num;j++)if(j!=i){if(outdegree[j]==0&&(xf+CGraph->courses[j].course.xf)<=CGraph->xfsx)/////////将之前因学分上限受制的出度为零的入队，即没有先修课的课程入队{queuein(&q,j);outdegree[j]--;xf+=CGraph->courses[j].course.xf;}else{p=CGraph->courses[j].firstnext;while(p){if(p->adjvex==i){outdegree[j]--;if(outdegree[j]==0&&(xf+CGraph->courses[i].course.xf)<=CGraph->xfsx)/////////出度为零的入队{queuein(&q,j);outdegree[j]--;pd=1;xf+=CGraph->courses[i].course.xf;}}p=p->pre;}}}}else{if(pd){pd=0;queuein(&q,-1);jxq++;xf=0;}else break;}}if(jxq>CGraph->xqs){printf("\n错误报告：\n在%d学期内是无法修完这些课程\n",CGraph->xqs);exit(0);}if(m<CGraph->num){printf("\n错误报告：\n");for(i=0;i<CGraph->num;i++)if(outdegree[i]>0)printf("%s ",CGraph->courses[i].course.id);printf("存在循环，因此课程安排不了\n");IsCricle=1;}}void layout1(AlGraph *CGraph,queue *q)////////////////编排1/////{printf("\n学生在各学期中的学习负担尽量均匀:\n\n");int i,j,xq=1,cxq=CGraph->xqs-jxq,ck[20];float xf,m=CGraph->num/CGraph->xqs*1.0f;//m是每学期要学的课程数queue q1=*q;////while(!queueempty(&q1)){for(i=0;i<20;i++)ck[i]=-1;for(i=0;i<m+1;i++){j=queueout(&q1);if(j==-1)break;ck[i]=j;}if(ck[0]!=-1){printf("\n第%d学期学：",xq++);xf=0;i=0;do{j=ck[i];printf(" %s ",CGraph->courses[j].course.id);i++;xf+=CGraph->courses[j].course.xf;}while(ck[i]!=-1);printf("获得学分是%.2f\n",xf);}}}void layout2(AlGraph *CGraph,queue *q)////////////////编排2{printf("\n课程尽可能地集中在前几个学期中:\n\n");int i,j,xq=1;float xf;printf("\n第%d学期学：",xq++);xf=0;queue q1=*q;////for(i=0;i<CGraph->num;){j=queueout(&q1);if(j!=-1){printf(" %s ",CGraph->courses[j].course.id);i++;xf+=CGraph->courses[j].course.xf;}else {printf("获得学分是%.2f\n第%d学期学：",xf,xq++);xf=0;}}while(xq<=CGraph->xqs){printf("获得学分是%.2f\n第%d学期学：无\t",xf,xq++);xf=0;} printf("获得学分是%.2f\n");}void main(){int choice;queue q;//用来存放已编排好的课程queueinit(&q);///////////////队初始化AlGraph CGraph;//课程图fflush(stdin);/////////////////////////////////////////////清空输入流CGraph=input();//输入并建立课程图system("cls");//用来清屏output(CGraph);///////////////输出先修关系printf("\n\n");fflush(stdin);/////////////////////////////////////////////清空输入流judgingcricle(&CGraph,&q);////////判断是否有环if(!IsCricle){printf("请选择编排策略:\n");printf("1.使学生在各学期中的学习负担尽量均匀;\n");printf("2.使课程尽可能地集中在前几个学期中。