大作业排课.cpp

简易教学任务安排 假设有n门课程需要n个教师去授课

/*题目：假设有n门课程需要n个教师去授课，由于每个教师的专业特长不同，因此，要
        求每位教师只能承担一门他所精通的课程的教学任务。
        请用图结构设计，在n门课程编号、n个教师编号和他们各自专业特长都已知的
		情况下，输出一张安排合理的教学任务表，支出每位教师要承担什么课程。
        实现要求：
        ⑴  用二维数组S存储所有教师的专业特长，其中：
        S[i][j]=0     表示i教师不精通j课程；S[i][j]=1     表示i教师精通j课程

        ⑵  用一维数组D存储安排的教学任务表，其中：
        D[i]=0     表示i教师未安排课；D[i]=K(1≤k≤n)    表示i教师已安排课程k

        ⑶  课程门数n应由输入随机确定，且约定课程编号和教师编号均采用1，2…n，
		各位教师的专业特长也应由输入随机确定。
        ⑷  教学任务安排应以表格形式显示。
---------------------------------------------------------------------
techer_speciality（教师专长课程设定）、主函数————————胡磊
edit（教师专长课程修改）,list(教师专长输出),creat(初始化函数),sjcount(随机生成老师专长) ——卢炯
serch、serch_error、anpai（课程安排） ———————————————钟小玲
print_screen,pint_single,pint_segment,display（查看已经安排的教学任务）——————陈振锋
cout_s,cout_t,print_list(按表格输出教学任务)——————————谢贤颖

——————————————————————————————————*/

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>//setw()
#include<time.h>
#define max 100
typedef struct {
        int s[max][max];//用二维数组存放教师专业特长
		int D[max];      //用一维数组存放安排的教学任务
}MGraph;
int c[max]={0};

///////////////初始化函数——卢炯//////////////////
int creat(MGraph &G,int *k,int &n,int b)         //初始化，将二维数组s和一维数组D的adj全部赋值为0
{
	int i,j;
	if(!b)
	{
		cout<<"请确定课程数或教师人数（1-"<<max-1<<"） ";cin>>n;

	    if (n<=0||n>max-1)  
		{cout<<"数字无效"<<endl;return (0);}
	    cout<<endl;
	    cout<<"科目数成功确定为  "<<n<<endl;
	}
	for(i=1;i<=n;i++)
	{	
		if(b==2)c[i]=0;
		else {
			G.D[i]=0;
            k[i]=0;
		    for(j=1;j<=n&&!b;j++)
		    G.s[i][j]=0;
		}
	}
	return(1);
	
}

/////////////教师专长课程设定——胡磊//////////////

int techer_speciality(MGraph &G, int n)
{
	
	int k;
	cout<<"请输入教师专业特长编号(1-"<<n<<")  0表示结束输入：\n";

	for(int i=1;i<=n;i++)
	{
		cout<<"输入教师编号为 "<<i<<" 的特长专业号："<<endl;;
		do {
			cin>>k;
			if(k>n) {cout<<"超出范围，重新输入:   ";continue;}
			else G.s[i][k]=1;
		}while(k);
	}
	cout<<"设定成功！"<<endl;
	return (1);//设定成功！
}
//////////////搜索——钟小玲////////////////

int serch(MGraph &G,int i,int j,int n)
{
	for(;j<=n;j++)
		if(G.s[i][j]==1)break;
		
		return(j);
}
//////////////课程安排——钟小玲////////////////

int serch_error(MGraph &G,int *k,int n)//在已被进行安排过的老师都里运行
{
	int t;static int b=0;              //b检测是否上一次没被安排的课程也是同这位老师精通
	for(int j=1;j<=n;j++)
		if(k[j]==0)                    //存在有科目没有老师授课
			for(int i=1;i<=n;i++)      //哪个老师可以授此科目且此科目当前还没有老师授课
				if(G.s[i][j]==1)
				{	
					if(G.D[i]==0)return 0;   //此老师还没受到安排，返回等此老师都有被进行安排过才进行
					if(b==i){k[G.D[i]]=-1;k[j]=i;G.D[i]=j;b=0;return 1;}else b=i;   //if(b!=i)b=i记录第一个没有授课的科目但有老师可以授课的老师下标
					                           //令这位老师只能选择现在没被安排的课程即k[j]=i，G.D[i]=j，
					                           //并令在再次搜索时即步骤①时，不再搜索上次没被安排的课程即令k[G.D[i]]=-1		                          
					t=G.D[i];G.D[i]=j;k[j]=i;k[t]=0;return 1;  //有，让此老师授此课，原来所授的课取消，重新安排过。
				}return 0;                     //(没有科目没有被安排)或者(有科目没有被安排但没有老师有此专长)
}
//——————————————————————//
void anpai(MGraph &G,int *k,int n)
{
	int j, js, p=1,t;
	for(int i=1;i<=n;i++)
		if(G.D[i]==0)
		{j=1;
		while(1)
		{
			js=serch(G,i,j,n);
			if(js<=n)
			{
				c[p++]=js;//保存从serch里返回的教师专长
				if(k[js]<=0)
				{
					G.D[i]=js;k[js]=i;p=1;creat(G,k,n,2);break;
				}
				else {j=js;j++;}
			}
			else {
				p=1;
				if(c[p]==0){ G.D[i]=0;break; }
				t=k[c[p]];
				j=c[p]+1;
				while(1)
				{
					js=serch(G,t,j,n);

					if(k[js]<=0&&js<=n)
					{
					    G.D[t]=js; k[js]=t; G.D[i]=c[p]; k[c[p]]=i; p=1; creat(G,k,n,2);break;
					}
					else if(js<=n)j++;
					else {
						p++;

						if(c[p]==0)
						{
							G.D[i]=0;creat(G,k,n,2); if(serch_error(G,k,n))anpai(G,k,n); break;
						}

					t=c[p];j=c[p]+1;
					}
				}//while
				break;
			}
		}//while
		}//if
}

/////////////////教师专长输出——卢炯/////////////////
void list(MGraph &G,int n)
{
	int i,j,k;//k=0 记录输出个数
	for (i=1;i<=n;i++)
	{
		k=0;
		cout<<setw(3)<<i<<" 号教师的专业特长有: ";
		for(j=1;j<=n;j++)
			if (G.s[i][j]){
				k++;
				cout<<j<<setw(4); if((k%12)==0) {cout<<endl;cout<<setw(25);}
			}//打印15个换一行
			cout<<endl;
	}
	

}


//////////////教师专业修改——卢炯////////////////
void edit(MGraph &G, int n,int*k)        
{
   int s,i=0,m=0,j=0;
   cout<<"请输入要修改的老师：";
   while(i==0||i>n){
                    cin>>i;
                   if(i>0&&i<=n)
                             cout<<"第"<<i<<"个老师的专长科目有: ";
                  else cout<<"没这个老师！请重新输入："<<endl;
                   }

   for(s=1;s<=n;s++)
 {
   if(G.s[i][s]==1)
  {
    cout<<s<<setw(3);
     j++;
  }
 }
   if(j==0)
   cout<<"没有专长科目"<<endl;

   cout<<endl<<"输入你要修改的科目(输入0结束)："<<endl;

   do {
       cin>>s;
       if(s>n) {  cout<<"超出范围，重新输入:   ";continue; }
       else if(G.s[i][s]==1)
                       G.s[i][s]=0;
           else G.s[i][s]=1;
      }while(s);

   cout<<"修改后第"<<i<<"个老师的专长科目有 :";
   for(s=1;s<=n;s++)
 {
    if(G.s[i][s]==1)
   {
     cout<<s<<setw(3);
     m++;
   }
 }
   if(m==0)
      cout<<"没有专长科目"<<endl;
   cout<<endl;
   creat(G,k,n,1);
}



///////////////随机生成老师专长——卢炯////////////////////////////
void sjcount(MGraph &G, int n,int*k)//随机生成老师专长
{
srand((unsigned int)time((time_t *)NULL));//srand() 来初始化伪随机数发生器的种子，(当前时间)
for (int i=1;i<=n;i++){
	for (int s=1;s<=n;s++)
	{
          G.s[i][s]=rand() % 2;
	}
}
creat(G,k,n,1);//修改后把数组D和k全部赋值为0
}


//////////////谢贤颖//////////////////////
void cout_s(int s,int D[]) {//输出科目编号 s , 当 D[s] 不足二位时前面输出0
	cout<<"│";
	if(D[s]>9)cout<<D[s];
	else cout<<"0"<<D[s];
}

void cout_t(int k) {//输出老师编号 k , 当 k 不足二位时前面输出0
	cout<<"│";
	if(k>9)cout<<k;
	else cout<<"0"<<k;
}

void print_list(int D[],int f,int n) {//输出数组D[f]至D[f+n-1]的所有元素

	int i,j,k,m,s;//m,s为开始位置,n为要输出的记录个数

	m=s=f;

	if(n>9) {//n>=10