教学计划编制问题.doc

背景大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。问题描述若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。一 需求分析1. 顶点表示课程名称（包含学分信息），有向边表示课程之间的先修关系，用有向图实现这个教学计划编制问题。2. 采用广度优先的方法搜索每个节点是否有边通向该节点。3. 对有向图实行拓扑排序4. 程序输出的拓扑排序就是其教学修读课程的序列5. 测试数据：输入：请输入课程的数量和课程先后关系：6 7 每门课程的编号：001 002 003 004 005 006 先修课程编号（课程 课程） 001 002001 003002 003002 004003 005 004 006 005 006输出：001 002 003 004 005 006二 概要设计1. 抽象数据类型：由于课程之间存在明显的先后关系，采用拓扑排序进行教学计划的排序，而拓扑排序不直接输出课程信息，而采用队列实现课程信息的输出拓扑图的ADT的定义：ADT Graph数据对象：Subject是课程编号，是类型为char的二维数组数据关系R：点a，bGraph，若点a到b有一条边，则arcsab=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|aiElemSet,i=1,2,n,n0数据关系：Rl=|ai-1,aiD,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)操作结果：构造一个空队列Qvoid 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 SubjectMAX_VEX5; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数Graph;图的伪代码：class Graph /图类private:int numVertex;int numEdge;Line* line;public:Graph(int v,int e)numVertex=v;numEdge=e;line =new Linev;void pushVertex() /读入点string ch;for(int i=0;inumVertex;i+)cout请输入课程i+1ch;linei.head-node=ch;linei.head-position=i;void pushEdge() /读入边string ch1,ch2;int pos1,pos2;for(int i=0;inumEdge;i+)cout请输入课程关系i+1ch1ch2;for(int j=0;jnode=ch1)pos1=j; /找到该字母对应的位置if(linej.head-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2);typedef struct int *base; int front; int rear; Queue;拓扑排序的伪代码为：void topsort() /拓扑排序int i;int *d=new intnumVertex; for(i=0;inumVertex;i+)di=0; /数组初始化for(i=0;inext!=NULL)dp-next-position+; /计算每个点的入度 p=p-next;用队列实现拓扑排序的伪代码：int top=-1,m=0,j,k;for(i=0;inumVertex;i+)if(di=0)di=top; /找到第一个入度为0的点 top=i;while(top!=-1) j=top; top=dtop; coutnodenext!=NULL) k=p-next-position; dk-; /当起点被删除，时后面的点的入度-1 if(dk=0)dk=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 002001 003002 003002 004003 005 004 006 005 006输出：教学计划为001 002 003 004 005 006实验结果截图：附录（代码）#include#includeusing namespace std;class Node/结点类public: string node; int position; /位置 Node* next; bool visit; /是否被访问 Node()visit=false;next=NULL;position=0;node= ;class 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+;class Graph /图类private:int numVertex;int numEdge;Line* line;public:Graph(int v,int e)numVertex=v;numEdge=e;line =new Linev;void pushVertex() /读入点string ch;for(int i=0;inumVertex;i+)cout请输入课程i+1ch;linei.head-node=ch;linei.head-position=i;void pushEdge() /读入边string ch1,ch2;int pos1,pos2;for(int i=0;inumEdge;i+)cout请输入课程关系i+1ch1ch2;for(int j=0;jnode=ch1)pos1=j; /找到该字母对应的位置if(linej.head-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2); void topsort() /拓扑排序int i;int *d=new intnumVertex; for(i=0;inumVertex;i+)di=0; /数组初始化for(i=0;inext!=NULL)dp-next-position+; /计算每个点的入度 p=p-next;int top=-1,m=0,j,k;for(i=0;inumVertex;i+)if(di=0)di=top; /找到第一个入度为0的点 top=i;while(top!=-1) j=top; top=dtop; coutnodenext!=NULL) k=p-next-position; dk-; /当起点被删除，时后面的点的入度-1 if(dk=0)dk=top; top=k; p=p-next; coutendl; if