实验五 教学计划的编制问题.doc

实验五 教学计划的编制问题 HUNAN UNIVERSITY课程实验报告题目教学计划的编制问题学生姓名学生学号xx08010专业班级计算机科学与技术班完成日期 一、需求分析 （1）输入的形式和输入值的范围输入参数课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。 （2）输出的形式若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。 （3）程序所能达到的功能按照用户的输入，给出每学期应学的课程。 （4）测试数据输入7（结点数）8（边的数量）结点1mat结点2che结点3eng结点4phy结点5bio结点6geo结点7边1mat che边2mat eng边3che eng边4che phy边5phy geo边6phy bio边7geo 边8eng geo输出mat che phy bioeng geo 二、概要设计抽象数据类型为实现上述功能，我们建立一个结点类，线性表类和图类。 结点的ADT如下数据类型字符串由于定义的结点是属于图的元素，故没有基本操作，里面所有的元素都用public存储。 线性表的ADT如下数据对象D=ai|ai?Node数据关系R1=|ai,ai+1?D基本操作void insert(int v,string ch)/插入元素图的ADT如下数据对象具有相同数据的结点类组成的顶点集数据关系R1=|w,v?Node，w,v表示w,v之间存在直接先修关系基本操作void pushVertex()/读入点void pushEdge()/读入边void topsort()/拓扑排序算法的基本思想先建立一个结点类，类中数据包括字符串、当前位置以及其指向的元素位置以及入度出度。 为了方便实现这个算法，图用线性表来存储，线性表中的元素为结点类。 将图中结点和边的关系输入这个图中，然后进行拓扑排序，若拓扑排序成功则输出正确的顺序，若不成功即有回路则输出提示语句。 程序流程程序由三个模块组成 （1）输入模块读入图的信息（顶点和边，用线性表进行存储）。 （2）处理模块topsort算法。 （3）输出模块将结果输出。 各程序模块之间的层次关系主函数会先调用输入模块确定图的结点和边，再循环调用Topsort算法，最后将结果提示给用户。 三、详细设计实现概要设计中的数据类型用整型存储用户的输入，并将相应数据存入Node类。 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;ich;linei.head-node=ch;linei.head-position=i;void pushEdge()/读入边string ch1,ch2;int pos1,pos2;for(int i=0;ich1ch2;for(int j=0;jnode=ch1)pos1=j;/找到该字母对应的位置if(linej.head-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2);Topsort算法先计算每个点的入度，保存在数组中。 找到第一个入度为0的点，将该点所连的各点的入度减一。 再在这些点中找入度为0的点。 如果找到，重复上述操作。 如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。 再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。 void topsort()/拓扑排序int i;int*d=new intnumVertex;for(i=0;inext!=NULL)dp-next-position+;/计算每个点的入度p=p-next;int top=-1,m=0,j,k;for(i=0;inodenext!=NULL)k=p-next-position;dk-;/当起点被删除，时后面的点的入度-1if(dk=0)dk=top;top=k;p=p-next;coutnm;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(pause);return0;算法的时空分析时间复杂度O（n），空间复杂度O（n）；函数的调用关系图开始输入图的结点数和边数输入图中各个课程名称输入边关系拓扑排序结束输入和输出的格式输入7（结点数）8（边的数量）结点1mat结点2che结点3eng结点4phy结点5bio结点6geo结点7边1mat che边2mat eng边3che eng边4chephy边5phy geo边6phy bio边7geo边8eng geo输出mat chephy bioeng geo 四、测试结果 五、用户使用说明（可选） 1、本程序的运行环境为DOS操作系统，执行文件为教学计划编制.exe 2、运行程序时 (1)显示提示“请输入结点数和边数”，此时输入结点数和边数。 (2)数据输入完毕后，拓扑排序若成功则输出排序结果，若不成功则输出提示语句。 六、实验心得这次实验让我更加了解图的定义，对课堂内容更加了解。 七、附录#include#includeusing namespacestd;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;ich;linei.head-node=ch;linei.head-position=i;void pushEdge()/读入边string ch1,ch2;int pos1,pos2;for(int i=0;ich1ch2;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;inext!=NULL)dp-next-position+;/计算每个点的入度p=p-next;int top=-1,m=0,j,k;f