教学计划编制问题

1一、设计内容与设计要求1．设计内容：1）问题描述大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。2）基本要求a.输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。b.允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。c.若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。3）测试数据学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。6.2源程序清单（带注释）#includestring.h#includectype.h#includemalloc.h//malloc()等#includelimits.h//INT_MAX等#includestdio.h//EOF(=^Z或F6),NULL#includestdlib.h//atoi()52#includeio.h//eof()#includemath.h//floor(),ceil(),abs()#includeprocess.h//exit()2#includeiostream.h//cout,cin//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE#defineMAX_NAME10/*顶点字符串的最大长度*/#defineMAXCLASS100intZ=0;intX=0;intxqzs,q=1,xfsx;typedefintInfoType;typedefcharVertexType[MAX_NAME];/*字符串类型*//*图的邻接表存储表示*/#defineMAX_VERTEX_NUM100typedefenum{DG}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstructArcNode{intadjvex;/*该弧所指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/InfoType*info;/*网的权值指针）*/}ArcNode;/*表结点*/typedefstruct{VertexTypedata;/*顶点信息*/ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/typedefstruct{AdjListvertices,verticestwo;intvexnum,arcnum;/*图的当前顶点数和弧数*/intkind;/*图的种类标志*/}ALGraph;/*图的邻接表存储的基本操作*/intLocateVex(ALGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;for(i=0;iG.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;3return-1;}StatusCreateGraph(ALGraph*G){/*采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)*/inti,j,k;VertexTypeva,vb;ArcNode*p;printf(请输入教学计划的课程数:);scanf(%d,&(*G).vexnum);printf(请输入拓扑排序所形成的课程先修关系的边数:);scanf(%d,&(*G).arcnum);printf(请输入%d个课程的代表值(%d个字符):\n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;++i)/*构造顶点向量*/{scanf(%s,(*G).vertices[i].data);(*G).vertices[i].firstarc=NULL;}printf(请输入%d个课程的学分值(%d个字符):\n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;++i)/*构造顶点向量*/{scanf(%s,(*G).verticestwo[i].data);}printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n);for(k=0;k(*G).arcnum;++k)/*构造表结点链表*/{scanf(%s%s,va,vb);i=LocateVex(*G,va);/*弧尾*/j=LocateVex(*G,vb);/*弧头*/p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=NULL;/*图*/p-nextarc=(*G).vertices[i].firstarc;/*插在表头*/(*G).vertices[i].firstarc=p;}returnOK;}voidDisplay(ALGraphG){/*输出图的邻接矩阵G*/inti;ArcNode*p;switch(G.kind){caseDG:printf(有向图\n);}printf(%d个顶点：\n,G.vexnum);for(i=0;iG.vexnum;++i)printf(%s,G.vertices[i].data);printf(\n%d条弧(边):\n,G.arcnum);4for(i=0;iG.vexnum;i++){p=G.vertices[i].firstarc;while(p){printf(%s→%s,G.vertices[i].data,G.vertices[p-adjvex].data);p=p-nextarc;}printf(\n);}}voidFindInDegree(ALGraphG,intindegree[]){/*求顶点的入度，算法调用*/inti;ArcNode*p;for(i=0;iG.vexnum;i++)indegree[i]=0;/*赋初值*/for(i=0;iG.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p-adjvex]++;p=p-nextarc;}}}typedefintSElemType;/*栈类型*//*栈的顺序存储表示*/#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;/*顺序栈*//*顺序栈的基本操作*/StatusInitStack(SqStack*S){/*构造一个空栈S*/(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}5voidClearStack(SqStack*S)//清空栈的操作{S-top=S-base;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusPop(SqStack*S,SElemType*e){/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee){/*插入元素e为新的栈顶元素*/if((*S).top-(*S).base=(*S).stacksize)/*栈满，追加存储空间*/{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;returnOK;}typedefintpathone[MAXCLASS];typedefintpathtwo[MAXCLASS];StatusTopologicalSort(ALGraphG){/*有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,*//*否则返回ERROR。*/6inti,k,j=0,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1]*/InitStack(&S);/*初始化栈*/for(i=0;iG.vexnum;++i)/*建零入度顶点栈S*/if(!indegree[i]){Push(&S,i);//cout*G.vertices[i].dataendl;}/*入度为者进栈*/count=0;/*对输出顶点计数*/while(!StackEmpty(S)){/*栈不空*/Pop(&S,&i);a[i]=*G.vertices[i].data;b[i]=*G.verticestwo[i].data;printf(课程%s→学分%s,G.vertices[i].data,G.verticestwo[i].data);/*输出i号顶点并计数*/++count;for(p=G.vertices[i].firstarc;p;p=p-nextarc){/*对i号顶点的每个邻接点的入度减*/k=p-adjvex;if(!(--indegree[k]))/*若入度减为,则入栈*/{Push(&S,k);//cout*G.vertices[i].dataendl;}}}if(countG.vexnum){printf(此有向图有回路\n);returnERROR;}else{printf(为一个拓扑序列。\n);has=true;}FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1]*/ClearStack(&S);cout======================课程