学期授课计划编制

“学期授课计划编制”实验报告实验目的题目：学期授课计划编制问题描述大学每个学期的课程授课有学分及授课门数上限的规定。课程之间有先行课的限制。设计编制学期授课计划，使得总的教学时长为最短的拓扑集合划分程序。实验要求设计大学四年制授课计划编制的模拟程序。（1）采用邻接表或邻接矩阵存储结构。（2）使用栈或队列等作为拓扑排序的辅助数据结构。（3）可以尝试采用深度优先遍历求解问题。需求分析根据我的调查及生活经验，学期授课计划的编制需要以下几个方面的信息汇总才可以实现确定学期数，以及一个学期的最大学分上限和最大的课程数目上限。确定一共需要上几门课，一级每门课的学分。确定课程的先行关系。综合以上信息采用拓扑排序制定出总的教学时长最短的教学授课计划。模块流程图排序模块栈模块主程序模块

排序模块栈模块主程序模块性能需求本程序在运行期间，为了避免在运行大量数据时不会出错，并且能够在很短的时间内将运行结果稳定输出，就需要系统达到安全性能好，可靠性高，稳定性强，处理数据迅速等特点。三、程序实现本程序采取数据结构模块化编程，很好的实现了实验所要求的各项功能，本程序分为三个主要模块：主程序模块、栈模块、排序模块。主程序模块intmain(){printf("学期授课计划编制\n");printf("//AOV-网:顶点表示活动，弧表示活动间优先关系的有向图；intCONTINUE=1;while(CONTINUE!=0){printf("------------------------------------------------\n");ALGraphf;//图的邻接表存储；printf("请输入学期总数:");scanf("%d",&term_num);printf("请输入每学期的学分上限:");scanf("%d",&credit_lim);CreateGraph(f);Display(f);TopologicalSort(f);printf("\n按1继续，按0结束:");scanf("%d",&CONTINUE);}return0;}栈模块typedefenum{DG}GraphKind;//{有向图,有向网,无向图,无向网};typedefstructArcNode{//弧结构；intadjvex;//该弧所指向的顶点的位置;structArcNode*nextarc;//指向下一条弧的指针;InfoType*info;//网的权值指针;}ArcNode;//表结点;typedefstruct{VertexTypedata;//顶点信息;ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices,vertices2;//分别存课程名和学分；intvexnum,arcnum;intkind;}ALGraph;intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph&G){inti,j,k;VertexTypev1,v2;//顶点信息；ArcNode*p;//指向第一条依附某顶点的弧的指针；printf("请输入教学计划的课程数:");scanf("%d",&G.vexnum);printf("请输入课程先修关系数（弧的数目）:");scanf("%d",&G.arcnum);printf("请输入%d个课程的代表值(如:c01):\n",G.vexnum);for(i=0;i<G.vexnum;++i){scanf("%s",G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf("请输入%d个课程的学分值:\n",(G).vexnum);for(i=0;i<G.vexnum;++i){scanf("%s",G.vertices2[i].data);}printf("请顺序输入每条弧的弧尾和弧头(以空格作为间隔):\n");for(k=0;k<G.arcnum;++k){scanf("%s%s",v1,v2);i=LocateVex(G,v1);j=LocateVex(G,v2);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){inti;ArcNode*p;switch(G.kind){caseDG:printf("有向图\n");}printf("%d个顶点：\n",G.vexnum);for(i=0;i<G.vexnum;++i)printf("%s",G.vertices[i].data);printf("\n%d条弧:\n",G.arcnum);for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;}printf("\n");}}voidFindInDegree(ALGraphG,intindegree[]){inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}typedefintSElemType;#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack*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;}voidClearStack(SqStack*S){//清空栈的操作S->top=S->base;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}排序模块StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee){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;}Statuszxf(ALGraphG){intz=0;for(inti=0;i<G.vexnum;i++){z+=atoi(G.vertices2[i].data);}returnz;}typedefintpathone[MAX_CLASS_NUM];typedefintpathtwo[MAX_CLASS_NUM];StatusTopologicalSort(ALGraphG){inti,k,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);InitStack(&S);for(i=0;i<G.vexnum;++i){if(!indegree[i])Push(&S,i);}count=0;while(!StackEmpty(S)){Pop(&S,&i);a[i]=*G.vertices[i].data;//课程名；b[i]=*G.vertices2[i].data;//学分；printf("课程%s→学分%s",G.vertices[i].data,G.vertices2[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k]))Push(&S,k);}}if(count<G.vexnum){printf("此有向图有回路\n");returnERROR;}else{printf("为一个拓扑序列。\n\n");has=true;}intpattern=2;FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1];ClearStack(&S);printf("=====================================================\n");printf("教学计划如下：\n");intxq=1;//学期数;intxfh;//学分和；intnow=0;inttop=G.vexnum/term_num;//平均每学期课程数；intpjxf=zxf(G)/term_num;//每学期平均学分；while(xq<=term_num+1){intresult[20];//某个学期的课程；intm=0;xfh=0;now=0;//当前学期课程数；for(i=0;i<G.vexnum;++i){if(0==indegree[i])Push(&S,i);}if(xq==term_num+1&&!StackEmpty(S)){printf("还有课程未安排！\n");}while(!StackEmpty(S)&&xq<=term_num){intxf;Pop(&S,&i);//弹出栈顶元素；xf=atoi(G.vertices2[i].data);//atoi:字符串转换成整型数,xf:学分;xfh=xfh+xf;now++;if(xfh>credit_lim){ClearStack(&S);break;}if(pattern==1){if(xq!=term_num/2&&now>top){ClearStack(&S);now=0;break;}}if(pattern==2){if(xq!=1&&xq!=term_num/2&&xq!=term_num/2-1&&now>top){ClearStack(&S);now=0;break;}}indegree[i]--;//减为-1,避免被再次计入；for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;indegree[k]--;if(indegree[k]==0)Push(&S,k);}result[m]=i;m++;}if(xq<=term_num){printf("第%d个学期的课程为：",xq);for(intj=0;j<m;j++){printf("课程%s",G.vertices[result[j]].data);}}printf("\n");xq++;ClearStack(&S);}printf("=====================================================\n");returnOK;}四、程序运行截图程序开始运行界面测试数据：学期一共为2个学期，每个学期上限10学分，总共教学计划安排5门课，分别为c1课2学分，c2课6学分，c3课4学分，c4课6学分，c5课2学分。必须先上c1课再上c2课，先上c3课再上c4课，根据总教学时间最少的要求排课，输出的排课结果为：第一学期c5、c3，第二学期c4、c1。还有c2没有安排，所以无法排课，排课失败。测试数据：学期一共为1个学期，每个学期上限10学分，总共教学计划安排3门课，分别为c1课2学分，c2课2学分，c3课2学分。必须先上c1课再上c3课，根据总教学时间最少的要求排课，输出的排课结果为：第一学期c2、c1、c3。排课成功。

五、调试总结由于对于指针的操作掌握的不是很熟练，导致越界访问现象频频发生，因此，今后自己应该加强对指针的掌握和使用，以便可以更加顺利的编程。各操作时空复杂性比较合理，时空复杂度均为O（n），O（1）。本程序作业采用数据结构抽象的程序设计方法，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。六、参考文献[1]严蔚敏、吴伟民编著.《数据结构题集》（C语言版）.北京：清华大学出版社.1999[2]严蔚敏、吴伟民编著.《数据结构》（C语言版）.北京：清华大学出版社.2007七、程序清单#include<string.h>#include<stdio.h>#include<stdlib.h>#include<iomanip>#include<math.h>//floor(),ceil(),abs()#include<iostream>usingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;//Status是函数的返回类型；typedefintBoolean;#defineMAX_NAME10//顶点字符串的最大长度;#defineMAX_CLASS_NUM100intZ=0;intX=0;intterm_num,credit_lim,q=1;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,vertices2;//分别存课程名和学分；intvexnum,arcnum;intkind;}ALGraph;intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph&G){inti,j,k;VertexTypev1,v2;//顶点信息；ArcNode*p;//指向第一条依附某顶点的弧的指针；printf("请输入教学计划的课程数:");scanf("%d",&G.vexnum);printf("请输入课程先修关系数（弧的数目）:");scanf("%d",&G.arcnum);printf("请输入%d个课程的代表值(如:c01):\n",G.vexnum);for(i=0;i<G.vexnum;++i){scanf("%s",G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf("请输入%d个课程的学分值:\n",(G).vexnum);for(i=0;i<G.vexnum;++i){scanf("%s",G.vertices2[i].data);}printf("请顺序输入每条弧的弧尾和弧头(以空格作为间隔):\n");for(k=0;k<G.arcnum;++k){scanf("%s%s",v1,v2);i=LocateVex(G,v1);j=LocateVex(G,v2);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){inti;ArcNode*p;switch(G.kind){caseDG:printf("有向图\n");}printf("%d个顶点：\n",G.vexnum);for(i=0;i<G.vexnum;++i)printf("%s",G.vertices[i].data);printf("\n%d条弧:\n",G.arcnum);for(i=0;i<G.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;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}typedefintSElemType;#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack*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;}voidClearStack(SqStack*S){//清空栈的操作S->top=S->base;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusPush(SqStack*S,SElemTypee){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;}Statuszxf(ALGraphG){intz=0;for(inti=0;i<G.vexnum;i++){z+=atoi(G.vertices2[i].data);}returnz;}typedefintpathone[MAX_CLASS_NUM];typedefintpathtwo[MAX_CLASS_NUM];StatusTopologicalSort(ALGraphG){inti,k,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);InitStack(&S);for(i=0;i<G.vexnum;++i){if(!indegree[i])Push(&S,i);}count=0;while(!StackEmpty(S)){Pop(&S,&i);a[i]=*G.vertices[i].data;//课程名；b[i]=*G.vertices2[i].data;//学分；printf("课程%s→学分%s",G.vertices[i].data,G.vertices2[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k]))Push(&S,k);}}if(count<G.vexnum){printf("此有向图有回路\n");returnERROR;}else{printf("为一个拓扑序列。\n\n");has=true;}intpattern=2;FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1];ClearStack(&S);printf("=====================================================\n");printf("教学计划如下：\n");intxq=1;//学期数;intxfh;//学分和；intnow=0;inttop=G.vexnum/term_num;//平均每学期课程数；intpjxf=zxf(G)/term_num;//每学期平均学分；while(xq<=term_num+1){intresult[20];//某个学期的课程；intm=0;xfh=0;now=0;//当前学期课程数}if(xq==term_num+1&&!StackEmpty(S)){printf("还有课程未安排！\n");}while(!StackEmpty(S)&&xq<=term_num){intxf;Pop(&S,&i);//弹出栈顶元素；xf=atoi(G.vertices2[i].data);//atoi:字符串转换成整型数