教学计划编排问题

西安财经学院信息学院《数据结构》课程设计报告课程设计名称教学计划编排问题实验室完成日期2018.12.1一、需求分析【问题描述】大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。【基本要求】（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。【测试数据】学期总数：8；学分上限：10；该专业共开设课数：16课程号：C01C02C03C04C05C06C07C08C09C10C11C12C13C14C15C16学分顺序：2343234445442323先修关系如下表：C01C02C04C03C12C02C03C03C05C07C08C04C05C05C07C06C08C07无C08无C09C10C11C12C10C12C11C06C12无C13C11姓名蒲茜学号1705990111班级计算机1701年级2017级指导教师杨新安【实现提示】可设学期总数不超过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；C14C13C15C13C11C16C1506110114120708021003161305040915voidClearStack(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;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;}}}//出栈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;iG.vexnum;++i){scanf(%s,G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf(请输入%d个课程的学分值:\n,(G).vexnum);for(i=0;iG.vexnum;++i){scanf(%s,G.vertices2[i].data);}printf(请顺序输入每条弧的弧尾和弧头(以空格作为间隔):\n);for(k=0;kG.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;}函数调用关系图：四、调试分析遇到的最大困难应该是算法的设计，因为平时学的比较死板，遇到这种设计作业就摸不着头脑。刚开始会就不停的复习栈，图，拓扑排序。但还是没有思路，翻阅了一些书籍，并在网上搜索了有关拓扑排序的算的大体思路，经过好几天的不断修改和调试，才完成了这个算法。设计的过程中还是存在很多问题。有时候程序运行到一半就自动闪退了，可能的是存储空间的问题，改了存储位置之后就好了。测试结果及分析：主界面设计输入需要输入的数据还算较多的，包括学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。弧尾和弧头指的是先修关系。TopologicalSortArcNode*pCreateGraphMain函数FindIndegreeInitStackPushStackemptyPop输入完所有的数据之后就会显示输出：因为有两种编排策略，程序运行一半后就会让用户选择策略，一是各个学期的学习负担平均，二是课程集中在前几个学期中。用户选择后，就会有相应的输出，之后可选择是否继续。结束程序：五、设计总结这次设计相对于我来说有点困难，需要查询很多资料，询问同学，巩固学过的知识，直到设计完成对数据结构也有了新的理解，虽然在这个设计上投入了很多，但也只能完成课题的基本要求，对于选做要求，我可能还要累计更多的知识和实践来完成。我觉得实践比理论要重要的多，在你学习到基本的知识后你不去试着编程，就像是纸上谈兵一样，没多大作用。我会尽量做好每个设计，减少程序中常见的语法错误，逻辑错误，减少调试分析的次数，解决问题更加细心认真些。这个程序还是有不足的，界面看上去不太美观，可以设计的更简洁一些。要输入很多数据，而且分的步数也多输入的时候容易出错，我就是输入了好几遍才完成整个程序的运行，还是要求用户细心些六、源程序清单#includestring.h#includestdio.h#includestdlib.h#includemath.h#includeiostreamusingnamespacestd;#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;iG.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;iG.vexnum;++i){scanf(%s,G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf(请输入%d个课程的学分值:\n,(G).vexnum