数据结构实验报告十—教学计划编制问题_数据结构实验报告实验
数据结构实验报告十—教学计划编制问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告实验”。
问题描述：
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。
基本要求：
（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。
（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。
一、需求分析：
本程序需要基于图的基本操作来实现
二、概要设计 ：
抽象数据类型 ：
为实现上述功能需建立一个结点类，线性表类，图类。
算法的基本思想 ：
1、图的构建：
建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。
2、Topsort算法：
先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。程序的流程
程序由三个模块组成：
输入模块： 读入图的信息（顶点和边，用线性表进行存储）。处理模块：topsort算法。输出模块：将结果输出。
三、详细设计
算法的具体步骤： cla Node{//结点类 public: string node;int position;//位置 Node* next;bool visit;//是否被访问
Node(){visit=false;next=NULL;position=0;node=' ';} };cla 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++;} };cla 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
cout
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
{
cout
cin>>ch1>>ch2;
for(int j=0;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
d[i]=0;//数组初始化
for(i=0;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
if(d[i]==0){
d[i]=top;//找到第一个入度为0的点
top=i;
}
while(top!=-1){ j=top;top=d[top];
coutnode
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
cout>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(“pause”);return 0;}
四、调试分析
略。
五、测试结果
本实验的测试结果截图如下：
注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入。
六、用户使用说明（可选）
1、本程序的运行环境为windows 操作系统，执行文件为Untitled1.exe 2、运行程序时
提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。
七、实验心得（可选）
1、本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图 的遍历问题中的代码（不过要将结点类中的char改为string型），自己另外写了topsort函数，就完成了整个程序。
2、topsort函数中一开始采用的方法是找到一个入度为0的点，完成 相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的 点后面连接的点，这样减少了算法复杂度。
附录（实验代码）：
#include #include using namespace std;cla Node{//结点类 public: string node;int position;//位置 Node* next;bool visit;//是否被访问
Node(){visit=false;next=NULL;position=0;node=' ';} };cla 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++;} };cla 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
cout
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
{
cout
cin>>ch1>>ch2;
for(int j=0;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
d[i]=0;//数组初始化
for(i=0;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
if(d[i]==0){
d[i]=top;//找到第一个入度为0的点
top=i;
}
while(top!=-1){ j=top;top=d[top];
coutnode
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
cout>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(“pause”);return 0;}
