资源描述：
《教学计划编制问题王鹏》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、背景大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。问题描述若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其
2、先修课程已经被安排）。一．需求分析1.顶点表示课程名称（包含学分信息），有向边表示课程之间的先修关系，用有向图实现这个教学计划编制问题。2.采用广度优先的方法搜索每个节点是否有边通向该节点。3.对有向图实行拓扑排序4.程序输出的拓扑排序就是其教学修读课程的序列5.测试数据：输入：请输入课程的数量和课程先后关系：67每门课程的编号：001002003004005006先修课程编号（课程课程）001002001003002003002004003005004006005006输出：001002003004005006二．概要设计1.抽象数据类型：由于课程之间存在
3、明显的先后关系，采用拓扑排序进行教学计划的排序，而拓扑排序不直接输出课程信息，而采用队列实现课程信息的输出拓扑图的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)//计算入度voidDeleteDegr
4、ee(Graph&G,intpos)//删除一条边队列的抽象数据类型定义：
ADTQueue{
数据对象：D={ai
5、ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：Rl={
6、ai-1,ai∈D,i=2,…,n}
约定其中ai端为队列头，an端为队列尾。
基本操作voidInitQueue(Queue&Q){//初始化队列voidEnQueue(Queue&Q,inte){//入队列voidDeQueue(Queue&Q,int&e){//出队列boolEmptyQueue(QueueQ)//判断是否为空voidInitQue
7、ue(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模块：
8、构建符合课程关系的有向图（3）排序模块：对有向图图进行拓扑排序（4）输出模块：输出拓扑序列三、详细设计物理数据类型由于课程与课程之间存在先修关系，可以采用有向图来构建课程与课程之间的关系，用邻接矩阵来实现图，采用入度为零的广度优先搜索来实现拓扑排序，用队列的方式来实现广度优先搜索typedefstruct{charSubject[MAX_VEX][5];//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;图的伪代码：classGraph{//图类private:i
9、ntnumVertex;intnumEdge;Line*line;public:Graph(intv,inte){numVertex=v;numEdge=e;line=newLine[v];}voidpushVertex(){//读入点stringch;for(inti=0;i>ch;line[i].head->node=ch;line[i].head->position=i;}}voidpushEdge(){//读入边stringch1,ch2;intpos1,pos2
10、;for(inti=0;i
