Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <conio.h>
- #include <assert.h>
- using namespace std;
- /*
- * Реализация класса множеств, перегрузка операторов.
- *
- * *****
- * 29.05.2011
- **/
- //Формат комментариев функций: [возвращаемая информация] [входящая информация] [задача функции]
- struct element
- {
- int v;
- struct element * next;
- };
- //Класс "множество"
- class set
- {
- public:
- set():power(0),rear(NULL){};
- set(const set & s);
- set(int p);
- set(int * a, int sz);
- ~set();
- friend ostream & operator <<(ostream & out, const set & s);
- set & operator --(); //prefix
- set & operator --(int); //postfix
- operator int() { return power; }
- short operator == (const set & s) const;
- set & operator = (const set & s);
- friend set operator +(int el, const set & s);
- set operator +(const int el) const;
- set operator +(const set & s)const;
- set operator -(const int el) const;
- set operator -(const set & s2) const;
- set operator & (const set & s2)const;
- set operator ^ (const set & s)const;
- short operator < (const set & s) const;
- short operator > (const set & s) const { return (s < *this);}
- short operator < (int el) const;
- set & operator += (const int el);
- set & operator += (const set & s);
- set & operator -= (const set & s);
- set & operator -= (const int el);
- set & operator &= (const set & s);
- set & operator ^= (const set & s);
- private:
- int power;
- struct element * rear;
- void push(int val);
- struct element * contains(int v) const;
- void delEl(struct element * p);
- };
- void set::push(int val)
- {
- struct element * newEl = new element;
- newEl->v = val;
- power++;
- if (rear) //если список не пустой
- {
- newEl->next = rear->next;
- rear->next = newEl;
- rear = newEl;
- }
- else //если список пустой, закольцовываем его
- {
- newEl->next = newEl;
- rear = newEl;
- }
- }
- set set::operator ^(const set &s) const //TEST
- {
- if (power==0) //если одно из множеств пустое, симм. разность будет равна другому мн-ву
- return s;
- if (s.power == 0)
- return *this;
- set newS;
- if (*this == s) //если множества равны, симм.разность равна пустому мн-ву.
- return newS;
- newS = (*this);
- newS = newS + (*this);
- newS^=s;
- return newS;
- }
- set::set(int * a, int sz):power(0),rear(NULL) //конструктор, изымающий множество из массива
- {
- push(a[0]);
- for (int i=1; i<sz; i++)
- {
- if (!contains(a[i]))
- push(a[i]);
- }
- }
- struct element * set::contains(int val) const //ищет элемент в множестве и возвращает указатель на него
- {
- if (!rear)
- return 0;
- struct element * p = rear;
- do
- {
- if (p->v == val)
- return p;
- p = p->next;
- } while (p != rear);
- return NULL;
- }
- void set::delEl(struct element * p)
- {
- power--;
- delete p;
- }
- set::set(const set & s):power(0),rear(NULL) //копирующий конструктор
- {
- if (s.rear)
- {
- struct element * p = s.rear->next;
- do
- { //почленное копирование
- push(p->v);
- p = p->next;
- } while (p != s.rear->next);
- }
- }
- set::~set()
- {
- if (power) //если содержит элементы, значит есть что удалять
- {
- struct element * p;
- do //удаляем последовательно все элементы
- {
- p = rear->next;
- rear->next = p->next;
- delEl(p);
- } while (power);
- }
- }
- ostream & operator <<(ostream & out, const set & s)
- {
- if (s.power == 0) //пусто
- {
- out<<"Empty set"<<endl;
- return out;
- }
- int i; //не пусто
- struct element * p = s.rear->next;
- out<<"power["<<s.power<<"]"<<endl;
- do
- {
- out<<p->v<<" "; //последовательный вывод значений эл-в мн-ва через пробел
- p = p->next;
- } while (p != s.rear->next);
- out<<endl;
- return out;
- }
- set & set::operator --() //удаление первого элемента
- {
- struct element * p = rear->next;
- rear->next = p->next;
- delEl(p);
- return (*this);
- }
- set & set::operator --(int) //удаление последнего элемента
- {
- *this -= rear->v;
- return (*this);
- }
- short set::operator == (const set & s) const
- {
- if (power != s.power) //если мощности множеств не равны, множества не равны
- return 0;
- if (power == 0) //два пустых множества равны
- return 1;
- struct element * p = s.rear;
- do //пробег по всем элементам одного множества
- {
- if (!contains(p->v)) //если во втором множестве не содержится такого элемента,
- return 0; //то множества не равны
- p = p->next;
- } while (p != s.rear);
- return 1; //иначе - равны.
- }
- set & set::operator = (const set & s) //присваивание
- {
- if (s == *this)
- return *this;
- if (s.power == 0)
- {
- delete this;
- power=0;
- return *this;
- }
- int i = 0, min=(power<s.power?power:s.power); //i - счетчик, max - минимальная мощность двух множеств.
- struct element *p = (power?rear->next:NULL), *p2 = s.rear->next; //р2 - указатель на эл-т присваивоемого мн-ва, р - указатель на элемент другого мн-ва.
- for (i = 0; i < min; i++) //копируем все, что влазит
- {
- p->v = p2->v;
- p = p->next;
- p2 = p2->next;
- }
- if (power < s.power) //если не влазит, добавляем
- {
- for (;i < s.power; i++)
- {
- push(p2->v);
- p2 = p2->next;
- }
- }
- else //если остается лишнее место, удаляем
- {
- while (power != s.power)
- (*this)--;
- }
- power=s.power;
- return *this;
- }
- set operator +(int el, const set & s) //элемент+множество
- {
- set newS(s); //копируем множество
- if (!newS.contains(el))
- {
- newS.push(el); //добавляем в конец
- struct element *p = newS.rear; //и притворяемся, что это - начало.
- while(p->next != newS.rear)
- p = p->next;
- newS.rear = p;
- }
- return newS;
- }
- set set::operator +(const int el)const
- {
- set newS = *this;
- if (!newS.contains(el))
- newS.push(el);
- return newS;
- }
- set set::operator +(const set & s)const //сложение(объединение)множеств
- {
- if (*this == s || s.power == 0)
- return *this;
- if (power == 0)
- return s;
- set newS;
- struct element *p2 = s.rear->next; //р2 - указатель на правое множество ((левое_множество+правое_множество))
- int i = 0;
- if (power >= s.power) //маленькая оптимизация
- {
- newS = *this; //копируем большее множество
- do //и добавляем в него элементы меньшего
- {
- newS+=p2->v;
- p2 = p2->next;
- } while (p2 != s.rear->next);
- }
- else
- {
- return (s+(*this));
- }
- return newS;
- }
- set set::operator -(const int el) const
- {
- set newS; //создаем пустое множество
- struct element *p = rear->next;
- do //и копируем внего все элементы множества-уменьшаемого
- { //за исключением эквивалентного элементу
- if (p->v != el)
- newS.push(p->v);
- p = p->next;
- } while (p != rear->next);
- return newS;
- }
- set set::operator -(const set & s2) const //разность множеств
- {
- if (s2.power == 0) //если вычитаемое пусто, разность равна вычитаемому
- return *this;
- set newS;
- if (((power == s2.power) && (*this == s2)) || power == 0) //если мн-ва равны (или уменьшаемое пусто), возвращаем пустое множество
- {
- return newS;
- }
- struct element *p = rear->next;
- int i;
- do //Для всех элементов уменьшаемого множества:
- {
- if (!s2.contains(p->v)) //если эл-т не содержится в вычитаемом множестве, добавляем его в разность.
- newS.push(p->v);
- p = p->next;
- } while (p != rear->next);
- return newS;
- }
- set set::operator & (const set & s2)const //пересечение множеств
- {
- if ((power == s2.power)&&(*this == s2)) //если множества равны, возращаем любое из них
- return *this;
- set spike; set spike2; set newS;
- if ((power == 0) || (s2.power == 0)) //если одно из множеств пусто, возвращаем пустое множество
- return newS;
- struct element *p = rear->next;
- if (power <= s2.power) //небольшая оптимизация
- {
- do
- {
- if (s2.contains(p->v)) //если элемент одного множества содержится в другом, добавляем его в результирующее мн-во
- newS.push(p->v);
- p = p->next;
- } while( p != rear->next);
- }
- else
- {
- newS = s2 & *this;
- }
- return newS;
- }
- set & set::operator += (const int el)
- {
- if (power == 0 || !contains(el)) //добавляем эл-т в мн-во
- push(el);
- return *this;
- }
- set & set::operator +=(const set & s) //добавление множества в множество
- {
- if (*this > s) //если добавляемое множество является подмножеством, делаем ничего.
- return *this;
- struct element *p = s.rear->next;
- do //добавляем все элементы множества
- {
- *this += p->v;
- p = p->next;
- } while (p != s.rear->next);
- return *this;
- }
- set & set::operator -=(const int el) //изъятие эл-та из мн-ва
- {
- struct element *p = contains(el);
- if (p==NULL || power == 0)
- return *this; //из пустого множества не получится изъять. Так же не изъять то, чего нет.
- if ((power == 1) & (p != NULL)) //если единственный элемент
- {
- delEl(rear);
- rear = NULL;
- return *this;
- }
- if (p == rear) //если конечный элемент
- {
- do
- {
- p = p->next; //приходится заморачиваться с изменением указателя на хвост
- } while (p->next != rear);
- p->next = rear->next;
- delEl(rear);
- rear = p;
- }
- else
- {
- struct element *tmp = p->next;
- p->v = p->next->v;
- p->next = p->next->next; //просто вынимаем элемент из списка
- if (tmp == rear)
- rear = p;
- delEl(tmp);
- }
- return *this;
- }
- set & set::operator -=(const set & s) //вычесть множество из множества
- {
- if (s.power == 0) //из пустого множества не вычесть
- return *this;
- struct element *p = s.rear->next;
- do //вычесть каждый член вычитаемого множества из уменьшаемого множества
- {
- *this-=p->v;
- p = p->next;
- } while (p != s.rear->next);
- return *this;
- }
- set & set::operator &= (const set & s) //пересечение с изменением
- {
- if (s.power == 0 || power == 0 || (power == s.power && *this == s)) //если изменений нет, возвратить без изменений
- return *this;
- if (*this < s) //если является подмножеством, изменений нет
- return *this;
- int i = 0;
- struct element *p = rear->next,*res,*tmp,*del; //res - результирующий список элементов
- res = NULL; //tmp - для swap'a;
- del = NULL; //del - удаляемые элементы
- do //проверяем все элементы изменяемого множества по очереди
- {
- if (s.contains(p->v)) //если элемент содержится во втором множестве
- { //то он идет в результирующий список
- tmp = res;
- res = p;
- p = p->next;
- res->next = tmp;
- i++;
- }
- else
- {
- tmp = del; //иначе - удаляется
- del = p;
- p = p->next;
- del->next = tmp;
- }
- power--;
- } while (power && p);
- p = del;
- while (p && p->next) //удаляем все неводшедшие в пересечение элементы
- {
- tmp = p->next;
- delEl(p);
- p = tmp;
- }
- delEl(p);
- p = res;
- power = i;
- if (p)
- {
- while (p->next) //находим конец результирующего списка - и замыкаем его.
- p = p->next;
- p->next = res;
- }
- rear = p; //и обновляем данные в результирующем множестве.
- return *this;
- }
- set & set::operator ^= (const set & s)
- {
- if (s.power == 0 || power == 0) //если изменений нет, возвращаем сразу
- return *this;
- if (*this == s) //если множества равны, удаляем все элементы
- {
- struct element *p;
- do{
- p = rear->next;
- delEl(rear);
- rear = p;
- } while (power);
- rear = NULL;
- return *this;
- }
- struct element *p = s.rear;
- do //каждый элемент, содержащийя в обоих множествах удаляется
- { //каждый элемент, содержащийся только в правом множестве добавляется в левое
- if (contains(p->v))
- (*this)-=(p->v);
- else
- (*this)+=(p->v);
- p = p->next;
- } while (p != s.rear);
- return *this;
- }
- short set::operator < (const set & s) const
- {
- if (power>s.power) //если мощность правого множества больше мощности левого, оно не может быть подмножеством.
- return 0;
- if (power == 0) //пустое множество - подмножество любого множества
- return 1;
- struct element * p = rear->next;
- do
- {
- if (!s.contains(p->v)) //если хотя бы один элемент левого мн-ва не принадлежит к правому мн-у, левое мн-во не
- return 0; //является подмножеством правого
- p = p->next;
- } while (p != rear->next);
- return 1; //иначе - является.
- }
- short set::operator < (int el) const //принадлежность элемента множеству
- {
- if (contains(el))
- return 1;
- else
- return 0;
- }
- void doSomething()
- {
- int ar[]={1,2,3,4},br[]={1,5,6,7,8,9},cr[]={1,4,9};
- set a(ar,4);
- set b(br,6);
- set c(cr,3);
- /*
- cout<<"Enter 4 elements for set a"<<endl;
- set a(4);
- cout<<"Enter 6 elements for set b"<<endl;
- set b(6);
- cout<<"Enter 3 elements for set c"<<endl;
- set c(3);
- */
- cout<<"Set d will be empty"<<endl;
- set d;
- cout<<"Lets make new set j = a"<<endl;
- set j;
- j = a;
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d<<"Set j:"<<j;
- cout<<"a+b=";
- cout<<"="<<(a+b);
- cout<<"a+a="<<(a+a);
- cout<<"d+c="<<(d+c);
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
- cout<<"b-c="<<(b-c);
- cout<<"d-a="<<(d-a);
- cout<<"c-d="<<(c-d);
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
- cout<<"Enter x. Then we will do b-x, x+a and c+x"<<endl;
- int x;
- cin>>x;
- cout<<"b-"<<x<<"="<<(b-x);
- cout<<x<<"+a"<<"="<<(x+a);
- cout<<"c+"<<x<<"="<<(c+x);
- if (b==b)
- cout<<"b==b"<<endl;
- else
- cout<<"b!=b"<<endl;
- if (d==a)
- cout<<"d==a"<<endl;
- else
- cout<<"d!=a"<<endl;
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
- cout<<"Now let's do c-- and --c"<<endl;
- cout<<"c-- = "<<(c--);
- cout<<"--c = "<<(--c);
- if (b<x)
- cout<<"b<x"<<endl;
- else
- cout<<"b!<x"<<endl;
- if (c<x)
- cout<<"c<x"<<endl;
- else
- cout<<"c!<x"<<endl;
- if (d<a)
- cout<<"d<a"<<endl;
- else
- cout<<"d!<a"<<endl;
- if (b>c)
- cout<<"b>c"<<endl;
- else
- cout<<"b!>c"<<endl;
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
- cout<<"Now lets make set e=a&b"<<endl;
- set e = a&b;
- cout<<"Set e:"<<e;
- cout<<"e^a="<<(e^a);
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d<<"Set e:"<<e;
- cout<<"Enter new x. We will c+=x; b-=x."<<endl;
- cin>>x;
- cout<<"c+=x = "<<(c+=x);
- cout<<"b-=x = "<<(b-=x);
- cout<<"c+=a = "<<(c+=a);
- cout<<"b-=e = "<<(b-=e);
- cout<<"a^=b = "<<(a^=b);
- cout<<"c&=e = "<<(c&=e);
- cout<<"b&=(a-9) = "<<(b&=(a-9));
- cout<<"---------------------------------------------"<<endl;
- cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d<<"Set e:"<<e;
- cout<<"a^=a = "<<(a^=a);
- cout<<"That's all."<<endl;
- getch();
- }
- int main()
- {
- //doSomething();
- set a,b;
- a+=1;
- a+=2;
- b+=3;
- b+=2;
- cout<<"+"<< (a + b) <<endl;
- //cout<<"+="<< (a+=b) <<endl;
- cout<<"-"<< (a - b) <<endl;
- cout<<"a:"<<a<<"b:"<<b;
- cout<<"^"<< (a ^ b) <<endl;
- cout<<"&"<< (a & b) <<endl;
- cout<<"end.";
- cout<<"^="<<(b^=a)<<endl;
- getch();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement