教学计划编制问题课程设计报告

中北大学数据结构与算法课程设计说明书学院、系：软件学院专业：软件工程学生姓名：学号：设计题目：教学计划编制问题起迄日期:2013年12月9日-2013年12月20日指导教师:2013年12月20日11需求分析1.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.2.本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程.3.测试数据：学期总数：6；学分上限：9；本专业共开设12门课，课程号从C00到C11，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。2概要设计1.抽象数据类型图的定义如下：ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作P:voidCreatGraph(ALGraph*);voidFindInDegree(ALGraph,int*);intTopologicalOrder(ALGraphG,AdjListR,structNamename[])intLocateVex(ALGraphG,VertexTypeu)/*查找图中某个顶点位置*/}ADTGraph2.栈的定义如下：ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n=0}数据关系:R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}基本操作：voidInitStack(SqStack*S);intStackEmpty(SqStackS);voidPush(SqStack*S,int);intPop(SqStack*S,int*e);2}ADTStack3.本程序有两个模块，调用关系简单：主程序模块→拓扑排序模块3系统完成功能及功能框图图3.1系统功能框图end采用第二种策略：使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图CreateGraph（）：结合先修关系的AOV网，采用邻接链表存储菜单OUTPUT()：显示代号所对应课程及课程的先修课程前插法main拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程输出图G的信息Display(G)：将图的顶点和弧边输出3图3.2邻接表0C11C22C33C44C55C66C7^7C8^8C99C1010C1111C12^1^5^11^111067^6^4^72^1134^9^4YYNYNY图3.3拓扑排序流程图对每个顶点求入度，并存入数组InDegree[i]中（i=0…n）初始化栈Stack,Counter=0ReturnOKReturnERROR依次将入度为0的顶点存入栈中对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter++)推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter++）堆栈是否为空？n个顶点全输出5图3.4课程先修关系图4详细设计1.图的邻接表的存储表示，即结构体的定义：typedefstructArcNode{intAdjOfV;//该弧所指向的顶点的位置structArcNode*next;//指向下一条弧的指针}ArcNode;typedefcharVertexType[MAXOfNAME];typedefstruct//链接表{VertexTypedata;//顶点信息intgrades;//存储学分信息ArcNode*first;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VER];//头结点typedefstruct{C1C4C5C7C2C3C8C9C12C10C11C66AdjListver;//vertices存储课程名intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;2.建立图的邻接链表：printf(请输入下列课程的先修课程(无先修课程输入0结束后也输入0)\n);for(h=0;hG.vexnum;++h)//构造表结点链表,利用前插法{printf(%s的先修课程:,G.ver[h].data);scanf(%s,va);getchar();while(va[0]!='0'){i=LocateVex(G,va);//弧头j=h;//弧尾p=(ArcNode*)malloc(sizeof(ArcNode));p-AdjOfV=j;p-next=G.ver[i].first;//插在表头G.ver[i].first=p;scanf(%s,va);getchar();}3.输出图的顶点和边：printf(%d个顶点,G.vexnum);for(i=0;iG.vexnum;++i)printf(%4s,G.ver[i].data);printf(\n%d条弧边:\n,G.arcnum);for(i=0;iG.vexnum;i++){p=G.ver[i].first;while(p){printf(%s----%s\n,G.ver[i].data,G.ver[p-AdjOfV].data);7p=p-next;}}4.通过栈实现拓扑排序：intTopologicalOrder(ALGraphG,AdjListR,structNamename[]){inti,k,j=0,count,indegree[MAX_VER];SqStackS;ArcNode*p;FindInDegree(G,indegree);//对各顶点求入度InitStack(S);//初始化栈for(i=0;iG.vexnum;++i)//建零入度顶点栈Sif(!indegree[i])Push(S,i);//入度为0者进栈count=0;//对输出顶点计数while(!StackEmpty(S)){Pop(S,i);printf(%s(%d学分),,G.ver[i].data,G.ver[i].grades);R[j++]=G.ver[i];//将当前的拓扑序列保存起来++count;//输出i号顶点并计数for(p=G.ver[i].first;p;p=p-next)//对i号顶点的每个邻接点的入度减1{k=p-AdjOfV;if(!(--indegree[k]))//若入度减为0,则入栈Push(S,k);}}if(countG.vexnum)8{printf(此有向图有回路无法完成拓扑排序);return0;}elseprintf(为一个拓扑序列);printf(\n);intq=1,Z=0;while(q=TotalOfTerms){intC=R[Z].grades;printf(\n第%d个学期应学课程:,q);while(C=MaxScores){C=C+R[Z+1].grades;if(ZG.vexnum){CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/++Z;}}printf(\n);if(q==TotalOfTerms)printf(\nOKOver!);q++;}return1;/**/}5.主程序和其他伪码算法：voidmain(){ALGraphG;9AdjListR;Structname；name[N]={{C1},{C2},{C3},{C4},{C5},{C6},{C7},{C8},{C9},{C10},{C11},{C12}};printf(***************教学计划编制问题**************\n);printf(请以课件9-2上课程先序图为例输入学期总数:);scanf(%d,&TotalOfTerms);getchar();printf(请输入学期的学分上限（8或9）:);scanf(%d,&MaxScores);getchar();CreateGraph(G);Display(G);TopologicalOrder(G,R,name);}intInitStack(SqStack&S)/*栈的初始化*/{S.a=(int*)malloc(StackofNUM*sizeof(int));if(!S.a)exit(-1);S.top=S.a;S.size=StackofNUM;return1;}intStackEmpty(SqStackS)/*判断栈是否为空*/{if(S.top==S.a)return1;elsereturn0;}10intPush(SqStack&S,intx)/*入栈*/{if(S.top-S.a=S.size){S.a=(int*)realloc(S.a,(S.size+StackforMore)*sizeof(int));if(!S.a)exit(-1);S.top=S.a+S.size;S.size+=StackforMore;}*S.top++=x;return1;}intPop(SqStack&S,int&x)/*出栈*/{if(S.top==S.a)return0;x=*--S.top;return1;}intLocateVex(ALGraphG,VertexTypeu)/*查找图中某个顶点位置*/{inti;for(i=0;iG.vexnum;++i)if(strcmp(u,G.ver[i].data)==0)returni;return-1;}intCreateGraph(ALGraph&G)/*采用邻接表存储结构*/{inti,j,h;11VertexTypeva;ArcNode*p;printf(请输入教学计划的课程数:);scanf(%d,&G.vexnum);getchar();printf(请输入各个课程的先修课程的总和(弧总数):);scanf(%d,&G.arcnum);getchar();printf(请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):,G.vexnum,MAXOfNAME);for(i=0;iG.vexnum;++i){scanf(%s,&G.ver[i].data);getchar();G.ver[i].first=NULL;}printf(请输入%d个课程的学分值:,G.vexnum);for(i=0;iG.vexnum;++i){scanf(%d,&G.ver[i].grades);getchar();}printf(请输入下列课程的先修课程(无先修课程输入0结束后也输入0)\n);for(h=0;hG.vexnum;++h)//构造表结点链表,利用前插法{printf(%s的先修课程:,G.ver[h].data);scanf(%s,va);getchar();while(va[0]!='0'){12i=LocateVex(G,va);//弧头j=h;//弧尾p=(ArcNode*)malloc(sizeof(ArcNode));p-AdjOfV=j;p-next=G.ver[i].first;//插在表头G.ver[i].first=p;scanf(%s,va);getchar();}}return1;}voidDisplay(ALGraphG)/*输出图G的信息*/{inti;ArcNode*p;printf(有向图\n);printf(%d个顶点,G.vexnum);for(i=0;iG.vexnum;++i)printf(%4s,G.ver[i].data);printf(\n%d条弧边:\n,G.arcnum);for(i=0;iG.vexnum;i++){p=G.ver[i].first;while(p){printf(%s----%s\n,G.ver[i].data,G.ver[p-AdjOfV].data);p=p-next;}}}13voidFin