教学计划编制问题_如何编制教学计划
教学计划编制问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“如何编制教学计划”。
背景
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
问题描述
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。
一． 需求分析
1.顶点表示课程名称（包含学分信息），有向边表示课程之间的先修关系，用有向图实现这个教学计划编制问题。
2.采用广度优先的方法搜索每个节点是否有边通向该节点。3.对有向图实行拓扑排序
4.程序输出的拓扑排序就是其教学修读课程的序列 5.测试数据：
输入：请输入课程的数量和课程先后关系：6
每门课程的编号：001 002 003 004 005 006
先修课程编号（课程 课程）
001 002 001 003 002 003 002 004 003 005
004 006
005 006 输出：001 002 003 004 005 006 二． 概要设计
1.抽象数据类型：
由于课程之间存在明显的先后关系，采用拓扑排序进行教学计划的排序，而拓扑排序不直接输出课程信息，而采用队列实现课程信息的输出 拓扑图的ADT的定义： ADT Graph{ 数据对象：Subject是课程编号，是类型为char的二维数组
数据关系R：点a，b∈Graph，若点a到b有一条边，则arcs[a][b]=1;否则=0； 基本操作P：
void Adj(Graph &G,char *c1,char *c2)//建立邻接矩阵
int Locate(Graph G,char *c){//图G中查找元素c的位置 int Indegree(Graph G,int pos)//计算入度 void DeleteDegree(Graph &G,int pos)//删除一条边 队列的抽象数据类型定义： ADT Queue{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：Rl={|ai-1,ai∈D,i=2,…,n}
约定其中ai端为队列头，an端为队列尾。基本操作
void InitQueue(Queue &Q){//初始化队列
void EnQueue(Queue &Q,int e){//入队列
void DeQueue(Queue &Q,int &e){//出队列
bool EmptyQueue(Queue Q)//判断是否为空 void InitQueue(Queue &Q)操作结果：构造一个空队列Q void EnQueue(Queue &Q,Node e)初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素 void DeQueue(Queue &Q,Node &e)初始条件：Q为非空队列
操作结果：删除Q的队头元素，并用e返回其值 } 2.算法的基本思想：
a.在有向图中选取一个入度为零的顶点并输出 b.删除该顶点及所有以它为尾的弧
c.重复a,b两步，知道所有节点均输出或者无度为零的节点结束。3.程序的流程
程序由四个模块组成：
（1）输入模块：从键盘键入课程编号和课程之间的先修关系（2）建立Graph模块：构建符合课程关系的有向图（3）排序模块：对有向图图进行拓扑排序（4）输出模块：输出拓扑序列
三、详细设计
物理数据类型
由于课程与课程之间存在先修关系，可以采用有向图来构建课程与课程之间的关系，用邻接矩阵来实现图，采用入度为零的广度优先搜索来实现拓扑排序，用队列的方式来实现广度优先搜索
typedef struct{
char Subject[MAX_VEX][5];//顶点向量
int arcs[MAX_VEX][MAX_VEX];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数 }Graph;图的伪代码：
cla Graph{
//图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点
string ch;
for(int i=0;i
cout
cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
} } void pushEdge(){ //读入边
string ch1,ch2;
int pos1,pos2;
for(int i=0;i
{
cout
cin>>ch1>>ch2;
for(int j=0;j
if(line[j].head->node==ch1)
pos1=j;
//找到该字母对应的位置
if(line[j].head->node==ch2){
pos2=line[j].head->position;
break;
}
}
line[pos1].insert(pos2,ch2);
} } typedef struct{
int *base;
int front;
int rear;
}Queue;拓扑排序的伪代码为：
void topsort(){
//拓扑排序
int i;
int *d=new int[numVertex];
for(i=0;i
d[i]=0;
//数组初始化
for(i=0;i
Node* p=line[i].head;
while(p->next!=NULL){
d[p->next->position]++;//计算每个点的入度
p=p->next;
} 用队列实现拓扑排序的伪代码：
int top=-1,m=0,j,k;
for(i=0;i
if(d[i]==0){
d[i]=top;
//找到第一个入度为0的点
top=i;
}
while(top!=-1){
j=top;
top=d[top];
coutnode
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;
} 算法的具体步骤
void CreateUDN(Graph &G){//建立一个有向图
//输入课程总数
//输入每门课程的编号 //输入课程的先修关系 } bool TopSort(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 每门课程的编号：001 002 003 004 005 006 输入课程关系（课程 课程）001 002 001 003 002 003 002 004 003 005
004 006
005 006 输出：教学计划为001 002 003 004 005 006 实验结果截图：
附录（代码）#include #include using namespace std;cla Node{//结点类 public:
string node;
int position;//位置
Node* next;
bool visit;//是否被访问
Node(){visit=false;next=NULL;position=0;node=' ';} };cla Line{
//线性表类 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();}
void insert(int v,string ch){
//插入元素
Node* current=new Node();
current->node=ch;
current->position=v;
fence->next=current;
fence=current;
num++;} };cla Graph{
//图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点
string ch;
for(int i=0;i
cout
cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
} } void pushEdge(){ //读入边
string ch1,ch2;
int pos1,pos2;
for(int i=0;i
{
cout
cin>>ch1>>ch2;
for(int j=0;j
if(line[j].head->node==ch1)
pos1=j;
//找到该字母对应的位置
if(line[j].head->node==ch2){
pos2=line[j].head->position;
break;
}
}
line[pos1].insert(pos2,ch2);
} }
void topsort(){
//拓扑排序
int i;
int *d=new int[numVertex];
for(i=0;i
d[i]=0;
//数组初始化
for(i=0;i
Node* p=line[i].head;
while(p->next!=NULL){
d[p->next->position]++;//计算每个点的入度
p=p->next;
}
} int top=-1,m=0,j,k;
for(i=0;i
if(d[i]==0){
d[i]=top;
//找到第一个入度为0的点
top=i;
}
while(top!=-1){
j=top;
top=d[top];
coutnode
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(m
//输出点的个数小于输入点的个数，不能完全遍历
cout
delete []d;} };int main(){
int n,m;cout>n>>m;if((n
G.pushVertex();G.pushEdge();G.topsort();system(“pause”);
return 0;} }
