教学计划编排问题

...wd......wd......wd...姓名蒲茜学号姓名蒲茜学号1705990111班级计算机1701年级2017级指导教师杨新安《数据构造》课程设计报告课程设计名称教学方案编排问题实验室完成日期2018.12.1一、需求分析【问题描述】大学的每个专业都要制订教学方案。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学方案编制程序。【根本要求】〔1〕输入参数包括：学期总数，一学期的学分上限，每门课的课程号〔固定占3位的字母数字串〕、学分和直接先修课的课程号。〔2〕允许用户指定以下两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。〔3〕假设根据给定的条件问题无解，则报告适当的信息；否则，将教学方案输出到用户指定的文件中。方案的表格格式自行设计。【测试数据】学期总数：8；学分上限：10；该专业共开设课数：16课程号：C01C02C03C04C05C06C07C08C09C10C11C12C13C14C15C16学分顺序：2

3

4

3

2

3

4

4

4

5

442323先修关系如下表：C01C02C04C03C12C02C03C03C05C07C08C04C05C05C07C06C08C07无C08无C09C10C11C12C10C12C11C06C12无C13C11C14C13C15C13C11C16C150504050402020701070103030808121206100906100911141114161613131515【实现提示】可设学期总数不超过10，课程总数不超过60。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建设内部课程号与课程号之间的对应关系。二、概要设计抽象数据类型描述：typedefstructArcNode{}ArcNode;表节点〔弧构造〕；typedefstruct{}VNode,AdjList[MAX_VERTEX_NUM];头结点；typedefstruct{}ALGraph;图构造；intLocateVex(ALGraphG,VertexTypeu)操作结果:假设G中存在顶点u,则返回该顶点在图中位置;否则返回-1；StatusCreateGraph(ALGraph&G)采用邻接表存储构造,构造没有相关信息的图G(用一个函数构造种图)；voidDisplay(ALGraphG)输出图的邻接矩阵G

；voidFindInDegree(ALGraphG,intindegree[])求顶点的入度；typedefstructSqStack{}SqStack;顺序栈；StatusInitStack(SqStack*S)构造一个空栈S；voidClearStack(SqStack*S)清空栈的操作；StatusStackEmpty(SqStackS)假设栈S为空栈，则返回TRUE，否则返回FALSE

；StatusPop(SqStack*S,SElemType*e)假设栈不空，则删除S的栈顶元素，用e返回其值，并返回O:否则返回ERROR

；StatusPush(SqStack*S,SElemTypee)插入元素e为新的栈顶元素；Statuszxf(ALGraphG)求大学所有课程总学分；StatusTopologicalSort(ALGraphG)程序的核心函数：有向图G采用邻接表存储构造，假设G无回路,则按用户选择的方案输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR；intmain()主函数；主程序模块功能模块图：主程序模块拓扑排序图的定义与操作栈的定义和操作拓扑排序图的定义与操作栈的定义和操作输出顶点删除顶点和弧图的邻接表存储输出顶点删除顶点和弧图的邻接表存储构造图求图中各个节点的入度栈的顺序存储构造栈出栈入栈三、详细设计存储构造及宏定义：#defineMAX_VERTEX_NUM100#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2图的邻接表存储：typedefstructArcNode{//弧构造；intadjvex;//该弧所指向的顶点的位置;structArcNode*nextarc;//指向下一条弧的指针;}ArcNode;//表结点;typedefstruct{AdjListvertices,vertices2;//分别存课程名和学分；intvexnum,arcnum;intkind;}ALGraph;栈的顺序存储：typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;算法设计：//对各顶点求入度indegreevoidFindInDegree(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;}}}//出栈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;}//构造图GStatusCreateGraph(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;}Main函数Main函数CreateGraphCreateGraphTopologicalSortTopologicalSortInitStackArcNode*pFindIndegreePInitStackArcNode*pFindIndegreePushStackemptyPop四、调试分析遇到的最大困难应该是算法的设计，因为平时学的比拟死板，遇到这种设计作业就摸不着头脑。刚开场会就不停的复习栈，图，拓扑排序。但还是没有思路，翻阅了一些书籍，并在网上搜索了有关拓扑排序的算的大体思路，经过好几天的不断修改和调试，才完成了这个算法。设计的过程中还是存在很多问题。有时候程序运行到一半就自动闪退了，可能的是存储空间的问题，改了存储位置之后就好了。测试结果及分析：主界面设计输入需要输入的数据还算较多的，包括学期总数，一学期的学分上限，每门课的课程号〔固定占3位的字母数字串〕、学分和直接先修课的课程号。弧尾和弧头指的是先修关系。输入完所有的数据之后就会显示输出：因为有两种编排策略，程序运行一半后就会让用户选择策略，一是各个学期的学习负担平均，二是课程集中在前几个学期中。用户选择后，就会有相应的输出，之后可选择是否继续。完毕程序：五、设计总结这次设计相对于我来说有点困难，需要查询很多资料，询问同学，稳固学过的知识，直到设计完成对数据构造也有了新的理解，虽然在这个设计上投入了很多，但也只能完成课题的根本要求，对于选做要求，我可能还要累计更多的知识和实践来完成。我觉得实践比理论要重要的多，在你学习到根本的知识后你不去试着编程，就像是纸上谈兵一样，没多大作用。我会尽量做好每个设计，减少程序中常见的语法错误，逻辑错误，减少调试分析的次数，解决问题更加细心认真些。这个程序还是有缺乏的，界面看上去不太美观，可以设计的更简洁一些。要输入很多数据，而且分的步数也多输入的时候容易出错，我就是输入了好几遍才完成整个程序的运行，还是要求用户细心些六、源程序清单#include<string.h>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<iostream>usingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;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;}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;}printf("请问您想使学生在各学期中的学习负担尽量均匀〔输入1〕\n");printf("还是想使课程尽可能地集中在前几个学期中〔输入2〕\n");intpattern;printf("请选择(1or2):");scanf("%d",&pattern);FindInDegree(G,indegree);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=