reduct2.cpp

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

/////////////////////////////////////////////////////
//  filename :reduct2.cpp
//	可辨识矩阵属性约简实现文件
//	作者：李鄂
//	2000/12
/////////////////////////////////////////////////////

#include "stdafx.h"
#include "Reduct2.h"
#include "fstream.h"
#include "Set.h"
#include "Lieselect.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

CReduct2::CReduct2()
{
}

CReduct2::~CReduct2()
{
}

#ifdef _DEBUG
void CReduct2::output()
{
	m_Matrix.outset(m_Matrix);
	TRACE("\n");
	m_Result.outset(m_Result);
}
#endif //_DEBUG

bool CReduct2::InitTable(CString txtname)	//初始化信息表
{
	TRACE("reduct2 ,initialize\n");
	if(CTable::InitTable(txtname)==false)
		return false;
	return true;
}

bool CReduct2::CreateMatrix()			
{
	TRACE("CReateMatrix");
	for(int i=1;i<m_nCount;i++)
		for(int j=0;j<i;j++)
		{
			if(m_Record[i][m_nConAttrNum]==m_Record[j][m_nConAttrNum])
				continue;//决策属性相同,不处理							
			CSet<int > tempset;
			for(int k=0;k<m_nConAttrNum;k++)
				if(m_Record[i][k]!=m_Record[j][k])
					tempset.AddToEnd(k);//将属性值不同的属性加入
			if(tempset.getCount()==0)
			{
			//	AfxMessageBox("发现矛盾数据");
			//	return false;
				continue;
			}
			m_Matrix.AddElement2(tempset);//加入差异矩阵
		}
 
	return true;
}

bool CReduct2::reductMatrix(CSet<CSet<int> >& Matrix)					//化简决策矩阵，便于求析取范式
{//化简可辨识矩阵，删除所有的包含关系，若A是B的子集，则可以删除B
	TRACE("reduct matrix\n");
	if(Matrix.getCount()==0)  // matrix is null
	{
		TRACE("matrix count is 0\n");
		return true;
	}
	setNode<CSet<int> >*temp=Matrix.getHead();
	setNode<CSet<int> >* p,*m;
	bool flag=false;
	while(temp)
	{//比较整个矩阵集合有没的包含temp的,有就删除.否则temp向后移,直到末尾为空
		p=Matrix.getHead();
		if( !flag && temp!=p &&
				(temp->element).BelongTo(p->element) )
			flag=true;//表明此时头节点p可以被删除
		while(p)
		{
			m=Matrix.getNext(p);
			if(m && temp!=m&& temp->element.BelongTo(m->element))
			{
				Matrix.deleteAfter(p);//删除p后面的元素m
			    int jjj=Matrix.getCount();
				   // if(Matrix.getCount()==1)
			}
			p=Matrix.getNext(p);
		}
		temp=Matrix.getNext(temp);
		if(flag) { Matrix.deleteHead(); flag=false;}//删除头部,头部向后移
	}
	return true;
}


bool CReduct2::reduct()
{
	if(CreateMatrix()==false) return false;
	if(m_Matrix.getCount()==0)
	{//差异矩阵为0矩阵
		for(int i=0;i<m_nConAttrNum;i++)
		m_bAttr[i]=false;
		AfxMessageBox("all condition attributes can be reduced！");
		return true;
	}
	else
	{//差异矩阵非0矩阵  
        reductMatrix(m_Matrix);//化简可辨识矩阵，删除所有的包含关系!!!
		setNode<CSet<int> > *temp=m_Matrix.getHead();
		setNode<CSet<int> > *temp1;
		CSet<int> attr_core;
		int i=0,j=m_Matrix.getCount();
    	while(i<j)
		{//得到差异矩阵中单属性元素的集合,即相对属性核
		//同时在差异矩阵中删除相对核属性
			if(temp->element.getCount()==1)
			{
			   	attr_core.AddInOrder(temp->element.getHead()->element);//将该属性加入相对属性核
			    if(i==0)//说明是头接点
				{
					m_Matrix.deleteHead();
					temp=m_Matrix.getHead();
					j--;
					continue;
				}
				else//其他节点,删除
				{
					m_Matrix.deleteAfter(temp1);
					temp=m_Matrix.getNext(temp1);
					i++;
					continue;
				}
			}//end if(temp->element.getCount()==1)
            temp1=temp;//此节点不是相对核属性元素时,对下一个节点操作
			temp=m_Matrix.getNext(temp);
			i++;
		}//ebd while(i<j)
		if(m_Matrix.getCount()>0)//差异矩阵中非空时
		{
			temp=m_Matrix.getHead();
            setNode<int> *temp2=temp->element.getHead();
    	    while(temp2)
			{//将第一个析取逻辑式中属性按照出现顺序插入排序,当作初始分类
		       CSet<int> mm;
			   mm.AddInOrder(temp2->element);
               m_Result.AddElement2(mm);
			   temp2=temp->element.getNext(temp2);
			} 
   /* 
        setNode<int>* p=mm.getHead();
		while(p)
		{
			m_Result.AddElement2((p->element);
		    p=p->next;
		}
	*/
	    	temp=m_Matrix.getNext(temp);//下一个析取逻辑表达式
		    while(temp)
	//集合操作,比如{a,bc}和{c,ac,de},开始得到m_Result={ac,bc},temp=ac
	//第一大步:
	//  第一小步temp2=a ,结果为ac,abc,m_Result={ac,bc,abc}
	//  第二小步temp2=c  结果为ac,bc,m_Result不变为{ac,bc,abc}
	//第三大步:temp=de  temp2=d 对m_Result进行操作,原理如上
			{
		    	CSet<CSet<int> >tempresult=m_Result;
			    CSet<CSet<int> >reserve=m_Result;
			    temp2=temp->element.getHead();
		    	if(temp2) 
			    	CSet<int>::AddToEverySubSet(m_Result,temp2->element);
			    while(temp2=temp->element.getNext(temp2))
				{
				   CSet<int>::AddToEverySubSet(tempresult,temp2->element);
				   m_Result+=tempresult;//集合相加,比如{a,bc}+{c,ac}={a,bc,c,ac}
				   tempresult=reserve;
				} 
			    temp=m_Matrix.getNext(temp);//下一个集合中的元素项,如
			    reductMatrix(m_Result);//化简结果矩阵
			} 
     		reductMatrix(m_Result);//化简结果矩阵
		}//end if(m_Matrix.getCount()>0)
		if(attr_core.getCount()>0)
		{
			int i=0;
			setNode<int>* p=attr_core.getHead();
		    while(i<attr_core.getCount())
			{
			  CSet<int>::AddToEverySubSet(m_Result,p->element);
			  p=attr_core.getNext(p);
			  i++;
			}
		}
	}
	/*//原先程序代码
		reductMatrix(m_Matrix);//化简可辨识矩阵，删除所有的包含关系
		setNode<CSet<int> > *temp=m_Matrix.getHead();
		setNode<int> *temp2=temp->element.getHead();
		CSet<int> mm;
		while(temp2)
		{//将第一个析取逻辑式中属性按照出现顺序插入排序,当作初始分类
			mm.AddInOrder(temp2->element);
			temp2=temp->element.getNext(temp2);
		}
		m_Result.AddElement2(mm);
		temp=m_Matrix.getNext(temp);//下一个析取逻辑表达式
		while(temp)
		{
			CSet<CSet<int> >tempresult=m_Result;
			CSet<CSet<int> >reserve=m_Result;
			temp2=temp->element.getHead();
			if(temp2)
				CSet<int>::AddToEverySubSet(m_Result,temp2->element);
			while(temp2=temp->element.getNext(temp2))
			{
				CSet<int>::AddToEverySubSet(tempresult,temp2->element);
				m_Result+=tempresult;
				//tempresult=reserve;
			}
			temp=m_Matrix.getNext(temp);
			reductMatrix(m_Result);//化简结果矩阵
		}
		reductMatrix(m_Result);//化简结果矩阵
	}*/
    TRACE("reduct finished");
////////////////////////moved from the next function
//             that is ,WriteFile()
	if(m_Result.getCount()==0)
		return false;
	CLieSelect dlg;
	dlg.itemCount=m_Result.getCount();	//约简结果类的个数
//	dlg.itemCount=0;
	CString* data=new CString[dlg.itemCount];
	dlg.data=data;
	setNode<CSet<int> >*resultp=m_Result.getHead();
	int m=-1;
//	int mm=dlg.itemCount;
	while(resultp)
	{
		m++;
		CString temp="",p;
		setNode<int> *subp=resultp->element.getHead();
		while(subp)
		{
			p.Format("%s ",m_AttrName[subp->element]);
			temp+=p;
			subp=resultp->element.getNext(subp);
		}
		dlg.data[m]=temp;//得到一行约简字符串
		resultp=m_Result.getNext(resultp);
	}
	MessageBeep(MB_OK);
	if(dlg.DoModal()==IDCANCEL)
		return false;
	setNode<CSet<int> >* resp=m_Result.getHead();
	for(int i=0;i<dlg.m_nSelected;i++)
		resp=m_Result.getNext(resp);//循环到所选择的那个属性约简结果
	for( i=0;i<m_nConAttrNum;i++)
		m_bAttr[i]=false;
	setNode<int> *subp=resp->element.getHead();
	while(subp)
	{
		m_bAttr[subp->element]=true;
		subp=resp->element.getNext(subp);
	}
	delete []data;
	///////////end////////
	return true;
}

bool CReduct2::WriteFile(CString name)
{
	
	//		TRACE(" select %d \n",dlg.m_nSelected);
	
	//		CSet<int>::outset(p->element);		
	
	return 	CTable::WriteFile(name);
	
	
	
	/*	setNode<CSet<int> > *resultp=m_Result.getHead();
	int m=-1;
	while(resultp)
	{
	m++;
	for(int i=0;i<m_nConAttrNum;i++)
	m_bAttr[i]=false;
	setNode<int> *subp=resultp->element.getHead();
	while(subp)
	{
			m_bAttr[subp->element]=true;
			subp=resultp->element.getNext(subp);
		}
		CString name1;
		name1.Format("red2%d.txt",m);
		
		CTable::WriteFile(name+name1);
		resultp=m_Result.getNext(resultp);
	}
	*/
}