course.cpp

一个简单的课表排课算法实现

struct out_index//指向后继的结构体
{
	int C_index;//存放后继的序号
	out_index *next;//存放下一个后继
};
struct course//课程结构体
{
	char C_name[100];//课程名
	int in_dgr;//课程入读数
	out_index *next;//指向后继的指针
};
#define M 73//宏变量,课程数
#include <iostream.h>
#include <fstream.h>
int tonum(char *p)//将字符转换为数字(to number)
{
	int x=0;
	while(*p!='\0')
	{
		x*=10;
		x+=*p-'0';
		p++;
	}
	return x;
}
int main()
{
	//定义程需要的变量
	course Cos[M];//课程数组
	ifstream in_file;//读取课程文件
	out_index *q,*p;//中间后继索引指针
	char t[10];//临时的一个数组,存放从文件中读取的后继序号
	int i,j;//循环变量
	int x_sum=0,sum=0;//x_sum为每个学期能选的课数，sum为共能选的课程数
	//定义程需要的变量
	for(j=0;j<M;j++)//初始化课程结构体
	{
		for(i=0;i<50;i++)
		{
			Cos[j].C_name[i]='\0';
		}
		Cos[j].in_dgr=0;
		Cos[j].next='\0';
	}
	for(i=0;i<10;i++)//初始化临时数组
	{
		t[i]='\0';
	}
	//读入课程文件,并初始化课程前后继关系.
	in_file.open("course.txt",33);
	if(!in_file)//文件打开错误处理
	{
		cout<<"course.txt open error!"<<endl;
		return 1;
	}
	for(i=0;i<M;i++)
	{
		
		in_file>>Cos[i].C_name>>Cos[i].in_dgr>>t;//将文件中的课程名及入读送入程序的课程结构体中
		if(t[0]=='@')//'@'为结束符
		{
			Cos[i].next='\0'; 
		}
		else//将课程的后继连接在课程后面，如果是多个，则顺次连接下去
		{
			q=new out_index;//申请一个存放后继序号的节点
			q->C_index=tonum(t);//存放序号
			Cos[i].next=q;//将节点挂到课程后面
			in_file>>t;//继续从文件中度字符
			while(t[0]!='@')//'@'为结束符，把所有的后继挂到课程上
			{
				p=new out_index;
				p->C_index=tonum(t);
				q->next=p;
				q=p;
				in_file>>t;
			}
			q->next='\0';
		}	
	}
	//读入课程文件,并初始化课程前后继关系.
	int n=0;//计算学年，学期的变量
	bool flag=true;//设置标志变量，真为还有输出，假即已无可输出课程
	while(flag)
	{
		flag=false;
		n+=1;
		x_sum=0;
		cout<<"==============第 "<<(n-1)/2+1<<" 学年"<<","<<"第 "<<(n+1)%2+1<<" 学期=============="<<endl;
		for(i=0;i<M;i++)//输出一个学期要最多能选的课
		{
			if(Cos[i].in_dgr==0)
			{
				Cos[i].in_dgr=-1;//输出后，课程入度置-1
				cout<<Cos[i].C_name<<endl;
				x_sum+=1;
			}
		}
		sum+=x_sum;
		cout<<"===================共 "<<x_sum<<" 门课==================="<<endl;
		for(i=0;i<M;i++)//将输出的课程的后继课程的入读都减1，并把输出课程的入读置-2
		{
			if(Cos[i].in_dgr==-1)//选择刚输出的课程
			{
				if(Cos[i].next!='\0')//后继不为空时，将之后继置为空
				{
					q=Cos[i].next;
					Cos[i].next='\0';
					while(q)//后继不为空时，改变后继入读，并释放存放后继序号的节点
					{
						p=q;
						Cos[(q->C_index)-1].in_dgr-=1;//后继课程的入读都减1
						q=q->next;
						delete(p);//释放存放后继序号的节点
					}
					flag=true;//有释放就有可能下一次由输出，故将flag置为真
				}
				Cos[i].in_dgr=-2;//把输出课程的入读置-2
			}
		}
	}
	if(sum<M)//如果输出不足课程数，则肯定存在课程前后继的循环，将有循环的课程输出，提示用户检查课程前后继关系表。
	{
	cout<<"!!!!!!!!!!!!!!!! 课程中有循环 !!!!!!!!!!!!!!!!!"<<endl;
	cout<<"!!!!!!!!!!!!!! 有 "<<M-sum<<" 门课无法排出 !!!!!!!!!!!!!!"<<endl;
	cout<<"!!!!!!!!!!! 请检查课表的前后继关系 !!!!!!!!!!!! "<<endl;
	for(i=0;i<M;i++)
	{
		if(Cos[i].in_dgr!=-2)
		{
			cout<<Cos[i].C_name<<endl;
		}
	}
	cout<<"!!!!!!!!!!! 请检查课表的前后继关系 !!!!!!!!!!!! "<<endl;
	cout<<"!!!!!!!!!!!!!! 有 "<<M-sum<<" 门课无法排出 !!!!!!!!!!!!!!"<<endl;
	cout<<"!!!!!!!!!!!!!!!! 课程中有循环 !!!!!!!!!!!!!!!!!"<<endl;
	}
	return 0;
}