valreductionthree.cpp

某个实验事编写粗糙集智能信息处理的程序

				find=FALSE;
			}
		if(att_num>0)      
		{//存在不包含核属性的属性组合
			int ** newarray=new int *[att_num];
			att_num=0;
    		for(i=0;i<element;i++)//决策矩阵的第i行
	    		if(array[i][0]>1)
				{
					find=FALSE;
			    	for(j=1;j<=array[i][0];j++)
					{
                        for(k=1;k<=redu_num;k++)
					    	if(array[i][j]==reductset[k])
							{
					    		find=TRUE;
						    	break;
							}
				    	if(find==TRUE)
					    	break;
					}
				    if(find==FALSE)
					{//此行为不包含核属性的属性组合 newarray中存储非核属性行
     			    	newarray[att_num]=new int[array[i][0]+1];//att_num初始为0
			     		for(k=0;k<array[i][0]+1;k++)
				        		newarray[att_num][k]=array[i][k]; 
			   		att_num++;
					}
				}
	    	for(k=0;k<element;k++)
				delete []array[k];
			if(array!=NULL) delete[] array;
			element=att_num;//元素数目为不包含核属性的行的数目
	    	array=newarray;
		}//得到不包含核属性属性组合列表
		else
		{//if(att_num==0)不存在不包括核属性的行
			reduct_att_num=1; //reduct_att_num:有几组值约简结果
			result=new int * [reduct_att_num];
			result[0]=new int[redu_num+1];
			result[0][0]=redu_num;
			for(i=0;i<redu_num;i++)
				result[0][i+1]=reductset[i+1];
			selectsort(result[0]);//用选择法对约简后的属性重新排列
			return;
		}//只有核属性,返回
	}
	if(element>1)//非核行数大于一
		DNF=CNFtoDNF(element,item_num);//和之积转化为积之和,积之和表达式的项数:item_num
	else if(element==1)
	{
		DNF=new int ** [array[0][0]];//array[0][0] 为核属性个数加1
		for(i=0;i<array[0][0];i++)
		{//将这一行属性变为一列 ,每列只包含两个元素;1和一个非核属性
			DNF[i]=new int * [2];
			for(k=0;k<2;k++)
				DNF[i][k]=new int[1];        
			DNF[i][0][0]=1;
			DNF[i][1][0]=(int)array[0][i+1];
		}
		item_num=array[0][0];
	}
	find_best_reduct(DNF,item_num); //输出规则
	if(DNF!=NULL)
	{//释放内存
		int number;
		for(i=0;i<item_num;i++)
		{
			number=DNF[i][0][0]+1;                   //加1是因为第一个值是计数器
			for(j=0;j<number;j++)
				delete []DNF[i][j];
			delete []DNF[i];
		}
		delete []DNF;
	}
}

int *** ValReductionThree::CNFtoDNF(int element,int& item_num)
{//和之积转化为积之和  element:积的个数;item_num为得到的积之和表达式的项数
	int i,j,k,t;                                          //循环变量
	int sum=0;                                            //属性相同的个数
	int * att=NULL;                                       //可删除的属性组
	int del=0;                                            //可删除的属性组个数
	char * newstr=NULL;                                        //由两条属性组成的新字符串
	int count=0;
	int att_num=0;
	int diff_num=0;
	int length;
	int *** DNF=NULL;
	bool find=FALSE;
	att=new int[element+1];
	if(att==NULL)
		return NULL;
	selectsort(array,element);//用选择法排序找出属性数目最小者  
	for(k=0;k<element-1;k++)
	    for(i=k+1;i<element;i++)
	    	if(array[k][0]<array[i][0])//前面行(k)的个数小于后面行(i)的个数
			{// 看是否前面的属性集包含于后面的属性集?yes:删除后面行i,no:保留
				sum=0;
		        for(j=1;j<=array[k][0];j++)
				{
					find=FALSE;
					for(t=1;t<=array[i][0];t++)
						if(array[k][j]==array[i][t])
						{
							sum++;
							find=TRUE;//k行中一个样例包含于i行
							break;
						}
					if(find==FALSE)
						break;//退出,进行下个i行
				}
		    	if(sum==array[k][0])
				{//包含,删除后面的行i
					find=FALSE;
					for(j=1;j<=del;j++)//del:可删除的属性组个数
						if(att[j]==i)//看i是否已经删除
						{
							find=TRUE;//已经删除了
							break;
						}
					if(find==FALSE)
					{//未删除,将i加入删除行列表
				    	att[++del]=i;//下标从1开始
				    	att[0]=del;
					}
				}
			}
	if(del>0)//删除的数目大于0
	{//保留非删除行
    	int ** newarray=new int *[element-del];
    	for(i=0;i<element;i++)
		{//先找到未被删除的行,再拷贝
			find=FALSE;
	    	for(j=1;j<=del;j++)
				if(i==att[j])
				{
		            find=TRUE;
					break;
				}
			if(find==FALSE)
			{
			   	newarray[count]=new int[array[i][0]+1];//count初始为0
			   	for(k=0;k<array[i][0]+1;k++)
			       	newarray[count][k]=array[i][k];
			   	count++;
			}
		}
		delete []array;
		array=newarray;
	}
	delete []att;
	element=element-del;//得到剩下的新的行数

   	struct intTostr
	{//int到str转换结构
    	char ** strarray;//字符串存储此行各个属性
		int item_num;//一行的属性数目
	};

	if(element>1)
	{
		intTostr * transfer=new intTostr[element];
		for(i=0;i<element;i++)
		{//对每个析取式
			transfer[i].item_num=array[i][0];
			transfer[i].strarray=new char * [array[i][0]];
			for(j=0;j<array[i][0];j++)
			{//将每个析取式用字符串表示
				transfer[i].strarray[j]=new char[2];
				transfer[i].strarray[j][0]=(char)(array[i][j+1]+1);//为什么最后要加1?
				transfer[i].strarray[j][1]='\0';
            }
		}
		while(element>1)
		{
	    	count=0;
			char ** stratt=new char * [transfer[0].item_num*transfer[1].item_num];
			//第一.二行元素个数之和
			for(j=0;j<transfer[0].item_num;j++)
				for(k=0;k<transfer[1].item_num;k++)
				{//charin(str1,str2):判断str1中的字符是否完全属于str2
					if(strcmp(transfer[0].strarray[j],transfer[1].strarray[k])==0||
					   charin(transfer[0].strarray[j],transfer[1].strarray[k])==TRUE||
					   charin(transfer[1].strarray[k],transfer[0].strarray[j])==TRUE)
					{ 
						if(strlen(transfer[0].strarray[j])<strlen(transfer[1].strarray[k]))
						{//0行j列元素长度小于1行k列字符长度,则以1行k列长度+1开辟单元,将1行k列元素拷贝入stratt中
							stratt[count]=new char[strlen(transfer[1].strarray[k])+1];
							strcpy(stratt[count++],transfer[1].strarray[k]);
						}
						else
						{//反之,将0行j列长度大于1行k列.则将0行j列元素拷贝到statt中(拷贝字符串长的)
							stratt[count]=new char[strlen(transfer[0].strarray[j])+1];
							strcpy(stratt[count++],transfer[0].strarray[j]);
						}
					}
					else
					{//将0行j列和1行k列合并加入stratt中
						newstr=new char[strlen(transfer[0].strarray[j])+strlen(transfer[1].strarray[k])+1];
						strcpy(newstr,transfer[0].strarray[j]);
						strcat(newstr,transfer[1].strarray[k]);
						stratt[count]=new char[strlen(transfer[0].strarray[j])+strlen(transfer[1].strarray[k])+1];
						strcpy(stratt[count++],newstr);
						delete []newstr;
					}
				}
			selectsort(stratt,count);//用选择法排序找出属性数目最小者
			int * over=new int[count];
			sum=0;
			for(j=0;j<count-1;j++)
				for(k=j+1;k<count;k++)
			    	if(strstr(stratt[k],stratt[j])!=NULL)
					{//strstr:返回stratt[j]在stratt中的中出现位置的指针,假如stratt不出现,返回为NULL
						find=FALSE;//j项在k中出现
						for(i=0;i<sum;i++)
							if(over[i]==k)
							{//看k字符串是否已经出现在over中
								find=TRUE;
								break;
							}
						if(find==FALSE)//否则加入k到over中
				        	over[sum++]=k;
					}
			if(sum)
			{
		    	char ** replace=new char * [count-sum];
		    	diff_num=0;
				att_num=0;
		    	for(j=0;j<count;j++)
				{//把非over中的字符串加入到replace中
			    	for(k=0;k<sum;k++)
				        if(j!=over[k])
						{ 
					    	diff_num++;
					    	if(diff_num==sum)
							{
					        	replace[att_num]=new char[strlen(stratt[j])+1];
					        	strcpy(replace[att_num],stratt[j]);
					           	att_num++;
							}
						}
						else 
							break;
			    	diff_num=0;
				}
				for(j=0;j<transfer[0].item_num*transfer[1].item_num;j++)
					delete []stratt[j];
		    	delete []stratt;
		    	stratt=replace;//得到相互之间互不包含的字符串
			}
		    delete []over;
			/* 修改原strarray中的第一项*/
			intTostr * new_transfer=new intTostr[element-1];
			/* 	struct intTostr
	            {//int到str转换结构
				char ** strarray;//字符串存储此行各个属性
				int item_num;//一行的属性数目
                };   */
			if(att_num==0)
				att_num=count;
			new_transfer[0].item_num=att_num;
			new_transfer[0].strarray=new char * [att_num];
			for(j=0;j<att_num;j++)
			{//得到合并0,1行后的新的0行
				new_transfer[0].strarray[j]=new char[strlen(stratt[j])+1];
				strcpy(new_transfer[0].strarray[j],stratt[j]);
			}
			for(j=1;j<element-1;j++)
			{//原先后面的行前移得到新的1到element-1行
                new_transfer[j].strarray=new char * [transfer[j+1].item_num];
				new_transfer[j].item_num=transfer[j+1].item_num;
				for(k=0;k<transfer[j+1].item_num;k++)
				{
					new_transfer[j].strarray[k]=new char[strlen(transfer[j+1].strarray[k])+1];
					strcpy(new_transfer[j].strarray[k],transfer[j+1].strarray[k]);
				}
			}
			for(j=0;j<element;j++)
			{//消除原先行
				for(k=0;k<transfer[j].item_num;k++)
         			delete []transfer[j].strarray[k];
				delete []transfer[j].strarray;
			}
			delete []transfer;
			transfer=new_transfer;//新行
			element--;//行数减一
			for(j=0;j<count-sum;j++)
				delete []stratt[j];
			delete []stratt;
		}//end while(element>1)
        //得到行数为一
		DNF=new int ** [transfer[0].item_num];
		for(i=0;i<transfer[0].item_num;i++)
		{
			length=strlen(transfer[0].strarray[i]);
			DNF[i]=new int * [length+1];
			DNF[i][0]=new int[1];
			DNF[i][0][0]=length;  //属性组合的属性个数
			for(j=1;j<=length;j++)
			{
                DNF[i][j]=new int[1];
				DNF[i][j][0]=(int)transfer[0].strarray[i][j-1]-1;
			}
		}
		item_num=transfer[0].item_num;//合取式的个数
		for(i=0;i<element;i++)
		{
			for(j=0;j<transfer[i].item_num;j++)
				delete []transfer[i].strarray[j];
			delete []transfer[i].strarray;
		}
		delete []transfer;
		return(DNF);
	}
	else
	{//if(element==1)//即此行的都是约简结果
        intTostr * transfer=new intTostr[element];
		transfer[0].item_num=array[0][0];
		transfer[0].strarray=new char * [array[0][0]];
		for(j=0;j<array[0][0];j++)
		{
			transfer[0].strarray[j]=new char[2];
			transfer[0].strarray[j][0]=(char)(array[0][j+1]+1);//为什么加一???
			transfer[0].strarray[j][1]='\0';
        }
		DNF=new int ** [transfer[0].item_num];
		for(i=0;i<transfer[0].item_num;i++)
		{//给DNF赋值
			length=strlen(transfer[0].strarray[i]);
			DNF[i]=new int * [length+1];
			DNF[i][0]=new int[1];
			DNF[i][0][0]=length;                      //属性组合的属性个数
			for(j=1;j<=length;j++)
			{
                DNF[i][j]=new int[1];
				DNF[i][j][0]=(int)transfer[0].strarray[i][j-1]-1;
			}
		}
		item_num=transfer[0].item_num;
		for(i=0;i<element;i++)
		{//析构
			for(j=0;j<transfer[i].item_num;j++)
				delete []transfer[i].strarray[j];
			delete []transfer[i].strarray;
		}
		delete []transfer;
		return(DNF);
	}//end else
}

void ValReductionThree::find_best_reduct(int *** DNF,int& item_num)
{//得到规则
	if(item_num==0)
		return;
	int i,j,k;                                     //循环变量
    int att_num;                                   //属性数目
    int * best_att=NULL;                           //去除核属性后的最佳约简所在的属性集合
    best_att=get_best_att(DNF,item_num);//get_best_att:得到最好的属性组合
	reduct_att_num=best_att[0];//此时的属性数目
	result=new int * [best_att[0]];
    for(i=0;i<best_att[0];i++)
	{//对每一个组合???
    	att_num=DNF[best_att[i+1]][0][0];
    	int * best_redu=new int[reductset[0]+att_num+1];//reductset存储核属性,核属性的个数为redu_num
    	best_redu[0]=reductset[0]+att_num;//包含的属性数目
    	for(j=0;j<reductset[0];j++)//拷贝核属性
            best_redu[j+1]=reductset[j+1];
    	for(j=reductset[0]+1;j<reductset[0]+att_num+1;j++)
		{//拷贝非核属性
        	k=j-reductset[0];
    		best_redu[j]=DNF[best_att[i+1]][k][0];
		}
    	selectsort(best_redu);	//用选择法对约简后的属性重新排列
		result[i]=new int[reductset[0]+att_num+1];//result:int **
		for(j=0;j<reductset[0]+att_num+1;j++)
	    	result[i][j]=best_redu[j];  //值约简第i个结果
		delete []best_redu;