类的赋值与构造:集合运算(链表和移动语义)

题目描述

请设计实现集合类,元素类型为整形, 集合采用带头结点单链表表示。该集合类成员函数须支持集合元素增加、删除、查询、显示,并支持集合并、交、差运算,运算结果要求返回集合对象(否则每项扣2分);利用你设计的集合类,实现本题要求。程序应体现面向对象程序设计思想,结构合理。为保证结果唯一,集合元素递增排列。要求实现拷贝构造和复制赋值重载、移动构造和移动赋值(否则每项扣2分),不可有内存泄漏(否则扣1~3分)。

输入描述

开始为两个正整数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}
{}

题解:
对类的使用的练习,要求用链表构建,其中三个运算分别从根节点遍历一遍就好了。
难点在于移动构造和移动赋值,以及最难的,思考函数应该用什么名字。
这里我采用经典命名法,在关键字前加my的方法,使函数名清晰易懂。

这里说一下移动构造和拷贝构造的区别,
拷贝构造就是把原来的对象,完完整整的拷贝过来————需要申请新的空间,以及最重要的,不干扰原对象的内容。

比如说,原对象内部有一个指针,指向一块地盘,如果是系统给的默认拷贝,就会把指针的内容赋给目标的对象,
让一块地盘,有2个主人。
这就是浅拷贝。

但这会遇到一个问题————调用析构函数时,将会两次释放这块区域,而这是不被允许的。

所以,我们需要定义一个深拷贝————再找一块新的土地,拷贝成和原来的一mu一样,再将它交给新的主人。
这就是拷贝构造。

但这还不够,我们总会遇到一个新的情况——比如说:抢地盘。
如果我们要把一块地盘送给新的大臣,又不想从匮乏的国土(内存)中新分出去一块,这时候我们需要做的很简单,
把这块地的原主人杀了————这就是移动构造,因为析构函数的存在,我们不允许一地二主。
讲道理这应该比拷贝赋值简单。

至于具体的语法内容,可以看:
https://www.jianshu.com/p/cb82c8b72c6b

代码:
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

class MySet//集合类
{
private:
      struct mylist
      {
            int num;
            mylist *next;
            mylist()
            {
                  num=0;
                  next=0;
            }
      }*root;
public:
      MySet(){root=new mylist;}

      //拷贝的重载与构造
      MySet& operator=(const MySet&a);//拷贝赋值
      MySet(const MySet& a);//拷贝构造

      //移动的重载与构造
      MySet & operator=(MySet && a);//移动赋值
      MySet(MySet&&a);//移动构造

      //清除
      ~MySet();//析构
      void clear();

      //操作
      bool push(int x);//添加
      bool erase(int x);//删除
      bool find(int x)const;//查找
      void show()const;//显示

      //运算
      MySet& myor(const MySet&a,const MySet&b);//
      MySet& myand(const MySet&a,const MySet&b);//
      MySet& minus(const MySet&a,const MySet&b);//

};




//拷贝
MySet& MySet::operator=(const MySet&a)//对 = 的拷贝重载
{

      (*this).clear();
      mylist*tmp=a.root->next,*t=this->root;
      while(tmp)
      {
            t->next=new mylist;
            t->next->num=tmp->num;
            t=t->next;
            tmp=tmp->next;
      }
      return *this;
}
MySet::MySet(const MySet & a)//拷贝构造
{
      this->root=new mylist;
      (*this)=a;
}



//移动
MySet& MySet::operator=( MySet&& a)//对 = 的移动重载
{
      (*this).clear();
      MySet tmp=move(a);
      a=move(*this);
      *this=move(tmp);
      return *this;
}
MySet::MySet(MySet && a)//移动构造
{
      this->root=new mylist;
      MySet tmp=move(a);
      a=move(*this);
      *this=move(tmp);
}



//清除
MySet::~MySet()//析构
{
      (*this).clear();
      delete root;
}
void MySet::clear()//清除除了root外的节点
{
      mylist*tmp=root->next,*a;
//      int cnt=1;
      while(tmp)
      {
//            cout<<"del: "<<cnt++<<endl;//检测是否清除内存
            a=tmp->next;
            delete tmp;
            tmp=a;
      }
      root->next=0;
}



//四个操作
bool MySet::push(int x)//添加
{
      mylist*tmp=root->next;
      if(!tmp)
      {
            root->next=new mylist;
            root->next->num=x;
            return true;
      }
      if(x<tmp->num)
      {
            mylist*a=new mylist;
            a->num=x;
            a->next=tmp;
            root->next=a;
      }
      while(x>=tmp->num)
      {
            if(x==tmp->num)
            {
                  return false;
            }
            if(!tmp->next)
            {
                  mylist*a=new mylist;
                  a->num=x;
                  tmp->next=a;
                  a->next=0;
                  return true;
            }
            if(tmp->next->num>x)
            {
                  mylist*a=new mylist;
                  a->num=x;
                  a->next=tmp->next;
                  tmp->next=a;
                  return true;
            }
            tmp=tmp->next;
      }
      return true;
}
bool MySet::erase(int x)//删除
{
      mylist*tmp=root;
      while(tmp->next)
      {
            if(tmp->next->num==x)
            {
                  mylist*a=tmp->next;
                  tmp->next=tmp->next->next;
                  delete a;
                  return true;
            }
            tmp=tmp->next;
      }
      return false;
}
bool MySet::find(int x)const//查找
{
      mylist*tmp=root;
      while(tmp->next)
      {
            if(tmp->next->num==x)
            {
                  return true;
            }
            tmp=tmp->next;
      }
      return false;
}
void MySet::show()const//显示
{
      mylist*tmp=root->next;
      if(!root->next)
      {
            cout<<"{}"<<endl;
            return;
      }
      cout<<{<<tmp->num;
      while(tmp->next)
      {
            cout<<,<<tmp->next->num;
            tmp=tmp->next;
      }
      cout<<}<<endl;
}


//三个运算
MySet& MySet::myor(const MySet&a,const MySet&b)//
{
      (*this).clear();
      mylist*tmp1=a.root->next;
      mylist*tmp2=b.root->next;
      mylist*ans=this->root;
      while(tmp1||tmp2)
      {
            if(!tmp1)
            {
                  while(tmp2)
                  {
                        ans->next=new mylist;
                        ans->next->num=tmp2->num;
                        ans=ans->next;
                        tmp2=tmp2->next;
                  }
                  break;
            }
            if(!tmp2)
            {
                  while(tmp1)
                  {
                        ans->next=new mylist;
                        ans->next->num=tmp1->num;
                        ans=ans->next;
                        tmp1=tmp1->next;
                  }
                  break;
            }
            if(tmp1->num>tmp2->num)
            {
                  ans->next=new mylist;
                  ans->next->num=tmp2->num;
                  ans=ans->next;
                  tmp2=tmp2->next;

            }
            else if(tmp1->num<tmp2->num)
            {
                  ans->next=new mylist;
                  ans->next->num=tmp1->num;
                  ans=ans->next;
                  tmp1=tmp1->next;
            }
            else
            {
                  ans->next=new mylist;
                  ans->next->num=tmp1->num;
                  ans=ans->next;
                  tmp1=tmp1->next;
                  tmp2=tmp2->next;
            }
      }
      return*this;
}
MySet& MySet::myand(const MySet&a,const MySet&b)//
{
      (*this).clear();
      mylist*tmp1=a.root->next;
      mylist*tmp2=b.root->next;
      mylist*ans=this->root;
      while(tmp1&&tmp2)
      {
            if(tmp1->num>tmp2->num)
            {
                  tmp2=tmp2->next;

            }
            else if(tmp1->num<tmp2->num)
            {
                  tmp1=tmp1->next;
            }
            else
            {
                  ans->next=new mylist;
                  ans->next->num=tmp1->num;
                  ans=ans->next;
                  tmp1=tmp1->next;
                  tmp2=tmp2->next;
            }
      }
      return*this;
}
MySet& MySet::minus(const MySet&a,const MySet&b)//
{
      (*this).clear();
      mylist*tmp1=a.root->next;
      mylist*tmp2=b.root->next;
      mylist*ans=this->root;
      while(tmp1)
      {
            if(!tmp2)
            {
                  while(tmp1)
                  {
                        ans->next=new mylist;
                        ans->next->num=tmp1->num;
                        ans=ans->next;
                        tmp1=tmp1->next;
                  }
                  break;
            }
            if(tmp1->num>tmp2->num)
            {
                  tmp2=tmp2->next;
            }
            else if(tmp1->num<tmp2->num)
            {
                  ans->next=new mylist;
                  ans->next->num=tmp1->num;
                  ans=ans->next;
                  tmp1=tmp1->next;
            }
            else
            {
                  tmp1=tmp1->next;
                  tmp2=tmp2->next;
            }
      }
      return*this;
}

int main()
{
    //  freopen("input.txt","r",stdin);//检验
      int m,n,t;
      MySet a,b;
      cin>>m>>n;
      while(m--)
      {
            cin>>t;
            if(!a.push(t))
                  cout<<"输入失败"<<endl;
      }
      while(n--)
      {
            cin>>t;
            if(!b.push(t))
                  cout<<"输入失败"<<endl;
      }
//      b.erase(2);//对erase函数的检验
      a.show();
      b.show();
      MySet c;
      c.myor(a,b);
      c.show();
      c.myand(a,b);
      c.show();
      c.minus(a,b);
      c.show();

}

 

类的赋值与构造:集合运算(链表和移动语义)

上一篇:拖拽+重叠+虚线框(解决移动文字复制问题)


下一篇:【Android】保存Fragment切换状态