数据结构程设计--教学计划编制问题

数据结构程设计----教学计划编制问题一.需求分析（1）实验内容和实验目的：1.大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。2.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.3.本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程.（2）测试数据：学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图7．26。（3）测试结果（包含正确和错误的）：正确测试结果：错误测试结果：二.概要设计1.抽象数据类型图的定义如下:ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作P:voidCreatGraph(ALGraph*);voidFindInDegree(ALGraph,int*);voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);}ADTGraph栈的定义: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);}ADTStack2.主程序intmain()//主函数{intnumterm;//学期总数intuplcredit;//一个学期的学分上限intselectway;ALGraphG;printf(请输入学期总数:\n);scanf(%d,&numterm);printf(请输入一个学期的学分上限:\n);scanf(%d,&uplcredit);CreatGraph(&G);printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布\n);scanf(%d,&selectway);if(selectway==1)TopologicalSort_1(G,numterm,uplcredit);if(selectway==2)TopologicalSort_2(G,numterm,uplcredit);system(pause);return0;}3.本程序只有两个模块,调用关系简单.主程序模块↓拓扑排序模块三．详细设计1．头结点，表结点，邻接表的定义#defineMAX_VERTEX_NUM100//最大课程总数typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{charname[24];//课程名intclassid;//课程号intcredit;//课程的学分intindegree;//该结点的入度intstate;//该节点的状态ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VEXTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;邻接表的基本操作：voidCreatGraph(ALGraph*);创建邻接表voidFindInDegree(ALGraph,int*);求一个结点的入度voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);拓扑排序来编排课程voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);拓扑排序来编排课程2．栈的定义：#defineSTACk_INIT_SIZE100//存储空间的初时分配量#defineSTACKINCREMENT10//存储空间的分配增量typedefintElemType;typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;基本操作：voidInitStack(SqStack*S);栈的初始化intStackEmpty(SqStackS);判断栈是否为空voidPush(SqStack*S,int);入栈操作intPop(SqStack*S,int*e);出栈操作3．主程序和其他算法intmain()//主函数{intnumterm;//学期总数intuplcredit;//一个学期的学分上限intselectway;ALGraphG;printf(请输入学期总数:\n);scanf(%d,&numterm);printf(请输入一个学期的学分上限:\n);scanf(%d,&uplcredit);CreatGraph(&G);printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布\n);scanf(%d,&selectway);if(selectway==1)TopologicalSort_1(G,numterm,uplcredit);if(selectway==2)TopologicalSort_2(G,numterm,uplcredit);system(pause);return0;}voidCreatGraph(ALGraph*G)//构件图{inti,m,n;ArcNode*p;printf(请输入需要编排课程总数:\n);scanf(%d,&G-vexnum);for(i=1;i=G-vexnum;i++){printf(请输入课程名\n);scanf(%s,&G-vertices[i].name);printf(请输入课程号\n);scanf(%d,&G-vertices[i].classid);printf(请输入该课程的学分\n);scanf(%d,&G-vertices[i].credit);G-vertices[i].indegree=0;G-vertices[i].state=NOTSTUDY;G-vertices[i].firstarc=NULL;}printf(请输入课程先修关系总数：);scanf(%d,&G-arcnum);printf(请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):\n);for(i=1;i=G-arcnum;i++){printf(\n请输入存在先修关系的两个课程的序号:);scanf(%d,%d,&n,&m);while(n0||nG-vexnum||m0||mG-vexnum){printf(输入的顶点序号不正确请重新输入:);scanf(%d,%d,&n,&m);}p=(ArcNode*)malloc(sizeof(ArcNode));if(p==NULL){printf(memoryallocationfailed,goodbey);exit(1);}p-adjvex=m;p-nextarc=G-vertices[n].firstarc;G-vertices[n].firstarc=p;}printf(\n建立的邻接表为:\n);//输出建立好的邻接表for(i=1;i=G-vexnum;i++){printf(%d:-,G-vertices[i].classid);for(p=G-vertices[i].firstarc;p!=NULL;p=p-nextarc)printf(%d-,p-adjvex);printf(NULL);printf(\n);}}voidInitStack(SqStack*S){S-base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S-base){printf(ERROR);exit(1);}S-top=S-base;S-stacksize=STACK_INIT_SIZE;}intStackEmpty(SqStack*S){if(S-top==S-base)returnOK;elsereturnERROR;}voidPush(SqStack*S,inte){if(S-top-S-base=S-stacksize){S-base=(int*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(int));if(!S-base){printf(ERROR);exit(1);}S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;}*S-top++=e;}intPop(SqStack*S,int*e){if(S-top==S-base)exit(1);*e=*--S-top;return0;}voidFindInDegree(ALGraphG,intindegree[])//求图中各节点的入度{inti;for(i=1;i=G.vexnum;i++)indegree[i]=0;for(i=1;i=G.vexnum;i++){while(G.vertices[i].firstarc){indegree[G.vertices[i].firstarc-adjvex]++;G.vertices[i].firstarc=G.vertices[i].firstarc-nextarc;}}}voidTopologicalSort_1(ALGraphG,intnumterm,intuplcredit){FILE*fp;fp=fopen(bianpai.txt,w);ArcNode*p;SqStackS;intindegree[M];//存放各节点的入度inti,j,k,m,n;intcount;//课程编排数目计数器intsumcredit;//每个学期的课程学分累加器FindInDegree(G,indegree);for(i=1;i=G.vexnum;i++)G.vertices[i].indegree=indegree[i];InitStack(&S);count=0;k=0;while(count!=G.vexnum&&k=numterm){sumcredit=0;for(i=1;i=G.vexnum;i++)//入度为零的节点入栈，即无先修的课程入栈if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY)){Push(&S,i);G.vertices[i].state=STUDY;//避免入度为零节点重复入栈}if(!StackEmpty(&S)&&(sumcredit=uplcredit)){k=k+1;printf(\n);printf(第%d个学期学得课程有:\n,k);sumcredit=0;for(i=1;i=G.vexnum;i++)//入度为零的节点入栈，即无先修的课程入栈if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY)