📄 m-in.cpp
字号:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
const int l=3; //l-diversity
const int limit=2; //l-diversity
struct element //病人的数据结构
{
int num;
int gid;
char name[10];
int age;
int zip;
char disease[20];
bool flag;
int bnum;
};
element op[50000]; //旧病人数据
element np[50000]; //新病人数据
int onum; //旧病人个数
int nnum; //新病人个数
int remain; //未被分配的病人个数
struct node //桶中病人的数据结构
{
char disease[100];
int people[5000];
int pnum;
int cnum;
};
node SA[10]; //用于记录等价类中的疾病
node distable[100]; //记录未被分组的疾病和病人情况
int remain_dis;
int dnum;
struct bucket //桶的数据结构
{
bool flag;
node dis[10];
int dnum;
int cnum;
}buc[500];
int bnum; //桶的个数
struct hash_node //hash表的数据结构
{
char disease[100];
int bnumber;
bool flag;
}hashtable[10000];
struct hashdis_node //hash表的数据结构
{
char disease[20];
int dnumber;
bool flag;
}hashdis[10000];
typedef struct t_node //语义树的定义
{
char disease[20];
struct t_node *father;
}t_node,*tree;
tree root;
struct f_node
{
char disease[20];
tree T;
int height;
}dislist[100];
int disnum=17;
int maxheight=3;
int cnum; //虚拟元素的个数
int fnum=1;
void input(void); //读文件函数
void division(void); //拆分阶段
void balancing(void); //平衡阶段
void assignment(void); //分配阶段
void split(void); //剥离阶段
int hash(int num); //hash的映射函数
int f(int num); //hash的key计算函数
int searchhash(int key, char disease[]); //查找hash表
void inserthash(int key, char disease[], int bnumber); //插入hash表
int hashdisease(char dis[]); //hash的映射函数
int searchdis(char dis[]); //查找hash表
void insertdis(char dis[], int dnumber); //插入hash表
void create_tree(void);
int caculate(char a[], char b[]);
int caculate_digit(int i, int j); //计算邮编
int filenum=0;
int main()
{
FILE *fptr;
char tt[20];
scanf("%s",tt);
if((fptr=fopen("500.txt",'r'))==NULL)
int b;
double m[55][2];
int i=0;
while(fscanf(fptr,"%lf %lf", &m[i][0],&m[i][1])!=EOF)
i++;
double t1=0;
double t2=0;
for(i=0;i<50;i++)
{
t1+=(500-m[i][0])/500;
t2+=m[i][1];
}
printf("%.1lf, %.1lf",t1/50,t2/50);
printf("剩余未分配人员 虚拟元素个数\n");
create_tree();
while(fnum!=51)
{
input();
if(onum!=0)
division();
balancing();
assignment();
split();
int i,j,k=0;
printf(" %d %d\n",remain,cnum);
for(i=0;i<bnum;i++)
{
for(j=0;j<buc[i].dnum;j++)
{
buc[i].dis[j].cnum=0;
buc[i].dis[j].pnum=0;
}
buc[i].flag=false;
buc[i].cnum=0;
}
bnum=0;
for(i=0;i<10000;i++)
{
hashdis[i].flag=false;
hashtable[i].flag=false;
remain=0;
}
cnum=0;
onum=0;
nnum=0;
dnum=0;
remain=0;
remain_dis=0;
for(i=0;i<100;i++)
{
distable[i].pnum=0;
}
for(i=0;i<5000;i++)
np[i].flag=false;
}
return 0;
}
void input(void)
{
FILE *fptr1;
FILE *fptr2;
char old[20];
char newfile[20];
// printf("源文件名称\n");
// scanf("%s",old);
// printf("新文件名称\n");
// scanf("%s",newfile);
itoa(fnum,old,10);
strcat(old,"gg.txt");
itoa(fnum,newfile,10);
strcat(newfile,".txt");
int i=0;
// if((fptr1=fopen("old.txt","r"))==NULL)
if((fptr1=fopen(old,"r"))==NULL)
printf("源文件打开失败/n");
else
{
if ((fptr2=fopen(newfile,"r"))==NULL)
printf("新文件打开失败/n");
else
{
while(fscanf(fptr1,"%d %s",&op[i].gid, op[i].name)!=EOF)
{
if(strcmp(op[i].name,"c")==0)
fscanf(fptr1,"%s",op[i].disease);
else
{
fscanf(fptr1,"%d %d %s",&op[i].age, &op[i].zip, op[i].disease);
op[i].num=++i;
}
}
onum=i;
i=0;
while(fscanf(fptr2,"%s %d %d %s",np[i].name,&np[i].age, &np[i].zip, np[i].disease)!=EOF)
np[i].num=++i;
nnum=i;
remain=nnum;
}
}
for(i=0;i<10;i++)
buc[i].flag=false;
bnum=0;
}
void division(void)
{
bool flag=false;
int i,j,k=0,g,key,save=0,bnumber;
int tap=1;
bnum=0;
for(i=0;i<onum+1;i++)
{
if(op[i].gid!=tap||i==onum)
{
key=f(k);
bnumber=searchhash(key, SA[k].disease);
if(bnumber<0) //建立新桶
{
buc[bnum].dnum=0;
buc[bnum].cnum=0;
buc[bnum].flag=false;
for(g=save;g<i;g++)
{
for(j=0;j<nnum;j++)
{
if(strcmp(op[g].name,np[j].name)==0)
{
flag=true;
np[j].flag=true;
break;
}
}
strcpy(buc[bnum].dis[buc[bnum].dnum].disease,op[g].disease);
buc[bnum].dis[buc[bnum].dnum].cnum=0;
buc[bnum].dis[buc[bnum].dnum].pnum=0;
if(flag==true)
{
flag=false;
buc[bnum].flag=true;
buc[bnum].dis[buc[bnum].dnum].people[buc[bnum].dis[buc[bnum].dnum].pnum++]=j;
remain--;
}
buc[bnum].dnum++;
}
inserthash(key, SA[k].disease, bnum);
bnum++;
}
else //桶可以合并
{
for(g=save;g<i;g++)
{
for(j=0;j<nnum;j++)
{
if(strcmp(op[g].name,np[j].name)==0)
{
flag=true;
np[j].flag=true;
break;
}
}
if(flag==true)
{
flag=false;
for(k=0;k<buc[bnumber].dnum;k++)
{
if(strcmp(np[j].disease,buc[bnumber].dis[k].disease)==0)
{
buc[bnumber].dis[k].people[buc[bnumber].dis[k].pnum++]=j;
remain--;
break;
}
}
}
}
}
save=i;
tap++;
k=0;
if(i!=onum)
strcpy(SA[k++].disease,op[i].disease);
}
else
strcpy(SA[k++].disease,op[i].disease);
}
}
void balancing(void)
{
int i,j,k,result,max=0,tmp,bnumber;
bool flag=false;
for(i=0;i<nnum;i++) //将新病人没有分配过的元素按照疾病分类
{
if(np[i].flag==false)
{
result=searchdis(np[i].disease);
if(result<0)
{
strcpy(distable[dnum].disease,np[i].disease);
distable[dnum].people[distable[dnum].pnum++]=i;
insertdis(np[i].disease,dnum);
remain_dis++;
dnum++;
}
else
distable[result].people[distable[result].pnum++]=i;
}
}
for(i=0;i<bnum;i++)
if (buc[i].flag==true)
{
max=0;
for(j=0;j<buc[i].dnum;j++)
if(buc[i].dis[j].pnum>max)
max=buc[i].dis[j].pnum; //求出分离阶段后桶中疾病人数最多的个数
for(j=0;j<buc[i].dnum;j++)
{
if(buc[i].dis[j].pnum<max)
{
bnumber=searchdis(buc[i].dis[j].disease);
if (bnumber<0)
for(k=buc[i].dis[j].pnum;k<max;k++)
{
buc[i].dis[j].people[buc[i].dis[j].pnum++]=-1;
cnum++;
buc[i].dis[j].cnum++;
buc[i].cnum++;
}
else
{
if(distable[bnumber].pnum>=(max-buc[i].dis[j].pnum))
{
for(k=buc[i].dis[j].pnum;k<max;k++)
{
np[distable[bnumber].people[distable[bnumber].pnum]].flag=true;
buc[i].dis[j].people[buc[i].dis[j].pnum++]=distable[bnumber].people[distable[bnumber].pnum-1];
distable[bnumber].pnum--;
remain--;
}
if(distable[bnumber].pnum==0)
remain_dis--;
}
else
{
tmp=distable[bnumber].pnum;
for(k=buc[i].dis[j].pnum;k<tmp;k++)
{
np[distable[bnumber].people[distable[bnumber].pnum]].flag=true;
buc[i].dis[j].people[buc[i].dis[j].pnum++]=distable[bnumber].people[distable[bnumber].pnum-1];
distable[bnumber].pnum--;
remain--;
}
remain_dis--;
for(k=buc[i].dis[j].pnum;k<max;k++)
{
buc[i].dis[j].people[buc[i].dis[j].pnum++]=-1;
cnum++;
buc[i].dis[j].cnum++;
buc[i].cnum++;
}
}
}
}
}
}
}
void assignment(void)
{
int i,j,k,i1,i2,i3,i4,i5;
struct order_node
{
int dnumber;
int pnum;
}order[20];
int choose[10];
int onum,min,bnumber;
int tmp1,tmp2,tmp3;
bool flag=false,flag2=false,flag3=false;
/*for(i=0;i<bnum;i++) //向已有桶内分配元素(优化)
{
int min=100000;
for(j=0;j<buc[i].dnum;j++)
{
flag=false;
bnumber=searchdis(buc[i].dis[j].disease);
if(bnumber<0)
flag=true;
if(distable[bnumber].pnum==0)
flag=true;
if(flag==true)
break;
if(min>distable[bnumber].pnum)
min=distable[bnumber].pnum;
}
if(flag==false)
for(j=0;j<buc[i].dnum;j++)
{
bnumber=searchdis(buc[i].dis[j].disease);
for(k=0;k<min;k++)
{
np[distable[bnumber].people[distable[bnumber].pnum]].flag=true;
buc[i].dis[j].people[buc[i].dis[j].pnum++]=distable[bnumber].people[distable[bnumber].pnum--];
remain--;
}
if(distable[bnumber].pnum==0)
remain_dis--;
}
}*/
flag=true;
while(remain!=0)
{
if(flag==false||remain_dis<l) //如果剩下的元素实在不能配分，退出
break;
else
{
flag=false;
onum=0;
for(i=0;i<dnum;i++) //按剩余元素个数进行排列
{
if(distable[i].pnum!=0)
{
order[onum].dnumber=i;
order[onum++].pnum=distable[i].pnum;
}
}
for(i=1;i<onum;i++)
for(j=onum-1;j>=i;j--)
if(order[j-1].pnum<=order[j].pnum)
{
order[onum]=order[j-1];
order[j-1]=order[j];
order[j]=order[onum];
}
////////////////////////////////////
if(remain_dis<2*l)
flag2=true;
if(l==2)
{
for(i=0;i<onum;i++)
{
tmp1=1; //找出l种满足条件的疾病
choose[0]=order[i].dnumber;
for(j=i+1;j<onum;j++)
{
if(caculate(distable[order[i].dnumber].disease,distable[order[j].dnumber].disease)>limit)
{
choose[tmp1++]=order[j].dnumber;
flag=true;
break;
}
}
if(flag==true)
break;
}
if((flag2==true)&&(flag==true))
{
for(k=0;k<remain_dis;k++)
choose[k]=order[k].dnumber;
tmp1=k;
}
}
else if (l==3)
{
for(i1=0;i1<onum-2;i1++)
{
choose[0]=order[i1].dnumber;
for(i2=i1+1;i2<onum-1;i2++)
{
tmp1=1;
if(caculate(distable[order[i1].dnumber].disease,distable[order[i2].dnumber].disease)>limit)
{
choose[tmp1++]=order[i2].dnumber;
for(i3=i2+1;i3<onum;i3++)
{
tmp1=2;
if((caculate(distable[order[i1].dnumber].disease,distable[order[i3].dnumber].disease)>limit)&&(caculate(distable[order[i2].dnumber].disease,distable[order[i3].dnumber].disease)>limit))
{
choose[tmp1++]=order[i3].dnumber;
flag=true;
break;
}
}
}
if(flag==true)
break;
}
if(flag==true)
break;
}
if((flag2==true)&&(flag==true))
{
for(k=0;k<remain_dis;k++)
choose[k]=order[k].dnumber;
tmp1=k;
}
}
else if (l==5)
{
for(i1=0;i1<onum-4;i1++)
{
choose[0]=order[i1].dnumber;
for(i2=i1+1;i2<onum-3;i2++)
{
tmp1=1;
if(caculate(distable[order[i1].dnumber].disease,distable[order[i2].dnumber].disease)>limit)
{
choose[tmp1++]=order[i2].dnumber;
for(i3=i2+1;i3<onum-2;i3++)
{
tmp1=2;
flag3=true;
for(i=0;i<tmp1;i++)
if(caculate(distable[choose[i]].disease,distable[order[i3].dnumber].disease)<=limit)
flag3=false;
if(flag3==true)
{
choose[tmp1++]=order[i3].dnumber;
for(i4=i3+1;i4<onum-1;i4++)
{
tmp1=3;
flag3=true;
for(i=0;i<tmp1;i++)
if(caculate(distable[choose[i]].disease,distable[order[i4].dnumber].disease)<=limit)
flag3=false;
if(flag3==true)
{
choose[tmp1++]=order[i4].dnumber;
for(i5=i4+1;i5<onum;i5++)
{
tmp1=4;
flag3=true;
for(i=0;i<tmp1;i++)
if(caculate(distable[choose[i]].disease,distable[order[i5].dnumber].disease)<=limit)
flag3=false;
if(flag3==true)
{
choose[tmp1++]=order[i5].dnumber;
flag=true;
break;
}
}
}
if(flag==true)
break;
}
}
if(flag==true)
break;
}
}
if(flag==true)
break;
}
if(flag==true)
break;
}
if((flag2==true)&&(flag==true))
{
int count=0;
for(k=0;k<remain_dis;k++)
choose[k]=order[k].dnumber;
tmp1=k;
}
}
//////////////////////////////////
int ll=tmp1;
if(flag==true) //找到了满足要求的l种疾病
{
for(i=0;i<ll;i++)
strcpy(SA[i].disease,distable[choose[i]].disease);
tmp2=f(tmp1);
tmp3=searchhash(tmp2, SA[tmp1].disease);
if(tmp3<0) //没有当前桶，需要建立新桶
{
buc[bnum].flag=true;
buc[bnum].dnum=0;
buc[bnum].cnum=0;
for(i=0;i<ll;i++)
{
strcpy(buc[bnum].dis[buc[bnum].dnum].disease,distable[choose[i]].disease);
buc[bnum].dis[buc[bnum].dnum].cnum=0;
buc[bnum].dis[buc[bnum].dnum].pnum=0;
buc[bnum].dnum++;
}
inserthash(tmp2,SA[tmp1].disease, bnum);
tmp3=bnum;
bnum++;
}
tmp1=(distable[choose[ll-1]].pnum+1)/2;
for(i=0;i<ll;i++) //向桶里添加元素
{
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -