教学计划的编制问题(实验10实验报告)

数据结构实验报告题目：教学计划的编制问题姓名：杨维学号：20090810229班级：物联网工程0901班指导老师：李晓鸿完成日期：2010年11月26日一、问题描述：若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。基本要求（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。二．需求分析：1、本程序需要基于图的基本操作来实现三．概要设计抽象数据类型：为实现上述功能需建立一个结点类，线性表类，图类。算法的基本思想：图的构建：建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。Topsort算法：先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。程序的流程：输入模块：读入图的信息（顶点和边，用线性表进行存储）。处理模块：topsort算法。输出模块：将结果输出。四．详细设计：算法的具体步骤：classNode{//结点类public:stringnode;intposition;//位置Node*next;boolvisit;//是否被访问Node(){visit=false;next=NULL;position=0;node='';}};classLine{//线性表类public: intnum; Node*head; Node*rear; Node*fence; Line(){num=0;head=fence=rear=newNode();} voidinsert(intv,stringch){//插入元素 Node*current=newNode(); current->node=ch; current->position=v; fence->next=current; fence=current; num++; }};classGraph{//图类private: intnumVertex; intnumEdge; Line*line;public: Graph(intv,inte){numVertex=v;numEdge=e;line=newLine[v];} voidpushVertex(){//读入点 stringch; for(inti=0;i<numVertex;i++){ cout<<"请输入顶点"<<i+1<<":"; cin>>ch; line[i].head->node=ch; line[i].head->position=i; } } voidpushEdge(){//读入边 stringch1,ch2; intpos1,pos2; for(inti=0;i<numEdge;i++) { cout<<"请输入边"<<i+1<<":"; cin>>ch1>>ch2; for(intj=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); } } voidtopsort(){//拓扑排序 inti; int*d=newint[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; } } inttop=-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]--;//当起点被删除，时后面的点的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } }cout<<endl; if(m<numVertex)//输出点的个数小于输入点的个数，不能完全遍历 cout<<"网络存在回路"<<endl; delete[]d; }};intmain(){intn,m; cout<<"请输入节点的个数和边的个数"<<endl; cin>>n>>m; GraphG(n,m); G.pushVertex(); G.pushEdge(); G.topsort(); system("pause");return0;}五．调试分析：将建立的线性表输出来检验图的信息是否完全被读入，构建是否正确。六．测试结果：七．实验心得：1、本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图的遍历问题中的代码（不过要将结点类中的char改为string型），自己另外写了topsort函数，就完成了整个程序。2、topsort函数中一开始采用的方法是找到一个入度为0的点，完成相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的点后面连接的点，这样减少了算法复杂度。八、附件教学计划的编制问题.cpp#include<iostream>#include<string.h>usingnamespacestd;classNode{//结点类public:stringnode;intposition;//位置Node*next;boolvisit;//是否被访问Node(){visit=false;next=NULL;position=0;node='';}};classLine{//线性表类public: intnum; Node*head; Node*rear; Node*fence; Line(){num=0;head=fence=rear=newNode();} voidinsert(intv,stringch){//插入元素 Node*current=newNode(); current->node=ch; current->position=v; fence->next=current; fence=current; num++; }};classGraph{//图类private: intnumVertex; intnumEdge; Line*line;public: Graph(intv,inte){numVertex=v;numEdge=e;line=newLine[v];} voidpushVertex(){//读入点 stringch; for(inti=0;i<numVertex;i++){ cout<<"请输入顶点"<<i+1<<":"; cin>>ch; line[i].head->node=ch; line[i].head->position=i; } } voidpushEdge(){//读入边 stringch1,ch2; intpos1,pos2; for(inti=0;i<numEdge;i++) { cout<<"请输入边"<<i+1<<":"; cin>>ch1>>ch2; for(intj=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); } } voidtopsort(){//拓扑排序 inti; int*d=newint[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; } } inttop=-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]--;//当起点被删除，时后面的点的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } }