disone.cpp

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

// DisOneDoc1.cpp: implementation of the CDisOneDoc class.
//
//////////////////////////////////////////////////////////////////////
 
#include "stdafx.h"
#include "../RSet.h"
#include "fstream.h"
#include "DisOne.h"
#include "String.h"
 
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CDisOne::CDisOne()
{		
	att_val=NULL;
	interval=NULL;
	formulas=NULL;
	matrix=NULL;
	cut=NULL;
	NewTable=NULL;
	pAttName=NULL;
	pDataType=NULL;
	pStringTable=NULL;
    pStringTableResult=NULL; 
    pStrResult=NULL; 
    pNonStringTable=NULL; 
    strCuts=NULL; 
}

CDisOne::~CDisOne()
{
	int i;                                       //循环变量
	if(interval!=NULL)
	{
    	for(i=0;i<iNonStrAttNum;i++)
 	    	delete []interval[i];
    	delete []interval;
	} 
	if(att_val!=NULL)
	{
    	for(i=0;i<iNonStrAttNum;i++)
    		delete []att_val[i];
    	delete []att_val;
	}

	if(cut!=NULL)
	{
    	for(i=0;i<iNonStrAttNum;i++)
	    	delete []cut[i];
    	delete []cut;
	}
	if(NewTable!=NULL)
	{
    	for(i=0;i<iRecordNum;i++)
	    	delete []NewTable[i];
    	delete []NewTable;
	}
	if(pAttName)
	{
		for(i=0;i<iAttNum+1;i++)
			delete []pAttName[i];
		delete[] pAttName;
	}

	if(pDataType)
	{
		for(i=0;i<iAttNum+1;i++)
			delete []pDataType[i];
		delete[] pDataType;
	}
	if(pStringTable)
	{
		for(i=0;i<iRecordNum;i++)
		{
			for(int j=0;j<iStrAttNum;j++)
				delete[] pStringTable[i][j];
			delete[] pStringTable[i];
		}
		delete[] pStringTable;
	}
    if(pStringTableResult!=NULL){ 
        for(i=0;i<iRecordNum;i++) 
            delete[] pStringTableResult[i]; 
        delete[] pStringTableResult; 
        }   
    if(pStrResult){ 
        for(i=0;i<iRecordNum;i++){ 
            for(int j=0;j<iStrAttNum;j++) 
                delete[] pStrResult[i][j]; 
            delete[] pStrResult[i]; 
        } 
        delete[] pStrResult; 
    } 
    if(pNonStringTable){ 
        for(i=0;i<iRecordNum;i++) 
            delete[] pNonStringTable[i]; 
        delete[] pNonStringTable; 
    } 
}

BOOL CDisOne::OnDisOne()
{   //具体执行主函数
	int matrix_row;                       //矩阵的行数
	int matrix_col;                       //矩阵的列数
	if(iNonStrAttNum!=0)
	{
		if(get_att_val()==-2)
			return FALSE;
		matrix_row=logic();
		matrix_col=init_matrix(matrix_row);
		findcuts(matrix_row,matrix_col);
	}
	make_new_table();
	if(iStrAttNum!=0) 
      doString(); 
	return TRUE;
}
 
int CDisOne::get_att_val()
{ //保存决策表中所有属性出现的值att_val中.并产生候选断点，保存在interval数组中
//其中att_val[i][j]表示第i个属性的第j个出现的值，att_val[i][0]保存第i个属性出现不同值的个数
//success:return 1; else return -2
	int i,j;                     //循环变量
	int n;                       //记录数
	att_val=new float * [iNonStrAttNum];	
	float * val=NULL;
	if((val=new float[iRecordNum+1])==0)
	{
		AfxMessageBox("Out of Memory!",MB_OK|MB_ICONSTOP);
		return -2;
	}
	for(i=0;i<iNonStrAttNum;i++)
	{//得到每个数值属性不同值.保存在att_val[][]中
        n=get_rec_num(i,val); //返回决策表中第i个属性中出现的不同值的个数,
		//把出现的属性值保存在数组val中，val[0]保存值的个数
    	try
		{
			att_val[i]=new float[n+1];
		}
		catch(CMemoryException * e)
		{
			::MessageBeep(MB_ICONHAND);
			AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
			e->Delete();
			return -2;
		}
		for(j=0;j<n+1;j++)
			att_val[i][j]=val[j];//
	}
	selectsort(att_val);//得到每个属性的从小到大的顺序排序
	interval=new float *[iNonStrAttNum];
	for(i=0;i<iNonStrAttNum;i++)
	{//求得每个属性的候选断点,存储在数组interval中
		interval[i]=new float[(int)att_val[i][0]];
			interval[i][0]=att_val[i][0]-1;//断点个数
		for(j=1;j<att_val[i][0];j++)
			interval[i][j]=(att_val[i][j]+att_val[i][j+1])/2;
	}
	delete[] val;
	return 1;
}

int CDisOne::get_rec_num(int att, float *val)
{//返回决策表中第att个属性中出现的不同值的个数，并把出现的属性值保存在数组val中，
	//val[0]保存了值的个数
    int i,j;             //循环变量
	bool find=FALSE;
	val[0]=0;
	for(i=0;i<iRecordNum;i++)
	{
		for(j=0;j<val[0];j++)
			if(pNonStringTable[i][att]==val[j+1])
			{//i样例att属性是否为重复属性值
				find=TRUE;
				break;
			}
		if(find==FALSE)
		{
			val[0]++;//不同属性值数加一
			val[(int)val[0]]=pNonStringTable[i][att];//加入
		}
		find=FALSE;
	}
	return (int)val[0];
}

void CDisOne::selectsort(float **val)
{//对数组val中的值按从小到大的顺序进行排序
	int i,j,k;                 //循环变量
	int mini=0;
	float middle_val;
	for(i=0;i<iNonStrAttNum;i++)//对每个属性i,都得到其排序
		for(j=1;j<(int)val[i][0];j++)
		{//不同值的序号j,和后面的值比较,找到最小的值
			mini=j;
			for(k=j+1;k<(int)val[i][0]+1;k++)
				if(val[i][k]<val[i][mini])
					mini=k;
			if(mini!=j)
			{//交换j和mini
				middle_val=val[i][j];
				val[i][j]=val[i][mini];
				val[i][mini]=middle_val;
			}
		}
}

int CDisOne::logic()
{  //返回决策表中决策属性不同的记录对的个数n，并生成数组formalas，
//formalas[i][j][k]表示第i个记录对在第j个属性上的第k个候选断点，formalas[i][j][0]
//表示第i个记录对在第j个属性上候选断点的个数 failed:return -1;else return count
    int i,j,k,m;          //循环变量
	int count=0;   
    int recnum1,recnum2,distance;
	float val1,val2;
	for(i=0;i<iRecordNum-1;i++)
		for(j=i+1;j<iRecordNum;j++)
			if(pNonStringTable[i][iNonStrAttNum]!=pNonStringTable[j][iNonStrAttNum])
				count++;//统计决策不同的样例对数目
    	try
		{
			formulas=new float ** [count];
		}
		catch(CMemoryException * e)
		{
			::MessageBeep(MB_ICONHAND);
			AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
			e->Delete();
			return -1;
		}
	count=0;
	for(i=0;i<iRecordNum-1;i++)
		for(j=i+1;j<iRecordNum;j++)
			if(pNonStringTable[i][iNonStrAttNum]!=pNonStringTable[j][iNonStrAttNum])
			{//i,j样例决策不同,对每个属性,判断i,j的属性距离,从而得到断点
            	try
				{
					formulas[count]=new float * [iNonStrAttNum];
				} 
		        catch(CMemoryException * e)
				{
					::MessageBeep(MB_ICONHAND);
					AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
					e->Delete();		
					return -1;
				} 				
				for(k=0;k<iNonStrAttNum;k++)
				{//每个属性k
 
					recnum1=search(pNonStringTable[i][k],k); //返回pNonStringTable[i][k]在数组att_val的下标
					recnum2=search(pNonStringTable[j][k],k);//返回属性值pNonStringTable[i][k]在属性数组att_val的下标
				    distance=abs(recnum2-recnum1);//差值  
					try
					{
						formulas[count][k]=new float[distance+1];
					}
                    catch(CMemoryException * e)
					{ 
				    	::MessageBeep(MB_ICONHAND);
				    	AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
				    	e->Delete();		
				    	return -1;
					} 
					formulas[count][k][0]=(float)distance;//count样例在k属性上候选断点数目
					if(recnum1<recnum2)//表示得到能够在k属性上区分i,j样例的断点集,相当于每个实
						for(m=1;m<distance+1;m++)//例对中的析取表达式
						{//加到recnum1==recnum2
							val1=att_val[k][recnum1];
							val2=att_val[k][recnum1+1];
							formulas[count][k][m]=(val1+val2)/2;
							recnum1++;
						}
					if(recnum1>recnum2)//
						for(m=1;m<distance+1;m++)
						{
							val1=att_val[k][recnum2];
							val2=att_val[k][recnum2+1];
							formulas[count][k][m]=(val1+val2)/2;
							recnum2++;
						}
				}//end for
				count++;//实例对数加一
			}//end if

	return count;
}

int CDisOne::init_matrix(int rows)
{//生成新的信息表，并返回该表的列数,即为总的断点数目,也就是矩阵的列数 failed:return -1
    int i,j,k,m;                          //循环变量
	int cols=0;                           //定义矩阵的行数
    bool find=FALSE;
	int num=0;                             //矩阵列数     
	try{
		matrix=new int * [rows];
	}
	catch(CMemoryException * e)
	{
			::MessageBeep(MB_ICONHAND);
			AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
			e->Delete();
			return -1;
	}
	for(i=0;i<iNonStrAttNum;i++)
		num+=(int)interval[i][0];//统计决策表中断点总数
	for(i=0;i<rows;i++)
	{//生成矩阵,i行
		try
		{
			matrix[i]=new int[num];//列
		}
		catch(CMemoryException * e)
		{
			::MessageBeep(MB_ICONHAND);
			AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
			e->Delete();
			return -1;
		}
		for(j=0;j<iNonStrAttNum;j++)//对每个属性j的每个断点
		{
			for(k=0;k<(int)interval[j][0];k++)
			{//属性候选断点集中循环
				if((int)formulas[i][j][0]==0)//实例对的候选断点集为0
					 matrix[i][cols]=0;//i行cols列为0.cols为列号,初始化为0
				if((int)formulas[i][j][0]>0)
				{//实例对的候选断点集不为0
				   for(m=0;m<(int)formulas[i][j][0];m++)
				    	if(interval[j][k+1]==formulas[i][j][m+1])
						{//说明interval[j][k+1]包含于实例对j属性中的候选断点集中
						  matrix[i][cols]=1;//对应矩阵元素为1
						  find=TRUE;
						  break;
						}
				    if(find==FALSE)
					  matrix[i][cols]=0;				
		    	    find=FALSE;
				}                
		        cols++;//最终cols等于num
			}
            delete []formulas[i][j];//释放空间
		}
		delete []formulas[i];
		cols=0;
	}
   delete []formulas;
   return num;//返回决策表的行数
}

void CDisOne::findcuts(int rows, int cols)
{//在新信息表中选取断点，记录在表中的列号，存入cuts数组中  
	int i,j;                    //循环变量
    int * cuts=NULL;
	if((cuts=new int[cols+1])==0)//定义断点
	{ 
		AfxMessageBox("分配内存失败!",MB_OK|MB_ICONSTOP);                     
		return;
	}
	cuts[0]=0;   //设置断点的初始个数
	if((rows==0)||(cols==0))
	{
	 	get_cut(cuts);//得到最终的断点集   
		return;
	}
    int num;
	int remains; //未处理的矩阵元素个数
	int maxvalue;//含1最多的列
	int minvalue; //在含1最多的列相等的情况下，求对应行断点和的最小值
	int maxnum; //含1最多的列中1的个数
	int maxcol=0;
    int **maxcols=NULL;
	if((maxcols=new int*[cols])==0)
	{  
		 AfxMessageBox("分配内存失败!",MB_OK|MB_ICONSTOP);                     
	  	 return;
	} 
	for(i=0;i<cols;i++)
		maxcols[i]=new int[2];
	int * countcols=NULL;
	if((countcols=new int[cols])==0) //各列中含1的个数
	{  
		  AfxMessageBox("分配内存失败!",MB_OK|MB_ICONSTOP);                     
		  return;
	}                
	int * countrows=NULL;
	if((countrows=new int[rows])==0)//各行中含1的个数
	{ 
		AfxMessageBox("分配内存失败!",MB_OK|MB_ICONSTOP);                     
		return;
	}
	//初始化各列1的总和以及各行1的总和为0
    for(i=0;i<cols;i++)
	{
       countcols[i]=0;
	   for(j=0;j<2;j++)
	    	maxcols[i][j]=0;
	}
    for(i=0;i<rows;i++)
		countrows[i]=0;

	for(i=0;i<cols;i++)//列
		  for(j=0;j<rows;j++)//行
			  if(matrix[j][i]==1)//统计i列1的数目和
			     countcols[i]++;
	for(i=0;i<rows;i++)//行
		for(j=0;j<cols;j++)//列
			if(matrix[i][j]==1)//统计i行1的数目和
				countrows[i]++;
   do//while(remains>0)
	{
		maxnum=0;
		maxvalue=0;
		remains=0;
	//先选列值为1总和最多的断点，
	//当有两列以上都为最多时，看行的总数
    //选取行总数最少的断点
		for(i=0;i<cols;i++)
			if(maxvalue<countcols[i])
				maxvalue=countcols[i];//找出列值最大的数
		for(i=0;i<cols;i++)
			if(countcols[i]==maxvalue)
			  maxnum++;//统计有几列都取得最大值
        if(maxnum==1)
		{//只有一列1的总数最多
			for(i=0;i<cols;i++)
               if(countcols[i]==maxvalue)
			        maxcol=i;//列号
		}
		else if(maxnum>1)//1的总数最多的列不止一个
		{			
		  num=0;
		  maxcols[num][0]=maxnum;
          for(i=0;i<cols;i++)
			  if(countcols[i]==maxvalue)
			  {
				  num++;
				  maxcols[num][0]=i;//将列号存入maxcols数组中  num从1开始
			  }
          //判断行总数最少的列
         num=1;
		 int num1=0;
		 for(i=0;i<maxnum;i++)
			 {//统计值最大的每个列对应的行的1之和
				 for(j=0;j<rows;j++)
		           if(matrix[j][maxcols[num][0]]==1)
				       num1+=countrows[j];//统计列maxcols[num][0]中1的行的1地个数之和
               //行为1的数放在maxcols[num][1]中
			     maxcols[num][1]=num1;//赋予列对应的行之和
				 num++;
			     num1=0;
			 }
		 num=1;
		 minvalue=maxcols[1][1];
		 for(i=0;i<maxnum;i++)
		 { //z找出行中1的最小值
		    if(minvalue>maxcols[num][1])
				minvalue=maxcols[num][1];
             num++;
		 }
		 num=1;
		 for(i=0;i<maxnum;i++)
		 {
		   if(minvalue==maxcols[num][1])
		   {
			   maxcol=maxcols[num][0];//得到此时的列号
			   break;
		   }
		    num++;
		 }
		} //end else if(maxnum>1)
		// 删除i所在的列和列值为1的行
		for(i=0;i<rows;i++)
			if(matrix[i][maxcol]==1)
			{				
                countrows[i]=0;//行标志标为0
				for(j=0;j<cols;j++)
					matrix[i][j]=-1;// 该行每个元素设为-1
			}
			for(i=0;i<rows;i++)
			   matrix[i][maxcol]=-1;//该列每个元素设为-1       
	   countcols[maxcol]=0;//列标志标为0
 	   cuts[0]++;//断点数目加一
	   cuts[cuts[0]]=maxcol;//记录此时断点对应的列
	   for(i=0;i<cols;i++)
		 if(countcols[i]!=0)//改列还没有删除
			 {//统计剩下的列
				 countcols[i]=0;
				 for(j=0;j<rows;j++)
				   if(matrix[j][i]==1)
					 countcols[i]++;//统计此时该列中'1'的个数
			 }
		for(i=0;i<rows;i++)//对每一行
			if(countrows[i]!=0)//改行还没有删除
			{//统计剩下的行
				countrows[i]=0;//行标设为0
				for(j=0;j<cols;j++)//列
					if(matrix[i][j]==1)
						countrows[i]++;//重新统计该行'1'的个数
			}
		for(i=0;i<rows;i++)
		  if(countrows[i]!=0)
			  remains+=countrows[i];//未处理的矩阵元素个数'1'的个数
	}while(remains>0);//当矩阵为0矩阵时退出
	if(countrows!=NULL)
		delete[] countrows;
	if(countcols!=NULL)
		delete[] countcols;	
	for(i=0;i<rows;i++)