utility.cpp

来自「某个实验事编写粗糙集智能信息处理的程序」· C++ 代码 · 共 211 行

// Utility.cpp: implementation of the CUtility class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "IntSet.h"
//#include "KnowDis.h"
#include "Utility.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CUtility::CUtility()
{
}

CUtility::~CUtility()
{
}

//typedef unsigned short      WORD

int CUtility::QuickSortPass(WORD* pData,int start,int end)
{//快速排序法对pData数组中s下标为tart和end之间的数进行一趟排序,返回得到的中间的坐标
	//坐标的左边的数比它小;右边的数比他大
	int s=start;
	int e=end;
	int pivot=pData[start];
	while(s<e)
	{
		while(s<e&&pData[e]>=pivot) e=e-1;
		pData[s]=pData[e];
		while(s<e&&pData[s]<=pivot) s=s+1;
		pData[e]=pData[s];
	}
	pData[s]=pivot;
	return s;
}

//quick sort 
void CUtility::QuickSort(WORD* pData,int start,int end)
{//整个快速排序 对pData数组中s下标为tart和end之间的数进行
	int p;
	if(start<end)
	{
       p=QuickSortPass(pData,start,end);
	   QuickSort(pData,start,p-1);
	   QuickSort(pData,p+1,end);
	   }
}

WORD* CUtility::RidSortRep(WORD* pData,int cIn,int &cRe)
{//对对pData数组中下标为0和cln之间的数进行排序,排序方式比较特别.返回排序后的数组指针
	//顺序加入,相邻两个数不相同
	int i;
	WORD temp,*pNewData,*pTempData;
	pTempData=new WORD[cIn];
	pTempData[0]=temp=pData[0];
	cRe=1;
	for(i=1;i<cIn;i++)
	{
		if(temp==pData[i]) continue;
		pTempData[cRe]=temp=pData[i];
		cRe++;
    }    
    pNewData=new WORD[cRe];
	for(i=0;i<cRe;i++)
	{
		pNewData[i]=pTempData[i];
	}
	delete[] pTempData;
	return pNewData;
}

//get a array to keep cut value
//input:  pData after soring and without repetitie value
//        cData is number of data
//output: cCut is number of cut
float*  CUtility::GetCut(WORD* pData, int cData,int& cCut)
{//pData为不同的属性值的集合.cData为集合中元素个数.cCut为计算得到的断点个数,返回断点集
	float* pCut;
	int i;
	if(cData==1)
	{//此时断点为数本身
		pCut=new float[1];
		pCut[0]=pData[0];
		cCut=1;
		return pCut;
	}
	cCut=cData-1;
	pCut=new float[cCut];
	for(i=0;i<cData-1;i++)
	{ 
		pCut[i]=float((pData[i]+pData[i+1])/2.0);
	}
	return pCut;
}


//following function reallots the memory of setOfSet after the redundant is removed 
//return value: the point to newly alloted memory
//setOfSet:the old array of set
//cSet: the size of old array
//newcSet:the size of new array
SETSLOT* CUtility::ChangeMemory(SETSLOT* setOfSet,int cSet,int newcSet)
{//返回消除了冗余的新的集合newSet
	int i;
	SETSLOT* newSet=new SETSLOT[newcSet];
/*
struct SETSLOT
{
	bool fValid;//非冗余的值
	CIntSet theSet;
};*/
    int j=0;
	for(i=0;i<cSet;i++)
	{
        if(setOfSet[i].fValid) //只拷贝非冗余的集合
		{
			newSet[j].fValid=setOfSet[i].fValid;
            newSet[j].theSet=setOfSet[i].theSet;
			j++;
		}
	}
	
	delete[] setOfSet;
	return newSet;
}


//the CutSet function perform the actual reduction
//setOfSet:the array of sets(one set present a disjunction or a conjunction)
//cSet: the size of the array
//newcSet:the new size
void CUtility::CutSet(SETSLOT* setOfSet,int cSet, int& newcSet)
{//得到标注了冗余的断点集合.newsSet为不冗余的子集数目
	int i,j;
	newcSet=cSet;
	for(i=0;i<cSet;i++)
	{
		if(!setOfSet[i].fValid) continue;
		for(j=i+1;j<cSet;j++)
		{//看是否存在集合包含的情况,有就将冗余集合的fValid设为false
			if(setOfSet[j].fValid && setOfSet[j].theSet.IsSubSetOf(setOfSet[i].theSet))
			{//如果存在大集合包含小集合,则大集合为冗余
			     setOfSet[i].fValid=false;
				 newcSet--;
				 break;
			}
			else if(setOfSet[j].fValid && setOfSet[i].theSet.IsSubSetOf(setOfSet[j].theSet))
			{
				setOfSet[j].fValid=false;
				newcSet--;
			}
		}
	}	//end 
}

//this is to simply 或与式到与或式
//setOfSet: sets stand for 或与式
//cSetOfSet:或与式的项数
//cOld:
SETSLOT* CUtility::SimpLogic(SETSLOT*setOfSet,int cSetOfSet,int&cOld)
{ //或与式到与或式转化
	int i,j,k,cNew,m,n,c;
	SETSLOT* oldSet,*newSet;
	cOld=setOfSet[0].theSet.NumOfEle();//第一个与或式的项数
    oldSet=new SETSLOT[cOld];
	for(i=0;i<cOld;i++)
	{//得到第一个或与式中的或式集合
		oldSet[i].fValid=true;
		oldSet[i].theSet.Insert(setOfSet[0].theSet.DropOne());//每个元素
	}
	
    for(i=1;i<cSetOfSet;i++)
	{//对后面的或与式
		k=setOfSet[i].theSet.NumOfEle();
		 cNew=k*cOld;
		 newSet=new SETSLOT[cNew];
		 for(m=0;m<k;m++)
		 {
			 for(n=0;n<cOld;n++)
			 {
				 newSet[n+m*cOld].fValid=oldSet[n].fValid;
				 newSet[n+m*cOld].theSet=oldSet[n].theSet;
			 }
		 }
		 delete[] oldSet;
		 for(m=0;m<k;m++)
		 {//将后面或式中每个元素插入到每个newSet中
			 c=setOfSet[i].theSet.DropOne();
			 for(n=0;n<cOld;n++)
			 {
				 newSet[n+m*cOld].theSet.Insert(c);
			 }
		 }
         
		 CutSet(newSet,cNew,j);//标注neSet中的冗余
		 cOld=j;//j为不冗余的子集数目
		 oldSet=ChangeMemory(newSet,cNew,cOld);//返回消除了冗余的新的集合
	}
	delete[]  setOfSet;
	return oldSet;
}