教学计划编制问题(数据结构 有向图 拓扑排序)
本文对以下教学计划编制问题的解决作出实现，主要使用c语言(带一点cpp)，开发环境为codeblocks 17.12,希望对各位读者有所帮助。（源码和数据文件可在主页获取，同时还有使用视频文件压缩包,数据文件需要和exe在同一目录下，结合某读者的意见同时放到github了 )
地址如下 git clone https://github.com/goLSX/courses_arrange.git
新手写文章，如有错漏欢迎评论区指出。
如果对你有帮助，可以给卑微的博主留个赞、关注、收藏 (不是) github的star也可以有啊
(骗一下数据，说不定以后恰好面试就过了，拜谢)
目录
题目：教学计划编制问题
一、题目分析
二、总体要求的实现思路
首先是用户：
参数输入：
结果输出：
存储结构：
系统结构：
三、各功能实现：
1.用户菜单
2.设置存储结构(放到头文件)
3.参数文件设计(可以参考)
4.读取课程信息
5.打印信息功能
6.修改信息功能
7.更新文件信息
8.拓扑排序
9.拓扑排序结果显示
10.策略选择
11.安排函数
四、函数调用关系
五、数据文件
(主页有代码和数据文件，数据文件记得和exe放在同一目录下)
六、运行测试
题目：教学计划编制问题
[问题描述]
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
[基本要求]
(1) 输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
(2) 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
(3) 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
[测试数据]
学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系见教科书图7.26。
[实现提示]
可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。
[选做内容]
产生多种(例如5种)不同的方案，并使方案之间的差异尽可能地大。
一、题目分析
很明显，题目所考查的是图相关内容，各门课程可以看作一个个图节点，最后需要得到各个节点的输出序列，且输出序列要满足拓扑排序要求。根据具体的输出要求，输出序列还会进一步被限制
用户所能进行的操作只有指定编排策略，但是如果要更人性化，用户还应该能够查询课程的具体信息，甚至作出一些改动。
其他的包括学习年限，学分上限等参数，应该由设计者指定
二、总体要求的实现思路
首先是用户：
我们需要提供一个用户操作界面，给予用户 查看、修改、指定策略、退出这几个选择。 具体操作可以用main函数调用菜单函数，由菜单函数提供操作界面并且对用户指定选项进行函数调用 。
参数输入：
对于参数的输入我们可以一开始在程序中指定，但是这样做的话，每次修改测试数据都需要在源码中修改并重新编译，所以我们可以采用在程序执行前读取参数文件，修改测试数据就很方便了
对于参数文件，可以自行格式，但是要便于读取
结果输出：
对于输入数据能够满足编排条件的情况，将安排计划用我们指定的格式输出到结果文件，对于输入不满足编排条件的情况，我们在用户界面给予错误提示，并且结果文件中也要给出错误提示
存储结构：
我们可以将各门课程存储在一个数组里，课程与先修课程的关系可以采用链表体现，因为每门课程有许多属性，所以课程节点用结构体；如果要给用户一定的修改权限，可以将学期数和每学期学分上限作为可修改项，当然必须限制在一定范围内修改。(选择这两项的原因是修改简单，且不会对程序的核心内容有影响，同时便于我们测试程序)
系统结构：
三、各功能实现：
1.用户菜单
void mainmenu( ) : 打印文本界面，从键盘获取字符，按字符选择对应操作，switch结束后再次调用mainmenu，直到switch中选择结束exit
void mainmenu()
{
char key; //变量key用与存取得到的字符
printf("\n\n\n\n");
printf(" 欢迎使用课程编排系统 \n\n\n");
printf("______________________________________________________________________\n");
printf(" 1. 查看课程信息 \n");
printf("______________________________________________________________________\n");
printf(" 2. 修改课程信息 \n");
printf("______________________________________________________________________\n");
printf(" 3. 均匀安排课程 \n");
printf("______________________________________________________________________\n");
printf(" 4. 尽快安排课程 \n");
printf("______________________________________________________________________\n");
printf(" 5. 关闭程序 \n");
printf("______________________________________________________________________\n");
printf("\n\n\n\n\t ") ;
key=getch();
key=key-'0'; //将字符转换成数字
switch(key)
{
case 1: system("cls"); //清空屏幕
Print_message(); //调用查看信息函数
break;
case 2: system("cls"); //清空屏幕
Adjust_message(); //调用修改信息函数
break;
case 3: system("cls"); //清空屏幕
//均匀安排函数，由于在实现时均匀安排与尽快安排很类似，所以复用函数，只是参数不同
Arrange_Select(AVERAGE);
break;
case 4: system("cls"); //清空屏幕
Arrange_Select(QUICKLY);
break;
case 5: exit(0); //退出程序
default :
cout << "该选项无效,请按任意键回主菜单" << endl;
key=getch(); //接收任意键
system("cls"); //清空屏幕
break;
}
mainmenu();
//执行完某个选项，如果用户没有选择退出，就会再次调用主菜单
}
2.设置存储结构(放到头文件)
宏定义：由于均匀策略和尽快策略复用了函数，于是定义参数AVERAGE和QUICKLY，
由于课程号占3位，根据测试数据的课程号格式，首位是C,后两位最高可以到99, 我们不使用C00，所以课程总数最大99(C01~C99)
图结构：存储课程信息的图包含邻接表指针，节点总数和读取到的学期信息；课程信息存 储在邻接表中，包含课程号，学分，第一个邻接点的指针还有课程入度(用于拓 扑排序)； 邻接节点包含位序和指向下一个邻接节点的指针；其中可以被用户修改 的内容分到一个message域中
#define AVERAGE 1 //均匀安排策略
#define QUICKLY 0 //尽快安排策略
#define MaxClass 99 //课程总数不超过99
#define MaxTerm 12 //学期总数不超过12
#define MaxCredit 30 //每学期学分不超过30
// 邻接表表示
typedef struct AdjVexNode {
int AdjVex; //邻接点位序
AdjVexNode * Next; //指向下一个邻接点的指针
}AdjVexNode; //邻接表结点
typedef struct {
char data[3]; //课程号
int credit; //节点学分（每门课学分）
AdjVexNode* FirstArc; //指向第一个邻边节点的指针域
int In_degree; //课程入度
}VexNode; //图节点
typedef struct {
int term_num; //学期数
int max_credit; //每学期学分上限
}Message; //学期信息
typedef struct {
VexNode* Vex; //节点数组域
int VexNum; //节点数
Message* mes; //每学期的信息(允许修改)
}Class_arrange_Graph; //图
3.参数文件设计(可以参考)
后面的文件读写都是按照这个格式来的，在修改文件内容时要按照以下说明操作
4.读取课程信息
void Read_file( ) : 打开文件，只读；
图的message先开辟空间，然后由文件读取学期数，每学期最大学分，课程总数给图赋值；图的节点数组开辟空间并初始化，循环读取文件课程号，课程学分，邻接表头指针记得置空；检查有无邻接点，有的话循环挂到邻接链表上；
文件关闭；
每个节点的邻接链表找有无邻接点，有的话邻接点入度加一，循环；
void Read_file()
{
//打开文件，路径为当前目录下的数据.txt,打开方式只读
FILE* fp = fopen("./数据.txt", "r"); //如果使用不同ide，文件路径可能需要调一下
if (NULL == fp)
{
printf("未找到文件,可能文件路径有误！！！");
exit(1); //异常退出
}
G.mes=(Message*)malloc(sizeof(Message)); //分配内存
//读取学期数，每学期最大学分，课程总数
fscanf(fp,"%d%d%d",&G.mes->term_num,&G.mes->max_credit,&G.VexNum);
if(G.VexNum > MaxClass || G.mes->term_num > MaxTerm || G.mes->max_credit > MaxCredit)
{
cout << "课程总数或学期数目或每学期最大学分超过上限" <<endl;
fclose(fp);
exit(1); //异常退出
}
G.Vex = (VexNode*)malloc(sizeof(VexNode) * G.VexNum); //分配内存
int i=0;
for(;i<G.VexNum;i++)
G.Vex[i].FirstArc=nullptr; //将邻接节点指针初始化为空
for (i = 0; i < G.VexNum; i++) //读取课程信息
{
fscanf(fp, "%s%d", G.Vex[i].data,&G.Vex[i].credit); //读取课程名称和学分
while ('\n' != fgetc(fp)) //根据先修课程建立邻接表结点
{
char str[4]; //读取课程号
int s;
fscanf(fp, "%s", str);
//将读取到的课程号转化为位序，该函数在下一代码段
s = Locate(str);
if (s = G.VexNum) //判断课程是否有错误
{
printf("%s课程错误，本专业无其先修课程！\n", G.Vex[i].data);
fclose(fp);
exit(1);
}
//更新邻接表结点
AdjVexNode* p = (AdjVexNode*)malloc(sizeof(AdjVexNode));
p->AdjVex = s;
p->Next = G.Vex[i].FirstArc;
G.Vex[i].FirstArc = p;
}
}
fclose(fp); //关闭文件
AdjVexNode * p;
for (i=0; i<G.VexNum; i++) //初始化入度
G.Vex[i].In_degree=0;
for(i=0;iAdjVex].In_degree++;
p=p->Next;
}
}
}
将课程号转换为位序。
课程号在数组中存储方式为: 0号单元为C，1、2号单元为数字，如果是课程号只有两位，那么2号单元空闲
int Locate(char* ch) //将C1 C2 C3...等 变为0 1 2... 课程号对应的位序
{
return (2 == strlen(ch)) ? ch[1] - '1' : (ch[1] - '0') * 10 + ch[2] - '1';
}
5.打印信息功能
void Print_message( ) : 打印 学期总数 每学期最大学分 必修课程数量；
循环打印 课程号 学分 所有先修课程；
打印完提示 “任意键回主菜单”，获取字符，然后调用主菜单
void Print_message()
{
printf("学期总数 : %d \t",G.mes->term_num);
printf("每学期最大学分 ： %d \t",G.mes->max_credit);
printf("必修课程数量 ： %d \n",G.VexNum);
cout << "\n\t\t\t本专业提供课程：\n"; //也是打印，c++的写法，可以用printf代替
for(int i=0;iNext)
printf("C%d ",p->AdjVex+1);
printf("\n");
}
cout << "\n\t\t\t按任意键回主菜单" <<endl;
getch();
system("cls");
mainmenu();
}
6.修改信息功能
可以修改的内容有两项，实现非常相似，也可以划分成两个函数。或许你会发现代码好像很长，但是其实两个选项几乎一样，只是因为提示不同，不太好复用
注：清除键盘缓存操作，是出错处理的手段。
scanf函数的读取是将用户输入存到键盘缓冲区，然后再从键盘缓冲区读取，如果我们输入错误数据，使得scanf按指定格式读取后，键盘缓冲区还有剩下的数据，那么下一次运行到scanf 时就不等待用户输入了，直接读取键盘缓冲区
Void Adjust_message( ) : 提示允许修改的信息，获取字符判断哪个信息需要修改；
提示输入修改后的值，获取该值，判断是否合法；
合法的话赋值给图的相应数据域，提示成功并更新文件内容；
非法的话提示出错，按任意键回主菜单，获取字符后调用主菜单
void Adjust_message()
{
printf("允许修改的内容有: 1.学期总数 2.个人每学期最大学分 ");
printf("\n\n请选择要修改的内容 ,或按其他键取消修改\n\n");
char key=getch();
key=key-'0'; //字符转换为数字
if(key==1)
{ int term;
printf("请输入学期总数：");
scanf("%d",&term);
fflush(stdin); //清除键盘缓存
if(term > MaxTerm || term < 1)
{
cout << "\n输入的学期数不合法 (大于最大允许的学期数 或 小于1 或 不是正整数)\n\n";
cout<< "请按任意键回主菜单"<term_num=term;
cout << "\n修改成功 (注：如果输入 数字+字符 那么只读入数字)\n" <<endl;
cout << "按任意键回主菜单" <<endl;
File_Update(); //更新文件信息
getch();
}
else if(key==2)
{
int credit;
printf("请输入个人每学期最大学分：");
scanf("%d",&credit);
fflush(stdin); //清除键盘缓存
if( credit MaxCredit)
{
cout << "\n输入的学分数不合法 (小于1或大于30)\n" <<endl;
cout<< "请按任意键回主菜单"<max_credit=credit;
cout << "\n修改成功 (如果输入 数字+字符 那么只读入数字)\n" <<endl;
cout << "按任意键回主菜单" <<endl;
File_Update(); //更新文件信息
getch();
}
system("cls");
mainmenu();
}
7.更新文件信息
在此函数中，采用c++的文件操作法，因为设计文件时课程信息和学期信息在同一个文件中，采用c语言的文件操作难度较大，如果想采用c语言的话，建议将学期信息和课程信息分成两个文件进行操作，会方便很多
void File_Update()
{
ofstream ofs; //创建文件流
// 路径为当前目录下的数据.txt , in | out 保持原内容不变 , binary指定二进制方式打开
ofs.open("./数据.txt",ios::in | ios::out | ios::binary);
//注：打开文件后默认指针指向开头，我们将可以修改的内容放在最前，这样便于修改
//覆盖文件第一行
ofs <term_num << " "<max_credit << " " << G.VexNum << "\n" ;
ofs.close(); //关闭文件
}
8.拓扑排序
题目要求均匀安排策略和尽快安排策略，选做内容是提供多种安排结果并且尽量差异大。
那我们可以在拓扑排序上解决这个问题，首先是拓扑排序的算法，其次是节点检索顺序。
下面代码用了两种算法，并且每一种算法的检索顺序分成 从前往后 与 从后往前 ，最终
我们可以得到4种拓扑排序结果。
之后用4个数组存储这4个结果，并且在用户选择一种策略后展示这4种先后序列让用户选择
其中一种，由用户选定的一种先后序列再结合策略进行输出。
注：在实现过程中，可以分成4个函数，也可以写在同一个函数 并使用不同参数区分。
4个函数有一定的复用性，可以自行设计，下面给予的参考实现没有复用代码。
各课程逻辑结构
(C1 C9为第一层 C2 C4 C10 C11为第二层 C3 C12 C6为第三层 C5 C8为第四层 C7为第五层)
从课程的逻辑结构我们发现最先应该最先输出的第一层节点不是入度为0，而应该最慢输出的节点入度为0，在这里我们可以采用栈，先将入度为0的节点输出到栈，最后弹出到结果数组。下面代码使用c++标准模板库的栈，也可以自己实现栈
(push操作是入栈; pop是出栈; top操作是获取栈顶元素; empty是判断是否栈空，栈空返回true; size操作获取栈中元素个数 )
void Top_Sort(VexNode* result,int choice) :
拓扑排序结果存入result, choice选择拓扑排序策略的一种；
给出4种拓扑排序策略，对应choice从1~4
定义局部变量：
int i； 循环控制变量
int tag=0; 判断图中还有没有入度为0的节点
AdjVexNode * p; 指向选中课程邻接表域的指针
stack S; 用来存储已被排序完的节点
stack S1; 用来存储每一层的节点的邻接表指针
读取文件更新节点信息。(注：我们的操作会使节点的入度改变，所以每次需要再读一次文件，也可以在排序前将各节点入度存到临时数组后再使用，不过因为Read_File函数现成，就偷懒一下，更好的做法是使用临时数组)
如果choice为1：
进入第一层循环：循环条件 tag==0（表示还有入度为0的节点）
tag=1；
进入第二层循环：循环条件 i从 课程总数减1 到 0
如果位序为i的节点入度为0
S.push(G.Vex[i]);
G.Vex[i].In_degree–;
p=G.Vex[i].FirstArc;
S1.push(p);
tag=0;
结束第二层循环
进入第二层循环(另一个循环) : 循环条件 栈S1非空
弹出栈顶元素到p
进入第三层循环：循环条件 ： p非空
G.Vex[p->AdjVex].In_degree–;
p=p->Next;
结束第三层循环
结束第二层循环
结束第一层循环
choice为2时思想和1一致，但是第二层循环条件i从0开始到节点数减1
choice为3时：不再采用层次遍历的思想，每次找到一个入度为0的节点，将其入栈S，
然后就进行入度减1，邻接点入度减1。 循环从课程总数减1到 0
choice为4时思想同3 ，循环条件从0开始到课程总数减1
判断环路，如果S的size小于课程总数说明存在回路，提示出错后任意键回主菜单。
没有环路就将S中的数据弹出到result数组
void Top_Sort(VexNode* result,int choice)
{
int i; //循环控制变量
int tag=0; //判断图中还有没有入度为0的节点
AdjVexNode * p; //指向选中课程邻接表域的指针
stack S; //用来存储已被排序完的节点
stack S1; //用来存储每一层的节点的邻接表指针
Read_file(); //读文件更新入度
if(choice==1)
while(tag==0)
{
tag=1;
for(i=G.VexNum-1;i>=0;i--)
if(G.Vex[i].In_degree==0) //将一个层次的节点入栈S，同时邻接表头入栈S1
{
S.push(G.Vex[i]);
G.Vex[i].In_degree--;
p=G.Vex[i].FirstArc;
S1.push(p);
tag=0;
}
while(S1.empty()==false) //一个层次的邻接点入度减一
{ p=S1.top();
S1.pop();
while(p!=nullptr)
{
G.Vex[p->AdjVex].In_degree--;
p=p->Next;
}
}
}
else if(choice==2)
while(tag==0)
{
tag=1;
for(i=0;iAdjVex].In_degree--;
p=p->Next;
}
}
}
else if(choice==3)
for(i=G.VexNum-1;i>=0;i--)
{
if(G.Vex[i].In_degree==0) //找到一个节点入度0就入栈并使邻接点入度减一
{
S.push(G.Vex[i]);
G.Vex[i].In_degree--;
p=G.Vex[i].FirstArc;
while(p!=nullptr)
{
G.Vex[p->AdjVex].In_degree--;
p=p->Next;
}
i=G.VexNum;
}
}
else
for(i=0;iAdjVex].In_degree--;
p=p->Next;
}
i=-1;
}
}
i=S.size();
if(i <G.VexNum) //查看节点是否都入栈了
{
cout<< "拓扑排序失败，课程先修关系可能存在环路，请按任意键回主菜单\n";
getch();
system("cls");
mainmenu();
}
for(i=0;i<G.VexNum;i++) //结果存到result数组
{
if(S.empty()==false)
{
result[i]=S.top();
S.pop();
}
else
{
cout << "拓扑排序弹栈失败,请按任意键回主菜单" << endl;
getch();
mainmenu();
}
}
}
9.拓扑排序结果显示
void Print_Top_Sort_Result( ) : 循环打印result1~result4的数据；可以自行设计输出格式
void Print_Top_Sort_Result()
{
printf("各课程安排先后顺序为:\n");
cout << "选择1：" ;
for(int i=0;i<G.VexNum;i++)
{
cout<< result1[i].data<< " " ;
}
cout << "\n\n选择2：" ;
for(int i=0;i<G.VexNum;i++)
{
cout<< result2[i].data<< " " ;
}
cout << "\n\n选择3：" ;
for(int i=0;i<G.VexNum;i++)
{
cout<< result3[i].data<< " " ;
}
cout << "\n\n选择4：" ;
for(int i=0;i<G.VexNum;i++)
{
cout<< result4[i].data<< " " ;
}
}
10.策略选择
用户选择某种策略后，会调用该函数。该函数的功能首先是调用拓扑排序得到结果，然后显示所有结果给用户，通过用户的选择，使用那个选择的结果序列去调用安排函数
void Arrange_Select(int choice)
{
Top_Sort(result1,1);
Top_Sort(result2,2); //调用4种拓扑排序，存到result 1~4
Top_Sort(result3,3);
Top_Sort(result4,4);
Print_Top_Sort_Result();
cout << "\n\n\n请输入你选择的课程安排先后顺序：";
char key=getch();
if (key=='1')
Arrange(result1,choice); //根据用户输入，确定使用哪种拓扑排序结果
else if(key=='2')
Arrange(result2,choice);
else if(key=='3')
Arrange(result3,choice);
else if(key=='4')
Arrange(result4,choice);
else
{
cout<<"\n\n选择有误，请按任意键回主菜单";
getch();
system("cls");
mainmenu();
}
}
11.安排函数
void Arrange(VexNode *result,int choice) :
// 拓扑排序结果由result传入，choice表示对应策略
定义局部变量
int arranged_num=0； 已经安排了的课程数
int j; 控制循环的变量
int k； 控制循环的变量
int course_num； 本学期安排的课程总数
int per_max_num； 每学期最大允许课程总数
int sumcredit； 本学期已安排课程的总学分
int tag; 标志，用来判断即将安排到本学期的课程 是否有先修课程在本学期
AdjVexNode* p; 用来遍历 即将安排课程的邻接链表 的指针
只写方式打开文件；
输入策略如果是QUICKLY，per_max_num为课程总数；
如果是AVERAGE，判断课程总数对总学期数取模的值,若小于学期总数的一半, per_max_num
为课程总数除以总学期数，否则再加1；
定义数组VexNode this_term_courses[per_max_num] 存放本学期已经安排的课程；
第一层循环k从0到总课程数减1
如果已经安排了的课程数等于课程总数，跳出循环。
文件中打印 “第k+1个学期课程为：” ；
程序界面显示相同文字；
初始化 sumcredit=0; //本学期安排课程的总学分
course_num=0; //本学期安排课程的总数
p=result[per_max_num].FirstArc; //先修课指针
tag=0; //标志本学期没有其先修课
进入第二层循环
循环执行条件：
本学期已安排课程的总学分 加上 即将安排课程的学分 小于每学期最大学分
本学期已安排课程没有其先修课程
本学期已安排课程数小于每学期允许的课程数
进入第三层循环
循环执行条件：p非空 且 本学期已安排课程没有其先修课程
进入第四层循环
for(j=0；j<本学期已安排的课程数；j++)
如果p指节点的位序和本学期已安排课程数组第j个元素位序一样
tag=1，跳出循环；
结束第四层循环
p=p->Next
结束第三层循环
如果tag==1，跳出第二层循环
文件和程序输出该课程号；
更新数据：
sumcredit+=result[arranged_num].credit; //本学期已安排课程总学分
this_term_courses[course_num]=result[arranged_num]; //本学期已安排的课程
if(arranged_num==G.VexNum) 跳出第二层循环
arranged_num++; 已安排的总课程数
course_num++; 本学期已安排课课程数
p=result[arranged_num].FirstArc; p指向下一个即将安排课程的邻接表域
结束第二层循环
结束第一层循环
关闭文件；
判断k是否大于学期总数，如果大于文件总数，打开文件，清空改写出错信息；
否则显示安排信息，任意键回主菜单
void Arrange(VexNode *result,int choice)
{
system("cls");
FILE *fp=fopen("./各学期课程安排结果.txt","w");
//文件路径为当前目录下的各学期课程安排结果.txt ,只写方式打开
int arranged_num=0; //已经安排了的课程数
int j; //控制循环的变量
int k; //控制循环的变量
int course_num; //本学期安排的课程总数
int per_max_num; //每学期最大允许课程总数
int sumcredit; //本学期已安排课程的总学分
int tag; //标志，用来判断即将安排到本学期的课程 是否有先修课程在本学期
AdjVexNode* p; //用来遍历 即将安排课程的邻接表 的指针
//计算不同情况下的每学期最大课程数。
if(choice==QUICKLY)
per_max_num=G.VexNum;
else
{ if(G.VexNum % G.mes->term_num term_num/2 )
per_max_num = G.VexNum/G.mes->term_num;
else
per_max_num = (G.VexNum/G.mes->term_num+1);
}
VexNode this_term_courses[10]; //存放本学期已经安排的课程
for(k=0;k<G.VexNum;k++)
{
if(arranged_num==G.VexNum) break;
fprintf(fp, "\n第%d个学期的课程为：", k+1);
printf("\n第%d个学期的课程为：", k + 1);
sumcredit=0; //本学期安排课程的总学分
course_num=0; //本学期安排课程的总数
p=result[arranged_num].FirstArc; //先修课指针
tag=0; //标志本学期是否有该课程的先修课程
while(sumcredit + result[arranged_num].credit max_credit && tag==0 &&
course_num<per_max_num)
{
while(p!=nullptr && tag==0)
{
for(j=0;jAdjVex == Locate(this_term_courses[j].data) )
{
tag=1;
break;
}
}
p=p->Next;
}
if(tag==1) break;
fprintf(fp, " %s ", result[arranged_num].data);
printf( " %s ", result[arranged_num].data);
sumcredit+=result[arranged_num].credit;
this_term_courses[course_num]=result[arranged_num];
if(arranged_num==G.VexNum) break;
arranged_num++;
course_num++;
p=result[arranged_num].FirstArc;
}
}
fclose(fp);
if(k>G.mes->term_num)
{
fp=fopen("./各学期课程安排结果.txt","w");
fprintf(fp,"%s%d","该课程安排先后顺序下，此策略无解,因为安排所需学期数超过学期总
数",G.mes->term_num);
fclose(fp);
cout << "\n\n\n该课程安排先后顺序下，此策略无解,因为安排所需学期数超过学期总数"<term_num<<endl;
cout <<"\n\n请按任意键回主菜单" <<endl;
getch();
system("cls");
mainmenu();
}
cout << "\n\n\n 课程安排信息已经存入当前目录下，“各学期课程安排结果.txt” \n\n请按任意键回
主菜单";
getch();
system("cls");
mainmenu();
}
四、函数调用关系
五、数据文件
(主页有代码和数据文件，数据文件记得和exe放在同一目录下)
测试数据
|
学期总数 |
每学期学分上限 |
课程总数 |
|
6 |
10 |
12 |
|
课程号 |
学分 |
先修课程号 |
|
C1 |
2 |
|
|
C2 |
3 |
C1 |
|
C3 |
4 |
C1 C2 |
|
C4 |
3 |
C1 |
|
C5 |
2 |
C3 C4 |
|
C6 |
3 |
C11 |
|
C7 |
4 |
C5 C6 |
|
C8 |
4 |
C3 C6 |
|
C9 |
7 |
|
|
C10 |
5 |
C9 |
|
C11 |
2 |
C9 |
|
C12 |
3 |
C9 C10 C1 |
txt文件内容如下
六、运行测试
1.用户界面
2.查看信息
3.修改信息
修改成功
修改失败
4.课程安排
选择任意一种后出现以下信息
如果选择不在1~4之中，提示错误，重新输入
如果选择正确，出现课程安排信息，如果选择的课程序列满足不了要求，会出现错误提示，同时文件里也会提示
5.退出程序
按5之后任意键退出
错误输入
如果C1有先修课程C12,提示拓扑排序失败，可能存在环路；
如果C2有先修课程C13,提示本专业没有C1的先修课程
如果学期总数大于12或每学期学分上限大于30或课程总数大于99，
提示 “课程总数或学期数目或每学期最大学分超过上限”
好像有小伙伴在评论区提出devc++ 有一个collect2: error: ld returned 1 exit status的问题，我之前没用过dev，不知道是不是dev的问题，就专门试了一下，发现还是可以正常运行的啊。我会把使用视频(codeblocks 和 devc++)放到主页，可以参考一下。还有什么问题可以继续评论区或者私信。
有人问了下时间和空间复杂度的问题，时间复杂度不太好评价，大概分析一下
主要花时间的模块是拓扑排序和安排课程
拓扑排序我们每次查询所有剩下的节点有无入度为0的，最差的时候就n^2，像冒泡一样,
还要考虑每个节点更新其临接节点,最差的时候也是n^2。
(1~n个节点，每个节点先修课程为1~n-1,1没有先修课)
安排课程的话，因为需要考虑这个学期安排的课程中不能出现
‘其中的某课程与其先修课程一起学’,那每次安排多一个课程都需要检查已经安排的课程，
假设某个学期安排了m门课程，(时间复杂度就是m^2的)
最差时间复杂度就需要考虑我们一开始的定义
#define MaxClass 99 //课程总数不超过99
#define MaxTerm 12 //学期总数不超过12
#define MaxCredit 30 //每学期学分不超过30
主要看我们每一学期能安排多少课，但是影响因素很多，像数据的先修状况，学分等。
无法单纯从课程数量判断。如果使用最差情况来算，
(n门课程(数量较大)，每门学分只有e分(e较小)，尽快安排,每学期最多c分(c较大))
那时间复杂度估计
[(c/e)^2]*n/(c/e)=c*n/e
空间复杂度O(n)，这就没什么好说了，result1~4，直接设置最大课程数的空间,
(使用vector动态数组可以减一点，但还是O(n)) 中间设置辅助栈什么的，也是O(n)空间
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/d3c75e5f4a.html
相关推荐
-
（python）NumPy 库常见版本
前言 NumPy 库有许多版本，每个版本都有不同的功能和改进。以下是一些常见的 NumPy 版本. 后续，会列举版本变化前后的函数方法变更. 版本变化 NumPy …
-
【HarmonyOS开发】ArkTs关系型和非关系型数据库的存储封装
前面使用了首选项的存储方式，因此将其他的两种存储方式（键值型数据库和关系型数据库）也学习一下，简单记录一下，并进行封装，方便后续使用。 1、效果预览 2、使用条件 2.1 键值型数…
-
SQL中使用的运算符号详解
文章目录 前言 1. 算术运算符 加法与减法运算符 乘法与除法运算符 求模（求余）运算符 2. 比较运算符 1．等号运算符 2．安全等于运算符 3．不等于运算符 4. 空运算符 5…
-
Python中使用matplotlib时显示中文乱码
一、问题描述 在使用matplotlib绘制可视化图表时，图表的中文显示乱码，只能正常显示英文内容，如下图所示： 二、问题分析 一般显示乱码是由于编码问题…
-
偏最小二乘(PLS)原理分析&Python实现
目录 1 偏最小二乘的意义 2 PLS实现步骤 3 弄懂PLS要回答的问题 4 PLS的原理分析 4.1 自变量和因变量的主成分求解原理 4.1.1 确定目标函数 …
-
安装Redis并把Redis设置成windows下的服务然后进行Redis实例演示
目录 （一）安装Redis （二）Redis设置成windows下的服务 1、把redis设置成windows下的服务 2、设置服务命令 （三）Redis实例演示 1、Redis插…
-
Mysql中in和exists的区别 & not in、not exists、left join的相互转换
文章目录 1. in 介绍 1.1 in中数据量的限制 1.2 null值不参与in或not in，也就是说in and not in 并不是全量值，排除了null值 1.3 in…
-
用 RemoteDebug iOS Webkit 在 Chrome DevTools 中调试iOS/iPadOS设备的前端页面
目录 前言 RemoteDebug iOS WebKit 适配器 Windows系统： 1. 安装scoop主程序（已安装可忽略此步骤） 1.1 首次安装（非管理员运行） 1.2 …
-
vue实现动态class
总结一下,vue实现动态class主要通过以下三种方式 1 通过对象方式 动态绑定一个类名的写法 : 动态绑定多个类名的写法 : 如 ifOn / ifDisabled 都是vue…
-
超详细的VSCode下载和安装教程以及解决VSCode下载速度特别慢的问题
文章目录 1. 引言 2. 下载VSCode 3. 解决VSCode下载速度特别慢 4. 安装VSCode 1. 引言 今天用WebStorm运行前端代码时，发现不太好打断点。 于…
