Enter Type Of Stack (1 – ImitationStack, 2 – TrueStack, 3 – PooledStack) 3 Enter Count Of Elements For Test 10000 Enter Count Of Iterations 20 Time Was Taken About 20 sec.
| « Структуры данных и алгоритмы. Практика. Рекурсия и исключения | Структуры данных и алгоритмы. Практика. Двунаправленные динамические списки и общие принципы проектирования контейнеров » |
Структуры данных и алгоритмы. Практика. Динамические структуры данных. Основы
Данная работа посвящена созданию и использованию контейнеров – классов которые служат для хранения и управления множеством объектов.1) Необходимо создать иерархию классов. В корне данной иерархии должен находиться абстрактный класс “GenericStack”. Интерфейс которого должен содержать следующие чисто виртуальные (pure-virtual) методы:
- push – данный метод должен вызываться когда нам необходимо поместить в стек еще один элемент.
Примечание: практически каждая операция с динамическими структурами данных может быть завершена не успешно. Поэтому я рекомендую предусмотреть и реализовать модель классов или структур, которые описывали бы иерархию исключений выбрасываемых методами класса GenericStack при возникновении ошибочных ситуаций.
- pop – данный метод служит только для извлечения элемента из стека (его удаления);
- top – этот метод класса должен возвращать значение последнего помещенного в стек элемента без его удаления.
- обязательным является определение деструктора (также обязательно виртуального).
Примечание 1: то что мы создали это заготовка для стека: в созданном нами классе не выполняется никаких реальных действий по выделению памяти, ее освобождению, не выполняется добавление и удаление элементов из стека. Мы, по сути, спроектировали только интерфейс будущего класса.
Примечание 2: при проектировании класса GenericStack создайте его в виде шаблона.
2) Опираясь на созданный в первом задании абстрактный класс вам необходимо создать небор классов реализующих конкретную дисциплину хранения элементов в стеке.
- первым классом который вы создадите будет класс ImitationStack он должен быть производен от GenericStack. Данный класс будет обманом пользователя, он будет только имитировать работу стека, храня все данные в статически создаваемом массиве. Примечание: нечто подобное я приводил в методическом пособии,
только там был стек для конкретного типа данных int. Вам же следует создаваемый класс оставить шаблонным.
- Следующий класс который вы создадите будет реально работать с памятью. Назовем класс “TrueStack”. Стек должен быть представлен в виде цепочки узлов. Добавление нового узла будет выполняться всякий раз, когда мы добавляем новый элемент. Соответственно всякий раз, когда мы удаляем элемент для верхнего элемента стека, должен вызываться оператор освобождения памяти delete. Также как и в предыдущем задании класс должен остаться шаблонным.
- И последний класс который вы должны создать это класс стека в котором идет оптимизация работы с памятью за счет создания и использования пула памяти. Также как и в предыдущем задании класс должен остаться шаблонным. Класс назовем “PooledStack”.
3) после того как вы создали иерархию классов стеков. Создадим такую функцию main в которой у пользователя при запуске программы должно спрашиваться с каким именно видом стека он хочет работать. После того как он выбрал вид стека. Программа должна запросить количество элементов которые он хочет добавить в стек “X” и количество итераций “Y”. После этого должен быть создан соответствующий экземпляр стека и в него указанное количество раз (количество итераций “Y”) необходимо поместить “X” элементов и извлечь их (элементами будут случайные числа, распределенные по нормальному закону с характеристиками Мат. ожидание=50, Дисперсия=20). Время выполнения алгоритма необходимо измерить. Пример диалога программы с пользователем приводится ниже:
a) EstackInvalidParameters - данное исключение следует генерировать в том случае, когда параметры конструктора стека были заданы неверно (например, для PooledStack, начальный размер или дельта прироста пула были заданы отрицательными).
b) EstackOverflow – при попытке добавить еще один элемент в стек, в котором закончилось место, а стек не обладает способностью выделить для себе еще ресурсов памяти.
c) EstackUnderflow - при попытке извлечения элемента из любого вида стека если в нем уже закончились данные.
d) EstackOutOfMemory - в том случае когда стек выделяет память для себя самостоятельно, и при этом в силу непредвиденных сложностей операционная система не смогла нам выделить запрошенный ресурс.
Примечание: после того как вы вызвали оператор new в случае нехватки ресурсов возвращаемое значение
char * ptr = new char [1000000].
| « Структуры данных и алгоритмы. Практика. Рекурсия и исключения | Структуры данных и алгоритмы. Практика. Двунаправленные динамические списки и общие принципы проектирования контейнеров » |