教学计划编制问题王鹏.docx
《教学计划编制问题王鹏.docx》由会员分享，可在线阅读，更多相关《教学计划编制问题王鹏.docx（13页珍藏版）》请在冰点文库上搜索。
教学计划编制问题王鹏
背景
大学的每个专业都要制定教学计划。
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。
每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。
每门课恰好占一个学期。
试在这样的前提下设计一个教学计划编制程序。
问题描述
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。
试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。
（课程线性排列，每门课上课时其先修课程已经被安排）。
一．需求分析
1.顶点表示课程名称（包含学分信息），有向边表示课程之间的先修关系，用有向图实现这个教学计划编制问题。
2.采用广度优先的方法搜索每个节点是否有边通向该节点。
3.对有向图实行拓扑排序
4.程序输出的拓扑排序就是其教学修读课程的序列
5.测试数据：
输入：
请输入课程的数量和课程先后关系：
67
每门课程的编号：
001002003004005006
先修课程编号（课程课程）
001002
001003
002003
002004
003005
004006
005006
输出：
001002003004005006
二．概要设计
1.抽象数据类型：
由于课程之间存在明显的先后关系，采用拓扑排序进行教学计划的排序，而拓扑排序不直接输出课程信息，而采用队列实现课程信息的输出
拓扑图的ADT的定义：
ADTGraph{
数据对象：
Subject是课程编号，是类型为char的二维数组
数据关系R：
点a，b∈Graph，若点a到b有一条边，则arcs[a][b]=1;否则=0；
基本操作P：
voidAdj（Graph&G,char*c1,char*c2）//建立邻接矩阵
intLocate（GraphG,char*c）{//图G中查找元素c的位置
intIndegree（GraphG,intpos）//计算入度
voidDeleteDegree（Graph&G,intpos）//删除一条边
队列的抽象数据类型定义：
ADTQueue{
数据对象：
D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：
Rl={|ai-1,ai∈D,i=2,…,n}
约定其中ai端为队列头，an端为队列尾。
基本操作
voidInitQueue（Queue&Q）{//初始化队列
voidEnQueue（Queue&Q,inte）{//入队列
voidDeQueue（Queue&Q,int&e）{//出队列
boolEmptyQueue（QueueQ）//判断是否为空
voidInitQueue（Queue&Q）
操作结果：
构造一个空队列Q
voidEnQueue（Queue&Q,Nodee）
初始条件：
队列Q已存在
操作结果：
插入元素e为Q的新的队尾元素
voidDeQueue（Queue&Q,Node&e）
初始条件：
Q为非空队列
操作结果：
删除Q的队头元素，并用e返回其值
}
2.算法的基本思想：
a.在有向图中选取一个入度为零的顶点并输出
b.删除该顶点及所有以它为尾的弧
c.重复a,b两步，知道所有节点均输出或者无度为零的节点结束。
3.程序的流程
程序由四个模块组成：
（1）输入模块：
从键盘键入课程编号和课程之间的先修关系
（2）建立Graph模块：
构建符合课程关系的有向图
（3）排序模块：
对有向图图进行拓扑排序
（4）输出模块：
输出拓扑序列
三、详细设计
物理数据类型
由于课程与课程之间存在先修关系，可以采用有向图来构建课程与课程之间的关系，用邻接矩阵来实现图，采用入度为零的广度优先搜索来实现拓扑排序，用队列的方式来实现广度优先搜索
typedefstruct{
charSubject[MAX_VEX][5];//顶点向量
intarcs[MAX_VEX][MAX_VEX];//邻接矩阵
intvexnum,arcnum;//图的当前顶点数和弧数
}Graph;
图的伪代码：
classGraph{//图类
private:
intnumVertex;
intnumEdge;
Line*line;
public:
Graph（intv,inte）{numVertex=v;numEdge=e;line=newLine[v];}
voidpushVertex（）{//读入点
stringch;
for（inti=0;icout<<"请输入课程"<";
cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
}
}
voidpushEdge（）{//读入边
stringch1,ch2;
intpos1,pos2;
for（inti=0;i{
cout<<"请输入课程关系"<";
cin>>ch1>>ch2;
for（intj=0;jif（line[j].head->node==ch1）
pos1=j;//找到该字母对应的位置
if（line[j].head->node==ch2）{
pos2=line[j].head->position;
break;
}
}
line[pos1].insert（pos2,ch2）;
}
}
typedefstruct{
int*base;
intfront;
intrear;
}Queue;
拓扑排序的伪代码为：
voidtopsort（）{//拓扑排序
inti;
int*d=newint[numVertex];
for（i=0;id[i]=0;//数组初始化
for（i=0;iNode*p=line[i].head;
while（p->next!
=NULL）{
d[p->next->position]++;//计算每个点的入度
p=p->next;
}
用队列实现拓扑排序的伪代码：
inttop=-1,m=0,j,k;
for（i=0;iif（d[i]==0）{
d[i]=top;//找到第一个入度为0的点
top=i;
}
while（top!
=-1）{
j=top;
top=d[top];
cout<node<<"";
m++;
Node*p=line[j].head;
while（p->next!
=NULL）{
k=p->next->position;
d[k]--;//当起点被删除，时后面的点的入度-1
if（d[k]==0）{
d[k]=top;
top=k;
}
p=p->next;
}
算法的具体步骤
voidCreateUDN（Graph&G）{//建立一个有向图
//输入课程总数
//输入每门课程的编号
//输入课程的先修关系
}
boolTopSort（Graph&G）
{
//有向图G采用邻接表储存结构
//若G无回路，则输出G的顶点的一个top序列并返回ture，否则返回false
//队列实现top序列的存储和输出
}
算法的时空分析
Top排序：
对有n个顶点和e条弧的有向图而言，将建立求各顶点的入度的时间复杂度为O（e）；建零入度定点站的时间复杂度为O（n），在top排序过程中，若有向图无环，则每个顶点近义词栈，出一次栈，入度减1的操作在while语句中总共执行e次，所以，总的时间复杂度为O（n+e）。
输入输出格式：
输入：
请输入课程的数量和课程先后关系的个数：
6
课程先后关系课程：
7
每门课程的编号：
001002003004005006
输入课程关系（课程课程）
001002
001003
002003
002004
003005
004006
005006
输出：
教学计划为001002003004005006
实验结果截图：
附录（代码）
#include
#include
usingnamespacestd;
classNode{//结点类
public:
stringnode;
intposition;//位置
Node*next;
boolvisit;//是否被访问
Node（）{visit=false;next=NULL;position=0;node='';}
};
classLine{//线性表类
public:
intnum;
Node*head;
Node*rear;
Node*fence;
Line（）{num=0;head=fence=rear=newNode（）;}
voidinsert（intv,stringch）{//插入元素
Node*current=newNode（）;
current->node=ch;
current->position=v;
fence->next=current;
fence=current;
num++;
}
};
classGraph{//图类
private:
intnumVertex;
intnumEdge;
Line*line;
public:
Graph（intv,inte）{numVertex=v;numEdge=e;line=newLine[v];}
voidpushVertex（）{//读入点
stringch;
for（inti=0;icout<<"请输入课程"<";
cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
}
}
voidpushEdge（）{//读入边
stringch1,ch2;
intpos1,pos2;
for（inti=0;i{
cout<<"请输入课程关系"<";
cin>>ch1>>ch2;
for（intj=0;jif（line[j].head->node==ch1）
pos1=j;//找到该字母对应的位置
if（line[j].head->node==ch2）{
pos2=line[j].head->position;
break;
}
}
line[pos1].insert（pos2,ch2）;
}
}
voidtopsort（）{//拓扑排序
inti;
int*d=newint[numVertex];
for（i=0;id[i]=0;//数组初始化
for（i=0;iNode*p=line[i].head;
while（p->next!
=NULL）{
d[p->next->position]++;//计算每个点的入度
p=p->next;
}
}
inttop=-1,m=0,j,k;
for（i=0;iif（d[i]==0）{
d[i]=top;//找到第一个入度为0的点
top=i;
}
while（top!
=-1）{
j=top;
top=d[top];
cout<node<<"";
m++;
Node*p=line[j].head;
while（p->next!
=NULL）{
k=p->next->position;
d[k]--;//当起点被删除，时后面的点的入度-1
if（d[k]==0）{
d[k]=top;
top=k;
}
p=p->next;
}
}
}
cout<if（mcout<<"网络存在回路"<delete[]d;
}
};
intmain（）{
intn,m;
cout<<"请输入课程总数和课程先后关系的个数"<cin>>n>>m;
if（（n<=0）||（m<=0））
{cout<<"输入错误"<else
{
GraphG（n,m）;
G.pushVertex（）;
G.pushEdge（）;
G.topsort（）;
system（"pause"）;
return0;
}
}
THANKS!
!
!
致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求
欢迎您的下载，资料仅供参考
升级会员 