set.h

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

// Set.h: interface for the CSet class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SET_H__76B80A82_C2BC_11D4_BFEA_0040054EF889__INCLUDED_)
#define AFX_SET_H__76B80A82_C2BC_11D4_BFEA_0040054EF889__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
// Set.h: interface for the CSet class.
//
//////////////////////////////////////////////////////////////////////
#include <iostream.h>

template<class T>
class setNode
{
public:
	setNode(const T& ele)
	{
		element=ele;
		next=NULL;
	}
	~setNode()	{}

/*	bool operator==(setNode<T>& item)
	{
		if(element==item)
			return true;
		return false;
	}
*/
	void DeleteAfter()
	{
		if(next==NULL) return;
		setNode* p=next;
		next=p->next;
		delete p;
	}
	T element;
	setNode* next;
};

template <class T>			//T :element data type
class CSet  
{
protected:
	int m_nCount;		//集合中元素的数目
	int ID;	    		//indicate the identity 属性值
	public:
	setNode<T> *m_Head;			//the head of the set list
	setNode<T> *m_Tail;			//tail
public:
	CSet(int id);
	CSet();
	CSet(const CSet& h);		//copy constructor
	~CSet();
	int getID() { return ID;}//得到当前分类的属性值
	int findID(int id);        //返回元素个数,找不到返回0
							   //仅对T为CSet<*>有效
	T* findItem(int id);
//	int setID(int id) {ID=id; return ID;}
	setNode<T>* getHead() { return m_Head;}
	setNode<T>* getNext(setNode<T>* p) {return p=p->next;}
	
	void deleteHead();
	void deleteAfter(setNode<T>* p);
	void operator = (const CSet& h);
	friend ostream& operator << (ostream&,CSet&);
	friend ostream& operator << (ostream&,CSet *);
	int getCount(){ return m_nCount;}//return the element number
	CSet<T> operator + (const CSet<T>& set);	//并运算
	CSet<T> operator * (CSet<T>& set);	//交运算
	void operator += (const CSet<T>& set);
	bool operator == (const CSet& comset);//if the set is equal to comset
	bool AddElement(const T& item);	//相等则不加入,否则插入末尾
	bool AddToEnd(const T& item);	//添加到尾巴上	
	bool AddElement2(const T& item);//已经有item的子集包含在集合中,就不再加入  因为:当集合中已经有a时,item为aVb就没必要加入
	bool AddInOrder(const T& item);		//加入但不打乱顺序,慎用
	bool BelongTo(const CSet& comset);
	bool HasMember(const T& item);
	static bool AddEleToSubSet(CSet<CSet<int> >& p,int item,int id);
	static void AddToEverySubSet(CSet<CSet<int> >& set,const T& m);	
			//给每个set的子集都添加元素值 m

#ifdef _DEBUG
	static void outset(CSet<int> &set);
	void static outset(CSet<CSet<int> > &set);
#endif //_DEBUG

};


template <class T>         //constructor
CSet<T>::CSet()
{
	m_Head=NULL;
	m_Tail=NULL;
	m_nCount=0;
	ID=0;
}

template <class T>         //constructor
CSet<T>::CSet(int id):ID(id)
{
	m_Head=NULL;
	m_Tail=NULL;
	m_nCount=0;
}

template <class T>
CSet<T>::CSet(const CSet& h)
{
	m_nCount=0;
	setNode<T>* p=h.m_Head;
	m_Head=NULL;
	m_Tail=NULL;
	ID=h.ID;
	while(p)
	{
		AddElement(p->element);
		p=p->next;
	}
}

template <class T>
CSet<T>::~CSet()
{
	setNode<T> *p=m_Head,*temp;
	while(p)
	{
		temp=p;
		p=p->next;
		delete temp;
	}
}

template <class T>
void CSet<T>::deleteHead()
{
	if(!m_Head) return;		//if m_Head is NULL, do nothing
	m_nCount--;
	if(m_Head==m_Tail)  
	{
		delete m_Head;
		m_Head=m_Tail=NULL;
		m_nCount--;
		return;
	}
	setNode<T> *p=m_Head;
	m_Head=m_Head->next;
	delete p;
}

template <class T>
void CSet<T>::deleteAfter(setNode<T>* p)
{
	if(p==m_Tail)  return;
	setNode<T> * temp;
	temp=getNext(p);
	if(temp==m_Tail)
	{
		m_Tail=p;
		p->next=NULL;
	}
	p->next=temp->next;
	m_nCount--;
	delete temp;
}

template <class T>
void CSet<T>::operator = (const CSet& h)
{
	if(m_Head!=NULL)
	{
		setNode<T>* p=m_Head;
		while(p)//删除原来所有集合元素
		{
			setNode<T>* temp=p;
			p=p->next;
			delete temp;
		}
	}
	m_nCount=0;
	setNode<T>* p=h.m_Head;//重新初始化
	m_Head=NULL;
	m_Tail=NULL;
	ID=h.ID;
	while(p)
	{//加入元素
		AddElement(p->element);
		p=p->next;
	}
}

template <class T>
bool CSet<T>::AddToEnd(const T& item)		//添加到尾巴上	
{
	m_nCount++;//集合中元素数目加一
	setNode<T> *node;
	try
	{
		node=new setNode<T>(item);//创建节点
	}
	catch(CMemoryException * e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return false;
	} 
	if (m_Head==NULL)
	{//如果原先集合不存在
		m_Head=node;
	}
	else//否则加到尾部 
		m_Tail->next=node;
	m_Tail=node;
	m_Tail->next=NULL;
	return true;
}

template <class T>
bool CSet<T>::AddElement(const T& item)
{//加入集合中的一个项,相同则不添加,不同则加到末尾
 //比如{a,bc}中项为a,bc
	setNode<T>* p=m_Head;
	while(p)//检测是否有相同的项
	{
		if(p->element==item)//集合比较,为真说明存在相同子集合
			return true;    //have been inserted
		else 
			p=p->next;
	}
	m_nCount++;
	setNode<T> *node;
	try
	{
		node=new setNode<T>(item);
	}
	catch(CMemoryException * e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return 0;
	} 
	if (m_Head==NULL)
	{
		m_Head=node;
	}
	else m_Tail->next=node;
	m_Tail=node;
	m_Tail->next=NULL;
	return true;
}

template <class T>
bool CSet<T>::AddInOrder(const T& item)
{	//加入但不打乱顺序,慎用  按从小到大顺序插入
	setNode<T>* p=m_Head;
	setNode<T> *temp;
	try
	{
		temp=new setNode<T>(item);//用item来初始化temp
	}
	catch(CMemoryException * e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return 0;
	} 
	if(m_Head==NULL)
	{
		m_nCount++;
		m_Head=m_Tail=temp;
		return true;
	}
	if(m_Head->element==item)
	{
		delete temp;
		return false;
	}
	if(m_Head->element>item)
	{//加到头部
		m_nCount++;
		temp->next=m_Head;
		m_Head=temp;
		return true;
	}
	if(m_Tail->element==item)
	{//不加入,因为已经集合中已经包含此元素
		delete temp;
		return false;
	}
	if(m_Tail->element<item)
	{//加到尾部
		m_nCount++;
		m_Tail->next=temp;
		m_Tail=temp;
		return true;
	}
	while(p&&p->next->element<item)
		p=p->next;//可能在中部插入,移位
	if(p->next->element==item)
	{
		delete temp;
		return false;
	}
	m_nCount++;
	temp->next=p->next;
	p->next=temp;
	return true;
}


template <class T>
bool CSet<T>::AddElement2(const T& item)
{//已经有item的子集包含在集合中,就不再加入  
//因为:当集合中已经有a时,item为aVb就没必要加入
	setNode<T>* p=m_Head;
//  setNode<T>* q=item.getHead();
	while(p)
	{
		if(p->element.BelongTo(item))
//        if(item.BelongTo(p->element))
	 	    return true; //p中元素包含于item中,此时就没的必要加入item
		else 
			p=p->next;
	}
	m_nCount++;//元素数目加一
	setNode<T> *node;
	try{
		node=new setNode<T>(item);//用item来初始化node
	}
	catch(CMemoryException * e)
	{
		::MessageBeep(MB_ICONHAND);
		AfxMessageBox("Out of the memory!",MB_OK|MB_ICONSTOP);
		e->Delete();
		return 0;
	} 
	if (m_Head==NULL)
	{
		m_Head=node;
	}
	else m_Tail->next=node;//直接插到尾部
	m_Tail=node;
	m_Tail->next=NULL;
	return true;
}

template <class T>
bool CSet<T>::operator == (const CSet& comset)
{//比较两个集合是否相等
	if (m_nCount!=comset.m_nCount)
		return false;
	setNode<T>* p=m_Head;
	while(p)
	{
		setNode<T> *temp=comset.m_Head;
		while(temp)
		{
			if (p->element==temp->element)
				break;//发现temp中存在一个相同的元素
			else temp=temp->next;
		}
		if(temp==NULL) return false;//循环完都没发现与p中元素相等的,说明不相等
		else p=p->next;
	}
	return true;
	//循环完所有可能,说明p中元素全部包含于comset中,故返回为真
	//有因为他们的元素个数相等,故完全相等
}
/*
template <class T>
ostream& operator << (ostream& out,CSet<T>& right)
{
	setNode<T> *p= right.m_Head;
	out<<right.getCount()<<"{";
	while(p)
	{
		out<<p->element;
		if(p=p->next)
			out<<",";
	}
	out<<"}";
	return out;
}
*/
template <class T>
bool CSet<T>::BelongTo(const CSet<T>& comset)
{
	setNode<T>* p=m_Head;
	while(p)
	{
		setNode<T> *temp=comset.m_Head;
		while(temp)
		{
			if (p->element==temp->element)
				break;
			else temp=temp->next;
		}
		if(temp==NULL) return false; 
		//在temp中没有发现p对应元素,说明p不属于temp
		else p=p->next;//p属于temp中的一个元素时
	}
	//全部循环完,说明当前类包含于comset中
	return true;
}

template <class T>
bool CSet<T>::HasMember(const T& item)
{//item包含于CSet中,返回为真,否则为假
	setNode<T> *p=m_Head;
	while(p)
	{
		if(p->element==item) return true;
		p=p->next;
	}
	return false;
}

template<class T>
void CSet<T>::operator += (const CSet<T>& set)
{//集合相加,比如说{a,bc}+{b,ac}={a,bc,b,ac}
	setNode<T> *p=set.m_Head;
	while(p)
	{
		AddElement(p->element);
		p=p->next;
	}
}

template<class T>
CSet<T> CSet<T>::operator + (const CSet<T>& set)
{//插入元素后返回此集合 只加入一个元素?
	CSet<T> answer;
	answer=set;
	setNode<T>* p=m_Head;
	//p=set2.m_Head;;
	while(p)
	{
		answer.AddElement(p->element);
		p=p->next;
	}
	return answer;
}
/*
template <class T>
ostream& operator << (ostream& out,CSet<T>* right)
{
	out<<*right;
	return out;
}
*/
template<class T>
CSet<T> CSet<T>::operator * (CSet<T>& set)
{//交运算
	CSet<T> answer;
	setNode<T>* p=m_Head;
	while(p)
	{
		if(set.HasMember(p->element))
			answer.AddInOrder(p->element);
		p=p->next;
	}
	return answer;//得到交集
}

template<class T>
int CSet<T>::findID(int id)	//仅对T为CSet<*>有效
{							//返回元素个数,找不到返回0
	setNode<T> *p=m_Head;
	while(p)
	{
		if(p->ID==id)
			return p->m_nCount;
		p=p->next;
	}
	return 0;
}

template<class T>
T* CSet<T>::findItem(int id)
{		//返回id对应的元素值					
	setNode<T> *p=m_Head;
	while(p)
	{
		if(p->element.getID()==id)
			return &p->element;
		p=p->next;
	}
	return NULL;
}
template <class T>
bool CSet<T>::AddEleToSubSet(CSet<CSet<int> >& set,int item,int id)
{
	setNode<CSet<int> >* p;
	p=set.getHead();
	while(p)
	{
		if((p->element.getID())==id)
		{//找到所属的类
			p->element.AddElement(item);
			return true;
		}
		p=set.getNext(p);
	}
	CSet<int>  temp(id);//没找到时,开创新的类
	temp.AddElement(item);
	set.AddElement(temp);//插入
	return true;
}
template <class T>
void CSet<T>::AddToEverySubSet(CSet<CSet<int> >& set,const T&  m)
{//给每个set的子集都添加元素值 m,如果存在就不添加,否则按照顺序加入
	setNode<CSet<int> > *p=set.getHead();
	setNode<CSet<int> > *q=p;
	while(p)
	{
		p->element.AddInOrder(m);
		p=set.getNext(p);
	}
	if(!q)
	{
	 //   q->element.AddElement(m);
  	CSet<int>  temp;//没找到时,开创新的类
	temp.AddElement(m);
	set.AddElement(temp);//插入
    }	
}


#ifdef _DEBUG
template<class T>
void CSet<T>::outset(CSet<int> &set)
{//用于调试,输出类中的每个元素
		TRACE("(%d)",set.getID());
		TRACE("{");
		setNode<int>* temp=set.getHead();
		while(temp)
		{
			TRACE("%d",temp->element);
			if(temp=set.getNext(temp))
				TRACE(",");
		}
		TRACE("}");
}

template <class T>
void CSet<T>::outset(CSet<CSet<int> > &set)
{//用于调试,输出类元素个数以及各个元素
	TRACE("(%d)",set.getCount());
	TRACE("{");
	setNode<CSet<int> >* p=set.getHead();
	while(p)
	{
		p->element.outset(p->element);
		if(p=set.getNext(p))
			TRACE(",");
	}
	TRACE("}\n");
}

#endif //_DEBUG
#endif // !defined(AFX_SET_H__76B80A82_C2BC_11D4_BFEA_0040054EF889__INCLUDED_)