数据结构与算法课程设计说明书-教学计划编制问题

PAGEPAGE1数据结构与算法课程设计说明书

学院、系：软件学院专业软件工程设计题目：教学计划编制问题1需求分析1.1程序的功能大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。本程序针对本科的学期内容，通过输入实际的课程及先后关系。结合每学期的学分及课程数，制定好学习计划。在输入相关数据后，程序会安排好每学期的课程。1.2.输入输出的要求输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。2概要设计ClearStack（）：清空栈StackEmpty（）：判断是否为空栈Pop（）：出栈Push（）：入栈TopologicalSort（）：输出G顶点的拓扑排序结果储存的数据为结构体类型数组，以及结构体单链表结点类型。3详细设计采用c语言定义相关的数据类型：字符常量，整型，字符型，字符串型，typedef定义的类型，结构体型，单链表节点类型，结构体数组。StackEmpty判断栈是否为空。若栈S为空栈，则返回TRUE，否则返回FALSEPop出栈。若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。Push入栈。插入元素e为新的栈顶元素。TopologicalSort输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。4编码单元测试4.1测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。数据如下：学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。19194212210113657884.2使用说明输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对学分值输入完成后执行可得到每个学期的课程结果5心得体会虽然在大一我们已经学习了C语言，但是，直到本期我们才开设了数据结构这一门课程。这门课程让我们对程序的原理有了系统的认识。对以往模糊的经验，起了总结提升的作用。在学习了这门课程后，我们进行了2个星期的课程设计，以实践我们的学习内容。在这次课程设计中，我被分配到了教学计划课程编制问题，开始感觉很难，因为我从未编写过如此复杂的程序。在多方查找资料并参考类似程序后，我大体将程序的构架描绘好了。一边对照着网上的资料，一边对程序进行修改补充，然后根据拟好的大纲进行编制。期间，我与其它同学进行了讨论和探究，对程序的细节问题和应用方面进行了探索，并解决了主要的问题，于是便着手写具体的程序。这次实验，我进行了大量的资料查阅，包括向老师请求帮助解释题目要求，对所学知识进行复习。通过这些努力，我对算法有了更深入的理解，对编程的步骤，有了具体的体会。通过和同学的广泛交流，我体会到了合作的必要性及合作的优势。更重要的是，这个课题完全脱胎于实际问题，让我对计算机行业，充满了信心和自豪。以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景，而较少注重我们对算法的实践锻炼。而这一次的实习既需要我们去联系理论，又需要我们去实践方法，很多东西看上去都学过，但是和实际联系才知道变通的艰难。纸上得来终觉浅，这是我这次实习的最大收获。这次的实验让我们知道该如何跨过实际和理论之间的鸿沟。通过这次课设，我认识到了以下几方面第一就是要合作。不懂的问题一定要向同学，老师请教。这样才能集思广益，有利于问题的解决。也能够让自己节省时间，有效率的完成工作。齐心协力完成这个程序，互相帮助，这是我们同做课题的同学的共同体会。第二就是要细心。程序的编制难免会出现错误，不能一次成功，出现错误后，一定要认真细心耐心的排查，这样千锤百炼，程序才能完成。在浮躁的时候能够静下心来思考，是极其重要的。第三就是要学习。学习网上已经有的类似程序，学习他们的方法与思想。这样，才能最快的了解问题，得到启迪。这两个星期的课程设计，让我受益匪浅。它不只对我们专业知识进行了加强，还锻炼了我们的思维能力，合作的精神，是我们理论与实际想结合。这些都是在书本上难以学习到的。这些弥足珍贵的经验和记忆，使我对我的未来从事的工作充满了信心，而最终程序的运行成功使我得到了莫大的满足。在日后的学习中，我会更加重视知识的积累，学好算法，为成为一名优秀的计算机专业人才努力。附录voidClearStack(SqStack*S)//清空栈的操作{ S->top=S->base;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusPop(SqStack*S,SElemType*e){/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee){/*插入元素e为新的栈顶元素*/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;}typedefintpathone[MAXCLASS];typedefintpathtwo[MAXCLASS];StatusTopologicalSort(ALGraphG){/*有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,*//*否则返回ERROR。*/inti,k,j=0,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1]*/InitStack(&S);/*初始化栈*/for(i=0;i<G.vexnum;++i)/*建零入度顶点栈S*/if(!indegree[i]) {Push(&S,i); //cout<<*G.vertices[i].data<<endl; } /*入度为者进栈*/count=0;/*对输出顶点计数*/while(!StackEmpty(S)){/*栈不空*/Pop(&S,&i);a[i]=*G.vertices[i].data;b[i]=*G.verticestwo[i].data;printf("课程%s→学分%s",G.vertices[i].data,G.verticestwo[i].data);/*输出i号顶点并计数*/++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){/*对i号顶点的每个邻接点的入度减*/k=p->adjvex;if(!(--indegree[k]))/*若入度减为,则入栈*/ {Push(&S,k); //cout<<*G.vertices[i].data<<endl; }}}if(count<G.vexnum){printf("此有向图有回路\n");returnERROR;}else{printf("为一个拓扑序列。\n"); has=true;} FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1]*/ ClearStack(&S); printf("======================课程计划如下===============================\n"); intqq=1;//学期数 intxxf; while(qq<=xqzs) { intresult[20]; intrtop=0; intnn=0; xxf=0; for(i=0;i<G.vexnum;++i)/*建零入度顶点栈S*/ { if(0==indegree[i]) { Push(&S,i); } } while(!StackEmpty(S)) { intbb; Pop(&S,&i); bb=atoi(G.verticestwo[i].data); xxf=xxf+bb; if(xxf>xfsx) { break; } indegree[i]--; for(p=G.vertices[i].firstarc;p;p=p->nextarc) {/*对i号顶点的每个邻接点的入度减*/ k=p->adjvex; indegree[k]--; } result[rtop]=i; rtop++; } printf("第%d个学期的课程为:\n",qq); for(nn=0;nn<rtop;nn++) { //printf("课程"G.vertices[result[nn]].dataendl); printf("课程%s\n",G.vertices[result[nn]].data); } qq++; }returnOK;}intmain(){AL