2 教学计划编制问题.docx
《2 教学计划编制问题.docx》由会员分享，可在线阅读，更多相关《2 教学计划编制问题.docx（19页珍藏版）》请在冰点文库上搜索。
2教学计划编制问题
教学计划编制问题
一．问题描述
我们知道教学计划在编制的过程中，有一个层次的关系。
比如说：
数值分析必须在高等数学学完之后才可以学习，数据结构必须要在学习了一两门程序设计语言之后才可以学习。
也就是说有的课程必须要在学习完了某些课程之后才可以学习。
二．设计思路
编制教学计划，当然涉及到的课程都要给学完。
所以我们可以将所以的课程编制成一张图，然后遍历图。
由于课程有前续后继的关系，所以用AOV网是最合适。
对AOV网进行拓扑排序即可以得出结果。
对AOV网进行拓扑排序有两种情况：
广度优先和深度优先。
在进行深度优先周游时，我们要考虑到一种情况。
例如：
高等数学和C语言编程是并列的两门学科，他们之间没有前续后继的关系，可以同时进行学习。
高等数学是数值分析和电子电路的基础课程，电子电路又是模拟电子电路的基础课程。
C语言编程是数据结构的基础课程，数据结构是算法设计与分析的基础课程。
如果按照深度优先周游的话就有可能将上面几门课程排成：
C语言程序设计，数据结构，算法设计与分析，高等数学，电子电路，模拟电子电路。
这样的教学计划很明显不符合实际教学的需要。
因此我们应该进行广度优先周游，将高等数学和C语言程序设计先学，再学其他后继课程。
三．解决问题
计算机系的课程如下：
（只罗列出具有前续后继关系的课程，像马列等课程由于和其他课程没有关联，所以在课程排序好后考虑每个学期的课程量时随机加入）
1，高等数学17，JAVA程序设计
2，概率论和数理统计18，编译原理
3，线形代数19，现代通信技术
4，C语言程序设计20，计算机网络
5，电路理论21，软件工程
6，模拟电子技术22，算法设计与分析
7，数字逻辑23，人工智能
8，面向对象编程技术24，Matlab编程技术
9，数据结构25，电子商务
10，汇编语言26，分布式数据库
11，计算机组成原理27，网络数据库编程
12，微机原理与接口技术28，计算机图形学
13，操作系统29，图象处理
14，数据库概论30，嵌入式系统
15，数值分析31，多媒体技术
16，计算机控制基础
下面是课程之间先后关系的AOV网：
注：
课程之间的先后关系可能可能不完全正确，我们以解决问题为主，其他的大家不要深究。
将上面的AOV网用邻接表表示如下：
入度
顶点
边表
30
∧
0
1
15
28
∧
0
2
15
28
∧
28
0
3
15
28
∧
0
4
8
9
10
24
0
5
6
∧
1
6
7
∧
1
7
11
∧
1
8
14
17
19
21
∧
1
9
14
21
22
∧
1
10
11
∧
2
11
12
∧
1
12
13
16
18
30
∧
1
13
∧
2
14
26
∧
3
15
∧
1
16
23
∧
1
17
∧
1
18
∧
1
19
20
∧
1
20
25
31
∧
2
21
∧
1
22
23
∧
2
23
∧
1
24
∧
1
25
∧
1
26
27
∧
1
27
∧
4
28
29
∧
1
29
∧
2
30
∧
1
31
∧
四．实现
1．功能函数设计
pGraphListinitGraph（void）;
此函数的作用是初始化一个AOV网，入度都初始化为零，边表都初始化为NULL。
课程代号从1按次序到31。
pLinkQueuecreatEmptyQueue（void）;
创建一个空队列
intisEmptyQueue（pLinkQueuepQueue）;
判断队列是否问空，如果为空返回1，否则返回0
voidenQueue（pLinkQueuepQueue,intx）;
入对操作
voiddeQueue（pLinkQueuepQueue）;
出队操作
intgetQueueHead（pLinkQueuepQueue）;
得到队列头部的数据
voidfindIndegree（pGraphListpList）;
得到每个顶点的入度
voidtopoSort（pGraphListpList）;
拓扑排序
pGraphListinitEdgeList（pGraphListpList,intx,intindex）;
初始化边表。
即在主函数中调用一次此函数就要一个结点存入指定的地方
下面是源代码：
#include
#include
intpTopo[31];//存放拓扑排序的结果
//为什么使用全局变量，在运行与测试中进行说明
structedgeNode;
typedefstructedgeNode*pEdgeNode;
typedefstructedgeNode*pEdgeList;
//邻接表中边表的结点
structedgeNode
{
intindex;
pEdgeNodenext;
};
//存放顶点信息的结构体
structvertexNode
{
intvertexInfo;
intinDegree;
pEdgeListnext;
};
typedefstructvertexNode*pVertexNode;
//对AOV网进行封装
structgraphList
{
intn;
pVertexNodevertex[31];
};
typedefstructgraphList*pGraphList;
structnode;
typedefstructnode*pNode;
//链接表队列中的结点
structnode
{
intinfo;
pNodelink;
};
//队列的封装
structlinkQueue
{
pNodehead;
pNoderear;
};
typedefstructlinkQueue*pLinkQueue;
//初始化图
pGraphListinitGraph（void）;
//创建空队列
pLinkQueuecreatEmptyQueue（void）;
//判断队列是否为空
intisEmptyQueue（pLinkQueuepQueue）;
//入队操作
voidenQueue（pLinkQueuepQueue,intx）;
//出队操作
voiddeQueue（pLinkQueuepQueue）;
//取队列头部的元素
intgetQueueHead（pLinkQueuepQueue）;
//得到每个结点的入度
voidfindIndegree（pGraphListpList）;
//拓扑排序
voidtopoSort（pGraphListpList）;
//输入每个边表
pGraphListinitEdgeList（pGraphListpList,intx,intindex）;
intmain（）
{
char*array[31];//存放课程名称
pGraphListpList;
pList=initGraph（）;
pList=initEdgeList（pList,15,0）;
pList=initEdgeList（pList,28,0）;
pList=initEdgeList（pList,15,1）;
pList=initEdgeList（pList,28,1）;
pList=initEdgeList（pList,15,2）;
pList=initEdgeList（pList,28,2）;
pList=initEdgeList（pList,8,3）;
pList=initEdgeList（pList,9,3）;
pList=initEdgeList（pList,10,3）;
pList=initEdgeList（pList,24,3）;
pList=initEdgeList（pList,28,3）;
pList=initEdgeList（pList,30,3）;
pList=initEdgeList（pList,6,4）;
pList=initEdgeList（pList,7,5）;
pList=initEdgeList（pList,11,6）;
pList=initEdgeList（pList,14,7）;
pList=initEdgeList（pList,17,7）;
pList=initEdgeList（pList,19,7）;
pList=initEdgeList（pList,21,7）;
pList=initEdgeList（pList,14,8）;
pList=initEdgeList（pList,21,8）;
pList=initEdgeList（pList,22,8）;
pList=initEdgeList（pList,11,9）;
pList=initEdgeList（pList,12,10）;
pList=initEdgeList（pList,13,11）;
pList=initEdgeList（pList,16,11）;
pList=initEdgeList（pList,18,11）;
pList=initEdgeList（pList,30,11）;
pList=initEdgeList（pList,26,13）;
pList=initEdgeList（pList,23,15）;
pList=initEdgeList（pList,20,18）;
pList=initEdgeList（pList,25,19）;
pList=initEdgeList（pList,31,19）;
pList=initEdgeList（pList,23,21）;
pList=initEdgeList（pList,27,25）;
pList=initEdgeList（pList,29,27）;
array[0]="1.高等数学";
array[1]="2.概率论与数理统计";
array[2]="3.线形代数";
array[3]="4.C语言程序设计";
array[4]="5.电路理论";
array[5]="6.模拟电子技术";
array[6]="7.数字逻辑";
array[7]="8.面向对象编程技术";
array[8]="9.数据结构";
array[9]="10.汇编语言";
array[10]="11.计算机组成原理";
array[11]="12.微机原理与接口技术";
array[12]="13.操作系统";
array[13]="14.数据库概论";
array[14]="15.数值分析";
array[15]="16.计算机控制基础";
array[16]="17.JAVA程序设计";
array[17]="18.编译原理";
array[18]="19.现代通信技术";
array[19]="20.计算机网络";
array[20]="21.软件工程";
array[21]="22.算法设计与分析";
array[22]="23.人工智能";
array[23]="24.Matlab编程技术";
array[24]="25.电子商务";
array[25]="26.分布式数据库";
array[26]="27.网络数据库编程";
array[27]="28.计算机图形学";
array[28]="29.图象处理";
array[29]="30.嵌入式系统";
array[30]="31.多媒体技术";
topoSort（pList）;
for（inti=0;i<31;i++）
printf（"%s\n",array[pTopo[i]-1]）;
return0;
}
pGraphListinitGraph（void）//初始化图，边表都赋值为NULL
{
inti;
pGraphListpList;
pList=（pGraphList）malloc（sizeof（structgraphList））;
for（i=0;i<31;i++）
pList->vertex[i]=（pVertexNode）malloc（sizeof（structvertexNode））;
pList->n=31;
for（i=0;i<31;i++）
pList->vertex[i]->vertexInfo=i+1;
for（i=0;i<31;i++）
pList->vertex[i]->next=NULL;
returnpList;
}
pLinkQueuecreatEmptyQueue（void）//创建空对列
{
pLinkQueuepQueue;
pQueue=（pLinkQueue）malloc（sizeof（structlinkQueue））;
if（pQueue!
=NULL）
{
pQueue->head=NULL;
pQueue->rear=NULL;
}
else
printf（"Outofspace!
\n"）;
returnpQueue;
}
intisEmptyQueue（pLinkQueuepQueue）
{
returnpQueue->head==NULL;
}
voidenQueue（pLinkQueuepQueue,intx）//判断队列是否为空
{
pNodep;
p=（pNode）malloc（sizeof（structnode））;
if（p==NULL）
printf（"Outofspace!
\n"）;
else
{
p->info=x;
p->link=NULL;
if（pQueue->head==NULL）
pQueue->head=p;
else
pQueue->rear->link=p;
pQueue->rear=p;
}
}
voiddeQueue（pLinkQueuepQueue）//出队
{
pNodep;
if（pQueue->head==NULL）
printf（"Emptyqueue.\n"）;
else
{
p=pQueue->head;
pQueue->head=p->link;
free（p）;
}
}
intgetQueueHead（pLinkQueuepQueue）//取队列头部的数据
{
if（pQueue->head==NULL）
printf（"Emptyqueue.\n"）;
else
returnpQueue->head->info;
}
voidfindIndegree（pGraphListpList）//计算出每个顶点的入度
{
inti;
pEdgeNodep;
for（i=0;in;i++）//初始化为0
pList->vertex[i]->inDegree=0;
for（i=0;in;i++）
{
p=pList->vertex[i]->next;
while（p!
=NULL）
{
pList->vertex[p->index-1]->inDegree++;
p=p->next;
}
}
}
voidtopoSort（pGraphListpList）//拓扑排序
{
intelement;
inti;
intn=0;
intk;
pLinkQueuepQueue;
pEdgeListp;
findIndegree（pList）;
pQueue=creatEmptyQueue（）;
for（i=0;in;i++）
if（pList->vertex[i]->inDegree==0）
{
enQueue（pQueue,pList->vertex[i]->vertexInfo）;
}
while（!
isEmptyQueue（pQueue））
{
element=getQueueHead（pQueue）;
deQueue（pQueue）;
pTopo[n++]=element;
p=pList->vertex[element-1]->next;
while（p）
{
k=p->index;
pList->vertex[k-1]->inDegree--;
if（pList->vertex[k-1]->inDegree==0）
{
enQueue（pQue
升级会员 