候选码最小函数依赖求解系统代码

#include"relation.h" //A->BC,D->E,ACD->G,DG->A,EG->B,E->DH //ABCDEGHJ vector<string> split(const string &s, const string &seperator) { vector<string> result; typedef string::size_type string_size; string_size i = 0; while(i != s.size()){ //找到字符串中首个不等于分隔符的字母； int flag = 0; while(i != s.size() && flag == 0){ flag = 1; for(string_size x = 0; x < seperator.size(); ++x) if(s[i] == seperator[x]){ ++i; flag = 0; break; } } //找到又一个分隔符，将两个分隔符之间的字符串取出； flag = 0; string_size j = i; while(j != s.size() && flag == 0){ for(string_size x = 0; x < seperator.size(); ++x) if(s[j] == seperator[x]){ flag = 1; break; } if(flag == 0) ++j; } if(i != j){ result.push_back(s.substr(i, j-i)); i = j; } } return result; } multimap<string,string> copyMap(multimap<string,string> map) { multimap<string,string> tfDepSet; multimap<string,string>::iterator i; multimap<string,string>::iterator j; for (i=map.begin();i!=map.end(); ++i) { tfDepSet.insert(multimap<string,string> ::value_type(i->first, i->second)); } return tfDepSet; } void DeDup(string& s) { string deDupStr; //保存删除重复后的字符串 bool list[128]={0}; //保存字符串s中所有字符的状态 int i; for(i=0; i!=s.size(); i++) list[s[i]]=1; for(i=0; i<128; i++) { if(list[i]) { deDupStr += i; } } s=deDupStr; } bool sfind(string s1,string s2) { //s1 find s2 //int flag=1; for(int i=0;i<s2.size();i++) { string::size_type idx = s1.find(s2[i]); if ( idx == string::npos ) { return false; } } return true; } char *toChar(string s) { char *p; int len = s.length(); p=(char *)malloc((len+1)*sizeof(char)); s.copy(p,len,0); return p; } void Combination_m(char *pStr, int m, vector<char> &result,vector<string> &setZ) { string s; if(pStr == NULL || (*pStr == '\0'&& m != 0)) return ; if(m == 0) //递归终止条件 { for(unsigned i = 0; i < result.size(); i++) s=s+result[i]; setZ.push_back(s); return ; } //选择这个元素 result.push_back(*pStr); Combination_m(pStr + 1, m - 1, result,setZ); result.pop_back(); //不选择这个元素 Combination_m(pStr + 1, m, result,setZ); } vector<string> Combination(char *pStr) { vector<char> result; vector<string> setZ; if(pStr == NULL || *pStr == '\0') { return setZ; } int number = strlen(pStr); for(int i = 1; i <= number; i++) { Combination_m(pStr, i, result,setZ); } return setZ; } void DeDDup(string &s1,string &s2) { DeDup(s1); DeDup(s2); int i=0; int j=0; vector<char> temp; while(i!=s1.size()&&j!=s2.size()) { if(s1[i]!=s2[j]) { if(s1[i]>s2[j]) { j++; } else { i++; } } else { temp.push_back(s1[i]); i++; j++; } } vector<char>::iterator it; for(it=temp.begin();it!=temp.end();it++) { int t=s1.find(*it,0); if(t!=string::npos) { s1.erase(t,1); } else { break; } int t2=s2.find(*it,0); if(t2!=string::npos) { s2.erase(t2,1); } else { break; } } } string setSub(string s1,string s2) { for(int it=0;it<s2.size();it++) { int t=s1.find(s2[it],0); if(t!=string::npos) { s1.erase(t,1); } else { break; } } return s1; } string Relation::getvCandidate() { // vector<string> v; string v; vector<string>::iterator i; for(i=vCandidate.begin();i!=vCandidate.end();i++) { v=v+*i+" "; } return v; } multimap<string,string> Relation::getfDepSet() { multimap<string,string> tfDepSet; multimap<string,string>::iterator i; multimap<string,string>::iterator j; for (i=fDepSet.begin();i!=fDepSet.end(); ++i) { tfDepSet.insert(multimap<string,string> ::value_type(i->first, i->second)); } return tfDepSet; } void Relation::setU(string s) { DeDup(s); vector<string> temp=split(s,"，,"); for(int i=0;i<temp.size();i++) { U=U+temp[i]; } } void Relation::setU2(string s) { vector<string> vecU=split(s,"，,->"); for(int i=0;i<vecU.size();i++) { U2=U2+vecU[i]; } DeDup(U2); } bool Relation::match() { bool b=sfind(U,U2); return b; } void Relation::setMapF(string f) { vector<string> vecF=split(f,"，,->"); for(int i=0;i<vecF.size();i=i+2) { string temp1=vecF[i]; string temp2=vecF[i+1]; multimap<string, string>::iterator it; int flag=0; for(it = fDepSet.lower_bound(temp1); it != fDepSet.upper_bound(temp1); it++) { if(temp2==it->second) { flag=1; } } if(flag==0) { fDepSet.insert(multimap<string,string> ::value_type(vecF[i], vecF[i+1])); } } } string Relation::GetClosure(string oldClosure,multimap<string,string> fDepSet) { sort(oldClosure.begin(), oldClosure.end()); DeDup(oldClosure); string newClosure=oldClosure;//初始化属性闭包 do { oldClosure=newClosure;//保存当前属性集 multimap<string,string>::iterator i; for (i=fDepSet.begin();i!=fDepSet.end(); ++i) { string item = (*i).first; bool isSubSet = true; string::iterator j; for(j=item.begin();j!=item.end();j++) { //一旦函数依赖的左边first中的某个字母没在newClosure中，那么first就不是子集，跳出循环 if(newClosure.find(*j,0)==string::npos) { isSubSet=false; break; } } //函数依赖的左边first是属性闭包newClosure子集，向newClosure中添加second if(isSubSet==true) newClosure+=(*i).second; DeDup(newClosure); sort(newClosure.begin(), newClosure.end()); } //如果属性闭包等于全集U，则跳出循环 if(newClosure==U) break; }while(newClosure!=oldClosure); return newClosure; } multimap<string,string> Relation::depart() { multimap <string, string>::iterator m1_Iter; for ( m1_Iter = fDepSet.begin(); m1_Iter != fDepSet.end(); m1_Iter++ ) { string temp=m1_Iter->second; if((temp.size())>1) { for(int i=0;i<temp.size();i++) { string s="a"; s[0]=temp[i]; multimap<string, string>::iterator it; int flag=0; for(it = mapF2.lower_bound(m1_Iter->first); it != mapF2.upper_bound(m1_Iter->first); it++) { if(s==it->second) { flag=1; } } if(flag==0) { mapF2.insert(multimap<string,string> ::value_type(m1_Iter->first, s))