教学计划编制问题文档格式.docx
《教学计划编制问题文档格式.docx》由会员分享，可在线阅读，更多相关《教学计划编制问题文档格式.docx（16页珍藏版）》请在冰点文库上搜索。
（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<
string.h>
stdio.h>
stdlib.h>
iomanip>
math.h>
//floor（）,ceil（）,abs（）
#include<
iostream>
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<
G.vexnum;
++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）;
请输入课程先修关系数（弧的数目）:
G.arcnum）;
请输入%d个课程的代表值（如:
c01）:
\n"
G.vexnum）;
++i）{
%s"
G.vertices[i].data）;
G.vertices[i].firstarc=NULL;
}
printf（"
请输入%d个课程的学分值:
（G）.vexnum）;
G.vertices2[i].data）;
请顺序输入每条弧的弧尾和弧头（以空格作为间隔）:
for（k=0;
k<
G.arcnum;
++k）{
%s%s"
v1,v2）;
i=LocateVex（G,v1）;
j=LocateVex（G,v2）;
p=（ArcNode*）malloc（sizeof（ArcNode））;
//新建一个节点；
p->
adjvex=j;
info=NULL;
nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
returnOK;
voidDisplay（ALGraphG）{
inti;
switch（G.kind）{
caseDG:
有向图\n"
%d个顶点：
%s"
\n%d条弧:
G.arcnum）;
i++）{
p=G.vertices[i].firstarc;
while（p）{printf（"
%s→%s"
G.vertices[i].data,G.vertices[p->
adjvex].data）;
p=p->
nextarcprintf（"
}}
voidFindInDegree（ALGraphG,intindegree[]）{
ArcNode*p;
i++）
indegree[i]=0;
while（p）{
indegree[p->
adjvex]++;
p=p->
nextarc;
#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;
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;
Statuszxf（ALGraphG）{//求大学所有课程总学分；
intz=0;
for（inti=0;
i<
G.vexnum;
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;
FindInDegree（G,indegree）;
InitStack（&
S）;
++i）{
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;
//学分；
课程%s→学分%s"
G.vertices[i].data,G.vertices2[i].data）;
++count;
for（p=G.vertices[i].firstarc;
p;
nextarc）{
k=p->
adjvex;
（--indegree[k]））
Push（&
S,k）;
}}
if（count<
G.vexnum）{
此有向图有回路\n"
else{printf（"
为一个拓扑序列。
\n\n"
has=true;
请问您想使学生在各学期中的学习负担尽量均匀（输入1）\n"
还是想使课程尽可能地集中在前几个学期中（输入2）？
intpattern;
请选择（1or2）:
"
pattern）;
//对各顶点求入度indegree[0..vernum-1];
ClearStack（&
=====================================================\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;
//当前学期课程数；
++i）{
if（0==indegree[i]）
if（xq==term_num+1&
&
!
还有课程未安排！
StackEmpty（S）&
xq<
=term_num）{
intxf;
//弹出栈顶元素；
xf=atoi（G.vertices2[i].data）;
//atoi:
字符串转换成整型数,xf:
学分;
xfh=xfh+xf;
now++;
if（xfh>
credit_lim）{
break;
}if（pattern==1）{
if（xq!
=term_num/2&
now>
topClearStack（&
//该操作使程序跳出此内层的while
now=0;
}if（pattern==2）{
=1&
xq!
=term_num/2-1&
top）{
}}
indegree[i]--;
//减为-1,避免被再次计入；
indegree[k]--;
if（indegree[k]==0）
result[m]=i;
m++;
if（xq<
第%d个学期的课程为：
xq）;
for（intj=0;
j<
m;
j++）{
课程%s"
G.vertices[result[j]].data）;
xq++;
intmain（）{
教学计划编制问题\n"
（拓扑排序AOV-网）\n\n"
//AOV-网:
顶点表示活动，弧表示活动间优先关系的有向图；
intCONTINUE=1;
//while（CONTINUE!
=0）{
------------------------------------------------\n"
ALGraphf;
//图的邻接表存储；
请输入学期总数:
term_num）;
请输入每学期的学分上限:
credit_lim）;
CreateGraph（f）;
Display（f）;
while（CONTINUE!
TopologicalSort（f）;
\n按1继续，按0结束:
CONTINUE）;
return0;
5程序的优点和不足：
在此程序中用户可以使用的订票，退票及航班信息查询，用户可以很方便的了解航班信息。
但程序美中不足的是程序的健壮性比较差，在输入数据的类型与预定义的类型不同时，不能进行判断和提示，直到对数据进行操作时，会出错并异常退出，没有达到预想的效果。
6心得体会
这次实习，我认识到了以下几个方面。
第一就是要合作。
不懂的问题一定要向同学，老师请教。
这样才能集思广益，有利于问题
的解决。
也能够让自己节省时间，有效率的完成工作。
齐心协力完成这个程序，互相帮助，这是我们同做课题的同学的共同体会。
第二就是要细心。
程序的编制难免会出现错误，不能一次成功，出现错误后，一定要认真
心的排查重要的。
的了解问题，得到启迪
升级会员 