教学计划编制问题

一．问题描述大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。二．基本要求（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。三．需求分析根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。end采用第二种策略：使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图CreateGraph（）：结合先修关系的AOV网，采用邻接链表存储菜单OUTPUT()：显示代号所对应课程及课程的先修课程前插法main拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程输出图G的信息Display(G)：将图的顶点和弧边输出四、主要设计程序#includestdio.h#includestdlib.h#includemath.h#includestring.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineMAX_NAME3#defineMAXCLASS100//顶点字符串的最大长度#defineMAX_VERTEX_NUM100//最大顶点数#defineN12typedefcharVertexType[MAX_NAME];intTotalTerms;//学期总数intMaxScores;//学分上限/*----图的邻接表存储表示----*/typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置弧的节点结构structArcNode*nextarc;//指向下一条弧的指针}ArcNode;//链表结点typedefstruct//链接表{VertexTypedata;//顶点信息intgrades;//存储学分信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstruct{AdjListvertices;//vertices存储课程名intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;voidOUTPUT(){ints;printf(\t\t教学计划编制菜单\n);printf(\t\t课程代码|课程名称|优先课程\n);printf(\t\tC1|程序设计基础|无\n);printf(\t\tC2|离散数学|C1\n);printf(\t\tC3|数据结构|C1，C2\n);printf(\t\tC4|汇编语言|C1\n);printf(\t\tC5|语言的设计和分析|C3，C4\n);printf(\t\tC6|计算机原理|C11\n);printf(\t\tC7|编译原理|C5，C3\n);printf(\t\tC8|操作系统|C3，C6\n);printf(\t\tC9|高等数学|无\n);printf(\t\tC10|线性代数|C9\n);printf(\t\tC11|普通物理|C9\n);printf(\t\tC12|数值分析|C9,C10,C1\n);printf(pressanynumkeytocontinue:);scanf(%d,&s);}/*查找图中某个顶点位置*/intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;iG.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}/*采用邻接表存储结构*/intCreateGraph(ALGraph&G){inti,j,k;VertexTypeva;ArcNode*p;printf(请输入教学计划的课程数:);scanf(%d,&G.vexnum);printf(请输入各个课程的先修课程的总和(弧总数):);scanf(%d,&G.arcnum);printf(请输入%d个课程的课程号(最多%d个字符,数字+字母):,G.vexnum,MAX_NAME);for(i=0;iG.vexnum;++i){scanf(%s,&G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf(请输入%d个课程的学分值:,G.vexnum);for(i=0;iG.vexnum;++i){scanf(%d,&G.vertices[i].grades);}printf(请输入下列课程的先修课程(无先修课程输入0结束后也输入0)\n);for(k=0;kG.vexnum;++k)//构造表结点链表,利用前插法{printf(%s的先修课程:,G.vertices[k].data);scanf(%s,va);while(va[0]!='0'){i=LocateVex(G,va);//弧头j=k;//弧尾p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=G.vertices[i].firstarc;//插在表头G.vertices[i].firstarc=p;scanf(%s,va);}}returnOK;}/*输出图G的信息*/voidDisplay(ALGraphG){inti;ArcNode*p;printf(有向图\n);printf(%d个顶点,G.vexnum);for(i=0;iG.vexnum;++i)printf(%4s,G.vertices[i].data);printf(\n%d条弧边:\n,G.arcnum);for(i=0;iG.vexnum;i++){p=G.vertices[i].firstarc;while(p){printf(%s---%s\n,G.vertices[i].data,G.vertices[p-adjvex].data);p=p-nextarc;}}}/*求顶点的入度*/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;}}}structName{charc[20];}name;voidpuanduan(VertexTypestr,structNamename[],intn){if(strcmp(str,name[0].c)==0)printf(程序设计基础);if(strcmp(str,name[1].c)==0)printf(离散数学);if(strcmp(str,name[2].c)==0)printf(数据结构);if(strcmp(str,name[3].c)==0)printf(汇编语言);if(strcmp(str,name[4].c)==0)printf(语言的设计和分析);if(strcmp(str,name[5].c)==0)printf(计算机原理);if(strcmp(str,name[6].c)==0)printf(编译原理);if(strcmp(str,name[7].c)==0)printf(操作系统);if(strcmp(str,name[8].c)==0)printf(高等数学);if(strcmp(str,name[9].c)==0)printf(线性代数);if(strcmp(str,name[10].c)==0)printf(普通物理);if(strcmp(str,name[11].c)==0)printf(数值分析);//}}/*栈定义*/typedefintSElemType;//栈类型#defineStack_NUM20//存储空间初始分配量#defineStack_MoreNUM5//存储空间分配增量typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;//分配的存储空间}SqStack;/*栈的初始化*/intInitStack(SqStack&S){S.base=(SElemType*)malloc(Stack_NUM*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base;S.stacksize=Stack_NUM;returnOK;}/*判空*/intStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}/*出栈*/intPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}/*入栈*/intPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+Stack_MoreNUM)*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base+S.stacksize;S.stacksize+=Stack_MoreNUM;}*S.top++=e;returnOK;}/*拓扑排序*/intTopoSort(ALGraphG,AdjListTemp,structNamename[]){inti,k,j=0,count,indegree[MAX_VERTEX_NUM];SqStackS;ArcNode*p;FindInDegree(G,indegree);//对各顶点求入度InitStack(S);//初始化栈for(i=0;iG.vexnum;++i)//建零入度顶点栈Sif(!indegree[i])Push(S,i);//入度为0者进栈count=0;//对输出顶点计数while(!StackEmpty(S)){Pop(S,i);printf(%s(%d分),,G.vertices[i].data,G.vertices[i].grades);Temp[j++]=G.vertices[i];//将当前的拓扑序列保存起来++count;//输出i号顶点并计数for(p=G.vertices[i].firstarc;p;p=p-nextarc)//对i号顶点的每个邻接点的入度减1{k=p-adjvex;if(!(--indegree[k]))//若入度减为0,则入栈Push(S,k);}}if(countG.vexnum){printf(此有向图有回路无法完成拓扑排序);returnERROR;}elseprintf(为一个拓扑序列);printf(\n);intq=1,Z=0;while(q=TotalTerms){intC=Temp[Z].grades;printf(\n第%d