依賴保持分解算法

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();/構造函數(shù)voidAdd_Function(char*,int,char*,int);/建立新的關系結點voidClear_Function();/清空表boolCheak_Function(Function*);/檢查該關系是否已經存在Function*Delete_Function(Function*);/刪除當前節(jié)點Function*Get_Head();/返回頭結點voidGet_Collection(char*);/返回這個關系中的所有

3、元素voidOutput();/輸出;Function_Set:Function_Set()/構造函數(shù)head=NULL;/head-next=NULL;Function*Function_Set:Delete_Function(Function*F_del)/刪除當前節(jié)點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();構造函數(shù)Devide*Get_Head();/返回頭結點intGet_Long();/返回鏈表長度voidAdd_Devide(char*);增加子關系voidOutput();輸出);Devide_Set:Devide_Set()/構造函數(shù)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)/去除冗余的函數(shù)依賴Function_Set*FS_te

19、mp1=newFunction_Set;Function*F_temp1=newFunction;Function*F_temp2=newFunction;F_temp1=Ans-Get_Head();指向當前節(jié)點F_temp2=FS_temp1-Get_Head();指向G的頭結點while(F_temp1!=NULL)/對Ans里面所有的function遍歷charC_temp120;/當前節(jié)點的左集Set_Null(C_temp1);charC_temp320;當前節(jié)點的右集Set_Null(C_temp3);charC_temp220;/當前節(jié)點在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)/構建函數(shù)依賴集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);/刪除當前關系節(jié)點并且返回下一節(jié)點的地址)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;/初始狀態(tài)指向G的頭結點Function*F_temp2=newFunction;/指向當前節(jié)點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