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

问题描述： 若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。 基本要求： （1） 3位的字母数字串）和直接先修课的课程号。 （2） 需求分析： 本程序需要基于图的基本操作来实现 二、概要设计 ： 抽象数据类型 ： 为实现上述功能需建立一个结点类，线性表类，图类。 算法的基本思想 ： 1、图的构建： 建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。 2、Topsort算法： 先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再有哪些信誉好的足球投注网站其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。 程序的流程 程序由三个模块组成： 输入模块： 读入图的信息（顶点和边，用线性表进行存储）。 处理模块：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=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 Line[v];} void pushVertex(){ //读入点 string ch; for(int i=0;inumVertex;i++){ cout请输入顶点i+1:; cinch; line[i].head-node=ch; line[i].head-position=i; } } void pushEdge(){ //读入边 string ch1,ch2; int pos1,pos2; for(int i=0;inumEdge;i++) { cout请输入边i+1:; cinch1ch2; for(int j=0;jnumVertex;j++){ if(line[j].head-node==ch1) pos1=j; //找到该字母对应的位置 if(line[j].head-node==ch2){ pos2=line[j].head-position; break; } } line[pos1].insert(pos2,ch2); } } void topsort(){ //拓扑排序 int i; int *d=new int[numVertex]; for(i=0;inumVertex;i++) d[i]=0; //数组初始化 for(i=0;inumVertex;i++){ Node* p=line[i].head; while(p-next!=NULL){ d[p-next-position]++; //计算