依赖保持分解算法

1、#include#includeusingnamespacestd;/charAns20;intGet_CLong(char*A_Char);/计算字符串的长度boolB_Equal(char*C_temp1,char*C_temp2);/判断两个字符串是否一样boolB_Belong(charx,char*X);/判断x是否属于X/char*Get_Closure(Function_Set*F,char*X);/求X在F上的闭包集structFunctioncharset_left20;intleft;charset_right20;intright;Function*next;Functi

2、on()next=NULL;classFunction_Setprivate:Function*head;public:Function_Set();/构造函数voidAdd_Function(char*,int,char*,int);/建立新的关系结点voidClear_Function();/清空表boolCheak_Function(Function*);/检查该关系是否已经存在Function*Delete_Function(Function*);/删除当前节点Function*Get_Head();/返回头结点voidGet_Collection(char*);/返回这个关系中的所有

3、元素voidOutput();/输出;Function_Set:Function_Set()/构造函数head=NULL;/head-next=NULL;Function*Function_Set:Delete_Function(Function*F_del)/删除当前节点Function*F_temp1=newFunction;F_temp1=head;if(head=NULL)elseif(head-next=NULL)(returnhead-next;)else(Function*F_temp1=newFunction;F_temp1=head;Function*F_temp2=newF

4、unction;F_temp2=head-next;while(F_temp2!=NULL)(if(B_Equal(F_del-set_left,head-set_left)&B_Equal(F_del-set_right,head-set_right)(head=head-next;returnhead;)elseif(B_Equal(F_del-set_left,F_temp2-set_left)&B_Equal(F_del-set_right,F_temp2-set_right)(F_temp1-next=F_temp2-next;returnF_temp1-next;)else(F_t

5、emp1=F_temp1-next;F_temp2=F_temp2-next;)returnNULL;)voidFunction_Set:Clear_Function()/清空表head=NULL;voidFunction_Set二Add_Function(char*t_sleft,intt_left,char*t_sright,intt_right)/增加一个关系结点Function*temp1=newFunction();for(inti=0;iset_lefti=t_slefti;temp1-left=t_left;for(inti=0;iset_righti=t_srighti;tem

6、p1-right=t_right;if(head=NULL)head=temp1;head-next=NULL;elseFunction*temp2=newFunction;temp2=head;while(temp2-next!=NULL)temp2=temp2-next;temp1-next=temp2-next;temp2-next=temp1;boolFunction_Set:Cheak_Function(Function*F_out)/检查该关系是否已经存在Function*F_temp1=newFunction;F_temp1=head;while(F_temp1!=NULL)if

7、(B_Equal(F_temp1-set_left,F_out-set_left)&B_Equal(F_temp1-set_right,F_out-set_right)returntrue;F_temp1=F_temp1-next;returnfalse;)Function*Function_Set:Get_Head()(returnhead;)voidFunction_Set:Get_Collection(char*C_temp1)/返回这个关系中的所有元素Function*F_temp1=newFunction;F_temp1=head;intI_temp2=0;while(F_temp1

8、!=NULL)for(inti=0;ileft;i+)输入左侧的元素if(!B_Belong(F_temp1-set_lefti,C_temp1)C_temp1I_temp2=F_temp1-set_lefti;I_temp2+;)for(inti=0;iright;i+)输入右侧的元素if(!B_Belong(F_temp1-set_righti,C_temp1)C_temp1I_temp2=F_temp1-set_righti;I_temp2+;)F_temp1=F_temp1-next;)cout关系中的所有元素为endl;for(inti=0;iGet_CLong(C_temp1);i

9、+)coutC_temp1i;)coutendl;)voidFunction_Set二Output()/输出Function*temp2=newFunction;temp2=head;if(temp2=NULL)else(Function*temp1=newFunction;temp1=head;while(temp1!=NULL)(for(inti=0;ileft;i+)(coutset_lefti;)cout;for(inti=0;iright;i+)(coutset_righti;)coutnext;)structDevide/构建一个分解的子关系chardev20;inttable;D

10、evide*next;);classDevide_Setprivate:Devide*head;intDS_table;public:Devide_Set();构造函数Devide*Get_Head();/返回头结点intGet_Long();/返回链表长度voidAdd_Devide(char*);增加子关系voidOutput();输出);Devide_Set:Devide_Set()/构造函数head=NULL;DS_table=0;)Devide*Devide_Set二Get_Head()/返回头结点returnhead;)intDevide_Set二Get_Long()/返回链表长度

11、returnDS_table;)voidDevide_Set:Add_Devide(char*C_temp1)/增加子关系Devide*D_temp1=newDevide;intI_temp1;I_temp1=Get_CLong(C_temp1);for(inti=0;idevi=C_temp1i;)D_temp1-table=DS_table;DS_table+;/D_temp1-next=NULL;if(head=NULL)head=D_temp1;head-next=NULL;)elseDevide*D_temp2=newDevide;D_temp2=head;while(D_temp2

12、-next!=NULL)D_temp2=D_temp2-next;)D_temp1-next=D_temp2-next;D_temp2-next=D_temp1;)voidDevide_Set:Output()/输出Devide*D_temp1=newDevide;D_temp1=head;while(D_temp1!=NULL)(intI_temp1;I_temp1=Get_CLong(D_temp1-dev);for(inti=0;iI_temp1;i+)(coutdevi;/couttable;coutnext;boolB_Contain(char*f_left,char*X)/判断f_

13、left是否包含于Xinttemp1,temp2,temp3;temp1=Get_CLong(X);temp2=Get_CLong(f_left);temp3=0;for(inti=0;itemp1;i+)for(intk=0;ktemp2;k+)if(f_leftk=Xi)temp3+;if(temp3=temp2)returntrue;elsereturnfalse;boolB_Belong(charx,char*X)判断x是否属于Xinttemp1;temp1=Get_CLong(X);for(inti=0;itemp1;i+)(if(x=Xi)(returntrue;returnfal

14、se;boolB_Equal(char*C_temp1,char*C_temp2)/判断两个字符串是否相等intI_temp1;I_temp1=Get_CLong(C_temp1);if(I_temp1!=Get_CLong(C_temp2)returnfalse;elsefor(inti=0;iI_temp1;i+)if(*(C_temp1+i)!=*(C_temp2+i)returnfalse;returntrue;intGet_CLong(char*A_Char)/计算字符串的长度inti=0;while(1)if(A_Chari64)i+;elsebreak;)returni;)voi

15、dSet_Null(char*C_temp1)/置空for(intii=0;ii20;ii+)C_temp1ii=;)voidOutput(char*C_temp1)/输出for(inti=0;iGet_CLong(C_temp1);i+)coutC_temp1i;)voidGet_Part(char*C_Previa,char*C_Rest,charC_Certain)去除C_Previa中的C_CertainintI_temp1,I_temp2=0;I_temp1=Get_CLong(C_Previa);for(inti=0;iI_temp1;i+)if(C_Previai!=C_Cert

16、ain)C_RestI_temp2=C_Previai;I_temp2+;)voidGet_Closure(Function_Set*F,char*X,char*Ans)/计算闭包集inttemp1;charbackup20;Set_Null(backup);temp1=Get_CLong(X);for(inti=0;itemp1;i+)Ansi=Xi;)Function*f_temp2=newFunction;boolA=true;while(A)(temp1=Get_CLong(Ans);for(inti=0;iGet_Head();while(f_temp2!=NULL)/一轮选择if(

17、B_Contain(f_temp2-set_left,Ans)/当F的左集合包含于Ans时inttemp3;inttemp4=Get_CLong(Ans);temp3=f_temp2-right;for(inti=0;iset_righti,Ans)/当Ans中不包含新的元素时Anstemp4=f_temp2-set_righti;temp4+;f_temp2=f_temp2-next;if(B_Contain(Ans,backup)A=false;/returnAns;voidDeal_Right(Function_Set*F,Function_Set*Ans)/将F右侧的属性集原子化Fun

18、ction*temp1=newFunction;inttemp2;temp1=F-Get_Head();while(temp1!=NULL)temp2=Get_CLong(temp1-set_right);for(inti=0;iCheak_Function(temp1)(Ans-Add_Function(temp1-set_left,Get_CLong(temp1-set_left),temp1-set_right+i,1);temp1=temp1-next;voidDeal_Redundancy_F(Function_Set*Ans)/去除冗余的函数依赖Function_Set*FS_te

19、mp1=newFunction_Set;Function*F_temp1=newFunction;Function*F_temp2=newFunction;F_temp1=Ans-Get_Head();指向当前节点F_temp2=FS_temp1-Get_Head();指向G的头结点while(F_temp1!=NULL)/对Ans里面所有的function遍历charC_temp120;/当前节点的左集Set_Null(C_temp1);charC_temp320;当前节点的右集Set_Null(C_temp3);charC_temp220;/当前节点在G上的闭包Set_Null(C_tem

20、p2);for(inti=0;ileft;i+)/存左集C_temp1i=F_temp1-set_lefti;for(inti=0;iright;i+)/存右集C_temp3i=F_temp1-set_righti;Function*F_temp4=Ans-Get_Head();/用于转移F-G时while(F_temp4!=NULL)/构建函数依赖集Gif(!B_Equal(F_temp4-set_left,C_temp1)|!B_Equal(C_temp3,F_temp4-set_right)FS_temp1-Add_Function(F_temp4-set_left,F_temp4-le

21、ft,F_temp4-set_right,1);F_temp4=F_temp4-next;)FS_temp1-Output();/coutendl;coutendl;Set_Null(C_temp2);Get_Closure(FS_temp1,C_temp1,C_temp2);/123/intI_temp2;I_temp2=Get_CLong(C_temp2);cout输出左集在G的闭包;for(inti=0;iI_temp2;i+)输出左集的闭包coutC_temp2i;)coutDelete_Function(F_temp1);/删除当前关系节点并且返回下一节点的地址)elseF_temp

22、1=F_temp1-next;)FS_temp1-Clear_Function();F_temp2=FS_temp1-Get_Head();)voidDeal_Redundancy_P(Function_Set*Ans)/去除元素冗余Function*F_temp1=newFunction;/初始状态指向G的头结点Function*F_temp2=newFunction;/指向当前节点F_temp2=Ans-Get_Head();while(F_temp2!=NULL)charC_temp120;/存放闭包集Set_Null(C_temp1);charC_temp220;/存放G中的新的属性集Set_Null(C_temp2);intI_temp1;if(Get_CLong(F_temp2-set_left)n