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

HUNAN UNIVERSITY 课程实验报告题目：教学计划的编制问题学生姓名学生学号201208010专业班级计算机科学与技术班完成日期一、需求分析（1）输入的形式和输入值的范围：输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。

（2）输出的形式：若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。

（3）程序所能达到的功能：按照用户的输入，给出每学期应学的课程。

（4）测试数据：输入：7（结点数）8（边的数量）结点1：mat结点2：che结点3：eng结点4：phy结点5：bio结点6：geo结点7：com边1：mat che边2：mat eng边3：che eng边4：che phy边5：phy geo边6：phy bio边7：geo com边8：eng geo输出：mat che phy bio eng geo com二、概要设计抽象数据类型为实现上述功能，我们建立一个结点类，线性表类和图类。

结点的ADT如下：数据类型：字符串由于定义的结点是属于图的元素，故没有基本操作，里面所有的元素都用public 存储。

线性表的ADT如下：数据对象：D={ai|aiЄNode}数据关系：R1={<ai,ai+1>|ai,ai+1ЄD}基本操作：void insert(int v,string ch) //插入元素图的ADT如下：数据对象：具有相同数据的结点类组成的顶点集数据关系：R1={<w,v>|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 Line[v];}void pushVertex(){ //读入点string ch;for(int i=0;i<numVertex;i++){cout<<"请输入顶点"<<i+1<<":";cin>>ch;line[i].head->node=ch;line[i].head->position=i;}}void pushEdge(){ //读入边string ch1,ch2;int pos1,pos2;for(int i=0;i<numEdge;i++){cout<<"请输入边"<<i+1<<":";cin>>ch1>>ch2;for(int j=0;j<numVertex;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);}}Topsort算法：先计算每个点的入度，保存在数组中。

找到第一个入度为0的点，将该点所连的各点的入度减一。

再在这些点中找入度为0 的点。

如果找到，重复上述操作。

如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。

再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。

void topsort(){ //拓扑排序int i;int *d=new int[numVertex];for(i=0;i<numVertex;i++)d[i]=0; //数组初始化for(i=0;i<numVertex;i++){Node* p=line[i].head;while(p->next!=NULL){d[p->next->position]++; //计算每个点的入度p=p->next;}}int top=-1,m=0,j,k;for(i=0;i<numVertex;i++){if(d[i]==0){d[i]=top; //找到第一个入度为0的点top=i;}while(top!=-1){j=top;top=d[top];cout<<line[j].head->node<<" ";m++;Node* p=line[j].head;while(p->next!=NULL){k=p->next->position;d[k]--; //当起点被删除，时后面的点的入度-1if(d[k]==0){d[k]=top;top=k;}p=p->next;}}}cout<<endl;if(m<numVertex) //输出点的个数小于输入点的个数，不能完全遍历cout<<"网络存在回路"<<endl;delete []d;}};int main(){int n,m;cout<<"请输入节点的个数和边的个数"<<endl;cin>>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort ();system("pause");return 0;}算法的时空分析时间复杂度：O（n），空间复杂度：O（n）；函数的调用关系图开始↓输入图的结点数和边数↓输入图中各个课程名称↓输入边关系↓拓扑排序↓结束输入和输出的格式输入：7（结点数）8（边的数量）结点1：mat结点2：che结点3：eng结点4：phy结点5：bio结点6：geo结点7：com边1：mat che边2：mat eng边3：che eng边4：che phy边5：phy geo边6：phy bio边7：geo com边8：eng geo输出：mat che phy bio eng geo com四、测试结果五、用户使用说明（可选）1、本程序的运行环境为DOS操作系统，执行文件为教学计划编制.exe2、运行程序时：(1) 显示提示“请输入结点数和边数”，此时输入结点数和边数。

(2) 数据输入完毕后，拓扑排序若成功则输出排序结果，若不成功则输出提示语句。

六、实验心得这次实验让我更加了解图的定义，对课堂内容更加了解。

七、附录#include<iostream>#include<string.h>using 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 Line[v];} void pushVertex(){ //读入点string ch;for(int i=0;i<numVertex;i++){cout<<"请输入顶点"<<i+1<<":";cin>>ch;line[i].head->node=ch;line[i].head->position=i;}}void pushEdge(){ //读入边string ch1,ch2;int pos1,pos2;for(int i=0;i<numEdge;i++){cout<<"请输入边"<<i+1<<":";cin>>ch1>>ch2;for(int j=0;j<numVertex;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;i<numVertex;i++)d[i]=0; //数组初始化for(i=0;i<numVertex;i++){Node* p=line[i].head;while(p->next!=NULL){d[p->next->position]++; //计算每个点的入度p=p->next;}}int top=-1,m=0,j,k;for(i=0;i<numVertex;i++){if(d[i]==0){d[i]=top; //找到第一个入度为0的点top=i;}while(top!=-1){j=top;top=d[top];cout<<line[j].head->node<<" ";m++;Node* p=line[j].head;while(p->next!=NULL){k=p->next->position;d[k]--; //当起点被删除，时后面的点的入度-1if(d[k]==0){d[k]=top;top=k;}p=p->next;}}}cout<<endl;if(m<numVertex) //输出点的个数小于输入点的个数，不能完全遍历cout<<"网络存在回路输入错误"<<endl;delete []d;}};int main(){int n,m;cout<<"请输入节点的个数和边的个数"<<endl;cin>>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort ();system("pause");return 0;}。