教学计划编制问题

PAGEPAGE1软件学院课程设计报告书课程名称数据结构设计题目教学计划编制问题专业班级学号姓名指导教师2013年1月目录1设计时间 22设计目的 23设计任务 24设计内容 24.1需求分析 24.2总体设计 34.3详细设计 64.4测试与分析 124.4.1测试 124.4.2分析 144.5附录 165总结与展望 276参考文献 281设计时间2013年1月21日2013年1月27日2设计目的了解并掌握数据结构预算法的设计算法，具备初步的独立分析和设计能力。提高综合运用所学理论知识和方法独立分析和解决问题的能力。掌握面向实际背景思考问题的方法。对于学生基本程序设计素养的培养和软件工作者工作作风的训练，起到显著的促进作用3设计任务掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽量可能地集中在前几个学期中。若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到屏幕。计划的表格格式自行设定。4设计内容4.1需求分析1、程序所能达到的功能：为用户编排课程,根据用户输入的信息来编排出每学期要学的课程。2、输入的形式和输入值的范围：学期总数：6；学分上限：30；该专业共开设12门课，课程号从S1到S12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系源自软件学院部分实际课程。3、测试数据及程序运行情况预测:编排方法输出结果为:

第一学期学的课程有:高等数学程序设计基础

第二学期学的课程有:大学物理上线性代数离散数学

第三学期学的课程有:数据结构概率论大学物理下

第四学期学的课程有:数据库

第五学期学的课程有:JAVA语言的设计和分析

第六学期学的课程有:编译原理

4.2总体设计内容包括：1.本程序中用到的所有抽象数据类型的定义如下:ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:

R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作P:intCreateGraph(ALGraph*pGraph);voidFindInDegree(ALGraphG,intindegree[])intTopoSort(ALGraphG,AdjListTemp)}ADTGraph栈的定义:ADTStack{

数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}

数据关系:R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}基本操作:intInitStack(SqStack*pStack)intStackEmpty(SqStackS)intPop(SqStackS,SElemTypee)intPush(SqStackS,SElemTypee)}ADTStack2.各程序模块之间的层次（调用）关系如图1所示：图13函数调用关系如图2所示：图24.主程序voidmain(){ALGraphG;AdjListTemp;OUTPUT();printf("**********教学计划编制问题**********\n");printf("请输入学期总数:");scanf("%d",&TotalTerms);printf("请输入学期的学分上限:");scanf("%d",&MaxScores);CreateGraph(&G);Display(&G);TopoSort(G,Temp);printf("\nOK\n");getchar(); }4.3详细设计一个栈对入度为零的顶点进行存放。根首先利用拓扑排序对课程先后顺序进行分析，邻接表为主要存储结构，栈为主要辅助结构，给出课程之间的先后有关系比如AOE网，然后进行拓扑排序，但当有向图中存在环时无法查找该图的的拓扑排序，当图中的所有顶点全部输出，表示对该图排序成功，实现拓扑排序算法时，相应的建立邻接表存储AOE网，为了避免重复检验入度为零的顶点，建立据课程的先后关系，对各学期的的课程进行排序，输出。（这是运用图的拓扑排序对课程先修排列的实现，并调用递归完成拓扑排序。内容包括：第一部分:数据类型定义#include<stdio.h>#include<math.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineMAX_NAME3#defineMAXCLASS100//顶点字符串的最大长度#defineMAX_VERTEX_NUM100//最大顶点数#defineN12typedefcharVertexType[MAX_NAME];intTotalTerms;//学期总数intMaxScores;//学分上限/*图的邻接表存储表示*/typedefstructArcNode{intadjvex; //该弧所指向的顶点的位置弧的节点结构structArcNode*nextarc; //指向下一条弧的指针}ArcNode; //链表结点typedefstructVNode //顶点结构{ //链接表VertexTypedata;//顶点信息intgrades;//存储学分信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstructALGraph //图结构{AdjListvertices;//vertices存储课程名应包含邻接表intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;第二部分:查找图中某个顶点位置并采用邻接表存储结构存储图intLocateVex(ALGraphG,VertexTypeu)/*查找图中某个顶点位置*/{inti;for(i=0;i<G.vexnum;++i) {if(strcmp(u,G.vertices[i].data)==0)returni;}return-1;}intCreateGraph(ALGraph*pGraph)/*采用邻接表存储结构*/{inti,k;VertexTypeva;ArcNode*pNode;printf("请输入教学计划的课程数:");scanf("%d",&pGraph->vexnum);printf("请输入各个课程的先修课程的总和(弧总数):");scanf("%d",&pGraph->arcnum);printf("请输入%d个课程的课程号(最多%d个字符,数字+字母)和学分值\n",pGraph->vexnum,MAX_NAME);for(i=0;i<pGraph->vexnum;++i){printf("课程号:");scanf("%s",&pGraph->vertices[i].data);printf("学分值:");scanf("%d",&pGraph->vertices[i].grades);pGraph->vertices[i].firstarc=NULL;}printf("\n请输入下列课程的先修课程(无先修课程输入0结束后也输入0)\n");for(k=0;k<pGraph->vexnum;++k)//构造表结点链表,利用前插法{printf("%s的先修课程:",pGraph->vertices[k].data);scanf("%s",&va);while(va[0]!='0'){i=LocateVex(*pGraph,va); //弧头 //增加对返回值的校验，因为输入的课程代码有可能找不到if(i<0){;//如果未找到应如何处理？}pNode=(ArcNode*)malloc(sizeof(ArcNode));//弧尾pNode->adjvex=k;pNode->nextarc=pGraph->vertices[i].firstarc;//插在表头pGraph->vertices[i].firstarc=pNode;scanf("%s",va);}}returnOK;}第三部分;对图的拓扑排序intTopoSort(ALGraphG,AdjListTemp)/*拓扑排序*/{inti,k,j=0,count,indegree[MAX_VERTEX_NUM];intq=1,Z=0;SqStackS;ArcNode*p;FindInDegree(G,indegree);//对各顶点求入度InitStack(&S);//初始化栈for(i=0;i<G.vexnum;++i)//建零入度顶点栈S {if(!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号顶点并计数 //对i号顶点的每个邻接点的入度减1 for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k]))//若入度减为0,则入栈Push(S,k);}}if(count>G.vexnum){printf("此有向图有回路无法完成拓扑排序\n");returnERROR;}elseprintf("为一个拓扑序列\n");while(q<=TotalTerms){intC=Temp[Z].grades;printf("\n第%d个学期应学课程:",q);while(C<=MaxScores){C=C+Temp[Z+1].grades;if(Z<G.vexnum){OutputNameByCode(Temp[Z].data);++Z;}}printf("\n");if(q==TotalTerms)printf("\n课程编制完成!");q++;}returnOK;}第四部分:编写主程序voidmain(){ALGraphG;AdjListTemp;OUTPUT();printf("**********教学计划编制问题**********\n");printf("请输入学期总数:");scanf("%d",&TotalTerms);printf("请输入学期的学分上限:");scanf("%d",&MaxScores);CreateGraph(&G);Display(&G);TopoSort(G,Temp);printf("\nOK\n");getchar(); }4.4测试与分析4.4.1测试栈对入度为零的顶点进行存放。首先利用拓扑排序对课程先后顺序进行分析，邻接表为主要存储结构，栈为主要辅助结构，给出课程之间的先后有关系比如AOE网，然后进行拓扑排序，得出教学计划编制结果。程序开始界面如图3所示：图32、学期数、学分上限、课程序号等信息输入如图4所示、：图43、课程先修顺序如图5所示：图54、程序输出结果如图6所示:图65、测试结论给出课程之间的先后有关系比如AOE网，然后进行拓扑排序，但当有向图中存在环时无法查找该图的的拓扑排序，当图中的所有顶点全部输出，表示对该图排序成功（这是运用图的拓扑排序对课程先修排列的实现，并调用递归完成拓扑排序。6、说明问题实现拓扑排序算法时，相应的建立邻接表存储AOE网，为了避免重复检验入度为零的顶点，建立据课程的先后关系，对各学期的的课程进行排序，输出。4.4.2分析内容包括：1.实验中出现的问题以及解决方法:我在实验过程中遇到的最大难题是课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过几天天的修改，终于写出了符合要求的排序算法。2.算法的时间复杂度的分析。求各顶点入度的时间复杂度是O(e)，即边的个数。

建零入度顶点栈的时间复杂度是O(n)，即顶点的个数。

每个顶点都需要进一次栈，出一次栈，然后把入度减一。执行的总次数也是边的个数。

所以时间复杂度是O(n+e)。4.5附录源程序代码及必要注释。#include<stdio.h>#include<math.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineMAX_NAME3#defineMAXCLASS100//顶点字符串的最大长度#defineMAX_VERTEX_NUM100//最大顶点数#defineN12typedefcharVertexType[MAX_NAME];intTotalTerms;//学期总数intMaxScores;//学分上限/*图的邻接表存储表示*/typedefstructArcNode{intadjvex; //该弧所指向的顶点的位置弧的节点结构structArcNode*nextarc; //指向下一条弧的指针}ArcNode; //链表结点typedefstructVNode //顶点结构{//链接表VertexTypedata;//顶点信息intgrades;//存储学分信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstructALGraph //图结构{AdjListvertices;//vertices存储课程名应包含邻接表intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;constchar*CourseCodes[N]={"S1","S2","S3","S4","S5","S6", "S7","S8","S9","S10","S11","S12"};constchar*CourseNames[N]={"程序设计基础","大学物理下","数据库","离散数学","语言的设计和分析","概率论","编译原理","JAVA","高等数学","线性代数","大学物理上","数据结构"};voidOUTPUT(){//ints;printf("\t\t欢迎使用教学计划编制系统\n");printf("\t\t请您根据系统提示按需求输入相关信息\n");printf("\n");printf("\t\t教学计划编制菜单\n");printf("\t\t课程代码|课程名称|优先课程\n");printf("\t\tS1|程序设计基础|无\n");printf("\t\tS2|大学物理下|S1\n");printf("\t\tS3|数据库|S1，S2\n");printf("\t\tS4|离散数学|S1\n");printf("\t\tS5|语言的设计和分析|S3，S4\n");printf("\t\tS6|概率论|S11\n");printf("\t\tS7|编译原理|S5，S3\n");printf("\t\tS8|JAVA|S3，S6\n");printf("\t\tS9|高等数学|无\n");printf("\t\tS10|线性代数|S9\n");printf("\t\tS11|大学物理上|S9\n");printf("\t\tS12|数据结构|S9,S10,S1\n");}/*查找图中某个顶点位置*/intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i<G.vexnum;++i) { if(strcmp(u,G.vertices[i].data)==0) returni; }return-1;}/*采用邻接表存储结构*/intCreateGraph(ALGraph*pGraph){//ALGraphG;inti,k;VertexTypeva;ArcNode*pNode;//G=*F;printf("请输入教学计划的课程数:");scanf("%d",&pGraph->vexnum);printf("请输入各个课程的先修课程的总和(弧总数):");scanf("%d",&pGraph->arcnum);printf("请输入%d个课程的课程号(最多%d个字符,数字+字母)和学分值\n",pGraph->vexnum,MAX_NAME);for(i=0;i<pGraph->vexnum;++i) { printf("课程号:"); scanf("%s",&pGraph->vertices[i].data); printf("学分值:"); scanf("%d",&pGraph->vertices[i].grades); pGraph->vertices[i].firstarc=NULL; }printf("\n请输入下列课程的先修课程(无先修课程输入0结束后也输入0)\n");for(k=0;k<pGraph->vexnum;++k)//构造表结点链表,利用前插法 { printf("%s的先修课程:",pGraph->vertices[k].data); scanf("%s",&va); while(va[0]!='0') { i=LocateVex(*pGraph,va); //弧头//增加对返回值的校验，因为输入的课程代码有可能找不到if(i<0) { ;//如果未找到应如何处理？ }//弧尾 pNode=(ArcNode*)malloc(sizeof(ArcNode)); pNode->adjvex=k; pNode->nextarc=pGraph->vertices[i].firstarc;//插在表头 pGraph->vertices[i].firstarc=pNode; scanf("%s",va); } }returnOK;}/*输出图G的信息*/voidDisplay(ALGraph*pGraph){inti;ArcNode*pNode;printf("有向图\n");printf("%d个顶点",pGraph->vexnum);for(i=0;i<pGraph->vexnum;++i)printf("%4s",pGraph->vertices[i].data);printf("\n%d条弧边:\n",pGraph->arcnum);for(i=0;i<pGraph->vexnum;i++) { pNode=pGraph->vertices[i].firstarc; while(pNode) { printf("%s>%s\n",pGraph->vertices[i].data, pGraph->vertices[pNode->adjvex].data); pNode=pNode->nextarc; } }}/*求顶点的入度*/voidFindInDegree(ALGraphG,intindegree[]){inti;ArcNode*pNode;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){pNode=G.vertices[i].firstarc; while(pNode) { indegree[pNode->adjvex]++; pNode=pNode->nextarc; }}}voidOutputNameByCode(char*theCode){inti;for(i=0;i<12;i++) { if(strcmp(theCode,CourseNames[i])==0) printf("%s\n",CourseNames[i]); }}/*栈定义*/typedefintSElemType;//栈类型#defineStack_NUM20//存储空间初始分配量#defineStack_MoreNUM5//存储空间分配增量typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;//分配的存储空间}SqStack;/*栈的初始化*/intInitStack(SqStack*pStack){SqStackS;S=*pStack;pStack->base=(SElemType*)malloc(Stack_NUM*sizeof(SElemType));if(!pStack->base)exit(-1);pStack->top=pStack->base;pStack->stacksize=Stack_NUM;returnOK;}/*判断栈是否为空*/intStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}/*出栈*/intPop(SqStackS,SElemTypee){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}/*入栈*/intPush(SqStackS,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){inti,k,j=0,count,indegree[MAX_VERTEX_NUM];intq=1,Z=0;SqStackS;ArcNode*p;FindInDegree(G,indegree);//对各顶点求入度InitStack(&S);//初始化栈for(i=0;i<G.vexnum;++i)//建零入度顶点栈S{ if(!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号顶点并计数//对i号顶点的每个邻接点的入度减1 for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!(--indegree[k]))//若入度减为0,则入栈 Push(S,k); } }if(c