indatt.cpp

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

	{//i为条件类中的类号
		int flag=1;//全部元素都是同一类的sign
		int tempsame=-1;//统一的类
		int sameclass=-1;//临时的类
		for(int k=0;k<pUindX[i][0];k++)
		{//第i个条件类中第k个元素，与uindd中的每一类比较
			for(int j=0;j<iClassNumD;j++)
			{//j为决策类中的类号  
				int oneflag=0;
				for(int l=0;l<UindD[j][0];l++)
				{//l为第j个决策类中第几个元素
				//UindD[j][0]和pUindX[i][0]中存储此类元素个数
					if(pUindX[i][k+1]==UindD[j][l+1])
					{//当发现pUindX[i][k+1]属于的类时，退出此决策类中的循环
						oneflag=1;
						break;
					}
				}
				if(oneflag==1)
				{
					sameclass=j;//表明此时pUindX[i][k]属于类j
					break;//退出对整个决策类的循环
				}
			}
			if(tempsame<0)
			{//最开始时赋值为第一个元素属于的决策类的类号
				tempsame=sameclass;
			}
			else
			{
				if(tempsame!=sameclass)
				{//前后两个元素属于不同的类
					flag=0;//说明不属于同一个决策类
					break;//退出对当前类元素的循环，进入下一个条件划分类
				}
			}
		}//end for(int k=0;k<pUindX[i][0];k++)
		if(flag==1)//所有元素属于同类，加入到PosXD中
		{//PosXD中循序存储正域
			for(int j=0;j<pUindX[i][0];j++)
				PosXD->PosSet[PosXD->PosNum+j]=pUindX[i][j+1];
			PosXD->PosNum+=pUindX[i][0];
		}
	}//end for(int i=0;i<iClassNumX;i++)
	for(j=0;j<iRecNum;j++)
	{	delete []UindD[j];
		delete []pUindX[j];
	}
	delete []pUindX;
	delete []UindD;
    return true;
}

//求Unid(X);
void IndAttRed::UindX(int XNum,int* XSet,int& iClassNumX,int**&pUindX)
{
	iClassNumX=0;
	//将第一条记录归入第一类
	pUindX[0][0]=1;
	pUindX[0][1]=0;
	iClassNumX++;//iClassNumX为1
//比较其他的类，对于剩下的每一条记录，如果相等归入同一类，不同就开辟新类
	for(int i=1;i<iRecNum;i++)
	{//第i个记录
		int flag=0;
		int sameClass=0;
		for(int j=0;j<iClassNumX;j++)//比较每一个已经存在的类
		{
			int oneflag=1;
			for(int k=0;k<XNum;k++)//对所有属性
			{//XSet[k]表示属性位置 
				if(pInfo[i][XSet[k]]!=pInfo[pUindX[j][1]][XSet[k]])
				{//最开始时后面的记录和第一条记录属性比较
					oneflag=0;
					break;//有一个属性值不等，说明不属于一类
				}
			}
			if(oneflag==1)//属于一类
			{
				flag=1;
				sameClass=j;//此时记录i属于类j
				break;
			}
		}
		if(flag==1)//同类
		{
			pUindX[sameClass][0]++;//类中的元素数目加一
			pUindX[sameClass][pUindX[sameClass][0]]=i;//增加一个元素
		}
		else//开辟一个新类
		{
			pUindX[iClassNumX][0]=1;
			pUindX[iClassNumX][1]=i;
			iClassNumX++;
		}
	}//endof for
}

//结果放在pPosCD中
void IndAttRed::PosCD()
{	//由于在私有的共有变量，可以这么判断，不然，一定要声明的时候初始化
	//局部指针不能作为函数的指针参数的。
	if((pPosCD=new PosD(iRecNum))==0)
	{
		AfxMessageBox("内存不足!");
		return;
	}
	int CNum=iConNum;
	int *CSet;
	if((CSet=new int[iConNum])==0)
	{
		AfxMessageBox("内存不足!");
		return;
	}
	for(int i=0;i<iConNum;i++)
	{
		CSet[i]=i;
	}	
	if(!PosXD(CNum,CSet,pPosCD))
	{//call PosXD
		AfxMessageBox("内存不足!");
		return;
	}
	delete []CSet;
}


//结果保留在PosD* pCoreCD中
bool IndAttRed::CoreCD()
{
	if((pCoreCD=new PosD(iConNum))==0)//对pCoreCD->PosSet进行了初始化
		return false;
	//求PosCD //	PosCD();
	//求Pos(C-Ci)D,并与pPosCD比较，相同的Ci不是核了。
	int XNum = iConNum-1;
	int *XSet;
	if((XSet=new int[iConNum-1])==0)
		return false;
	for(int i=0;i<iConNum;i++)
	{//对每一个元素进行判断是否是核属性
		for(int j=0;j<i;j++)
			XSet[j]=j;
		for(j=i;j<iConNum-1;j++)
			XSet[j]=j+1;
		PosD* pPosXD;//pPosXD用来记录正域
		if((pPosXD=new PosD(iRecNum))==0)
			return false;
		PosXD(XNum,XSet,pPosXD);
		if(!(pPosXD->compare(pPosCD)))//比较正域的每个对应元素是否相等
			pCoreCD->PosSet[pCoreCD->PosNum++]=i;//不等是，说明是核属性
		pPosXD->DeletePos();//析构
		delete pPosXD;
	}//endof for
	delete []XSet;
    return true;
}
	
//求negcoreCD的Xnum阶幂集，用递归算法
//首先求一阶的，再求2阶的，再求3阶，慢慢地递归调用而已
//当XNum降到2阶时，DemNum也恰好增大到最初XNum的值
//注意：求得的结果不是属性在原集合中的排列位置，其值是相对negCoreCD而言
bool IndAttRed::DemSet(int XNum,int DemNum,int& iDemSetNum,
					   int XCoreNum,int*** pDemSet)
{//XNum：阶数  //结果放在DemSet,iDemSetNum中  // DemNum:阶数，最小为2
////pDemSet:pCoreCD的幂集   iDemSetNum:pCoreCD幂集的元素个数
/*
    二阶时 tempDemSetNum最终为：1/2*CoreNum*(CoreNum-1)
i=0:	tempDemSet[0][0]=0  [0][1]=1  //一个二阶幂
	          [1][0]=0      [1][1]=2//一个二阶幂
			  [2][0]=0      [2][1]=3
i=1:  [XCoreNum-1][0]=1     [..][1]=2
              [..+1][0]=1   [..+1][1]=3
			  [..+2][0]=1   [..+2][1]=4
			  ...
*/
	if(XNum<2)//只计算高于2阶的幂子集 
		return true;
	int tempDemSetNum=0;
	int** tempDemSet=NULL;//存储临时的DemNum阶幂集
	if((tempDemSet=new int*[iDemSetNum*XCoreNum])==0)
		return false;
	for(int i=0;i<iDemSetNum*XCoreNum;i++)
		if((tempDemSet[i]=new int[iConNum])==0)
			return false;
	for(i=0;i<iDemSetNum;i++)
	{
		for(int j=(*pDemSet)[i][DemNum-2]+1;j<XCoreNum;j++)
		{
			for(int k=0;k<DemNum-1;k++)
				tempDemSet[tempDemSetNum][k]=(*pDemSet)[i][k]; 
			tempDemSet[tempDemSetNum++][DemNum-1]=j;
		}
	}
//	for(i=0;i<tempDemSetNum;i++)
//		delete [](*pDemSet)[i];
//	delete [](*pDemSet);
//	(*pDemSet)=tempDemSet;
	if(tempDemSetNum>max2)
	{
		for(i=0;i<max2;i++)
    		delete [](*pDemSet)[i];
        delete [](*pDemSet);
		max2=tempDemSetNum;
		if(((*pDemSet)=new int*[tempDemSetNum])==0)//init the DemSet阶
		     return false;
     	for(i=0;i<tempDemSetNum;i++)
	     	if(((*pDemSet)[i]=new int[iConNum])==0)
		     	return false;
	}
	for(i=0;i<tempDemSetNum;i++)
		for(int j=0;j<DemNum;j++)
			(*pDemSet)[i][j]=tempDemSet[i][j];
	for(i=0;i<iDemSetNum*XCoreNum;i++)
		delete[] tempDemSet[i];
	delete tempDemSet;
	iDemSetNum=tempDemSetNum;
	//递归调用
	if(!DemSet(XNum-1,DemNum+1,iDemSetNum,XCoreNum,pDemSet))
		return false;
    return true;
}
//求CoreCD的反，结果放在negCoreCD中
void IndAttRed::negCoreCD()
{
	if((pnegCoreCD=new PosD(iConNum))==0)//对pnegCoreCD初始化
	{
		AfxMessageBox("内存不足!");
		return;
	}
	for(int i=0;i<iConNum;i++)
	{
		int flag=0;
		for(int j=0;j<pCoreCD->PosNum;j++)
		{
			if(pCoreCD->PosSet[j]==i)
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{//不包含在pCoreCD中，要加入pnegCoreCD中
			pnegCoreCD->PosSet[pnegCoreCD->PosNum++]=i;
		}
	}//endof for
}

//计算 Card(U|X)
int IndAttRed::CardUX(PosD *SetX)
{
	int XNum=SetX->PosNum;
	int *XSet;
	if((XSet=new int[iConNum])==0)
		return -1;
	for(int i=0;i<XNum;i++)
		XSet[i]=SetX->PosSet[i];
	int iClassNumX=0;
	int **pUindX;
	if((pUindX=new int*[iRecNum+1])==0)
		return -1;
	for(i=0;i<iRecNum+1;i++)
		if((pUindX[i]=new int[iRecNum+1])==0)
			return -1;
	UindX(XNum,XSet,iClassNumX,pUindX);
	for(i=0;i<iRecNum+1;i++)
		delete []pUindX[i];
	if(pUindX)
		delete []pUindX;
	delete []XSet;
	return iClassNumX;
}

//计算C的d最小属性约简,结果放入mRedCD中 
bool IndAttRed::mRedCD()
{
	CoreCD();//得到C的D正域pPosc(D)
	negCoreCD();	//求posX(D)
	int XNum=pCoreCD->PosNum;// 得到核属性数目
	int *XSet;
	if((XSet=new int[XNum+1])==0)//核属性为空时,XNum为0.故取XNum+1
	{
		AfxMessageBox("内存不足!");
		return false;
	}
	for(int i=0;i<XNum;i++)
		XSet[i]=pCoreCD->PosSet[i];//核属性赋值
	PosD* PosCoreD;
	if((PosCoreD=new PosD(iRecNum))==0)//D的C正域
		return false;
	PosXD(XNum,XSet,PosCoreD);//得到核属性的正域PosCoreD
	delete []XSet;
	max1=iConNum*iConNum;
	if((pDemSet=new int*[MAX])==0)//init the DemSet阶
		return false;
	for(i=0;i<MAX;i++)
		if((pDemSet[i]=new int[iConNum])==0)
			return false;
	//求C的D正域:pPosc(D),在CoreCD中已经求得。
	if((pmRedCD=new PosD(iConNum))==0)//存储最终结果
		return false;
	if((XNum>0)&&(PosCoreD->compare(pPosCD)))//pPosCD为
	//核属性的数目不为零并且其正域是等于C的正域
	{//yes  用C的对pmRedCD赋值
		pmRedCD->PosNum=pCoreCD->PosNum;
		for(int i=0;i<pmRedCD->PosNum;i++)
			pmRedCD->PosSet[i]=pCoreCD->PosSet[i];
		PosCoreD->DeletePos();
		delete PosCoreD;
		return true;
	}
	//2.3正域不等时
	//temp variable
	PosD* tempmRedCD;//最终约简结果
	if((tempmRedCD=new PosD(iRecNum))==0)//iRecNum:记录数
		return false;
	PosD* tempPosD;
	if((tempPosD=new PosD(iRecNum))==0)
		return false;
	for(i=1;i<=pnegCoreCD->PosNum;i++)
	{//i表示补集的阶数，分别对从1到补集元素总数的阶数求
		int flag=0;//mRedCD!=Z;
		//2.4
		iDemSetNum=pnegCoreCD->PosNum;//iDemSetNum:pCoreCD幂集的元素个数  补集的元素数目
		for(int j=0;j<iDemSetNum;j++)//一阶？
			pDemSet[j][0]=j;//
		if(!DemSet(i,2,iDemSetNum,pnegCoreCD->PosNum,&pDemSet))
			return false;//求i阶幂集
//	bool IndAttRed::DemSet(int XNum,int DemNum,int& iDemSetNum,int XCoreNum,int*** pDemSet)
		//2.5//求negcoreCD的Xnum阶幂集，用递归算法  结果放在DemSet,iDemSetNum中
        int tempNum1;
		for(j=0;j<iDemSetNum;j++)
		{//j每循环一此，表示尝试过一种i阶幂子集。循环完时，表示Y为空
	       tempNum1=0;
			int *tempSet;
			if((tempSet=new int[iConNum])==0)
				return false;
			if(pCoreCD->PosNum>0)
	        	for(int k=0;k<pCoreCD->PosNum;k++)//将已有正域中的元素加入
			    	tempSet[tempNum1++]=pCoreCD->PosSet[k];
			for(int k=0;k<i;k++)//i为幂，一次可以包含的元素个数//然后将y加入（y见课本定义）
				tempSet[tempNum1++]=pnegCoreCD->PosSet[pDemSet[j][k]];
			//tempNum1表示A中的元素个数 最开始为0,然后为1  tempSet表示A
			if(!PosXD(tempNum1,tempSet,tempPosD))
				return false;//tempPosD:求PosA(D)
			if(tempPosD->compare(pPosCD))//看正域是否相等
			{//ok POSA(D)=POSC(D)
				if(flag==0)
				{//Z=A;flag=1  Z:tempmRedCD其中PosNum表示属性个数
					tempmRedCD->PosNum=tempNum1;//从零开始计数
					for(int m=0;m<tempmRedCD->PosNum;m++)
						tempmRedCD->PosSet[m]=tempSet[m];
					flag=1;
				}
				else
				{ 
					PosD *tempPosD1;//创建临时节点,存储临时约简集
					if((tempPosD1=new PosD(tempNum1))==0)
                 		return false;
					//tempPosD1->PosNum=;
                    tempPosD1->PosNum=tempNum1;
					for(int m=0;m<tempPosD1->PosNum;m++)
						tempPosD1->PosSet[m]=tempSet[m];
					int cardux1,cardux2;
					cardux1=CardUX(tempmRedCD);
					cardux2=CardUX(tempPosD1);
					if(cardux1>cardux2)
					{//if(card(U|Z)>card(U|A)) then Z＝A
						tempmRedCD->PosNum=tempNum1;
						for(int m=0;m<tempmRedCD->PosNum;i++)
							tempmRedCD->PosSet[m]=tempSet[m];
					}
				}
			}//endof if 正域相等
			delete []tempSet;
		}//endof 2.5
		//2.8
		if(flag==1)//pmRedCD存储最终结果
		{//判断if(flag=1) 则mredD(C)约简为Z。结束算法
//			pmRedCD=tempPosD;  
			pmRedCD->PosNum=tempmRedCD->PosNum;
			for(int i=0;i<pmRedCD->PosNum;i++)
				pmRedCD->PosSet[i]=tempmRedCD->PosSet[i];
			return true;//算法结束
		}
	}//endof for 2.3
	tempmRedCD->DeletePos();
	delete tempmRedCD;
	tempPosD->DeletePos();
	delete tempPosD;
    return true;
}//endof function

void IndAttRed::FreeContent()
{
	for(int i=0;i<MAX;i++)
		delete []pDemSet[i];
	delete []pDemSet;

	for(i=0;i<ipriRecNum;i++)
		delete []pIntTable[i];
	delete []pIntTable;

	for (i=0;i<iRecNum;i++)
		delete []pInfo[i];
	delete []pInfo;

	for(i=0;i<iConNum+1;i++)
	{
		delete []pDataType[i];
		delete []pAttName[i];
	}
	delete []pDataType;
	delete []pAttName;

	delete []cStyle;

	pCoreCD->DeletePos();
	delete pCoreCD;

	pmRedCD->DeletePos();
	delete pmRedCD;

	pnegCoreCD->DeletePos();
	delete pnegCoreCD;

	pPosCD->DeletePos();
	delete pPosCD;

	//free struWCutRecord
	struct WCutRecord* pHead=NULL;
	while(struWCutRecord != NULL)
	{
		pHead = struWCutRecord->next;
		for(int i = 0;i < struWCutRecord->iCuts;i++)
			delete[] struWCutRecord->cpCut[i];
		delete[] struWCutRecord->cpCut;
		delete struWCutRecord;
		struWCutRecord = pHead;
	}

}