教学计划编排问题文档良心出品

课程设计名称需求分析〖问题描述〗西安财经学院信息学院《数据结构》课程设计报告姓名蒲茜学号1705990H1计算机1701年级2017级指导教师杨新安教学计划编排1司题实验室 完成日期201&120大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系：每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。〖基本要求〗（0输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号：允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前且个学期中。若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中：计划的表格格式自行设计。〖测试数据〗学期总数：&学分上限：10；该专业共开设课数：16课程号：C01C02C03〔04〔05C06C07COSC09C10以1〔12C13C14C15C16学分顺序：2343234季45442323先修关系如下表：C01C02C04C03口2CO2〔03CO3C05〔07C08CO4〔05CO5〔07CO6C08CO7无CO8CO9C10CllC12C10〔12C11〔06C12无C13C14〔13C15〔13CllC16C15〖实现提示〗可设学期总数不超过10，课程总数不超过60。如果输入的先修课程号不在该专业开设的课程序列中，贝刂作为错误处理：应建立内部课程号与课程号之间的对应关系：概要设计抽象数据类型描述：typedefstructArcNode(}ArcN0de,表节点（弧结构）．typedefstruct{}VNode,Ad_iListCMAXVERTEX〕《头结点：typedefstruct{}ALGraph,图结构；intLocateVex(ALGrabh0VertexTypeu)操作结果若G中存在顶点u，则返回该顶点在图中位置，否则返回一1StatusCreateGraph(ALGraph(G)采用邻接表存储结构，构造没有相关信息的图GC用一个函数构造种图）：“Display(ALGraphG）输出图的邻接矩阵GvoidFindlnDegree(ALGraphG,intindegree的求顶点的入度typedefstructSqStack(}SqStack,顺序栈；StatusInitStack(SQStack(S)构造一个空栈S；voidClearstack(sqstack(S)清空栈的操作；StatusStackEmpty(SqStackS〕若栈S为空栈，则返回TRUE，否则返回FALSEStatusPop(SQStack*S,SEIemType*e）若栈不空，则删除S的栈顶元素，用e返回其值，并返回0否则返回ERRORStatusPush(SqStack*S,SEIemTypee)插人元素e为新的栈顶元素；statuszxf(ALGraphG）求大学所有课程总学分；Status丁。“1。过calS“t（ALGE“hG〕程序的核心函数：有向图G采用邻接表春储结构，若G无回路，则按用户选择的方案输出G的顶点的一个拓扑序列并返回0K，否则返回ERROR;mn()mn()主数；、详细设计存储结构及宏定义：#defineMAXVERTEXNUM100*defineSTACKINITSIZE10#defineSTACKINCREIMENT2图的邻接表存储typedefstruct、ArcNode{ ／/弧结构；Intadjvex,//该弧所指向的顶点的位置，structArcNode*nextarc,/／指向下一条弧的指针．}ArcNode, //表结点typedefstruct{AdListvertices,vertxces2,1ntvexnum,arcnum;intkind,}ALGraph.typedefstructSQStackSEIemType*baseSEIemTyoe*top,intstacksize,}SQStack.indegreevoidFindlnDegree(ALGraphG,1ntindegree1nti,ArcNode*p;for(i—O,i(G.vexnum;i++)indegreeCiJfor(i—O,i(G.vexnum;i++){p=G.verticesi].firstarc;while(p){indegreeindegreecpStatusPop(SQStack*S,SEIemTyoe*e){if((*S).top—(*S).base)returnERROR,—(*S).top;return0K,//ABStatusPush(SqStack*S,SEIemTypee){if((*S).top—(*S).(*S).stacksize){(*S).base=(SEIemTyperealloc((*S).base,((*S).stacksize+STACKlNCREME.NT)*sizeof(SEIemType))if(l(*S).base)ex-it(OVERFLOW),(*S).too¯(*S).base+(*S).stacksize,(*S).stacksize+-STACKINCREMENT*((*S).top)-H-:r-ereturn0K,StatusCreateGraph(ALGraph&G){inti,inti,j,k,vexnum),G.verticesci].flrstarc=NULLprintf("Låå6üA%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) sca.nf VI,v?);i±LocateVex(G,VI),J=LocateVex(G,v2)(ArcNode*)malloc(sizeof(ArcNode)),p>adjvex=Jinfo=NULL,p>nextarc=G.vertices[i].firstarc;G.vertices[i].firstarcPP，return0K函数调用关系图：四、调试分析遇到的最大困难应该是算法的设计，因为平时学的比较死板，遇到这种设计作业就摸不着头脑。刚开始会就不停的复习栈，图，拓扑排序。但还是没有思路，翻阅了一些书籍，并在网上搜索了有关拓扑排序的算的大体思路，经过好几天的不断修改和调试，才完成了这个算法。设计的过程中还是存在很多问题。有时候程序运行到一半就自动闪退了，可能的是存储空间的问题，改了春储位置之后就好了。测试结果及分析：主界而设计输入需要输入的数据还算较多的，包括学期总数，一学期的学分上限，每门课的课程号〔固定占3位的字母数字串），学分和直接先修课的课程号。弧尾和弧头指的是先修关系。输输入完所有的数据之后就会显示输出；因为有两种编排策略，程序运行一半后就会让用户选择策略，一是各个学期的学习负担平均，二是课程集中在前丿L个学期中。用户选择后，就会有相应的输出，之后可选择是否经续。《《。结束程序：五、设计总结这次设计相对于我来说有点困难，需要查询很多资料，询问同学，巩固学过的知识，直到设计完成对数据结构也有了新的理解，虽然在这个设计上投入了很多，但也只能完成课题的基本要求，对于选做要求，我可能还要累计更多的知识和实践来完成。我觉得实践比理论要重要的多，在你学习到基本的知识后你不去试着编程，就像是纸上谈兵一样，没多大作用．我会尽量做好每个设计，减少程序中常见的语法错误，逻辑错误，减少调试分析的次数，解决问题更加细心认真些。这个程序还是有不足的，界面看上去不太美观，可以设计的更简洁一些。要输人很多数据，而且分的步数也多输入的时候容易出错，我就是输入了好且遍才完成整个程序的运行，还是要求用户细心些六、源程序清单#xnclude〈string.h)#include〈stdio.h>#xnclude〈stdllb.h)#include〈math．h>#1nclude<lostream>namespaceStd#defxneTRUE1#defineFALSE0#define0K1*defineERROR0#defxneINFEASIBLE一1typedefintStatus,typedefintBoolean*define讥监N正10#defme讥CLASS《用0int2一0，intX二0：intterm冂n，credit1过m，0亡1，typedefintInfoTypertypedefcharVertexType簋XN伍〕#define讥VERTEXNUM100typedefenum{DG}GraphKxnd,typedefstructArcNode[intad:vex，structArcNode*nextarcInfoType冰info}ArcNode,typedefstruct{VertexTypedata,ArcNode*firstarc;}VN0de,AdjListCWXVERTEXNUM)typedefstruct{AdjLxstvertices,vertices2,intvexnum,arcnum;intkind,}ALGraph,intLocateVex(Al-GraphG,VertexTypeu)int1,for(1=0;i(G.vexnum;++i)if(strcmp(u,G.verticesi.data)return1;return—1, StatusCreateGraph(ALGraph {int1,j,kVertexTypev1,v2;ArcNode*p;printf:: scanf G.vexnum)scanf G.arcnum)printf(AllCOL).\n»,G.vexnum)for(1—O;i(G.vexnum;++i){scanf("%s",G.verticesi).data), G.vertices .firstarc=NULL•printf:,(G).vexnum);:for(i=0;i(G.vexnum,++i){scanf("%s",G.vertices2Ci].data)for(k=0;k<G.arcnum,++k){scanf VI,v?)1=LocateVex(G,VI)j=LocateVex(G,v2),p(ArcNode*)malloc(sizeof(ArcNode))pp->info-NULL,G.verticesi.furstarc,G.verticesi].firstarcp,returnOK,voidDisplay(ALGraphG){int1•ArcNode*p,switch(G.kind){caseDG:printf("filfiJA\n"),\n",G.vexnum),for(1=0;i(G.vexnum;++i)N,G.verticesi).data)%GJL:\n",G.arcnum)for(i—O;i(G.vexnum;i++){p=G.vertices1J.firstarc;while(p){printfarc,,G.vertaces[iJ.data,G.verticesdata),arc,voidFindlnDegree(Al-GraphG,intindegreeCJ)int1•ArcNodefor(1=0;i(G.vexnum;i++)indegreeifor(1=0;i<G.vexnum;i++){p=G.verticesi).firstarc,while(p){typedefintSEIemType,*defineSTACKINITSIZE10#defineSTACKINCREMENT2typedefstructSqStackSEIemType*baseSEIemlype*top,intstacksize;}SOStack,StatusInitStack(SQStack*S)(*S).base=(SEIemType(STACKINITSIZE*sizeof(SEIemType))if(!(*S).base)t(OVERFLOW)(*S).top:(*S).base,(*S).stacksize=STACKINITSIZE;return0KvoidClearStack(SqStack*S)>base,StatusS)if(S.top—S.base)returnTRUE,elsereturnFALSE,StatusPap(SqStack*S,SEIemType*e){if((*S).top—(*S).base)returnERROR,—(*S).top,StatusPush(SqStack SEIemTypee){if((*S).top—(*S).base>¯(*S).stacksize){(*S).base—(SEIemTyperealloc((*S).base,((*S).stacksize+STACKINCREMELVT)*sizeof(SEIemType)),if(!(*S).base)exit(OVERFLOW)(*S).top:(*S).base+(*S).stacksize,(S).stacksize+±STACKINCREMENT,*((*S).top)++±e,return0KStatuszxf(ALGraphG){intz=0;for(1nti=O,i<G.vexnum;i++)z+=atoi(G.vertices2[iJ.data)•returnz;typedefintpathone,typedefintpathtwo[MAXCLASSNUM]StatusTopologicalSort(Al-GraphG){int1,k,count,indegreeCMAXVERTEXNUM]boolhas¯false,SqStackS,pathonea,pathtwob;ArcNode*p,FindlnDegree(G,indegree)InitStack('S),for(1=0;i<G.vexnum;++i){if(!indegree[i])Push(&S,i)countOwhiPopcountOwhiPopdata,printfG.verticesCiJ.data,G.vertices2[iJ.data),for(p=G.verticesci].firstarcp;p=p—>nextarc)(if(!("indegree[k]))Push(&S,k)if(count<G.vexnum){printfreturnERROR;elseprintf("%has¯true,intpattern;or2).,scanf("%d",&pattern);FindlnDegree(G,FindlnDegree(G,indegree);ClearStack(&S)G.vexnumtermnumzxf(G)/termnumwhile(xq<=term_