Personal Assignment #3 Containers. Abstaract Data Types. - xivol/AM-PRO2-2016 GitHub Wiki

##Указания к выполнению Каждый класс должен быть объявлен и описан в собственном файле. Для вспомогательных классов (узел списка, дерева) заводить отдельный файл не обязательно.

Реализация каждого класса должна содержать:

  • конструтор по умолчанию;
  • деструктор;
  • конструтор копии;
  • операцию присваивания.

В ходе работы программы должна происходить проверка отсутствия утечек памяти (например, при помощи crtdbg) и обработка возможных исключений.

Правильная реализация АТД шаблонами дает дополнительные баллы. ##Варианты

  1. Матрица на базе вектора
  2. Куча на базе динамического массива
  3. Разреженный массив на базе двусвязного списка
  4. Множество на базе двусвязного списка
  5. Ассоциативный массив на базе двусвязного списка
  6. Множество с повторениями на базе двоичного дерева
  7. Разреженный массив на базе двоичного дерева
  8. Ассоциативный массив на базе двоичного дерева
  9. Куча на базе двоичного дерева
  10. Граф на базе списка смежности

##1. Матрица на базе вектора Класс должен содержать следующие методы:

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

Для класса необходимо перегрузить следующие операции:

  • operator[] - обращения к элементам;
  • сложение, вычитание матриц;
  • умножение матрицы на число, вектор, матрицу;
  • операторы сравнения на равенство/неравенство;
  • ввод/вывод в поток.

Используя матрицу вещественных чисел решить задачу: Дана невырожденная квадратная матрица. Найти обратную к ней, выполнить проверку.

##2. Куча на базе динамического массива Двоичная куча – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению). Класс должен содержать следующие методы:

  • добавление значения в кучу;
  • получить максимум в куче;
  • извлечение максимума из кучи;
  • замена значения в куче.

Для класса необходимо перегрузить следующие операции:

  • operator<< - добавление значения в кучу;
  • operator>> - извлечение максимума из кучи;
  • operator+ - слияние двух куч;
  • ввод/вывод в поток.

Используя кучу целых чисел решить задачу: Реализовать метод пирамидальной сортировки для массива целых чисел.

##3. Разреженный массив на базе двусвязного списка Разрежённый массив — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимают одно и то же значение (значение по умолчанию, обычно 0 или null). Полезные данные хранятся в структуре индекс-значение, для всех остальных элементов возвращается значение по умолчанию.

Класс должен содержать поля:

  • размер массива;
  • значение элемента по умолчанию.

Класс должен содержать методы:

  • получение длины массива;
  • получение количества не пустых элементов;
  • вывод не пустых элементов массива;
  • доступ по итератору к не пустым элементам массива.

Для класса необходимо перегрузить следующие операции:

  • operator[] - доступа к элементам;
  • ввод/вывод в поток.

Используя разреженный массив вещественных чисел решить задачу: Дан массив вещественных чисел большого размера (ULONG_MAX) и двоичный файл, содержащий положительные целые числа в диапазоне 0..ULONG_MAX-1. Посчитать частоту вхождений каждого целого числа в файле.

##4. Множество на базе двусвязного списка Множество — абстрактная структура данных, которая позволяет хранить значения определённого типа без определённого порядка и без повторений.

Класс должен содержать следующие методы:

  • добавление элемента в множество;
  • исключение элемента из множества;
  • проверка множества на пустоту;
  • поиск элемента во множестве.

Для класса необходимо перегрузить следующие операции:

  • operator+= - добавление элемента;
  • operator-= - исключение элемента;
  • operator- - исключение множества;
  • operator&& - пересечение множеств;
  • ввод/вывод в поток.

Используя множество символов решить задачу: Даны два текстовых файла. Вывести все символы которые встречаются в первом файле и не встречаются во втором.

##5. Ассоциативный массив на базе двусвязного списка Ассоциативный массив — абстрактный тип данных, позволяющий хранить пары вида (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу. В узле списка хранится ключ и значение, связанное с ним. Для ускорения поиска по ключу, необходимо хранить список упорядоченным по значению ключа.

Класс должен содержать методы:

  • проверка наличия заданного ключа в массиве;
  • добавление значения для заданного ключа;
  • удаление ключа из массива;
  • подсчет количества элементов.

Для класса необходимо перегрузить следующие операции:

  • operator[] - обращение к элементу массива;
  • ввод/вывод в поток.

Используя ассоциативный массив строк решить задачу: Дан список текстовых файлов. Вывести количество слов.

##6. Множество с повторениями на базе двоичного дерева Множество — абстрактная структура данных, которая позволяет хранить значения определённого типа без определённого порядка. В узле дерева хранится значение и количество раз, сколько это значение содержится во множестве.

Класс должен содержать методы:

  • проверка наличия элемента во множестве;
  • добавление элемента во множество;
  • удаление элемента из множества;
  • подсчет количества элементов;
  • подсчет суммарного количества элементов.

Для класса необходимо перегрузить следующие операции:

  • operator+= - добавление элемента;
  • operator-= - исключение элемента;
  • operator|| - объединение множеств;
  • операторы сравнения множеств на равенство/ неравенство;
  • ввод/вывод в поток.

Используя частотный словарь символов решить задачу: Дан текстовый файл. Посчитать количество вхождений каждого символа, исключая пробелы и знаки препинания.

##7. Разреженный массив на базе двоичного дерева Разрежённый массив — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимают одно и то же значение (значение по умолчанию, обычно 0 или null). Полезные данные хранятся в структуре индекс-значение, для всех остальных элементов возвращается значение по умолчанию.

Класс должен содержать поля:

  • размер массива;
  • значение элемента по умолчанию.

Класс должен содержать методы:

  • получение длины массива;
  • получение количества не пустых элементов;
  • доступ по итератору к не пустым элементам массива.

Для класса необходимо перегрузить следующие операции:

  • operator[] - доступа к элементам;
  • ввод/вывод в поток.

Используя разреженный массив целых чисел решить задачу: Почитать частоту выпадения различных значений функции rand() для N вызовов. Результат сохранить в файл.

##8. Ассоциативный массив на базе двоичного дерева Ассоциативный массив — абстрактный тип данных, позволяющий хранить пары вида (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу.

Класс должен содержать методы:

  • проверка наличия заданного ключа в массиве;
  • добавление значения для заданного ключа;
  • удаление ключа из массива;
  • подсчет количества элементов.

Для класса необходимо перегрузить следующие операции:

  • operator[] - обращение к элементу массива;
  • ввод/вывод в поток.

Используя разреженный массив целых чисел решить задачу: Даны два текстовых файла, вычислить их «похожесть». Посчитать частоту слов в первом и втором файлах. Сравнить первые K наиболее часто встречающихся слов.

##9. Куча на базе двоичного дерева Двоичная куча – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с минимальным приоритетом (например, минимальным по значению). Класс должен содержать следующие методы:

  • добавление значения в кучу;
  • получить минимум в куче;
  • извлечение минимума из кучи;
  • замена значения в куче.

Для класса необходимо перегрузить следующие операции:

  • operator<< - добавление значения в кучу;
  • operator>> - извлечение минимума из кучи;
  • operator+ - слияние двух куч;
  • ввод/вывод в поток.

Используя кучу вещественных чисел решить задачу: Дан массив вещественных чисел и целое число K. Найти K-ый минимальный элемент в массиве.

##10. Граф на базе списка смежности Графом называется структура, состоящая из вершин и дуг их соединяющих. Одним из вариантов представления графа, является список смежности.

Класс должен содержать следующие методы:

  • добавление вершины;
  • добавление дуги;
  • удаление вершины;
  • удаление дуги;
  • проверка связи двух вершин дугой;
  • подсчет количества вершин;
  • подсчет количества дуг;
  • проверка связности графа;
  • вычисление степени вершины с заданным номером.

Для класса необходимо перегрузить следующие операции:

  • сравнение графов на равенство/ неравенство;
  • ввод/ вывод в поток.

Используя граф решить задачу: Дан неориентированный граф. Проверить что на нем существует Эйлеров путь.