求最小覆盖繁版c++程序.doc

#includeusing namespace std;#include/*描述依赖的结构体*/struct FDstring foreward;string backward; ; /*求最小覆盖有关的函数*/void input(FD fd)string a,b;cout请您输入依赖关系：endl;for(int i=0;iab;fdi.backward=b;fdi.foreward=a;coutabendl;cout您输入的依赖关系有：endl;for(int j=0;j6;j+)coutfdj.forewardfdj.backward , ;coutendl;bool in(string fw,string res1)int count=0;for(int k=0;kfw.size();k+)for(int p=0;pres1.size();p+)if(fwk=res1p)count+;if(count=fw.size()return true;else return false;string join(string res1,string bw)int count=0;for(int k=0;kbw.size();k+)for(int p=0;pres1.size();p+)if(bwk!=res1p)count+;if(count=res1.size()res1=res1+bwk;count=0;else count=0;return res1;string closure(string x1,FD fd,string res) /求X在某个R上的闭包res=x1;int i=0;string oldres;dooldres=res;for(i;i5;i+)if(in(fdi.foreward, res)res=join(res,fdi.backward);i=0;while(oldres!=res);return res;FD *zuoquchong(FD fd) /使依赖关系右侧属性单一static FD fd110;int count=0; for(int i=0;i6;i+)for(int i1=0;i1A；static FD fdg10;int count=0;for(int i=0;i10;i+) if(i!=i1) fdgcount.foreward=fd1i.foreward; fdgcount.backward=fd1i.backward; count+; return fdg;FD *quchongFD(FD fd) /去掉冗余的FD； static FD fd210;for(int j=0;j10;j+)fd2j.foreward=fdj.foreward;fd2j.backward=fdj.backward;string re,re1;int count=0; for(int i=0;i10;i+)re1=closure(fd2count.foreward,GFD(fd2,count),re);if(in(fd2count.backward,re1)for(int p=0;p10;p+)fd2p.backward=GFD(fd2,count)p.backward;fd2p.foreward=GFD(fd2,count)p.foreward; elsecount+;return fd2;string determinant(string resd,int key) /求X-Bi; for(int p=key;presd.size();p+)resdp=resdp+1;return resd;FD *youquchong(FD fd) /去掉冗余的决定因素；static FD fd310;string re,re1;int count=0;for(int i=0;i10;i+)fd3i.foreward=fdi.foreward;fd3i.backward=fdi.backward;for(int j=0;j10;j+)count=0;for(int p=0;pfdj.foreward.size();p+)re1=closure(determinant(fd3j.foreward,count),fd3,re); /cout当前re1： re1endl;if(in(fd3j.backward,re1)fd3j.foreward=determinant(fd3j.foreward,count);else count+; return fd3; FD *MiniCoverage(FD fdf) /求R的最小覆盖FD *p,*q,*z;p=zuoquchong(fdf);q=quchongFD(p);z=youquchong(q);return z;/*输出函数一览*/void output1(FD fd11) cout右端属性单一后的函数依赖如下：endl; for(int j=0;j10;j+)coutfd11j.forewardfd11j.backward , ; coutendl; void output2(FD fd11) cout去掉重复依赖后的函数依赖如下：endl; for(int j=0;j10;j+)coutfd11j.forewardfd11j.backward , ; coutendl;void output3(FD fd11) cout去掉重复的决定因素后的函数依赖如下：endl; for(int j=0;j10;j+) coutfd11j.forewardfd11j.backward , ;coutendl;coutendl;void output4(FD fd11) cout您所求的关系模式R(U,F)的最小覆盖为：endl; for(int j=0;j10;j+) coutfd11j.forewardfd11j.backward , ; coutendl; /*主函数*/void main()cout提示1：此处仅限输入6组函数依赖,若小于6组，余下的位置请您用平凡依赖填补!endl;cout提示2：此处仅限函数依赖右端元素总和不得超过10个!endl;FD fds6;input(fds);output1(zuoquchong