Set实现

/********************************************
CopyRight 2007 北京交通大学
工程名称： 子集
文件名： 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;
}

测试程序

/********************************************
CopyRight 2007 北京交通大学
工程名称： 子集
文件名： 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;
}