CSet生成组合数集合(幂集的子集)–C++实现

Set实现

[cpp]
/********************************************
CopyRight 2007 北京交通大学 计科0601 李赫元
工程名称: 子集
文件名: 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;
}
[/cpp]

测试程序

[cpp]
/********************************************
CopyRight 2007 北京交通大学 计科0601 李赫元
工程名称: 子集
文件名: 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;
}

[/cpp]

Leave a Reply

Your email address will not be published.