目录
一、要求
? ? ? ?学院要求对每个专业的学生制定完备的教学计划，教学计划由课程组成，课程之间会有先后依赖关系（例如必须先学完《程序设计语言》后才能学习《数据结构》），假定每门课程需要一个学期学完，同一个学期可学习多门课程。请设计存储结构存储所有课程及其之间的依赖关系，并在此存储结构基础上完成如下操作：
1. 输入并保存课程及课程之间的依赖关系。
2. 判断课程能否顺利学完，若能，输出一个正确的学习顺序。
3. 求学完这些课程最少需要几个学期，并给出一个初步的教学计划（每个学期学习哪几门课程）。
4. 由于学生精力的限制，学校对每学期选课数的上限进行了约束，请判断约束后学生能够在原来的学期数内完成学习，若不能，此时最少需要几个学期学完这些课程（选做）。
二、分析
?1. 存储结构
由于课程与课程之间的关系较为复杂，并且后续操作涉及到度的操作，增加、删除操作不是很重要。所以，我们采取邻接矩阵进行存储点与点之间的关系。
2. 算法分析
1）拓扑排序
? ? ? ?根据第二问的提问，我们可以很自然的联系到运用拓扑排序的知识进行解决。如果根据拓扑排序，所有的点(课程)能够以特殊的先后顺序进行排序，那么这些课程便能够学完，反之，则不行。
2）入度为0
? ? ? ?第三问，最短时间，我们可以想到，每一个学期先把入度为0的课程学完，这样就可以保证最短时间。
3）关键路径
? ? ? ?第四问，看似只是加入了时间限制，但是正是因为有了时间限制，那么就会产生如何选择的问题。举个例子：
? ? ? ?比如有四门课，分别是1，2，3，4；其中先学3才能学4其他都是独立的，假如我每学期只允许2门课，那么我的排序有可能是1，2；3；4共三学期，或者1，3；2，4共两学期，那么我要怎么处理才能保证是第二种排序？
? ? ? ?联想到关键路径，我们应该能够想到，当存在多个入度为0的点是，在科目数量限制下，我们应该优先选择关键路径上的点来保证整个流程的时间是最少的。
三、代码分析
1. 整体设计
- 定义一个课程结构体
- 定义一个图类，里面包含对课程操作的具体函数
- 设计菜单栏
2. 具体操作
1）定义一个课程结构体
里面包含课程的具体信息，也就是课程编号和名字
struct Course //定义课程结构体
{
char id[5]; //课程编号
char name[max]; //课程名字
};2）定义一个图类
包含对课程具体操作的函数
class Graph //定义一个类
{
public:
void Creat_graph(Graph *G); //将课程信息存入邻接矩阵
void TopologicalSort(Graph *G,int topo[]); //根据课程关系进行拓扑排序
void PrintPlan1(Graph *G); //短时间编排教学计划
void PrintPlan2(Graph *G,int topo[]); //对学期约束编排教学计划
void PrintCourse(Graph *G); //将科学信息打印搭配屏幕上
int Menu(); //菜单界面
protected: //不能访问私有
Course course[max];
int course_count; //课程数量
int arcs[max][max]; //邻接矩阵
};3）输入课程具体信息
输入课程编号、名字；以及课程之间的关联关系
void Graph::Creat_graph(Graph *G)
{
cout<<"请输入课程总数："<<endl; //分别输入一些列课程信息
cin>>G->course_count;
cout<<"请依次输入课程编号、名字："<<endl;
int i,j;
for(i=1;i<=G->course_count;i++)
{
cin>>G->course[i].id>>G->course[i].name;
}
memset(G->arcs,0,sizeof(G->arcs));
cout<<"请输入课程之间的关系："<<endl;
for(int k=0;k<16;k++)
{
cin>>i>>j;
G->arcs[i][j]=1; //邻接矩阵中将输入对应课程信息的位置置为1
}
cout<<"键盘信息成功录入！"<<endl;
}4）打印课程信息和邻接矩阵
void Graph::PrintCourse(Graph *G)
{
int i,j;
cout<<"课程信息："<<endl; //分别将课程信息和邻接矩阵打印出来
for(i=1;i<=G->course_count;i++)
{
cout<<G->course[i].id<<" ";
cout<<G->course[i].name<<" ";
cout<<endl;
}
cout<<endl<<"课程关系矩阵："<<endl;
for(i=1;i<=G->course_count;i++)
{
for(j=1;j<=G->course_count;j++)
{
cout<<G->arcs[i][j]<<" ";
}
cout<<endl;
}
}
5）拓扑排序
? ? ? ?我们需要定义一个辅助数组，用来存储各个点的入度，之后我们基本的操作思路就是，利用一个栈，暂时的将入度为0的点放进去，在依次取栈顶元素输出，并且在此还要进行的操作就是入栈点到关联点的那个关联点的入度就要-1，所以我们还要访问邻接矩阵。最终如果所有点都成功保存在topo[]中，那么我们就能成功学完所有科目。
void Graph::TopologicalSort(Graph *G,int topo[])
{
int indegree[max]; //定义辅助数组，存储每个点的入度
memset(indegree,0,sizeof(indegree)); //对数组初始化置0
int i,j;
for(i=1;i<=G->course_count;i++)
{
for(j=1;j<=G->course_count;j++)
{
if(G->arcs[i][j]) //遍历邻接矩阵，存在指向j就在j点的入度+1
{
indegree[j]++;
}
}
}
cout<<"统计结点入度："<<endl; //将辅助数组中统计的入度结果输出
for(i=1;i<=G->course_count;i++)
{
cout<<i<<": "<<indegree[i]<<endl;
}
stack<int> s; //定义一个int类型的栈
for(i=1;i<=G->course_count;i++) //先对所有点进行遍历，如果入度为0；就入栈
{
if(!indegree[i])
{
s.push(i);
}
}
int num =0; //定义num为拓扑排序数组里面的下标，每存入一个就+1
int top; //用来暂时保存栈顶元素，传给拓扑数组并且带入对应邻接矩阵位置，将指向位置的入度-1
while(!s.empty()) //当栈里面的元素不为空时持续做循环
{
top=s.top();//取栈顶元素保存在top变量中
s.pop(); //将栈顶元素出栈
topo[num]=top; //将取出的栈顶元素保存在topos数组中
++num; //topo数组的下标+1
for(j=1;j<=G->course_count;j++) //将top指向j的邻接表位置，入度-1，并且判断不为0是入栈
{
if(G->arcs[top][j])
{
if(!--indegree[j])
{
s.push(j);
}
}
}
}
if(num==G->course_count)//如果保存进入topo数组的下标等于课程数，那么课程能够顺利学完
{
cout<<"课程能够顺利学完！"<<endl;
}
else
{
cout<<"课程不能顺利学完！可以顺利学习的课程排序如下："<<endl;
}
cout<<"教学安排如下（拓扑排序）："<<endl; //将topo排序好的课程编号和名字依次打印出来
for(i=0;i<G->course_count;i++)
{
cout<<G->course[topo[i]].id<<" ";
cout<<G->course[topo[i]].name<<" ";
cout<<endl;
}
}6）最短时间
? ? ? ?根据之前的思路，我们想要将每一次入度为0的点进行输出作为一个学期，当输出这些点后，与她有关联的点的入度也要-1.我们也需要定义一个辅助数组存储入度，之后利用栈暂时存储入度为0的点再释放，巧妙的运用学期数与循环的关系构建循环体，在循环体之间对点进行操作。
void Graph::PrintPlan1(Graph *G)
{
cout<<"课程编排最少学期安排："<<endl;
int indegree[max]; //定义辅助数组，存储每个点的入度
memset(indegree,0,sizeof(indegree)); //对数组初始化置0
int i,j,k,c,term,index[max]; //i,j,k循环变量，c保存栈的大小用于循环，将第一学期选中的课保存在index数组中，避免重复循环
term=1; //学期
memset(index,0,sizeof(index)); //对数组初始化置0
int num=G->course_count;
int top; //取栈顶元素保存在top变量中
for(i=1;i<=G->course_count;i++) //遍历邻接矩阵，存在指向j就在j点的入度+1
{
for(j=1;j<=G->course_count;j++)
{
if(G->arcs[i][j])
{
indegree[j]++;
}
}
}
stack<int> s; //定义一个int类型的栈
for(i=1;i<=num;) //从第一个元素开始循环，如果一个学期入栈c个，用num-c，保证一学期一学期计算
{
cout<<"第"<<term<<"学期："<<endl;
term++;
for(j=1;j<=G->course_count;j++)
{
if(!indegree[j]&&j!=index[j])//如果满足入度为0，并且前面没有选过就入栈
{
s.push(j);
}
}
c=s.size(); //统计栈里有的元素个数
num=num-c; //最外层循环减去入栈的元素，这样就可以解决学期问题
for(j=0;j<c;j++) //将栈里的元素出栈，并且输出对应课程信息
{
top=s.top();
index[top]=top; //这里index的下标和值一样，可以巧妙的带入前面入栈条件的筛选
s.pop();
cout<<G->course[top].id<<" ";
cout<<G->course[top].name<<" "<<endl;
for(k=1;k<=G->course_count;k++) //遍历邻接矩阵，top指向k,k的入度-1；
{
if(G->arcs[top][k])
{
--indegree[k];
}
}
}
}
}
7）关键路径
? ? ? ?这个问题很容易就只在上一问基础上加上学期数目控制。但是，如果我们仔细推敲就会想到之前我提出的问题。那么我们就要结合关键路径进行分析。
? ? ? ?首先计算关键路径，我们先要得到最早开始时间ve，接着计算最晚开始时间，两者时间一致即为关键路径。
? ? ? ?得到关键路径之后，我们对入度为0的点根据其关键路径的先后顺序和科目数量上限进行排序输出，这样就保证整体时间最少且符合最短时间。
? ? ? ?最后，将求得的最短时间与之前求得的最短时间相比，如果一致，则可以在原来时间完成，反之不可以。
void Graph::PrintPlan2(Graph *G,int topo[])
{
int i,j,k,x,ve[max],vl[max];//分别定义最早开始时间和最晚开始时间数组
x=0;
memset(ve,0,sizeof(ve));//最早开始时间数组初始化
cout<<"最早发生时间："<<endl;
for(i=0;i<G->course_count;i++) //根据拓扑排序，在邻接矩阵具体位置，将最早发生时间存储在ve中
{
k=topo[i];
for (j=0;j<G->course_count;j++)
{
if (G->arcs[k][j+1]!=0)
{
if(ve[j]<ve[k-1]+1)
{
ve[j]=ve[k-1]+1;
}
}
}
}
for(i=0;i<G->course_count;i++) //将最早发生时间依次输出
{
cout<<i+1<<": "<<ve[i]<<endl;
}
cout<<"最晚发生时间："<<endl;
for(i=0;i<G->course_count;i++)//在最早发生时间中，找到最大值x
{
if(ve[i]>x)
{
x=ve[i];
}
}
for(i=0;i<G->course_count;i++)//给最晚发生时间全部赋最大值
{
vl[i]=x;
}
for(i=G->course_count;i>=0;i--) //根据拓扑排序，倒着看，将最小的(最晚发生时间)存储在vl中
{
k=topo[i];
for(j=0;j<G->course_count;j++)
{
if(G->arcs[k][j+1]!=0)
{
if(vl[k-1]>vl[j]-1)
{
vl[k-1]=vl[j]-1;
}
}
}
}
for(i=0;i<G->course_count;i++)//依次输出最晚发生时间
{
cout<<i+1<<": "<<vl[i]<<endl;
}
cout<<"课程编排最少学期安排（选课数量约束）："<<endl;
int indegree[max];
memset(indegree,0,sizeof(indegree));
for(i=1;i<=G->course_count;i++) //遍历邻接矩阵，存在指向j就在j点的入度+1
{
for(j=1;j<=G->course_count;j++)
{
if(G->arcs[i][j])
{
indegree[j]++;
}
}
}
stack<int> s; //定义一个int类型的栈
int term=1,max_sub,tmp;//学期数初始值，最大学习科目，排序交换变量
int now_sub=0;//记录已近计算了的当前科目
x=0;//记录处理完的科目，便于循环结束
cout<<"输入每学期限制的科目数："<<endl;
cin>>max_sub; //输入限制科目数
int temp[max]; //将所有入度为0的点放入temp中
memset(temp,0,sizeof(temp));//将temp初始化为0
cout<<"学期安排情况："<<endl;
while(x<G->course_count) //入度为0的点放入temp中
{
for(i=1,now_sub=0;i<=G->course_count;i++)
{
if(0==indegree[i])
{
temp[now_sub]=i;
now_sub++;
}
}
for(i=0;i<now_sub;i++) //根据temp数组中值对应的最迟开始时间，对temp数组进行排序
{
for(j=0;j<now_sub-1;j++)
{
if(vl[(temp[j]-1)]>vl[(temp[j+1])-1]){
tmp=temp[j];
temp[j]=temp[j+1];
temp[j+1]=tmp;
}
}
}
for(i=0;i<now_sub&&i<max_sub;i++)//将满足科目数目和关键路径的点入栈
{
s.push((temp[i]));
indegree[(temp[i])]=-2;
}
cout<<"第"<<term<<"学期："<<endl;
while(!s.empty()) //输出栈元素并且对相应入度值-1
{
int top=s.top();
s.pop();
x++;
now_sub++;
cout<<G->course[top].id<<" ";
cout<<G->course[top].name<<" "<<endl;
for(i=1;i<=G->course_count;i++)
{
if(G->arcs[top][i])
{
indegree[i]--;
}
}
}
term++;//循环结束时，学期数+1
}
if(term==6)//因为最后依次循环term已经加了一，所以判断的学期数为6
{
cout<<"综上，约束后学生能够在原来的学期数内完成学习!"<<endl;
}
else
{
cout<<"综上，约束后学生不能够在原来的学期数内完成学习!增加了"<<term-6<<"个学期。"<<endl;
}
}
?8）菜单栏
int Graph::Menu()
{
int i;
do
{
system("cls");
cout << "***************教学计划编制系统****************" << endl << endl;
cout << " 1.读入课程信息" << endl;
cout << " 2.课程信息输出" << endl;
cout << " 3.输出一个正确的课程学习顺序" << endl;
cout << " 4.按尽可能短的时间完成学习制定教学计划" << endl;
cout << " 5.对选课数量约束后制定的教学计划(前提：使用过功能3!)" << endl;
cout << " 6.退出程序" << endl << endl;
cout << "请输入您的选择：";
cin >> i;
}while(i<1||i>6);
return i;
}?9）主函数
int main()
{
int i;
Graph graph,*G;
int topo[max];
memset(topo,0,sizeof(topo));
G =(Graph*)malloc(sizeof(Graph));
first:
switch(graph.Menu())
{
case 1:
{
system("cls");
graph.Creat_graph(G);
system("pause");
goto first;
}
case 2:
{
system("cls");
graph.PrintCourse(G);
system("pause");
goto first;
}
case 3:
{
system("cls");
graph.TopologicalSort(G,topo);
system("pause");
goto first;
}
case 4:
{
system("cls");
graph.PrintPlan1(G);
system("pause");
goto first;
}
case 5:
{
system("cls");
graph.PrintPlan2(G,topo);
system("pause");
goto first;
}
}
return 0;
}
三、功能实现
1.菜单栏
?2.输入课程信息
3.输出课程信息
?
4.输出正确的课程学习顺序?
?5.最短学习时间
?6.科目数量限制后最短学习时间
?四、整体代码呈现
#include <stack> //关于栈的一些函数，后面直接调用
#include <cstring>
#include <fstream>
#include <iostream>
#include <cstdlib>
#define max 20 //将下面数组最大定义位为20
using namespace std;
struct Course //定义课程结构体
{
char id[5]; //课程编号
char name[max]; //课程名字
};
class Graph //定义一个类
{
public:
void Creat_graph(Graph *G); //将课程信息存入邻接矩阵
void TopologicalSort(Graph *G,int topo[]); //根据课程关系进行拓扑排序
void PrintPlan1(Graph *G); //短时间编排教学计划
void PrintPlan2(Graph *G,int topo[]); //对学期约束编排教学计划
void PrintCourse(Graph *G); //将科学信息打印搭配屏幕上
int Menu(); //菜单界面
protected: //不能访问私有
Course course[max];
int course_count; //课程数量
int arcs[max][max]; //邻接矩阵
};
void Graph::Creat_graph(Graph *G)
{
cout<<"请输入课程总数："<<endl; //分别输入一些列课程信息
cin>>G->course_count;
cout<<"请依次输入课程编号、名字："<<endl;
int i,j;
for(i=1;i<=G->course_count;i++)
{
cin>>G->course[i].id>>G->course[i].name;
}
memset(G->arcs,0,sizeof(G->arcs));
cout<<"请输入课程之间的关系："<<endl;
for(int k=0;k<16;k++)
{
cin>>i>>j;
G->arcs[i][j]=1; //邻接矩阵中将输入对应课程信息的位置置为1
}
cout<<"键盘信息成功录入！"<<endl;
}
void Graph::PrintCourse(Graph *G)
{
int i,j;
cout<<"课程信息："<<endl; //分别将课程信息和邻接矩阵打印出来
for(i=1;i<=G->course_count;i++)
{
cout<<G->course[i].id<<" ";
cout<<G->course[i].name<<" ";
cout<<endl;
}
cout<<endl<<"课程关系矩阵："<<endl;
for(i=1;i<=G->course_count;i++)
{
for(j=1;j<=G->course_count;j++)
{
cout<<G->arcs[i][j]<<" ";
}
cout<<endl;
}
}
void Graph::TopologicalSort(Graph *G,int topo[])
{
int indegree[max]; //定义辅助数组，存储每个点的入度
memset(indegree,0,sizeof(indegree)); //对数组初始化置0
int i,j;
for(i=1;i<=G->course_count;i++)
{
for(j=1;j<=G->course_count;j++)
{
if(G->arcs[i][j]) //遍历邻接矩阵，存在指向j就在j点的入度+1
{
indegree[j]++;
}
}
}
cout<<"统计结点入度："<<endl; //将辅助数组中统计的入度结果输出
for(i=1;i<=G->course_count;i++)
{
cout<<i<<": "<<indegree[i]<<endl;
}
stack<int> s; //定义一个int类型的栈
for(i=1;i<=G->course_count;i++) //先对所有点进行遍历，如果入度为0；就入栈
{
if(!indegree[i])
{
s.push(i);
}
}
int num =0; //定义num为拓扑排序数组里面的下标，每存入一个就+1
int top; //用来暂时保存栈顶元素，传给拓扑数组并且带入对应邻接矩阵位置，将指向位置的入度-1
while(!s.empty()) //当栈里面的元素不为空时持续做循环
{
top=s.top();//取栈顶元素保存在top变量中
s.pop(); //将栈顶元素出栈
topo[num]=top; //将取出的栈顶元素保存在topos数组中
++num; //topo数组的下标+1
for(j=1;j<=G->course_count;j++) //将top指向j的邻接表位置，入度-1，并且判断不为0是入栈
{
if(G->arcs[top][j])
{
if(!--indegree[j])
{
s.push(j);
}
}
}
}
if(num==G->course_count)//如果保存进入topo数组的下标等于课程数，那么课程能够顺利学完
{
cout<<"课程能够顺利学完！"<<endl;
}
else
{
cout<<"课程不能顺利学完！可以顺利学习的课程排序如下："<<endl;
}
cout<<"教学安排如下（拓扑排序）："<<endl; //将topo排序好的课程编号和名字依次打印出来
for(i=0;i<G->course_count;i++)
{
cout<<G->course[topo[i]].id<<" ";
cout<<G->course[topo[i]].name<<" ";
cout<<endl;
}
}
void Graph::PrintPlan1(Graph *G)
{
cout<<"课程编排最少学期安排："<<endl;
int indegree[max]; //定义辅助数组，存储每个点的入度
memset(indegree,0,sizeof(indegree)); //对数组初始化置0
int i,j,k,c,term,index[max]; //i,j,k循环变量，c保存栈的大小用于循环，将第一学期选中的课保存在index数组中，避免重复循环
term=1; //学期
memset(index,0,sizeof(index)); //对数组初始化置0
int num=G->course_count;
int top; //取栈顶元素保存在top变量中
for(i=1;i<=G->course_count;i++) //遍历邻接矩阵，存在指向j就在j点的入度+1
{
for(j=1;j<=G->course_count;j++)
{
if(G->arcs[i][j])
{
indegree[j]++;
}
}
}
stack<int> s; //定义一个int类型的栈
for(i=1;i<=num;) //从第一个元素开始循环，如果一个学期入栈c个，用num-c，保证一学期一学期计算
{
cout<<"第"<<term<<"学期："<<endl;
term++;
for(j=1;j<=G->course_count;j++)
{
if(!indegree[j]&&j!=index[j])//如果满足入度为0，并且前面没有选过就入栈
{
s.push(j);
}
}
c=s.size(); //统计栈里有的元素个数
num=num-c; //最外层循环减去入栈的元素，这样就可以解决学期问题
for(j=0;j<c;j++) //将栈里的元素出栈，并且输出对应课程信息
{
top=s.top();
index[top]=top; //这里index的下标和值一样，可以巧妙的带入前面入栈条件的筛选
s.pop();
cout<<G->course[top].id<<" ";
cout<<G->course[top].name<<" "<<endl;
for(k=1;k<=G->course_count;k++) //遍历邻接矩阵，top指向k,k的入度-1；
{
if(G->arcs[top][k])
{
--indegree[k];
}
}
}
}
}
void Graph::PrintPlan2(Graph *G,int topo[])
{
int i,j,k,x,ve[max],vl[max];//分别定义最早开始时间和最晚开始时间数组
x=0;
memset(ve,0,sizeof(ve));//最早开始时间数组初始化
cout<<"最早发生时间："<<endl;
for(i=0;i<G->course_count;i++) //根据拓扑排序，在邻接矩阵具体位置，将最早发生时间存储在ve中
{
k=topo[i];
for (j=0;j<G->course_count;j++)
{
if (G->arcs[k][j+1]!=0)
{
if(ve[j]<ve[k-1]+1)
{
ve[j]=ve[k-1]+1;
}
}
}
}
for(i=0;i<G->course_count;i++) //将最早发生时间依次输出
{
cout<<i+1<<": "<<ve[i]<<endl;
}
cout<<"最晚发生时间："<<endl;
for(i=0;i<G->course_count;i++)//在最早发生时间中，找到最大值x
{
if(ve[i]>x)
{
x=ve[i];
}
}
for(i=0;i<G->course_count;i++)//给最晚发生时间全部赋最大值
{
vl[i]=x;
}
for(i=G->course_count;i>=0;i--) //根据拓扑排序，倒着看，将最小的(最晚发生时间)存储在vl中
{
k=topo[i];
for(j=0;j<G->course_count;j++)
{
if(G->arcs[k][j+1]!=0)
{
if(vl[k-1]>vl[j]-1)
{
vl[k-1]=vl[j]-1;
}
}
}
}
for(i=0;i<G->course_count;i++)//依次输出最晚发生时间
{
cout<<i+1<<": "<<vl[i]<<endl;
}
cout<<"课程编排最少学期安排（选课数量约束）："<<endl;
int indegree[max];
memset(indegree,0,sizeof(indegree));
for(i=1;i<=G->course_count;i++) //遍历邻接矩阵，存在指向j就在j点的入度+1
{
for(j=1;j<=G->course_count;j++)
{
if(G->arcs[i][j])
{
indegree[j]++;
}
}
}
stack<int> s; //定义一个int类型的栈
int term=1,max_sub,tmp;//学期数初始值，最大学习科目，排序交换变量
int now_sub=0;//记录已近计算了的当前科目
x=0;//记录处理完的科目，便于循环结束
cout<<"输入每学期限制的科目数："<<endl;
cin>>max_sub; //输入限制科目数
int temp[max]; //将所有入度为0的点放入temp中
memset(temp,0,sizeof(temp));//将temp初始化为0
cout<<"学期安排情况："<<endl;
while(x<G->course_count) //入度为0的点放入temp中
{
for(i=1,now_sub=0;i<=G->course_count;i++)
{
if(0==indegree[i])
{
temp[now_sub]=i;
now_sub++;
}
}
for(i=0;i<now_sub;i++) //根据temp数组中值对应的最迟开始时间，对temp数组进行排序
{
for(j=0;j<now_sub-1;j++)
{
if(vl[(temp[j]-1)]>vl[(temp[j+1])-1]){
tmp=temp[j];
temp[j]=temp[j+1];
temp[j+1]=tmp;
}
}
}
for(i=0;i<now_sub&&i<max_sub;i++)//将满足科目数目和关键路径的点入栈
{
s.push((temp[i]));
indegree[(temp[i])]=-2;
}
cout<<"第"<<term<<"学期："<<endl;
while(!s.empty()) //输出栈元素并且对相应入度值-1
{
int top=s.top();
s.pop();
x++;
now_sub++;
cout<<G->course[top].id<<" ";
cout<<G->course[top].name<<" "<<endl;
for(i=1;i<=G->course_count;i++)
{
if(G->arcs[top][i])
{
indegree[i]--;
}
}
}
term++;//循环结束时，学期数+1
}
if(term==6)//因为最后依次循环term已经加了一，所以判断的学期数为6
{
cout<<"综上，约束后学生能够在原来的学期数内完成学习!"<<endl;
}
else
{
cout<<"综上，约束后学生不能够在原来的学期数内完成学习!增加了"<<term-6<<"个学期。"<<endl;
}
}
int Graph::Menu()
{
int i;
do
{
system("cls");
cout << "***************教学计划编制系统****************" << endl << endl;
cout << " 1.读入课程信息" << endl;
cout << " 2.课程信息输出" << endl;
cout << " 3.输出一个正确的课程学习顺序" << endl;
cout << " 4.按尽可能短的时间完成学习制定教学计划" << endl;
cout << " 5.对选课数量约束后制定的教学计划(前提：使用过功能3!)" << endl;
cout << " 6.退出程序" << endl << endl;
cout << "请输入您的选择：";
cin >> i;
}while(i<1||i>6);
return i;
}
int main()
{
int i;
Graph graph,*G;
int topo[max];
memset(topo,0,sizeof(topo));
G =(Graph*)malloc(sizeof(Graph));
first:
switch(graph.Menu())
{
case 1:
{
system("cls");
graph.Creat_graph(G);
system("pause");
goto first;
}
case 2:
{
system("cls");
graph.PrintCourse(G);
system("pause");
goto first;
}
case 3:
{
system("cls");
graph.TopologicalSort(G,topo);
system("pause");
goto first;
}
case 4:
{
system("cls");
graph.PrintPlan1(G);
system("pause");
goto first;
}
case 5:
{
system("cls");
graph.PrintPlan2(G,topo);
system("pause");
goto first;
}
}
return 0;
}
五、感谢
教学计划编制_zhuhezhang的博客-CSDN博客_教学计划编制
?
?