#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<windows.h>
#include<conio.h>
#include<fstream.h>
struct CourseLink //该结构体用于具体运算
{ //关联了课程的关系
int Index; //该课程在一维数组的下标，绑定他与课程的关系
CourseLink *next; //下一门与他同一尾节点的课程
};
struct CourseHead //表头结点的结构体
{
int flag; //标记该门课程是否已经编排
int priornum; //给课程的直接先修课的个数
CourseLink *first; //以该门课程为先修的后修课程
char Name[30]; //课程的名字
char Ofcourse[4]; //课程号
float Score; //学分
};
struct ArryInTopo
{
int Index; //保存课程的序号
int Time; //保存课程的开课时间
};
struct Topo
{
int level; // 标记是否平均分配,也就是课程安排效果标记
ArryInTopo *toporesualt; //一个一维数组保存拓扑排序--保存课程的序号
Topo *next; //拓扑排序的下一种情况
};
struct Zero //保存可以选择的课程
{
int zero; //课程在原始数据里的下标
Zero *next; //下一个课程结点的地址
};
//**************函数介绍********************************************
void InitData();//...................... 1 调用一下两个函数完成数据初始化
void InitData(int num);//................. 2 由课程数目num来完成数据的细节
float InitData(char *b);//.............. 2 方便判断输入数据的准确性而已
void StartTopoSort();//................1 初始化要用到的各个数据再调用下面这个函数
void TopoSort(int topotempsum,int time);
//.2递归函数，完成拓扑排序，用到以下四个函数
void Check(int index);
//3当选择course[index]时，相应的链表的头结点的priornum项要减一
void CheckBack(int index);
// 3当退选course[index]时，相应的链表的头结点的priornum项要加一
int ZERO(); //..3统计该层递归可以选择的课程并且完成可选课程的记录
void Ifsuccessed();
//3当课程安排成功时将课程安排记录保存，并对课程安排做评价
void Print();//............................1 根据客户要求输出相应的课程安排
void printf0();//..........................1 界面
void printf1(int );//......................1 负责输出课程信息,并且还调用下面
void printf2();//...........................2 输出课程的联系
void printf1(FILE *);//......................1 负责将课程信息写入文件,并且还调用下面
void printf2(FILE *);//...........................2 将课程的联系写入文件
//****************************函数介绍*****************************//
int Time=0; // 全局变量 学期总数
float MaxSource=0.0; // 全局变量 一学期的学分上限
int SourceNum=0; // 全局变量 课程总数
CourseHead *coursehead; // 全局变量 链表的有节点数组
Topo *topo; // 全局变量 保存课程的安排情况,
//头结点保存课程安排平均的总数目
ArryInTopo *topotemp; // 全局变量 数组临时保存某一种拓扑排序情况
Zero *ZeroTemp; // 全局变量 链式保存入度为零的课程的index
// 随着递归的进行他的值也在变化
int *ClassInTime; // 全局变量 临时保存每一学期课程的数目
void main()
{
char i;
printf0();
do
{
printf(" 按任意 非<Esc> 键开始，按<Esc> 退出!\n\n");
i=getch();
fflush(stdin); //刷新输入流
if(i!=27)
{
system("cls"); //刷新屏幕
printf0();
InitData(); //输入数据
StartTopoSort(); //处理数据
Print(); //按要求输出结果
}
if(i==27)
return;
}while(i!=27);
}
//@@@@@@@@@@@@@@@@@@@@@@@@数据初始化全部完成
void InitData()
{
Time=int(InitData("学期总数")); //输入学期总数
MaxSource=InitData("一学期的学分上限"); //输入一学期的学分上限
SourceNum=int(InitData("课程总数")); //输入课程总数
InitData(SourceNum); //输入课程有关的各个信息
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@数据初始化全部完成
float InitData(char *b) //输入学期总数，一学期的学分上限，课程总数
{
int flag=0;
float a=0;
do
{
if(flag==1)
printf("请重新输入%s\n ",b);
else
printf("请输入%s :\n ",b);
scanf("%f",&a);
fflush(stdin);
flag=1;
}while(a<=0.0); //严格检查输入数据的准确性
return a;
}
void InitData(int num) //输入课程有关的各个信息:
Source->name[]; //每门课的课程名
Source->OfSource[]; //课程号(固定占3位的字母数字串)
Source->Source; //学分
//直接先修课的课程号//
{
int i=0,j=0;
int flag=0; //标记出错
coursehead=(CourseHead *)malloc(num*sizeof(CourseHead));
//为全局变量course和coursehead分配内存
CourseLink *courselink=NULL;
CourseLink *courselinktemp=NULL;
for(i=0;i<num;++i)
{
coursehead[i].Name[0]='\0';
coursehead[i].Ofcourse[0]='\0';
coursehead[i].Score =0;
coursehead[i].flag=0;
coursehead[i].first=NULL;
coursehead[i].priornum=0;
}
//为全局变量course和coursehead完成初始化
for(i=0;i<num;++i)//............输入每一门课程的信息
{
do
{
flag=0;
if(flag==1)
printf("输入的信息不符合要求，请检查后再输入!\n 请重新输入第 %d 门课程的 课程名(限长12位),课程号(固定占3位)，学分\n ",i);
printf(" 请输入第 %d 门课程的 课程名(限长14位),课程号(固定占3位)，学分\n",i+1);
scanf("%s%s%f",coursehead[i].Name,coursehead[i].Ofcourse,&(coursehead[i].Score));
fflush(stdin);
//正确输入 课程名
if(strlen(coursehead[i].Name)>28)
{
printf(" 警告 ! 课程名太长，请简写!\n\n");flag=1;
}
//正确输入 课程号
if(strlen(coursehead[i].Ofcourse)!=3)
{
printf(" 警告 ! 课程号必须是是三位\n\n\n");flag=1;
}
for(j=0;flag==0&&j<i;++j)
if(strcmp(coursehead[i].Ofcourse,coursehead[j].Ofcourse)==0)
{
printf(" 警告 ! 已经有了一个同样的课程号!\n\n");
flag=1;
break;
}
if(coursehead[i].Score>MaxSource||coursehead[i].Score<=0.0)
{
printf(" 警告 ! 学分必须是在 0 到 最大限制 %3.1f 之间,请检查后再输入\n\n",MaxSource);flag=1;
} //正确输入 学分
}while(flag==1);
//严格控制输入数据的正确性
}
printf1(1); //输出已经输入的课程信息
//以下是输入课程的关系
int Sort=0,NUM=0; //先修课的序号 ,先修课的的个数
char temp[4]; //保存输入的课程号
do
{
printf(" 请输入 课程号 与 它的先修课的的个数(输入 0 0 结束):\n");
scanf("%s%d",temp,&NUM);
fflush(stdin);
Sort=SourceNum;
for(i=0;i<SourceNum;++i)
if(strcmp(temp,coursehead[i].Ofcourse)==0)
{
Sort=i;
break;
}
if(NUM>=SourceNum)
printf(" 警告 ! 先修课数目值无意义!\n\n");
if(Sort==SourceNum)
printf(" 警告 ! 该课程不存在!\n\n");
if(Sort<SourceNum&&coursehead[Sort].priornum!=0)
{
printf(" 警告 ! 该课程已经输入过!\n\n");
Sort=SourceNum;
}
if(Sort!=SourceNum&&NUM<SourceNum) //输入各个关系
for(i=1;i<=NUM;++i)
{
if(i==1)
coursehead[Sort].priornum=NUM;
//先修课程数目
flag=0;
do
{
printf(" 请");
if(flag==1) { printf("重新");flag=0;}
printf("输入课程%s的第 %d 个直接先修课的课程号\n ",coursehead[Sort].Ofcourse ,i);
scanf("%s",temp);
fflush(stdin);
//*********************检查输入的课程号的正确性
for(j=0;j<SourceNum;++j)
if(strcmp(temp,coursehead[j].Ofcourse)==0&&Sort!=j)
{
break;
}
//课程号不与自己相同
if(j==SourceNum)
{ printf(" 警告 ! 输入的课程号有误!!\n\n ");flag=1;}
//课程号存在
if(flag==0)
{
courselinktemp=NULL;
courselink=coursehead[Sort].first;
while(courselink!=NULL)
{
if(courselink->Index==j)
{
printf(" 警告 ! 课程不能互为先修课!\n\n");
flag=1;
break;
}
courselink=courselink->next;
}
} //不存在 a--->b && b--->a 的情况
if(flag==0)
{
courselinktemp=NULL;
courselink=coursehead[j].first;
while(courselink!=NULL)
{
if(courselink->Index==Sort)
{
printf(" 警告 ! 关系重复了!\n\n");
flag=1;
break;
}
courselink=courselink->next;
}
}
//检查输入的课程号的正确性
//输入正确时给相应的地方赋值
if(flag==0)
{
courselink=(CourseLink *)malloc(sizeof(CourseLink));
courselink->Index=Sort;
courselink->next=coursehead[j].first;
coursehead[j].first=courselink;
}
//输入正确时给相应的地方赋值
}while(flag==1); //输入有错则重新输入
//The End of do{} while();
printf1(0);
}
//The End of for(){}
}while(!(Sort==SourceNum&&NUM==0)); //判断关系是否结束
} //.......................... 所有的数据存储结构初始化已经完成
void StartTopoSort() // 初始化要用到的各个数据
{ // 再调用递归函数TopoSort(int topotempsum,int time)
// 来完成课程的具体安排
int i=0;
topotemp=(ArryInTopo *)malloc(SourceNum*sizeof(ArryInTopo));
for(;i<SourceNum;++i)
{
topotemp[i].Time=0;
topotemp[i].Index=0;
}
// 为全局变量ArryInTopo *topotemp完成初始化
topo=(Topo *)malloc(sizeof(Topo));
topo->level=0;
topo->toporesualt=NULL;
topo->next=NULL;
// 为全局变量Topo *topo 完成初始化
ZeroTemp=(Zero *)malloc(sizeof(Zero));
ZeroTemp->next=NULL;
ZeroTemp->zero=0;
// 为全局变量Zero *ZeroTemp完成初始化，头结点不用
ClassInTime=(int *)malloc(Time*sizeof(int));
for(i=0;i<Time;i++)
ClassInTime[i]=0;
// 为全局变量int *ClassInTime完成初始化
TopoSort(0,1); //调用递归函数TopoSort 完成课程安排
}
void TopoSort(int tempsum,int time)
{ //递归完成拓扑排序
//tempsum ，已经安排的课程的数目
//要安排课程的time学期
int i=0,j=0;
int zero=ZERO(); //index 课程的后继课程中前驱为零的个数
if(zero==0)return; //没有课程可选，返回
int *ZeroArry;
ZeroArry=(int *)malloc(zero*sizeof(int));
Zero *zerolink=ZeroTemp->next;
for(i=0;i<zero;++i)
{
ZeroArry[i]=zerolink->zero;
zerolink=zerolink->next;
} //将 Zero *ZeroTemp链里的数据赋给
//局部变量int *ZeroArry赋值，方便操作
int xuan=1; //该层递归在ZeroArry[i]已经选择的课程的数目
int sum=tempsum; //已经安排的课程的数目
double ScoreNum=0; //该层递归选择的课程的学分的和
int flag=0; //标记某一种课程选择是否正确
for(i=1;i<int(pow(2,zero));++i)
{ //这是本人写这个程序的唯一的得意之处
//将课程的选择情况用二进制的0，1表示
//例如 i=6 则 i=110(2)
//i 分别与j 100(2), 10(2),1(2) 进行“与”运算
//分别得到j 100(2), 10(2),0(2)
//j==j 1 1 0
//则表示在这种情况下 在数组int *ZeroArry 里面
//选择 ZeroArry[1-1], ZeroArry[2-1]的课程
//不选 ZeroArry[3-1]
//并且是 i从 1 到 pow(2,zero)-1,
//这样可以不重不漏地将所有情况都考虑进去
sum=tempsum; //已经安排的第sum课程
ScoreNum=0;
flag=0;
ClassInTime[time-1]=0;
//每一次循环都必须将数据初始化
for(j=1,xuan=1;xuan<=zero;xuan++)
{
if((j&i)==j)//选择ZeroArry[xuan-1]的课程
{
coursehead[ZeroArry[xuan-1]].flag=1;
//标记已选
topotemp[sum].Index=ZeroArry[xuan-1];
topotemp[sum].Time=time;
//全局变量数组ArryInTopo *topotemp记录选课情况
Check(ZeroArry[xuan-1]);
//将课程Course[index] 的后继课程的入度减一
ScoreNum+=coursehead[ZeroArry[xuan-1]].Score;
//选择的课程的学分的和
sum++;
ClassInTime[time-1]++;
// 更改全局变量time学期课程的数目
}
j=j*2; // 也可以用j=j<<1;
}
if(sum==SourceNum)
{ // 课程安排成功
Ifsuccessed();
flag=1;
}
if(ScoreNum!=0&&ScoreNum<=MaxSource&&time<Time)
TopoSort(sum,time+1);
// 继续递归
for(j=1,xuan=1;xuan<=zero;xuan++)
{
if((j&i)==j)
{
CheckBack(ZeroArry[xuan-1]);
coursehead[ZeroArry[xuan-1]].flag=0;
}
j=j*2;
}
//这个for循环用于在i=i+1之前将所有的数据还原
if(flag==1)
{
ClassInTime[time-1]=0;
return;
}
}
ClassInTime[time-1]=0;
free(ZeroArry);
}
void Ifsuccessed() //当课程安排成功时将课程安排记录保存
{ // 并对课程安排做评价
int i=0;
Topo * temp;
temp=(Topo *)malloc(sizeof(Topo));
temp->level=0;
temp->toporesualt=(ArryInTopo *)malloc(SourceNum*sizeof(ArryInTopo));
temp->next=NULL;
temp->next=topo->next;
topo->next=temp;
//当某一种课程安排成立时新建一个
//Topo * temp结点，并且连接到全局变量topo后面
for(i=0;i<SourceNum;++i)
{
temp->toporesualt[i].Index=topotemp[i].Index;
temp->toporesualt[i].Time=topotemp[i].Time;
} //完成对结点Topo * temp的内容的添加
//下面对该种安排做一个评估
int Average=int(SourceNum/Time); //平均每学期的课程数目
for(i=0;i<Time;++i)
if(ClassInTime[i]<Average||ClassInTime[i]>Average+1||ClassInTime[Time-1]==0)
break;
//判断是否平均
if(i==Time)
{
temp->level=1; //标记课程安排平均
topo->level++; //课程安排平均的数目+1
}
}
int ZERO() // 统计某层递归可以选择的课程
{ // 并且完成可选课程的记录
Zero *p=ZeroTemp->next;
Zero *zerotemp=NULL;
ZeroTemp->next=NULL;
while(p!=NULL)
{
zerotemp=p->next;
free(p);
p=zerotemp;
}//释放全局变量Zero *ZeroTemp的内存
//为记录新的入度为零的课程做准备
p=ZeroTemp;
int zero=0;
int i=0;
for(i=0;i<SourceNum;++i)
if(coursehead[i].priornum==0&&coursehead[i].flag==0)
{ //入度为零，并且还没有被选中
zerotemp=(Zero *)malloc(sizeof(Zero));
p->next=zerotemp;
p=zerotemp;
zerotemp->zero=i;
zerotemp->next=NULL;
zero++; //完成对全局变量Zero *ZeroTemp重新赋值
}
return zero; //返回可选课程的个数
}
void Check(int index) //将课程coursehead[index] 的后继课程的入度减一
{
CourseLink *courselinktemp=NULL;
courselinktemp=coursehead[index].first;
while(courselinktemp!=NULL)
{
coursehead[courselinktemp->Index].priornum--;
courselinktemp=courselinktemp->next;
}
}
void CheckBack(int index)
// 当 coursehead[index] 课程 "推选" 时 ，要将与他有关的课程的入度数还原
{
CourseLink *courselinktemp;
courselinktemp=coursehead[index].first;
while(courselinktemp!=NULL)
{
coursehead[courselinktemp->Index].priornum++;
courselinktemp=courselinktemp->next;
}
}
void Print() // 根据客户要求输出相应的课程安排
{
printf1(1); //刷新屏幕
int i=0 ,j=1,flag=1;
FILE *f;
Topo *pp=topo->next;
do
{
printf(" 课程编排结束!!\n\n");
printf(" 请选择操作!\n");
printf(" 选项(0/1/2) :\n");
printf(" (0) 重新初始化课程信息!\n");
printf(" (1) 学习负担尽量均匀!\n");
printf(" (2) 所有课程安排情况!\n");
do
{
if(!(flag==1||flag==2||flag==0))
printf(" 注意!!! 请输入合法选择!\n");
scanf("%d",&flag);
fflush(stdin);
}while(!(flag==1||flag==2||flag==0));
//严格控制输入的准确性
printf("以下是所有符合您要求的课程安排情况!\n");
printf1(1); //刷新屏幕
if(flag==1)
f=fopen("分配均匀.txt","w");
else
f=fopen("所有情况.txt","w");
printf1(f);
if(flag==0)
return;
else
{
pp=topo->next;
j=1;
while(pp!=NULL)
{
if(flag==1&&pp->level==1||flag==2)
{
printf(" 第 %d 种课程安排!\n\n",j);
printf(" 开课时间 课程名称 课程号 学分 先修课数目\n");
fprintf(f," 第 %d 种课程安排!\n\n",j);
fprintf(f," 开课时间 课程名称 课程号 学分 先修课数目\n");
for(i=0;i<SourceNum;++i)
{
printf("%8d%20s%11s%7.1f%10d\n",pp->toporesualt[i].Time,coursehead[pp->toporesualt[i].Index].Name,coursehead[pp->toporesualt[i].Index].Ofcourse,coursehead[pp->toporesualt[i].Index].Score,coursehead[i].priornum);
fprintf(f,"%8d%20s%11s%7.1f%10d\n",pp->toporesualt[i].Time,coursehead[pp->toporesualt[i].Index].Name,coursehead[pp->toporesualt[i].Index].Ofcourse,coursehead[pp->toporesualt[i].Index].Score,coursehead[i].priornum);
}
fprintf(f,"\n\n");
printf("\n\n");
j++;
}
pp=pp->next;
} //输出完毕
printf(" 一共 %d 种符合您要求的课程安排!\n\n",j-1);
fprintf(f," 一共 %d 种符合您要求的课程安排!\n\n",j-1);
fclose(f);
}
}while(1);
}
void printf0() // 界面
{
printf("*****************************************************************************\n\n");
printf(" 数 据 结 构 课 程 设 计\n\n");
printf(" 课 题 : 《教学计划编制》\n\n");
printf("*****************************************************************************\n\n");
}
void printf1(int a) //负责输出课程信息
{ //若 a=1 则 刷新屏幕
if(a==1)
system("cls");
int i=0;
for(i=0;i<80;++i) printf("%c",6);
printf("\n\n");
printf(" 课程基本信息 \n\n");
//---序号----------课程名----课程号---学分---qianxu
printf(" 序号 课程名 课程号 学分 必修课数目\n");
for(i=0;i<SourceNum;++i)
printf("%8d%16s%10s%7.1f%5d\n",i+1,coursehead[i].Name ,coursehead[i].Ofcourse ,coursehead[i].Score,coursehead[i].priornum);
printf("\n\n");
printf2(); // 输出课程的联系
//printf("\t注意!! 每一学期的学分的上线为 :%f\n",MaxSource);
printf(" 学期总数 : %d 课程总数 : %d 一学期的学分上限 :%3.1f\n",Time,SourceNum,MaxSource);
for(i=0;i<80;++i) printf("%c",6);
printf("\n\n");
}
void printf2()// 输出课程的联系
{
int i=0,p=0;
CourseLink *courselinktemp=NULL;
for(i=0;i<SourceNum;++i)
{
p=0;
courselinktemp=coursehead[i].first;
while(courselinktemp)
{
if(p==0)
{
printf("%5s",coursehead[i].Ofcourse);
printf(" ----> ");
}
printf("%5s",coursehead[courselinktemp->Index].Ofcourse);
p++;
courselinktemp=courselinktemp->next;
}
if(p!=0)
printf("\n");
}
printf("\n");
}
void printf1(FILE *p) //负责向文件里面写数据-----课程基本信息
{
int i=0;
for(i=0;i<80;++i) fprintf(p,"%c",6);
fprintf(p,"\n\n");
fprintf(p," 课程基本信息 \n\n");
//---序号----------课程名----课程号---学分---qianxu
fprintf(p," 序号 课程名 课程号 学分 必修课数目\n");
for(i=0;i<SourceNum;++i)
fprintf(p,"%8d%16s%10s%7.1f%5d\n",i+1,coursehead[i].Name ,coursehead[i].Ofcourse ,coursehead[i].Score,coursehead[i].priornum);
fprintf(p,"\n\n");
printf2(p); // 输出课程的联系
fprintf(p," 学期总数 : %d 课程总数 : %d 一学期的学分上限 :%3.1f\n",Time,SourceNum,MaxSource);
for(i=0;i<80;++i) fprintf(p,"%c",6);
fprintf(p,"\n\n");
}
void printf2(FILE *ff) //负责向文件里面写数据-----课程的关系
{
int i=0,p=0;
CourseLink *courselinktemp=NULL;
for(i=0;i<SourceNum;++i)
{
p=0;
courselinktemp=coursehead[i].first;
while(courselinktemp)
{
if(p==0)
{
fprintf(ff,"%5s",coursehead[i].Ofcourse);
fprintf(ff," ----> ");
}
fprintf(ff,"%5s",coursehead[courselinktemp->Index].Ofcourse);
p++;
courselinktemp=courselinktemp->next;
}
if(p!=0)
fprintf(ff,"\n");
}
fprintf(ff,"\n");
}}
|
发表于 2015-1-9 16:12:47
收藏
转播
分享
