教学计划编制问题.docx
《教学计划编制问题.docx》由会员分享，可在线阅读，更多相关《教学计划编制问题.docx（28页珍藏版）》请在冰点文库上搜索。
教学计划编制问题
一、设计内容：
问题描述
大学的每个专业都要制订教学计划。
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。
每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。
每门课恰好占一个学期。
试在这样的前提下设计一个教学计划编制程序。
1、基本要求
（1）.输入参数包括：
学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：
一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。
计划的表格格式自行设计。
2、测试数据
学期总数：
6；
学分上限：
10；
该专业共开设课数：
12
课程号：
从C01到C12；
学分顺序：
2，3，4，3，2，3，4，4，7，5，2，3。
先修关系见教科书图7.26。
3、输出输入要求
输入参数包括：
学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。
4、实现提示
可设学期总数不超过12，课程总数不超过100。
如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。
应建立内部课程号与课程号之间的对应关系。
二、概要设计
1、抽象数据类型图的定义如下:
ADTGraph{
数据对象V:
V是具有相同特性的数据元素的集合,称为顶点集.
数据关系R:
R={VR}
VR={（v,w）|v,w∈V,（v,w）表示v和w之间存在直接先修关系}
基本操作P:
LocateVex（ALGraphG,VertexTypeu）：
图的邻接表存储的基本操作
CreateGraph（ALGraph*G）：
构造生成树
Display（ALGraphG）：
输出图的邻接矩阵
FindInDegree（ALGraphG,intindegree）：
求顶点的入度
TopologicalSort（ALGraphG）：
有向图G采用邻接表存储结构。
若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。
}ADTGraph
2、栈的定义:
ADTStack{
数据对象:
D={ai|ai∈ElemSet,i=1,2,…n,n>=0}
数据关系:
R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}
基本操作D：
InitStack（SqStack*S）;初始化一个空栈S
StackEmpty（SqStackS）;若栈S为空栈，则返回TRUE，否则返回FALSE
Push（SqStack*S,SElemType*e）;插入元素e为新的栈顶元素
Pop（SqStack*S,SElemType*e）;若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
}ADTStack
3、主程序
voidmain（）
{ALGraphf;
printf（"教学计划编制问题的数据模型为拓扑排序AOV-网结构。
\n"）;
printf（"以下为教学计划编制问题的求解过程:
\n"）;
printf（"请输入学期总数:
"）;
scanf（"%d",&xqzs）;
printf（"请输入学期的学分上限:
"）;
scanf（"%d",&xfsx）;
CreateGraph（&f）;
Display（f）;
TopologicalSort（f）;
}
4、本程序只有两个模块,调用关系简单.
主程序模块
↓
拓扑排序模块
三、详细设计
1、顶点、边、图类型
#defineMAX_VERTEX_NUM100
typedefintpathone[MAXCLASS];
typedefintpathtwo[MAXCLASS];
typedefenum{DG}GraphKind;/*{有向图,有向网,无向图,无向网}*/
typedefstructArcNode
{
intadjvex;/*该弧所指向的顶点的位置*/
structArcNode*nextarc;/*指向下一条弧的指针*/
InfoType*info;/*网的权值指针）*/
}ArcNode;/*表结点*/
typedefstruct
{
VertexTypedata;/*顶点信息*/
ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/
typedefstruct
{
AdjListvertices,verticestwo;
intvexnum,arcnum;/*图的当前顶点数和弧数*/
intkind;/*图的种类标志*/
}ALGraph;
2、图的基本操作
intInitGraph（ALGraph&G）;初始化邻接多重表，表示一个空图。
intLocateVex（ALGraphG,VertexTypeu）；若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
StatusCreateGraph（ALGraph*G）；采用邻接表存储结构,构造没有相关信息的图G（用一个函数构造种图。
voidDisplay（ALGraphG）；输出图的邻接矩阵G。
voidFindInDegree（ALGraphG,intindegree[]）；求顶点的入度，算法调用。
StatusTopologicalSort（ALGraphG）；有向图G采用邻接表存储结构。
若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR
3、栈类型
#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT2/*存储空间分配增量*/
typedefstructSqStack
{
SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/
SElemType*top;/*栈顶指针*/
intstacksize;/*当前已分配的存储空间，以元素为单位*/
}SqStack;/*顺序栈*/
4、栈的基本操作
StatusInitStack（SqStack*S）；初始化
voidClearStack（SqStack*S）；清空栈的操作
StatusStackEmpty（SqStackS）；若栈S为空栈，则返回TRUE，否则返回FALSE
StatusPop（SqStack*S,SElemType*e）；若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
StatusPush（SqStack*S,SElemTypee）；插入元素e为新的栈顶元素
5、部分操作代码如下：
intLocateVex（ALGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for（i=0;iif（strcmp（u,G.vertices[i].data）==0）
returni;
return-1;
}
StatusCreateGraph（ALGraph*G）
{/*采用邻接表存储结构,构造没有相关信息的图G（用一个函数构造种图）*/
inti,j,k;
VertexTypeva,vb;
ArcNode*p;
printf（"请输入教学计划的课程数:
"）;
scanf（"%d",&（*G）.vexnum）;
printf（"请输入拓扑排序所形成的课程先修关系的边数:
"）;
scanf（"%d",&（*G）.arcnum）;
printf（"请输入%d个课程的代表值（<%d个字符）:
\n",（*G）.vexnum,MAX_NAME）;
for（i=0;i<（*G）.vexnum;++i）/*构造顶点向量*/
{scanf（"%s",（*G）.vertices[i].data）;
（*G）.vertices[i].firstarc=NULL;
}
printf（"请输入%d个课程的学分值（<%d个字符）:
\n",（*G）.vexnum,MAX_NAME）;
for（i=0;i<（*G）.vexnum;++i）/*构造顶点向量*/
{scanf（"%s",（*G）.verticestwo[i].data）;
}
printf（"请顺序输入每条弧（边）的弧尾和弧头（以空格作为间隔）:
\n"）;
for（k=0;k<（*G）.arcnum;++k）/*构造表结点链表*/
{scanf（"%s%s",va,vb）;
i=LocateVex（*G,va）;/*弧尾*/
j=LocateVex（*G,vb）;/*弧头*/
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）
{/*输出图的邻接矩阵G*/
inti;
ArcNode*p;
switch（G.kind）
{caseDG:
printf（"有向图\n"）;
}
printf（"%d个顶点：
\n",G.vexnum）;
for（i=0;iprintf（"%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->nextarc;
}
printf（"\n"）;
}
}
voidFindInDegree（ALGraphG,intindegree[]）
{/*求顶点的入度，算法调用*/
inti;
ArcNode*p;
for（i=0;iindegree[i]=0;/*赋初值*/
for（i=0;i{
p=G.vertices[i].firstarc;
while（p）
{indegree[p->adjvex]++;
p=p->nextarc;
}
}
StatusInitStack（SqStack*S）
{/*构造一个空栈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）
{/*若栈S为空栈，则返回TRUE，否则返回FALSE*/
if（S.top==S.base）
returnTRUE;
else
returnFALSE;
}
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;
}
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;iif（!
indegree[i]）
{Push（&S,i）;
//cout<<*G.vertices[i].data<}
/*入度为者进栈*/
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<}
}
}
if（count{printf（"此有向图有回路\n"）;
returnERROR;
}
else
{printf（"为一个拓扑序列。
\n"）;
has=true;
}
FindInDegree（G,indegree）;/*对各顶点求入度indegree[0..vernum-1]*/
ClearStack（&S）;
cout<<"======================课程计划如下==============================="
<intqq=1;//学期数
intxxf;
while（qq<=xqzs）
{
intresult[20];
intrtop=0;
intnn=0;
//intccount=0;
//学期学分计算
xxf=0;
for（i=0;i{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]--;
/*if（!
（--indegree[k]））若入度减为,则入栈
{
Push（&S,k）;
}*/
}
result[rtop]=i;
rtop++;
}
cout<<"第"<"<for（nn=0;nn{
cout<<"课程"<}
qq++;
}
returnOK;
}
6、主函数：
intmain（）
{ALGraphf;
printf（"教学计划编制问题的数据模型为拓扑排序AOV-网结构。
\n"）;
printf（"以下为教学计划编制问题的求解过程:
\n"）;
printf（"请输入学期总数:
"）;
scanf（"%d",&xqzs）;
printf（"请输入学期的学分上限:
"）;
scanf（"%d",&xfsx）;
CreateGraph（&f）;
Display（f）;
TopologicalSort（f）;
}
四、调试分析
1、实验过程中出现的问题及解决方法
我们在实验过程中遇到的最大难题是两个课程排序算法的编写。
刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。
经过请教同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。
经过三天的修改，终于写出了符合要求的排序算法。
2、实验体会:
经过此次课程设计，我认识到了理论与实践结合的重要性，仅仅只是从课本上学到算法原理是远远不够的。
在实践中，我们总会出现许多错误。
这就要求我们以一个脚踏实地的态度来处理问题。
我们深刻地认识到自己写程序的不足，使我们学到了好多有用的知识，让我们明白了C语言的语句用法。
五、用户手册及测试结果
输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对学分值
输入完成后执行可得到每个学期的课程结果
六、附录（程序源代码）
#include
#include
#include//malloc（）等
#include//INT_MAX等
#include//EOF（=^Z或F6）,NULL
#include//atoi（）52
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
#include//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等
typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE
#defineMAX_NAME10
/*顶点字符串的最大长度*/
#defineMAXCLASS100
intZ=0;
intX=0;
intxqzs,q=1,xfsx;
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,verticestwo;
intvexnum,arcnum;/*图的当前顶点数和弧数*/
intkind;/*图的种类标志*/
}ALGraph;
/*图的邻接表存储的基本操作*/
intLocateVex（ALGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for（i=0;iif（strcmp（u,G.vertices[i].data）==0）
returni;
retur
升级会员 