思想:面试轮数少的先安排面试。
1.建立学生数组stu[M],每个数组元素带有一个指针,指向其要参与面试的项目,指针初始化为NULL
2.读入数据,为每个学生添加要参与面试的项目号,表示项目的节点被添加到学生节点的项目指针中组成链表
3.建立一个数组表示面试安排表table[M+1][N+1](第0行和第0列空置不用),table[i][j]表示第i个学生参加第j个项目面试被安排在第table[i][j]轮,所有数组元素初始化为0 ;
4.找到参与项目面试轮数最少的学生i,从i要参与面试的项目中找出参与面试的人数最少的项目j
5.填面试安排表,在table[i][j]处填入该元素所在行和列都没出现过的最小正整数。
6.从学生i的项目链表中删除项目j,如果任一学生的项目链表非空,重复步骤4---步骤6.
5.建立最终结果数组resulttable[N+1][M+1],resulttable[i][j]表示第i个项目在第j轮面试第resulttable[i][j]个学生,把填好的表格table[M+1][N+1]依次整理到resulttable中,方法为resulttable[j][table[i][j]]=i;
#include<stdio.h>
#define M 3 //学生数
#define N 3 //项目数
/*
改进:
1.合法性判断:判断是否有学生没有参加项目或者参加了3个以上的项目
2.学生参与项目数可以在学生的结构体中用count体现
*/
static int stu_occur[M+1],pri_occur[N+1],table[M+1][N+1];
typedef struct prjnode
{
int data;
struct prjnode *next;
} Prjnode;
typedef struct stunode
{
int data;
Prjnode *next;
} Stunode;
void initial()
{
int i;
for(i=1;i<=M;i++)
stu_occur[i]=0;
for(i=1;i<=N;i++)
pri_occur[i]=0;
stu_occur[0]=N+1;//从最小值开始选取,下标为0的元素用不到,设置为最大
pri_occur[0]=M+1;//从最小值开始选取,下标为0的元素用不到,设置为最大
}
void AddPrjtoStu(Stunode *stu,int i) //为每个学生添加要参与面试的项目
{
Prjnode *pprj=(*stu).next;//指向项目节点的指针
if(pprj==NULL)
{
(*stu).next=(Prjnode *)malloc(sizeof(Prjnode));
pprj=(*stu).next;
pprj->data=i;
pprj->next=NULL;
}
else
{
while(pprj->next!=NULL)
pprj=pprj->next;
pprj->next=(Prjnode *)malloc(sizeof(Prjnode));
pprj=pprj->next;
pprj->data=i;
pprj->next=NULL;
}
}
void filltable(int x,int y)
{
int hang[N+1],lie[M+1],i;//每行N个元素,每列M个元素,头部下标为0的元素不用
for(i=1;i<=N;i++)
hang[i]=0;
for(i=1;i<=M;i++)
lie[i]=0;
for(i=1;i<=N;i++)
hang[table[x][i]]++;//当前行中出现过的元素
for(i=1;i<=M;i++)
lie[table[i][y]]++;//当前列中出现过的元素
for(i=1;i<=3;i++)
if(hang[i]==0&&lie[i]==0)
break;
table[x][y]=i;
}
void delprj(Stunode *stu,int i)
{
Prjnode *ptmp,*pprj=(*stu).next;
while(pprj->data!=i)
{
ptmp=pprj;
pprj=pprj->next;
}
if(pprj==(*stu).next)
(*stu).next=pprj->next;
else
ptmp->next=pprj->next;
free(pprj);
}
void main()
{
Stunode stu[M];
int i,j,xmin,ymin,max; //xmin待填表的横坐标,ymin待填表的纵坐标,max所需最少的面试轮数
Prjnode *pprj;
int resulttable[N+1][M+1];
int *a=(int *)malloc(2*3*M*sizeof(int)); //学生数为M,每个同学至多参与3个项目的面试,读入文件中的条目不会超过3M个,数组不会超过6M
int illgal=0; //判断输入文件中的数据是否合法
FILE*fp,*fwp;//fp读文件指针,fwp写文件指针
void initial();
void AddPrjtoStu(Stunode *stu,int i);
for(i=0;i<M;i++)
{
stu[i].next=NULL;
stu[i].data=i+1;
}
initial();
for(i=0;i<3*M;i++)
a[i]=0;
if((fp=fopen("iw.in", "r"))==NULL)
{
printf("can't open input file\n");
}
else
{//tag1
for(i=0;;i+=2)
{
fscanf(fp, "%d%d", &a[i], &a[i+1]);
if(a[i]==0)
break;
printf("%d %d\n",a[i],a[i+1]);
}
printf("0 0\n");
fclose(fp);
for(i=0;a[i]!=0;i+=2)
{
AddPrjtoStu(&stu[a[i]-1],a[i+1]); //为学生添加面试的项目数,a[i]学生号码,a[i+1]项目号码,
stu_occur[a[i]]++; //a[i]号学生参与项目面试总次数
pri_occur[a[i+1]]++; //a[i+1]号项目参与面试的次数
}
for(i=1;i<=M;i++)
if(stu_occur[i]>3||stu_occur[i]<1) //参与了3个以上项目或者没有参加项目,非法
illgal=1;
if(illgal==1)
printf("输入非法,请确保每个学生参加至少一个且不超过三个项目面试\n");
else
{
while(stu[0].next!=NULL||stu[1].next!=NULL||stu[2].next!=NULL) //邻接表非空
{
for(i=1;i<=M&&stu_occur[i]==0;i++); //找要填表格的横坐标xmin;
if(i<=M) //此if不在for循环体内
xmin=i;
for(i=xmin+1;i<=3;i++)
if(stu_occur[i]<stu_occur[xmin]&&stu_occur[i]!=0)
xmin=i; //确定下来要填表格的横坐标xmin,xmin代表学生要参加的项目面试次数最少;
for(pprj=stu[xmin-1].next,ymin=pprj->data;;pprj=pprj->next)//前面已经保证stu[xmin-1]所指向的链表非空。
{
if(pprj==NULL) break;
if(pri_occur[pprj->data]<pri_occur[ymin])
ymin=pprj->data;
}
filltable(xmin,ymin); //填表函数,确定面试顺序
delprj(&stu[xmin-1],ymin); //删除函数,删除学生项目练表中已经安排面试的项目
stu_occur[xmin]--; //学生待参与面试的项目数减一
pri_occur[ymin]--; //参与面试的学生数减一
}
///*
printf("面试安排表格式1:A[i][j]表示第i个学生参加第j个项目面试的次序为A[i][j]\n");
for(i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
{
printf("%d",table[i][j]);
if(j!=4) printf(" ");
}
printf("\n");
}
//*/
for(i=1;i<=M;i++)
for(j=1;j<=N;j++)
resulttable[i][j]=0;
max=table[1][1];
for(i=1;i<=M;i++)
for(j=1;j<=N;j++)
if(table[i][j]!=0)
{
if(table[i][j]>max)
max=table[i][j];
resulttable[j][table[i][j]]=i;
}
printf("面试安排表格式2:A[i][j]表示第i个项目在第j轮面试第A[i][j]个学生\n");
for(i=1;i<=N;i++)
{
for(j=1;j<=max;j++)
{
printf("%d",resulttable[i][j]);
if(j!=4) printf(" ");
}
printf("\n");
}
if((fwp=fopen("iw.out","w+"))==NULL)
{
printf("can't open output file\n");
}
else
{
for(i=1;i<=N;i++)
{
for(j=1;j<=max;j++)
{
fprintf(fwp,"%d",resulttable[i][j]);
if(j!=max)
fprintf(fwp," ");
}
fprintf(fwp,"\n");
}
printf("结果已按照格式2写入iw.out,可用记事本打开查看\n");
};
free(a);
}
}//tag1
}