教学计划编制问题课程设计报告书.docx
《教学计划编制问题课程设计报告书.docx》由会员分享，可在线阅读，更多相关《教学计划编制问题课程设计报告书.docx（22页珍藏版）》请在冰点文库上搜索。
教学计划编制问题课程设计报告书
任务要求:
大学的每个专业都要制定教学计划。
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。
每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。
每门课恰好占一个学期，试在这样的前提下设计一个教学计划编制程序。
内容摘要:
本程序是一个教学计划的编制的问题，而由任务要求了解到的已知的条件及这次设计的目的。
我们在分析问题后决定采用AOV网图来解决。
首先，了解本系统要实现的基本功能，大致划分模块。
其次，由已知条件画出先修关系图，以此来设计邻接表存储结构。
接下来，借助于栈，设计拓扑排序的流程。
最后，对系统开始进行详细的前台界面和后台程序的设计，完善系统。
教师评语:
成绩
签名:
日期:
课程设计报告书
教学计划编制问题
一设计思想
根据任务要求及对实际情况的了解，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，采用邻接表存储结构，利用栈作辅助结构，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。
二系统完成功能及功能框图
图1系统功能框图
0
C1
1
C2
2
C3
3
C4
4
C5
5
C6
6
C7
^
7
C8
^
8
C9
9
C10
10
C11
11
C12
^
图2：
邻接表
Y
N
N
Y
图3拓扑排序流程图
图4课程先修关系图
三核心算法及说明
（1）采用邻接表存储结构，创建图
intCreateGraph（ALGraph&G）
{
inti,j,k;
VertexTypeva;
ArcNode*p;
printf（"请输入教学计划的课程数:
"）;
scanf（"%d",&G.vexnum）;
printf（"请输入各个课程的先修课程的总和（弧总数）:
"）;
scanf（"%d",&G.arcnum）;
printf（"请输入%d个课程的课程号（最多%d个字符,数字+字母）:
",G.vexnum,MAX_NAME）;
for（i=0;i{
scanf（"%s",&G.vertices[i].data）;
G.vertices[i].firstarc=NULL;
}
printf（"请输入%d个课程的学分值:
",G.vexnum）;
for（i=0;i{
scanf（"%d",&G.vertices[i].grades）;
}
printf（"请输入下列课程的先修课程（无先修课程输入0结束后也输入0）\n"）;
for（k=0;k{
printf（"%s的先修课程:
",G.vertices[k].data）;
scanf（"%s",va）;
while（va[0]!
='0'）
{
i=LocateVex（G,va）;//弧头
j=k; //弧尾
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;//插在表头
G.vertices[i].firstarc=p;
scanf（"%s",va）;
}
}
returnOK;
}
（2）通过栈实现拓扑排序
FindInDegree（G,indegree）; //对各顶点求入度
InitStack（S）; //初始化栈
for（i=0;iif（!
indegree[i]）Push（S,i）; //入度为0者进栈
count=0; //对输出顶点计数
while（!
StackEmpty（S））
{
Pop（S,i）;
printf（"%s（%d分）,",G.vertices[i].data,G.vertices[i].grades）;
Temp[j++]=G.vertices[i]; //将当前的拓扑序列保存起来
++count; //输出i号顶点并计数
for（p=G.vertices[i].firstarc;p;p=p->nextarc）//对i号顶点的每个邻接点的入度减1
{
k=p->adjvex;
if（!
（--indegree[k]））//若入度减为0,则入栈
Push（S,k）;
}
}
if（count{
printf（"此有向图有回路无法完成拓扑排序"）;
returnERROR;
}
elseprintf（" 为一个拓扑序列"）;
printf（"\n"）;
returnok;
（3）解决问题
根据学分上限决定出每学期应学课程，其中Temp[]中存储的是经过拓扑排序后的课程先后顺序。
intq=1,Z=0;
while（q<=TotalTerms）
{
intC=Temp[Z].grades;
printf（"第%d个学期应学课程:
",q）;
while（C<=MaxScores）
{
C=C+Temp[Z+1].grades;
if（Z++Z;
}
printf（"\n"）;
if（q==TotalTerms）printf（"课程编制完成！
"）;
q++;
}
四界面设计
五结论
本次课程设计主要是拓扑排序的应用，我们根据问题描述给出了数据模型以及能够体现问题本身特点的逻辑结构。
但是，在算法设计创建邻接表的部分仍然有一些不足。
通过与同学的讨论、上网查询和请教老师，解决了疑难，同时我们也巩固和丰富了这方面的知识以及动手实践的能力。
参考资料
1．《数据结构》（C语言版）作者：
严蔚敏、吴伟民 清华大学出版社
2．《C++语言基础教程》（第二版）作者：
徐孝凯 清华大学出版社
3.《数据结构题集》（C语言版）作者：
严蔚敏、吴伟民、米宁 清华大学出版
附录
#include
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineMAX_NAME3
#defineMAXCLASS100//顶点字符串的最大长度
#defineMAX_VERTEX_NUM100//最大顶点数
#defineN12
typedefcharVertexType[MAX_NAME];
intTotalTerms;//学期总数
intMaxScores;//学分上限
/*----图的邻接表存储表示----*/
typedefstructArcNode
{
intadjvex;//该弧所指向的顶点的位置弧的节点结构
structArcNode*nextarc;//指向下一条弧的指针
}ArcNode;//链表结点
typedefstruct//链接表
{
VertexTypedata;//顶点信息
intgrades;//存储学分信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];//头结点
typedefstruct
{
AdjListvertices;//vertices存储课程名
intvexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
voidOUTPUT（）
{
ints;
printf（"\t\t教学计划编制菜单\n"）;
printf（"\t\t课程代码|课程名称|优先课程\n"）;
printf（"\t\tC1|程序设计基础|无\n"）;
printf（"\t\tC2|离散数学|C1\n"）;
printf（"\t\tC3|数据结构|C1，C2\n"）;
printf（"\t\tC4|汇编语言|C1\n"）;
printf（"\t\tC5|语言的设计和分析|C3，C4\n"）;
printf（"\t\tC6|计算机原理|C11\n"）;
printf（"\t\tC7|编译原理|C5，C3\n"）;
printf（"\t\tC8|操作系统|C3，C6\n"）;
printf（"\t\tC9|高等数学|无\n"）;
printf（"\t\tC10|线性代数|C9\n"）;
printf（"\t\tC11|普通物理|C9\n"）;
printf（"\t\tC12|数值分析|C9,C10,C1\n"）;
printf（"pressanynumkeytocontinue:
"）;
scanf（"%d",&s）;//scanf（"格式控制符",&地址表列）格式输入函数，即按用户指定的格式从键盘上把数据输入到指定的变量之中
}
/*查找图中某个顶点位置*/
intLocateVex（ALGraphG,VertexTypeu）
{
inti;
for（i=0;iif（strcmp（u,G.vertices[i].data）==0）
returni;
return-1;
}
/*采用邻接表存储结构*/
intCreateGraph（ALGraph&G）
{
inti,j,k;
VertexTypeva;
ArcNode*p;
printf（"请输入教学计划的课程数:
"）;
scanf（"%d",&G.vexnum）;//?
?
?
?
printf（"请输入各个课程的先修课程的总和（弧总数）:
"）;
scanf（"%d",&G.arcnum）;
printf（"请输入%d个课程的课程号（最多%d个字符,数字+字母）:
",G.vexnum,MAX_NAME）;//?
?
for（i=0;i？
？
{
scanf（"%s",&G.vertices[i].data）;
G.vertices[i].firstarc=NULL;//?
?
?
?
}
printf（"请输入%d个课程的学分值:
",G.vexnum）;
for（i=0;i{
scanf（"%d",&G.vertices[i].grades）;
}
printf（"请输入下列课程的先修课程（无先修课程输入0结束后也输入0）\n"）;
for（k=0;k{
printf（"%s的先修课程:
",G.vertices[k].data）;///
scanf（"%s",va）;//
while（va[0]!
='0'）//?
?
?
?
?
?
?
?
?
ikva
{
i=LocateVex（G,va）;//弧头
j=k;//弧尾
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;//插在表头
G.vertices[i].firstarc=p;
scanf（"%s",va）;
}
}
returnOK;
}
/*输出图G的信息*/
voidDisplay（ALGraphG）
{
inti;
ArcNode*p;
printf（"有向图\n"）;
printf（"%d个顶点",G.vexnum）;
for（i=0;iprintf（"%4s",G.vertices[i].data）;
printf（"\n%d条弧边:
\n",G.arcnum）;
for（i=0;i{
p=G.vertices[i].firstarc;
while（p）
{
printf（"%s--->%s\n",G.vertices[i].data,G.vertices[p->adjvex].data）;
p=p->nextarc;
}
}
}
/*求顶点的入度*/
voidFindInDegree（ALGraphG,intindegree[]）
{
inti;
ArcNode*p;
for（i=0;ifor（i=0;i{
p=G.vertices[i].firstarc;
while（p）
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
structName
{
charc[20];
}name;
/*栈定义*/
typedefintSElemType;//栈类型
#defineStack_NUM20//存储空间初始分配量
#defineStack_MoreNUM5//存储空间分配增量
typedefstructSqStack
{
SElemType*base;
SElemType*top;
intstacksize;//分配的存储空间
}SqStack;
/*栈的初始化*/
intInitStack（SqStack&S）
{
S.base=（SElemType*）malloc（Stack_NUM*sizeof（SElemType））;
if（!
S.base）
exit（-1）;
S.top=S.base;
S.stacksize=Stack_NUM;
returnOK;
}
/*判空*/
intStackEmpty（SqStackS）
{
if（S.top==S.base）
returnTRUE;
else
returnFALSE;
}
/*出栈*/
intPop（SqStack&S,SElemType&e）
{
if（S.top==S.base）
returnERROR;
e=*--S.top;
returnOK;
}
/*入栈*/
intPush（SqStack&S,SElemTypee）
{
if（S.top-S.base>=S.stacksize）
{
S.base=（SElemType*）realloc（S.base,（S.stacksize+Stack_MoreNUM）*sizeof（SElemType））;
if（!
S.base）exit（-1）;
S.top=S.base+S.stacksize;
S.stacksize+=Stack_MoreNUM;
}
*S.top++=e;
returnOK;
}
/*拓扑排序*/
intTopoSort（ALGraphG,AdjListTemp,structNamename[]）
{
inti,k,j=0,count,indegree[MAX_VERTEX_NUM];
SqStackS;
ArcNode*p;
FindInDegree（G,indegree）;//对各顶点求入度
InitStack（S）;//初始化栈
for（i=0;iif（!
indegree[i]）Push（S,i）;//入度为0者进栈
count=0;//对输出顶点计数
while（!
StackEmpty（S））
{
Pop（S,i）;
printf（"%s（%d分）,",G.vertices[i].data,G.vertices[i].grades）;
Temp[j++]=G.vertices[i];//将当前的拓扑序列保存起来
++count;//输出i号顶点并计数
for（p=G.vertices[i].firstarc;p;p=p->nextarc）//对i号顶点的每个邻接点的入度减1
{
k=p->adjvex;
if（!
（--indegree[k]））//若入度减为0,则入栈
Push（S,k）;
}
}
if（count{
printf（"此有向图有回路无法完成拓扑排序"）;
returnERROR;
}
elseprintf（"为一个拓扑序列"）;
printf（"\n"）;
intq=1,Z=0;//解决问题，学分
while（q<=TotalTerms）
{
intC=Temp[Z].grades;
printf（"\n第%d个学期应学课程:
",q）;
while（C<=MaxScores）
{
C=C+Temp[Z+1].grades;
if（Z{
printf（"%4s",Temp[Z].data）;
if（strcmp（Temp[Z].data,"c1"）==0）
printf（"程序设计基础"）;
if（strcmp（Temp[Z].data,"c2"）==0）
printf（"离散数学"）;
if（strcmp（Temp[Z].data,"c3"）==0）
printf（"数据结构"）;
if（strcmp（Temp[Z].data,"c4"）==0）
printf（"汇编语言"）;
if（strcmp（Temp[Z].data,"c5"）==0）
printf（"语言的设计和分析"）;
if（strcmp（Temp[Z].data,"c6"）==0）
printf（"计算机原理"）;
if（strcmp（Temp[Z].data,"c7"）==0）
printf（"编译原理"）;
if（strcmp（Temp[Z].data,"c8"）==0）
printf（"操作系统"）;
if（strcmp（Temp[Z].data,"c9"）==0）
printf（"高等数学"）;
if（strcmp（Temp[Z].data,"c10"）==0）
printf（"线性代数"）;
if（strcmp（Temp[Z].data,"c10"）==0）
printf（"普通物理"）;
if（strcmp（Temp[Z].data,"c12"）==0）
printf（"数值分析"）;
++Z;
}
}
printf（"\n"）;
if（q==TotalTerms）printf（"\n课程编制完成!
"）;
q++;
}
returnOK;
}
voidmain（）
{
ALGraphG;
AdjListTemp;
structNamename[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{"C8"},{"C9"},{"C10"},{"C11"},{"C12"}};
OUTPUT（）;
printf（"**********教学计划编制问题**********\n"）;
printf（"请输入学期总数:
"）;
scanf（"%d",&TotalTerms）;
printf（"请输入学期的学分上限:
"）;
scanf（"%d",&MaxScores）;
CreateGraph（G）;
Display（G）;
TopoSort（G,Temp,name）;
printf（"OK\n"）;
scanf（"*c"）;
}
升级会员 