#include <iostream>#include <stdlib.h>#include <memory.h>using namespace std;
class Set{ friend void InsertSort(int *array1, int len); friend void MergePlus(int *array1, const int *arrA,const int *arrB, int lenA, int lenB, int *ilen); friend void MergeCut(int *array1, const int *arrA, const int *arrB, int lenA, int lenB, int *ilen); friend void MergeCross(int *array1, const int *arrA, const int *arrB, int lenA, int lenB, int *ilen); //friend Set operator+(const Set& A, const Set &B);public: Set(); Set(int s[],int n); Set(const Set &ohter); //拷贝构造 int find(int x)const; //判断x是否在集合中 Set& operator=(const Set &other);//赋值运算符重载 Set operator+(const Set &other);//集合的并集 Set operator-(const Set &other);//集合的差集 Set operator*(const Set &other);//集合的交集 void disp(); ~Set();
private: int *elem;//存放集合元素的指针 int count;//存放集合中的元素个数};
void InsertSort(int *array1, int len) //直接插入排序{ int i, j; int curKey;
for(i = 1; i < len; ++i) { curKey = array1[i]; j = i - 1;
while(curKey < array1[j] && j >= 0) { array1[j+1] = array1[j]; --j; } array1[j+1] = curKey; }}
void MergePlus(int *array1, const int *arrA, const int *arrB, int lenA, int lenB, int *ilen) //归并排序{ static int ia = 0, ib = 0; static int flag = 1; if(lenA <= 0 && lenB <= 0) { flag = 0; return; } if(lenA <= 0 && lenB>0) { array1[(*ilen)++] = arrB[ib++]; MergePlus(array1, arrA, arrB, lenA, lenB-1, ilen); } if(lenA >0 && lenB <= 0) { array1[(*ilen)++] = arrA[ia++]; MergePlus(array1, arrA, arrB, lenA -1, lenB, ilen); }
if( flag && arrA[ia] < arrB[ib]) { array1[(*ilen)++] = arrA[ia++]; MergePlus(array1, arrA, arrB, lenA -1, lenB, ilen); } else if(flag && arrA[ia] == arrB[ib]) { array1[(*ilen)++] = arrA[ia++]; ib++; MergePlus(array1, arrA, arrB, lenA -1, lenB -1, ilen); } else if(flag) { array1[(*ilen)++] = arrB[ib++]; MergePlus(array1, arrA, arrB, lenA, lenB - 1, ilen); }}
void MergeCut(int *array1, const int *arrA, const int *arrB, int lenA, int lenB, int *ilen) //归并排序{ static int ia = 0, ib = 0; static int flag = 1; if(lenA <= 0 && lenB <= 0) { flag = 0; return; } if(lenA <= 0 && lenB>0) { array1[(*ilen)++] = arrB[ib++]; MergeCut(array1, arrA, arrB, lenA, lenB-1, ilen); } if(lenA >0 && lenB <= 0) { array1[(*ilen)++] = arrA[ia++]; MergeCut(array1, arrA, arrB, lenA -1, lenB, ilen); }
if( flag && arrA[ia] < arrB[ib]) { array1[(*ilen)++] = arrA[ia++]; MergeCut(array1, arrA, arrB, lenA -1, lenB, ilen); } else if(flag && arrA[ia] == arrB[ib]) { ia++; ib++; MergeCut(array1, arrA, arrB, lenA -1, lenB -1, ilen); } else if(flag) { array1[(*ilen)++] = arrB[ib++]; MergeCut(array1, arrA, arrB, lenA, lenB - 1, ilen); }}
void MergeCross(int *array1, const int *arrA, const int *arrB, int lenA, int lenB, int *ilen) //归并排序{ static int ia = 0, ib = 0; static int flag = 1; if(lenA <= 0 && lenB <= 0) { flag = 0; return; }
if( flag && arrA[ia] < arrB[ib]) { ia++; MergeCross(array1, arrA, arrB, lenA -1, lenB, ilen); } else if(flag && arrA[ia] == arrB[ib]) { array1[(*ilen)++] = arrA[ia++]; ib++; MergeCross(array1, arrA, arrB, lenA -1, lenB -1, ilen); } else if(flag) { ib++; MergeCross(array1, arrA, arrB, lenA, lenB - 1, ilen); }}
Set::Set(){ elem = NULL; count = 0;}
Set::~Set(){ delete[]elem; elem = NULL;}
Set::Set(int s[], int n){ elem = new int[n]; if(elem == NULL) { cout << "Memory assign failure!!" << endl; exit(1); } for(int i = 0; i < n; ++i) { elem[i] = s[i]; } count = n;}
Set::Set(const Set &other){ if(other.elem == NULL) { cout << "other object is empty!~!" <<endl; exit(1); } else { elem = new int[other.count]; if(elem == NULL) { cout << "Memory assign failure!!" << endl; exit(1); } for(int i =0; i < other.count; ++i) { elem[i] = other.elem[i]; } count = other.count; }}
Set& Set::operator =(const Set &other){ if(this == &other) { return *this; } delete[] elem; elem = new int[other.count]; if(elem == NULL) { cout << "Memory assign failure!!" << endl; exit(1); } for(int j = 0; j < other.count; ++j) { elem[j] = other.elem[j]; } count = other.count; return *this;}
int Set::find(int x) const{ if(elem == NULL) { cout << "The set now is empty!!/n" << endl; exit(1); } else { for(int i = 0; i < count; ++i) { if(x == elem[i]) { return 1; } } return 0; }}/*Set operator+(const Set& A, const Set &B){ if(A.elem == NULL && B.elem != NULL) { return Set(B.elem, B.count); } else if(B.elem == NULL) { return A; } else { int length = 0; InsertSort(A.elem, A.count); InsertSort(B.elem, B.count); int *array1 = new int[A.count + B.count]; if(array1 == NULL) { cout << "Memory assign failure~~"<< endl; exit(1); } MergePlus(array1,A.elem, B.elem, A.count, B.count, &length); Set temp(array1, length);//构造临时对象 //temp.count = length; //temp.elem = new int[length]; //memcpy(temp.elem, array1, length * sizeof(*array1)); delete[]array1; array1 = NULL; return temp; }}*/Set Set::operator+(const Set &other){ if(this == NULL && other.elem != NULL) { return Set(other.elem, other.count); } else if(other.elem == NULL) { return *this; } else if(this == &other) //判断两个集合相等 { return *this; } else { int length = 0; InsertSort(this->elem, count); InsertSort(other.elem, other.count); int *array1 = new int[this->count + other.count]; if(array1 == NULL) { cout << "Memory assign failure~~"<< endl; exit(1); } MergePlus(array1,this->elem, other.elem, this->count, other.count, &length); Set temp(array1, length); //temp.count = length; //构造临时对象 //temp.elem = new int[length]; //memcpy(temp.elem, array1, length * sizeof(*array1)); delete[]array1; array1 = NULL; return temp; }}
Set Set::operator-(const Set &other){ if(this == NULL && other.elem != NULL) { return Set(other.elem, other.count); } else if(other.elem == NULL) { return *this; } else if(this == &other) //判断两个集合相等 { return *this; } else { int length = 0; InsertSort(this->elem, count); InsertSort(other.elem, other.count); int *array1 = new int[this->count + other.count]; if(array1 == NULL) { cout << "Memory assign failure~~"<< endl; exit(1); } MergeCut(array1,this->elem, other.elem, this->count, other.count, &length); Set temp(array1, length); delete[]array1; array1 = NULL; return temp; }}
Set Set::operator*(const Set &other){ if(this == NULL && other.elem != NULL) { return Set(other.elem, other.count); } else if(other.elem == NULL) { return *this; } else if(this == &other) //判断两个集合相等 { return *this; } else { int length = 0; InsertSort(this->elem, count); InsertSort(other.elem, other.count); int *array1 = new int[this->count + other.count]; if(array1 == NULL) { cout << "Memory assign failure~~"<< endl; exit(1); } MergeCross(array1,this->elem, other.elem, this->count, other.count, &length); Set temp(array1, length); delete[]array1; array1 = NULL; return temp; }}void Set::disp(){ for(int i = 0; i < count; ++i) { cout << elem[i]<< ", "; if((i+1) % 11 == 0) { cout << endl; } } cout << endl;}int main(){ int Setobj1[] = {1,3,4,5,6,7}; int Setobj2[] = {2,4,5,8,9,0};
int len1 = sizeof(Setobj1)/ sizeof(int); int len2 = sizeof(Setobj2)/ sizeof(int);
Set SetA(Setobj1, len1); Set SetB(Setobj2, len2); cout << "The Set A is :" << endl; SetA.disp(); cout << "The Set B is :" << endl; SetB.disp(); cout<< endl; Set SetAplusB; SetAplusB = (SetA + SetB); cout << "The Set A plus Set B is : " << endl; SetAplusB.disp(); cout <<endl; Set SetCut; SetCut = (SetA - SetB); cout << "The Set A Cut Set B is : " << endl; SetCut.disp(); cout << endl; Set SetCross; SetCross = (SetA * SetB); cout << "The Set A Cross Set B is : " << endl; SetCross.disp(); cout << endl;
int key; cout << "Input the key to serch " << endl; cin>>key; if(SetAplusB.find(key)) { cout << "Success !!" << endl; } else { cout << "No found!!" << endl; } return 0;}/*The Set A is :1, 3, 4, 5, 6, 7,The Set B is :2, 4, 5, 8, 9, 0,
The Set A plus Set B is :0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
The Set A Cut Set B is :0, 1, 2, 3, 6, 7, 8, 9,
The Set A Cross Set B is :4, 5,
Input the key to serch4Success !!请按任意键继续. . .*/