6.6.13.cpp

本代码包括函数最小覆盖算法（最小依赖）和无损分解的判断。

//算法6.6.13 
#include<iostream>
#include<string>
#include<list>
using namespace std;

const int size = 1024;
/*数据结构的定义,函数依赖集，对于X->Y,X用数组X[size]来保存，Y用数组Y[size]来保存。*/ 
struct AttrSet	
{
	AttrSet()
	{
		for(int i=0;i<size;i++)
		{
			X[i]=Y[i]="";
		}
	}
	string X[size];
	string Y[size];

	int count;/*用来计数，即有多少个函数依赖*/
};  
/*-------------------------------------*/
/*第一步*/
void Step1(AttrSet F,AttrSet &H); 
/*-----------------------------------*/
/*第二步，删除非关键的函数依赖*/
void Step2(AttrSet &H);
/*----------------------------------------*/ 
/*第三步，对于左边可以减少属性元素，即对属性的闭包集无影响的依赖，用少的属性来代替。*/
void Step3(AttrSet &H);
/*--------------------------------*/
/*第四步，对于左边相同的函数依赖，进行整合。*/
void Step4(AttrSet &H);
/*--------输出最小覆盖的函数---------*/ 
void print(AttrSet H);
/*对于X[I]->Y[I]，如果Y[I]已在X[i]的属性集合中，则返回false，即不加入，否则返回真，加入Y[I]。*/
bool not_exist(string y,list<char>front);
/*判定x[i]是否被已存在的闭包所包含。
即把x[i]中的每个元素都拿到闭包中去搜索。全部存在返回真，否则返回假。
*/
bool X_exist(string x,list<char>front);
/*-------------------------------------*/
/*第一步*/
void Step1(AttrSet F,AttrSet &H)
{
	H.count=0;
	for(int i=0;i<F.count;i++)
	{
		if(F.Y[i].length()>1)
		{	/*Y[i]包含多个属性，则每个属性都形成H的一个函数依赖*/
			for(int j=0;j<F.Y[i].length();j++)
			{
				H.X[H.count]=F.X[i];
				H.Y[H.count]=F.Y[i].substr(j,1);
				H.count++;
			}
		}
		else
		{
			H.X[i]=F.X[i];
			H.Y[i]=F.Y[i];
			H.count++;
		}
	}
}

void print(list<char> L)
{
	list<char> :: iterator it;
	for(it=L.begin();it!=L.end();it++)
	{
		cout<<(*it)<<" ";
	}
	cout<<endl;

}

/*对于X[I]->Y[I]，如果Y[I]已在X[i]的属性集合中，则返回false，即不加入，否则返回真，加入Y[I]。*/
bool not_exist(string y,list<char>front)
{
	
	list<char> :: iterator it;

	for(it=front.begin();it!=front.end();it++)
	{
		if(y[0]==(*it))
		{
			return false ;
		}
	}
	return true;
}
/*判定x[i]是否被已存在的闭包所包含。
即把x[i]中的每个元素都拿到闭包中去搜索。全部存在返回真，否则返回假。
*/
bool X_exist(string x,list<char>front)
{
	    int i=0;
		while(i<x.length())
		{
			bool in = false;
			list<char> :: iterator it;
			for(it=front.begin();it!=front.end();it++)
			{
				if(x[i] == *it)
				{
					in=true;
				}
			}
			i++;
			if(in==false)
			{
				return false;
			}
		};
	return true;
}
/*下面的函数实现属性集x关于函数依赖H的闭包 xF+*/ 
list<char> Set_Closure(string x,AttrSet H)
{
	int i=0;
	string A[size];
	list<char>front,back;
	for(int t=0;t<x.length();t++)
	{
		front.push_back(x[t]);
	}/*把x中所含有的单一属性都压入list中*/
	while( (front!=back) )
	{
		back = front;
		for(int i=0;i<H.count;i++)
		{	list<char> :: iterator it;
			for(it=front.begin();it!=front.end();it++)
			{
				if( ( X_exist(H.X[i],front) )&& not_exist(H.Y[i],front) )
				{
	
					front.push_back(H.Y[i][0]);	/*如果X[I]->Y[I]，把Y[I]给装入属性集*/
					
				}
			}
		}

	};
	return front;
}
AttrSet delete_elem(AttrSet H,int i)
{
	    AttrSet J;
		for(int j=0;j<i;j++)/*两个for循环得到函数集J = {H- {其中一个函数依赖}}*/
		{
			J.X[j] = H.X[j];
			J.Y[j] = H.Y[j];
		}
		for(int j=H.count-1;j>i;j--)
		{
			J.X[j-1] = H.X[j];
			J.Y[j-1] = H.Y[j];
		}
		J.count = H.count-1;
		return J;
}
/*-----------------------------------*/
/*第二步，删除非关键的函数依赖*/
void Step2(AttrSet &H)
{
	AttrSet temp = H;
	for(int i=0;i<H.count;i++)
	{
		AttrSet J;
		J=delete_elem( H, i);
		list<char>result;
		result = Set_Closure(H.X[i],J);

		list<char> :: iterator it;
		for(it=result.begin();it!=result.end();it++)
		{
			
			if((*it)==H.Y[i][0])
			{
				temp.X[i]="";
				temp.Y[i]="";
			}/*表示删除函数依赖i后仍然可以推出 Y[i]，则说明x第i个函数依赖不是关键的 */
		}

	}
	H=temp;

}

bool operator==(list<char>result1,list<char>result2)
{
	list<char> :: iterator it1;
	list<char> :: iterator it2;
	for(it1=result1.begin();it1!=result1.end();it1++)
	{
		bool right = false;
		for(it2=result2.begin();it2!=result2.end();it2++)
		{
			if( (*it1)==(*it2) )
			{
				right =true;
			}
		}
		if(right == false)
		{
			return false;
		}
	}
	return true;
}
/*----------------------------------------*/ 
/*第三步，对于左边可以减少属性元素，即对属性的闭包集无影响的依赖，用少的属性来代替。*/
void Step3(AttrSet &H)
{
	AttrSet H1 =H;
	AttrSet H2 = H;
	for(int i=0;i<H.count;i++)
	{
		if(H.X[i].length()>1)
		{for(int j=0;j<H.X[i].length();j++)
		{
			
			string x =H.X[i];
			AttrSet J  = H;
			J.X[i] = x.replace(j,1,"");//去除H.X[i]中的某一个元素
	
			list<char>result1,result2;
			result1 = Set_Closure(J.X[i],H);
			result2 = Set_Closure(J.X[i],J);
	
			if((result1==result2) &&(result2==result1) )
			{
			
				H.X[i] = x;
				j--;
			}
			
		}
		}
		
	}
		Step2(H);
}
/*--------------------------------*/
/*第四步，对于左边相同的函数依赖，进行整合。*/
void Step4(AttrSet &H)
{
	for(int i=0;i<H.count;i++)
	{
		for(int j=0;j<H.count;j++)
		{
			if( (H.X[i]==H.X[j])&& (i!=j) )
			{
				H.Y[i]=H.Y[i]+H.Y[j];
				H.X[j]=H.Y[j]="";
			}
		}
	}
}

/*--------输出最小覆盖的函数---------*/ 
void print(AttrSet H)
{
	for(int i=0;i<H.count;i++)
	{
		if(H.X[i]=="")
		{
			for(int j=i;j<H.count;j++)
			{
				H.X[j]=H.X[j+1];
				H.Y[j]=H.Y[j+1];
			}
			H.count--;
			i--;
		}
	}

	for(int i=0;i<H.count;i++)
	{
		cout<<H.X[i]<<" -> "<<H.Y[i]<<endl;
	}
}
int main()//测试函数 
{
	AttrSet H,F;
	F.count=4;
	F.X[0]="ABD";	F.X[1]="C";		F.X[2]="AD";	F.X[3]="B";		
	F.Y[0]="AC";	F.Y[1]="BE";	F.Y[2]="BF";	F.Y[3]="E";
	Step1(F,H);//第一步 
	Step2(H);//第二步 
	Step3(H);//第三步 
	Step4(H);//第四步 
	cout<<"函数依赖集的最小覆盖算法(以课本例题为测试用例)："<<endl;
	cout<<"最小函数依赖为："<<endl;
	print( H);//输出最小函数依赖 
	system("pause");
}