集合运算(链表和移动语义)

题目描述：

请设计实现集合类，元素类型为整形, 集合采用带头结点单链表表示。该集合类支持集合元素增加、删除、查询；并支持集合并、交、差运算；利用你设计的集合类，实现本题要求。程序应体现面向对象程序设计思想，结构合理。为保证结果唯一，集合元素递增排列。如需用到拷贝构造和赋值应重载. 空间应正确释放. 要求使用移动复制和移动赋值,但本平台编译器不支持，所以，这部分代码以注解形式提供.

输入描述：

开始为两个正整数m,n；后续m个整数构成集合A,再后续n个整数构成集合B

输出描述：

集合A、B和他们的并、交、差集；每个集合元素间以,分隔；不同集合显示在不同行

输入样例：

3 5
1 2 3
3 5 8 2 1

输出样例：

{1,2,3}
{1,2,3,5,8}
{1,2,3,5,8}
{1,2,3}
{}
——————————————————————————————————————

代码：

#include <iostream>
using namespace std;

class CSet{
private:
    struct Node{
        int data;
        Node *next;
    } *m_pHead; // 集合采用递增排序单链表表示
public:
    //构造函数
    CSet();
    //析构函数，释放链表
    ~CSet();
    //增加元素
    bool Add(int x);
    //显示集合
    void Display();
    //结果为A、B并集
    CSet UnionBy(const CSet &rhs) const;
    //结果为A、B交集
    CSet IntersectionBy(const CSet &rhs) const;
    //结果为A、B差集
    CSet DifferentBy(const CSet &rhs) const;

    //下列成员函数本例未用，纯完整性考虑
    //拷贝构造函数
    CSet(const CSet &);
    //移动构造函数
    //CSet(CSet &&);
    //删除元素x
    bool Remove(int x);
    //是否包含元素x
    bool In(int x);
    //复制赋值
    CSet & operator = (const CSet &rhs);
    //移动赋值
    //CSet & operator = (CSet &&rhs);

private:
    //集合清空
    void    _Clear();
};


//构造函数
CSet::CSet()
{
    m_pHead = new Node;;
    m_pHead->next = NULL;
}
//析构函数，释放链表
CSet::~CSet()
{
    while (m_pHead) {
        Node *p = m_pHead;
        m_pHead = p->next;
        delete p;
    }
}

//集合清空
void    CSet::_Clear()
{
    while (m_pHead->next) {
        Node *p = m_pHead;
        m_pHead = p->next;
        delete p;
    }
}

//增加元素
bool CSet::Add(int x)
{
    Node *p = m_pHead;
    while (p->next && (p->next->data < x)) {
        p = p->next;
    }
    if (p->next && p->next->data == x)
        return false; //元素已在集合中
    Node *q = new Node;
    q->data = x;
    q->next = p->next;
    p->next = q;
    return true;

}

//显示集合
void CSet::Display()
{
    Node *p = m_pHead->next;
    cout << "{";
    while (p)
    {
        cout << p->data;
        p = p->next;
        if (p) cout << ",";
    }
    cout << "}" << endl;
}

//结果为A、B并集，为效率避免拷贝构造
//本例为简化逻辑直接调用Add成员函数，效率为O（M*N）；实际应参考IntersectionBy展开，效率可为O（M+N）
CSet CSet::UnionBy(const CSet &rhs) const
{
    CSet  result;

    Node *p = m_pHead->next;
    Node *q = rhs.m_pHead->next;
    while (p && q) {
        if (p->data == q->data) {
            result.Add(p->data);
            p = p->next;
            q = q->next;
        }
        else if (p->data < q->data) {
            result.Add(p->data);
            p = p->next;
        }
        else {
            result.Add(q->data);
            q = q->next;
        }
    }
    while (p) {
        result.Add(p->data);
        p = p->next;
    }
    while (q) {
        result.Add(q->data);
        q = q->next;
    }
    return result;
}

//结果为A、B交集，为效率避免拷贝构造
CSet CSet::IntersectionBy(const CSet &rhs) const
{
    CSet  result;

    Node *last = result.m_pHead;

    Node *p = m_pHead->next;
    Node *q = rhs.m_pHead->next;
    while (p && q)  {
        if (p->data == q->data) {
            //          Add(p->data);
            Node * s = new Node;
            s->data = p->data;
            last->next = s;
            last = s;

            p = p->next;
            q = q->next;
        }
        else if (p->data  < q->data)
            p = p->next;
        else
            q = q->next;
    }
    last->next = NULL;
    return result;
}

//结果为A、B差集，为效率避免拷贝构造
//本例为简化逻辑直接调用Add成员函数，效率为O（M*N）；实际应参考IntersectionBy展开，效率可为O（M+N）
CSet CSet::DifferentBy(const CSet &rhs) const
{
    CSet  result;

    Node *p = m_pHead->next;
    Node *q = rhs.m_pHead->next;
    while (p && q) {
        if (p->data == q->data) {
            p = p->next;
            q = q->next;
        }
        else if (p->data  < q->data) {
            result.Add(p->data);
            p = p->next;
        }
        else
            q = q->next;
    }
    while (p) {
        result.Add(p->data);
        p = p->next;
    }
    return result;
}

//删除元素
bool CSet::Remove(int x)
{
    Node *p = m_pHead;
    while (p->next && (p->next->data < x)) {
        p = p->next;
    }
    if (p->next == NULL || p->next->data != x)
        return false; //元素未在集合中
    Node *q = p->next;
    p->next = q->next;
    delete q;
    return true;
}

//是否包含元素x
bool CSet::In(int x)
{
    Node *p = m_pHead;
    while (p->next && (p->next->data < x)) {
        p = p->next;
    }
    if (p->next && p->next->data == x)
        return true;
    return false;
}

//拷贝构造函数
CSet::CSet(const CSet &rhs)
{
    //复制头结点
    m_pHead = new Node;
    Node *last = m_pHead; //最后结点

    Node *p = rhs.m_pHead->next;//不可修改rhs.m_pHead， 故引入临时变量p
    while (p) {
        Node *q = new Node;//申请一结点
        q->data = p->data; //复制元素
        //挂在最后
        last->next = q;
        last = q;
        //后移一结点
        p = p->next;
    }
    last->next = NULL;
}
//移动构造函数
/*
CSet::CSet(CSet &&rhs)
{
    //复制头结点
    m_pHead = rhs.m_pHead;
    rhs.m_pHead = NULL;
}
*/
//复制赋值
CSet & CSet::operator = (const CSet &rhs)
{
    this->_Clear();

    Node *last = m_pHead; //最后结点

    Node *p = rhs.m_pHead->next;//不可修改rhs.m_pHead， 故引入临时变量p
    while (p) {
        Node *q = new Node;//申请一结点
        q->data = p->data; //复制元素
        //挂在最后
        last->next = q;
        last = q;
        //后移一结点
        p = p->next;
    }
    last->next = NULL;

    return *this;
}
//移动赋值
/*
CSet & CSet::operator = (CSet &&rhs)
{
    Node *p = this->m_pHead;
    this->m_pHead = rhs.m_pHead;
    rhs.m_pHead = p;

    return *this;
}
*/
int main()
{
    CSet A, B, S;
    int i, m, n, x;
    cin >> m >> n;
    while ((m + n) >= 100) exit(-1);
    for (i = 0; i < m; i++)
    {
        cin >> x;
        A.Add(x);
    }
    for (i = m; i < n + m; i++)
    {
        cin >> x;
        B.Add(x);
    }
    A.Display();
    B.Display();


    S = A.UnionBy(B);
    S.Display();

    S = A.IntersectionBy(B);
    S.Display();

    S= A.DifferentBy(B);
    S.Display();

    return 0;
}