题目描述
请设计实现集合类,元素类型为整形, 集合采用带头结点单链表表示。该集合类成员函数须支持集合元素增加、删除、查询、显示,并支持集合并、交、差运算,运算结果要求返回集合对象(否则每项扣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(); }