АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

229. Шаблонный класс "множество"

Ограничение времени: 3 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Неизвестный

Напишите шаблонный класс Set для представления АТД "множество" на основе рандомизированного двоичного дерева, хеш-таблицы или другой структуры, обеспечивающей требуемую производительность (использование класса std::set не допускается). Интерфейс класса должен выглядеть следующим образом:

template <class T>
class Set {
  //закрытые данные (какие считаете нужными)
public:
  
  //конструкторы (если нужны)
  Set(); 
  Set(const Set &s);
  
  //вставка элемента в множество
  Set operator + (const T &t) const;
  friend Set operator + (const T &t, const Set &s);
  Set &operator += (const T &t);

  //удаление элемента из множества
  Set operator - (const T &t) const;
  Set &operator -= (const T &t);
  
  //проверка наличия элемента в множестве
  bool exists(const T &t) const;

  //объединение множеств
  Set operator + (const Set &s) const;
  Set& operator += (const Set &s);

  //разность множеств
  Set operator - (const Set &s) const;
  Set& operator -= (const Set &s);

  //операции сравнения
  bool operator == (const Set &s) const;
  bool operator != (const Set &s) const;

  //мощность множества (число элементов)
  int size(void) const;

  //вывод элементов в порядке возрастания, разделяя их пробелом
  friend ostream& operator << (ostream& os, const Set &s) {
    //поместите соответствующий код сюда
  }

  //операция присваивания (если нужна)
  Set &operator = (const Set &s);

  //деструктор (если нужен)
  ~Set();

};

Гарантируется, что для шаблонного типа T определены операции сравнения < и ==.

В проверяющую систему отправляется полная реализация класса без какого-либо дополнительного кода. В том числе ваша программа не должна содержать функцию main! Вместо этого в конце программы поставьте строчку:

#include "set-test.h"

Тем самым вы подключите функцию main (её текст вам недоступен), которая и будет тестировать ваш класс.


Гарантируется, что корректная реализация на базе рандомизированного двоичного дерева поиска проходит все тесты, укладываясь в отведенное время и память.


Пример некоторых проверок, которые могут выполняться над вашим классом:

int main(void)
{
  Set<int> a;
  for (int i=50; i>=0; i--) a+=i;
  for (int i=0; i<=50; i+=2) a-=i;
  for (int i=0; i<=50; i+=3) a-=i;
  cout << a << endl;
  Set<int> b = ((a + 999)+9999) - 89;
  cout << b.size() << endl;
  cout << b.exists(1) << b.exists(2)
    << b.exists(3) << b.exists(4)
    << b.exists(5) << endl;
  Set<int> *c = new Set<int>;
  *c +=1; *c +=5; *c +=6;
  cout << c->size() << endl;
  cout << a-*c << endl;
  *c += 1111;
  cout << a+*c << endl;
  delete c;
  return 0;
}

Правильный результат:

1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
19
10001
3
7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
1 5 6 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 1111

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Учебные курсы / Программирование на языке высокого уровня / Лабораторная 5 /
229.
 
время генерации 0.109 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.