h

/********************************************
  CopyRight 2007 北京交通大学
  工程名称：  CSet
  文件名：    Set.h
  修改日期：  2007-4-30 20:19:59
  描述：      定义并实现了集合的封装，子集的输出，全排列的输出
 ********************************************/
#include <iostream>
using namespace std;

template <class T>
class CSet
{
public:
 CSet(int n);
 CSet();
 CSet(const CSet &C);
 CSet& operator = (const CSet &C);

 //拷贝入数据的接口
 void InPut(T *ptr,int n);
 
 //输出全集接口
 void OutPut();

 //输出子集接口
 void ChildSet();

 void OrderSet();

 ~CSet();
private:

 //先序遍历，生成子集
 SelectChild(int pos);
 //输出一个子集
 void OutChild();
 void SelectOrder(int pos);
 void OutOrder();
 void Swap(int pos1,int pos2);
 
 T *m_elem;    //存储元素

 int m_size;   //存储集合大小

 int m_nout; //输出个数

 bool *m_set;  //标记元素是否被选中
};

template <class T>
CSet<T>::CSet(int n)
:m_set(0)
{
 m_size = n;
 
 m_elem = new T[n];
 
 m_set = new bool[n];
 
 cout<<"请输入"<<n<<"个元素：";
 for (int i=0;i!=m_size;i++)
 {
  cin>>m_elem[i];
 }
}

template <class T>
CSet<T>::CSet()
:m_elem(0),m_size(0),m_set(0)
{
}

template <class T>
CSet<T>::CSet(const CSet &C)
{
 if (m_elem)
 {
  delete [] m_elem;
 }

 if (m_set)
 {
  delete [] m_set;
 }
 
 m_size=C.m_size;
 
 m_elem=new T[m_size];

 m_set = new bool[m_size];
 
 memcpy(m_elem,C.m_elem,sizeof(T)*m_size);

}

template <class T>
CSet<T>& CSet<T>::operator =(const CSet &C)
{
 if (m_elem)
 {
  delete [] m_elem;
 }
 
 if (m_set)
 {
  delete [] m_set;
 }

 m_size=C.m_size;
 
 m_set = new bool[m_size];

 m_elem=new T[m_size];
 
 memcpy(m_elem,C.m_elem,sizeof(T)*m_size);

 return *this;
}

template <class T>
CSet<T>::~CSet()
{
 if (m_elem)
 {
  delete [] m_elem;
 }

 if (m_set)
 {
  delete [] m_set;
 }
}

template <class T>
void CSet<T>::OutPut()
{
 
 cout<<"输出所有元素：\n";
 for (int i=0;i!=m_size;i++)
 {
  cout<<m_elem[i]<<" ";
 }

 cout<<endl;
}

template <class T>
CSet<T>::SelectChild(int pos)
{
 if (pos >= m_size)
 {
  OutChild();
  m_nout++;
 }
 else
 {
  m_set[pos] = true;
  SelectChild(pos+1);
  m_set[pos] = false;
  SelectChild(pos+1);
 }
}

template <class T>
void CSet<T>::OutChild()
{
 for (int i=0;i!=m_size;i++)
 {
  if (m_set[i])
  {
   cout<<m_elem[i]<<" ";
  }
 }
 cout<<endl;
}

template <class T>
void CSet<T>::ChildSet()
{
 memset(m_set,0,sizeof(bool)*m_size);
 m_nout = 0;

 cout<<"输出所有子集：\n";

 SelectChild(0);

 cout<<"共计："<<m_nout<<"个子集"<<endl;

 m_nout = 0;
}

template <class T>
void CSet<T>::InPut(T *ptr,int n)
{
 if (m_elem)
 {
  delete [] m_elem;
 }

 if (m_set)
 {
  delete [] m_set;
 }

 m_set = new bool[n];

 m_size = n;

 m_elem = new T[n];

 memcpy(m_elem,ptr,sizeof(T)*n);
}

template <class T>
void CSet<T>::OrderSet()
{
 m_nout=0;
 cout<<"输出全排列：\n";
 SelectOrder(0);
 cout<<"共计"<<m_nout<<"种全排列.\n";
 m_nout=0;
}

template <class T>
void CSet<T>::Swap(int pos1,int pos2)
{
 T tmp = m_elem[pos1];
 m_elem[pos1] = m_elem[pos2];
 m_elem[pos2] = tmp;
}

template <class T>
void CSet<T>::SelectOrder(int pos)
{

 if(pos >= m_size)
 {
  OutOrder();
  ++m_nout;
 }
 else
 {
  for(int i=pos;i!=m_size;i++)
  {
   Swap(pos,i);
   SelectOrder(pos+1);
   Swap(pos,i);
  }
 }

}

template <class T>
void CSet<T>::OutOrder()
{
 for(int i=0;i!=m_size;i++)
 {
  cout<<m_elem[i]<<" ";
 }
 cout<<endl;
}

main

/********************************************
  CopyRight 2007 北京交通大学
  工程名称：  CSet
  文件名：    main.cpp
  修改日期：  2007-4-30 20:19:52
  描述：      测试集合类CSet，输出子集，全排列
 ********************************************/
#include "Set.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
 //几种初始化CSet的方法
 //1.调用默认构造函数，然后用Input接口输入
 //例：
 
 /*
 CSet<int> C;
 int arr[]={1,2,3,4,5};
 
 C.InPut(arr,sizeof(arr)/sizeof(int));
 */

 //2.构造时候加参数n，表示集合含有几个元素，顺便完成输入
 //例：
 CSet<int> C(5);

 //输出全集
 C.OutPut();

 //输出全排列
 C.OrderSet();

 //输出子集
 C.ChildSet();

 return 0;
}