数据结构实验报告十—教学计划编制问题

1、.问题描述： 若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。基本要求：（1） 输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。（2） 若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。一、 需求分析：本程序需要基于图的基本操作来实现二、概要设计 ： 抽象数据类型 ：为实现上述功能需建立一个结点类，线性表类，图类。 算法

2、的基本思想 ： 1、图的构建：建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。2、Topsort算法：先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数

3、，说明该图存在环。程序的流程 程序由三个模块组成： 输入模块： 读入图的信息（顶点和边，用线性表进行存储）。处理模块：topsort算法。输出模块：将结果输出。 三、详细设计 算法的具体步骤：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

4、=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 pushVerte

5、x() /读入点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.inser

6、t(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-positio

7、n; dk-; /当起点被删除，时后面的点的入度-1 if(dk=0)dk=top; top=k; p=p-next; coutendl; if(mnumVertex) /输出点的个数小于输入点的个数，不能完全遍历 cout网络存在回路endl; delete d;int main() int n,m;cout请输入节点的个数和边的个数nm;Graph G(n,m); G.pushVertex();G.pushEdge();G.topsort ();system(pause); return 0;四、调试分析 略。 五、测试结果 本实验的测试结果截图如下：注：此处由于不会用文件流输入和输出，故

8、在命令提示符上直接进行输入。六、用户使用说明（可选） 1 、本程序的运行环境为windows 操作系统，执行文件为Untitled1.exe 2 、运行程序时 提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。七、实验心得（可选） 1、 本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图的遍历问题中的代码（不过要将结点类中的char改为string型），自己另外写了topsort函数，就完成了整个程序。2、 topsort函数中一开始采用的方法是找到一个入度为0的点，完成相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的点后面连接的点，这样减少了算法复

9、杂度。附录（实验代码）： #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

10、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+)cou

11、t请输入顶点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=n

12、ew 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; cou