C++写的集合的交叉并

    技术2022-05-14  1

    #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 !!请按任意键继续. . .*/


    最新回复(0)