教学计划编制问题课程设计Word版.docx
《教学计划编制问题课程设计Word版.docx》由会员分享，可在线阅读，更多相关《教学计划编制问题课程设计Word版.docx（29页珍藏版）》请在冰点文库上搜索。
教学计划编制问题课程设计Word版
信息与电气工程学院
课程设计说明书
（2015/2016学年第一学期）
课程名称：
软件算法分析与设计
题目：
教学计划编制
专业班级：
计算机1401
学生姓名：
李丹丹
学号：
140210132
指导教师：
陈丽
设计周数：
一周
设计成绩：
2016年1月13日
一、课题的主要功能1
1.1程序的功能1
1.2.输入输出的要求1
1.3运行环境1
1.4开发工具1
二、概要设计2
2.1程序的模块组成2
2.2模块的层次结构及调用关系2
2.3模块的主要功能3
2.4数据结构和数据库结构3
三．主要功能的实现3
3.1采用C语言定义相关的数据类型。
3
3.2主要函数的流程图4
3.3画出各函数的调用关系图11
四、程序调试12
4.1测试数据：
12
4.2使用说明13
五．心得体会14
六、附录15
6.1参考书目15
6.2源程序清单（带注释）16
一、课题的主要功能
1.1程序的功能
大学的每个专业都要制订教学计划。
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。
每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。
每门课恰好占一个学期。
试在这样的前提下设计一个教学计划编制程序。
本程序针对本科的学期内容，通过输入实际的课程及先后关系。
结合每学期的学分及课程数，制定好学习计划。
在输入相关数据后，程序会安排好每学期的课程。
1.2.输入输出的要求
输入参数包括：
学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。
1.3运行环境
1.WINDOWS7系统
2.Vc++6.0编译环境
1.4开发工具
C语言
二、概要设计
2.1所负责的程序的模块
LocateVex（）：
图的邻接表存储的基本操作
CreateGraph（）：
构造生成树
Display（）：
输出图的邻接矩阵
FindInDegree（）：
求顶点的入度
2.2模块的层次结构及调用关系
2.3模块的主要功能
见“详细设计”－“主要函数流程图”
2.4数据结构和数据库结构
储存的数据为结构体类型数组，以及结构体单链表结点类型。
1typedefstructArcNode
弧所指定点位置
指向下一条弧的指针
网的权值指针
int
struct
InfoType
2typedefstruct
顶点信息
第一个表结点的地址
VertexType
ArcNode
三．主要功能的实现
3.1采用C语言定义相关的数据类型。
其中包括字符常量，整型，字符型，字符串型，typedef定义的类型，结构体型，单链表节点类型，结构体数组。
3.2主要函数的流程图
1.LocateVex（）：
图的邻接表存储的基本操作。
由初始条件:
图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
2.CreateGraph（）：
构造生成图。
采用邻接表存储结构,构造没有相关信息的图G（用一个函数构造种图）。
3.Display（）：
输出图的邻接矩阵。
采用循环设置输出图的邻接矩阵。
4.FindInDegree（）：
求顶点的入度。
所负责的部分程序：
/*图的邻接表存储的基本操作*/
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;
}
}
}
3.3画出各函数的调用关系图
四、程序调试
4.1测试数据：
准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。
数据如下：
学期总数：
6；
学分上限：
10；
该专业共开设课数：
12
课程号：
从C01到C12；
学分顺序：
2，3，4，3，2，3，4，4，7，5，2，3。
先修顺序（有向图表示）：
4.2使用说明
输入学期总数，学分上限，课程数，先修关系边数
输入课程代表符号：
输入相对学分值：
回车，将显示顶点的个数和弧的条数
输入完成后执行可得到每个学期的课程计划结果
5．总结体会
虽这门课程让我从C语言基础再深入的了解了软件开发的复杂性。
对以往模糊的经验，起了总结提升的作用。
在学习了这门课程后，我们进行了1个星期的课程设计，来实践我们所学这门课的内容。
由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。
这需要我们不断的调试分析。
符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。
在逐条排除，向同学老师请教后，程序终于得以完成。
这让我明白了，解决问题，要细心认真，集思广益，这样才能把问题解决。
六、附录
6.1参考书目
1黄同成，黄俊民，董建寅．数据结构[M]．北京：
中国电力出版社，2008
2董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：
中国电力出版社，2008
3严蔚敏，吴伟民.数据结构（C语言版）[M].北京：
清华大学出版社，2002
4唐策善，李龙澍，黄刘生．数据结构—用C语言描述[M]．北京：
高等教育出版社，2001
6.2源程序清单（带注释）
#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;
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;
}
}
}
typedefintSElemType;/*栈类型*/
/*栈的顺序存储表示*/
#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT2/*存储空间分配增量*/
typedefstructSqStack
{
SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/
SElemType*top;/*栈顶指针*/
intstacksize;/*当前已分配的存储空间，以元素为单位*/
}SqStack;/*顺序栈*/
/*顺序栈的基本操作*/
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;
}
typedefintpathone[MAXCLASS];
typedefintpathtwo[MAXCLASS];
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;
升级会员 