教学计划编制问题.docx
- 文档编号:2388739
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:16
- 大小:274.05KB
教学计划编制问题.docx
《教学计划编制问题.docx》由会员分享,可在线阅读,更多相关《教学计划编制问题.docx(16页珍藏版)》请在冰点文库上搜索。
教学计划编制问题
中北大学
数据结构与算法课程设计
说明书
学院、系:
软件学院
专业:
软件工程
班级:
学生姓名:
学号:
设计题目:
教学计划编制问题
起迄日期:
2015年1月12日-2015年1月29日
指导教师:
王秀娟
2015年1月29日
1.问题描述
大学的每个专业都要制订教学计划。
假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限均相等。
每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。
每门课恰好占一学期。
试在这样的前提下设计个教学计划编制程序
基本要求
输入参数包括:
学期总期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)课程名等信息均以文件方式存放在磁盘中;安排教学计划时以使学生在各学期中的学习负担尽量均匀;输出的计划存入文件中。
提示设学期总数不超过8,课程总数不超过100。
2.需求分析
根据问题描述及要求可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体,在运行结果中将图的信息显示出来,利用先修关系将课程排序,最后解决问题输出每学期的课程。
(1)用学分来实现每学期课程数大致相同;
(2)根据教学计划中的课程及其关系和学分来定义图的顶点及边的结构体。
(3)创建图CreateGraph():
结合先修关系的AOV网,采用邻接表存储。
(4)菜单OUTPUT():
显示代号所对应课程及课程的先修课程。
(5)拓扑排序TopoSort(G):
将课程排序后并决定出每学期所学课程。
(6)输出图G的信息Display(G):
将图的顶点和弧边输出
3.程序设计方法及主要函数介绍
在程序中采用了图的方法,用邻接矩阵存储节点。
使用拓扑排序的方法为图的遍历提供查找StatusCreateGraph(ALGraph&G)采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。
voidDisplay(ALGraphG)输出图的邻接矩阵G
VoidFindInDegree(ALGraphG,intindegree[])求顶点的入度,算法调用
typedefintSElemType;栈的顺序存储表示
StatusTopologicalSort(ALGraphG)有向图G采用邻接表存储结构。
若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR
4.程序代码
#include
#include
#include
#include
#include
#include
usingnamespacestd;
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;//Status是函数的返回类型;
typedefintBoolean;
#defineMAX_NAME10//顶点字符串的最大长度;
#defineMAX_CLASS_NUM100
intZ=0;
intX=0;
intterm_num,credit_lim,q=1;
typedefintInfoType;
typedefcharVertexType[MAX_NAME];//字符串类型;
#defineMAX_VERTEX_NUM100
typedefenum{DG}GraphKind;//{有向图,有向网,无向图,无向网};
typedefstructArcNode{//弧结构;
intadjvex;//该弧所指向的顶点的位置;
structArcNode*nextarc;//指向下一条弧的指针;
InfoType*info;//网的权值指针;
}ArcNode;//表结点;
typedefstruct{
VertexTypedata;//顶点信息;
ArcNode*firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针;
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{AdjListvertices,vertices2;//分别存课程名和学分;
intvexnum,arcnum;
intkind;
}ALGraph;
intLocateVex(ALGraphG,VertexTypeu){inti;
for(i=0;i if(strcmp(u,G.vertices[i].data)==0) returni;return-1;} StatusCreateGraph(ALGraph&G){ inti,j,k; VertexTypev1,v2;//顶点信息; ArcNode*p;//指向第一条依附某顶点的弧的指针; printf("请输入教学计划的课程数: "); scanf("%d",&G.vexnum); printf("请输入课程先修关系数(弧的数目): "); scanf("%d",&G.arcnum); printf("请输入%d个课程的代表值(如: c01): \n",G.vexnum); for(i=0;i scanf("%s",G.vertices[i].data); G.vertices[i].firstarc=NULL;} printf("请输入%d个课程的学分值: \n",(G).vexnum); for(i=0;i scanf("%s",G.vertices2[i].data);} printf("请顺序输入每条弧的弧尾和弧头(以空格作为间隔): \n"); for(k=0;k scanf("%s%s",v1,v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode));//新建一个节点; p->adjvex=j; p->info=NULL; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p;} returnOK;} voidDisplay(ALGraphG){ inti; ArcNode*p; switch(G.kind){ caseDG: printf("有向图\n");} printf("%d个顶点: \n",G.vexnum); for(i=0;i printf("%s",G.vertices[i].data); printf("\n%d条弧: \n",G.arcnum); for(i=0;i p=G.vertices[i].firstarc; while(p){printf("%s→%s",G.vertices[i].data,G.vertices[p->adjvex].data); p=p->nextarcprintf("\n");}} voidFindInDegree(ALGraphG,intindegree[]){ inti; ArcNode*p; for(i=0;i indegree[i]=0; for(i=0;i p=G.vertices[i].firstarc; while(p){ indegree[p->adjvex]++; p=p->nextarc; typedefintSElemType; #defineSTACK_INIT_SIZE10 #defineSTACKINCREMENT2 typedefstructSqStack{ SElemType*base; SElemType*top; intstacksize; }SqStack; StatusInitStack(SqStack*S){ (*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(! (*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK;} voidClearStack(SqStack*S){//清空栈的操作 S->top=S->base;} StatusStackEmpty(SqStackS){if(S.top==S.base) returnTRUE; elsereturnFALSE;} StatusPop(SqStack*S,SElemType*e){ if((*S).top==(*S).base) returnERROR; *e=*--(*S).top; returnOK;} StatusPush(SqStack*S,SElemTypee){ if((*S).top-(*S).base>=(*S).stacksize){(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(! (*S).baseexit(OVERFLOW); (*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e; returnOK;} Statuszxf(ALGraphG){//求大学所有课程总学分; intz=0; for(inti=0;i z+=atoi(G.vertices2[i].data);} returnz;} typedefintpathone[MAX_CLASS_NUM]; typedefintpathtwo[MAX_CLASS_NUM]; StatusTopologicalSort(ALGraphG){ inti,k,count,indegree[MAX_VERTEX_NUM]; boolhas=false; SqStackS; pathonea; pathtwob; ArcNode*p; FindInDegree(G,indegree); InitStack(&S); for(i=0;i if(! indegree[i])Push(&S,i);} count=0; while(! StackEmpty(S)){ Pop(&S,&i); a[i]=*G.vertices[i].data;//课程名; b[i]=*G.vertices2[i].data;//学分; printf("课程%s→学分%s",G.vertices[i].data,G.vertices2[i].data); ++count; for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; if(! (--indegree[k])) Push(&S,k);}} if(count printf("此有向图有回路\n"); returnERROR;} else{printf("为一个拓扑序列。 \n\n"); has=true;} printf("请问您想使学生在各学期中的学习负担尽量均匀(输入1)\n"); printf("还是想使课程尽可能地集中在前几个学期中(输入2)? \n"); intpattern; printf("请选择(1or2): "); scanf("%d",&pattern); FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]; ClearStack(&S); printf("=====================================================\n"); printf("教学计划如下: \n"); intxq=1;//学期数; intxfh;//学分和; intnow=0; inttop=G.vexnum/term_num;//平均每学期课程数; intpjxf=zxf(G)/term_num;//每学期平均学分; while(xq<=term_num+1){ intresult[20];//某个学期的课程; intm=0; xfh=0; now=0;//当前学期课程数; for(i=0;i if(0==indegree[i]) Push(&S,i); } if(xq==term_num+1&&! StackEmpty(S)){ printf("还有课程未安排! \n");} while(! StackEmpty(S)&&xq<=term_num){ intxf; Pop(&S,&i);//弹出栈顶元素; xf=atoi(G.vertices2[i].data);//atoi: 字符串转换成整型数,xf: 学分;xfh=xfh+xf;now++; if(xfh>credit_lim){ ClearStack(&S); break; }if(pattern==1){ if(xq! =term_num/2&&now>topClearStack(&S);//该操作使程序跳出此内层的while now=0; break;}if(pattern==2){ if(xq! =1&&xq! =term_num/2&&xq! =term_num/2-1&&now>top){ ClearStack(&S); now=0;break;}} indegree[i]--;//减为-1,避免被再次计入; for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; indegree[k]--; if(indegree[k]==0) Push(&S,k);} result[m]=i;m++;} if(xq<=term_num){ printf("第%d个学期的课程为: ",xq); for(intj=0;j printf("课程%s",G.vertices[result[j]].data); }} printf("\n");xq++; ClearStack(&S);} printf("=====================================================\n"); returnOK;} intmain(){ printf("教学计划编制问题\n"); printf("(拓扑排序AOV-网)\n\n"); //AOV-网: 顶点表示活动,弧表示活动间优先关系的有向图; intCONTINUE=1; //while(CONTINUE! =0){ printf("------------------------------------------------\n"); ALGraphf;//图的邻接表存储; printf("请输入学期总数: "); scanf("%d",&term_num); printf("请输入每学期的学分上限: "); scanf("%d",&credit_lim); CreateGraph(f); Display(f); while(CONTINUE! =0){ TopologicalSort(f); printf("\n按1继续,按0结束: "); scanf("%d",&CONTINUE);} return0;} 5程序的优点和不足: 在此程序中用户可以使用的订票,退票及航班信息查询,用户可以很方便的了解航班信息。 但程序美中不足的是程序的健壮性比较差,在输入数据的类型与预定义的类型不同时,不能进行判断和提示,直到对数据进行操作时,会出错并异常退出,没有达到预想的效果。 6心得体会 这次实习,我认识到了以下几个方面。 第一就是要合作。 不懂的问题一定要向同学,老师请教。 这样才能集思广益,有利于问题 的解决。 也能够让自己节省时间,有效率的完成工作。 齐心协力完成这个程序,互相帮助,这是我们同做课题的同学的共同体会。 第二就是要细心。 程序的编制难免会出现错误,不能一次成功,出现错误后,一定要认真 心的排查重要的。 的了解问题,得到启迪
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学计划 编制 问题