« Структуры данных и алгоритмы. Практика. Динамические структуры данных. Основы Структуры данных и алгоритмы. Практика. Контейнеры »

Структуры данных и алгоритмы. Практика. Двунаправленные динамические списки и общие принципы проектирования контейнеров

January 18, 2007



1) Необходимо создать класс MultiDimensionalMatrix который будет являться представлением многомерного массива, количество размерностей которого заранее не известно.

Пример кода для создания данного контейнера: 
  1. MultiDimensionalMatrix matr (1,2,4,7,0);
В качестве подсказки я напоминаю вам что конструктор – это обычная функция C/C++, а мы когда-то упоминали о передачах функциям произвольного количества параметров с помощью “...”.

Внутреннее устройство я рекомендую построить на основе обычного одномерного массива имеющего размер 
 Size = Dimension1 * Dimension2 * … * DimensionN.
Для доступа к элемента необходимо выполнить перегрузку оператора “[]”. В качестве входного параметра для данного оператора используйте решение Элджера – вспомогательную структуру Index (на лекции я рассматривал этот прием перед приемом с классом-посредником).

Пример окончательного кода по применению данного массива: 
  1. /*
  2.    0 - выступает в роли завершающего значения т.к. 
  3.    не может быть так, чтобы какая либо размерность оказалась бы равной нулю.
  4.  */
  5.  MultiDimensionalMatrix matr (1,2,4,7,0); 
  6.  
  7.  /*
  8.    при индексации элементов список индексов 
  9.    не может содержать отрицательных величин поэтому их можно использовать
  10.    как специально оговоренный ограничитель последовательности индексов.
  11.  */
  12.  matr [Index (1, 1 , 1 , 1 , -1)] = 5;
  13. cout << matr [Index (1, 1 , 1 , 1 , -1)];
2) Данное задание является дальнейшим развитем задания из предыдущих лабораторных работ со стеком. Вам необходимо создать надстройку над классом PooledStack – назовем потомка, например, IterablePooledStack.

3) Данный класс должен обладать способностью к просмотру всех помещенных внутрь него элементов с помощью итераторов. Создайте вложенную структуру PooledStackIterator и выполните перегрузку для него всех необходимых операторов. А теперь внимание: мы должны сделать так, что все итераторы, которые были запрошены нашей программой, отслеживали состояние стека. И после того, как он изменил свой размер или был добавлен/удален какой-либо из элементов, должны становиться не действительными. Так при вызове любого из вышеописанных операторов должно выбрасываться исключение “error_invalid_iterator_state”. Для отслеживания действительности итераторов воспользуйтесь методом временных отметок. Добавьте в состав класса IterablePooledStack дополнительное поле TimeStamp которое должно быть равно моменту времени когда была проведена последняя модификация стека. Каждый из создаваемых нами итераторов должен хранить внутри себя не только служебную информацию о позиции текущего элемента на который он указывает но и время стека на момент создания итератора. Внимание, критически важно: дискретность системного таймер слишком велика чтобы мы могли полагаться на текущее время при съеме показаний о времени стека, более нам необходимо ввести условное время. Подумайте и сообщите мне какие у вас есть идеи как можно ввести (определить) понятие “время стека”.

4) Необходимо создать класс Deque который и реализует дисциплину дека. Класс должен быть шаблонным. В состав класса необходимо ввести следующие методы:
  • push_back () – добавление нового элемента в конец дека;
  • push_front () - добавление нового элемента в начало дека;
  • pop_back () – удаление элемента с конца дека;
  • pop_front () – удаление элемента в начале дека;
  • Print () – данный метод должен распечатывать на экран все узлы списка.
  • Также необходимо предусмотреть наличие конструктора копирования, перегрузить оператор присвоения, создать деструктор для удаления ресурсов занятых узлами дека.

Первые четыре метода (push_back, push_front, pop_back, pop_front) должны в случае невозможности выполнения запрошенной операции выбрасывать исключения:
  • EgenericDequeException – базовое исключение, основа всех конкретных видов исключений.
  • EdequeOutOfMemory - ошибка выделения памяти.
  • EdequeOnderflow – попытка удаления несуществующего элемента.

Созданный нами класс должен уметь работать с итераторами. Следовательно, вам необходимо создать еще два класса-итератора:
  • const_iterator – данный итератор должен позволять выполнять проход в обоих направлениях по деку, но при этом запрещать модификацию элементов;
  • iterator - также как и в предыдущем задании разрешено перемещение в обоих направлениях, и уже разрешена модификация элементов дека.

После создания этих двух классов, реализовать которые Вам необходимо в виде вложенного класса, вам следует предусмотреть возможность существования одновременно двух или более независимых (не влияющих друг на друга) итераторов. Затем добавьте к эти классам следующие методы:
  • begin () – данный метод должен возвращать итератор указывающий на первый узел дека.
  • end () – данный метод возвращает итератор указывающий на за последний элемент (здесь будьте внимательны: итератор не может просто так ссылаться на NULL, ведь мы решили что итератор должен быть двунаправленным, а, следовательно, если мы выполним

  1. I = deq.end () – 1,
то должны получить итератор указывающий на последний элемент);
  • erase (iterator From , iterator To ) – данный метод служит для удаления узлов списка находящихся в диапазоне от [From, End);
  • insert (iterator To, const Value & what) – данный метод должен будет вставлять в наш дек элементы уже не в конец или начало, а точно за позицией на которую указывает To;
  • insert (iterator To, iterator From, iterator End) – обобщение предыдущего метода – теперь мы должны вставить не один элемент, а множество. Входные значения которых задаются с помощью 2-ого и третьего параметра [From, End).

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

Попробуйте методы erase, insert над этими двумя контейнерами.

Categories: Структуры данных и алгоритмы

« Структуры данных и алгоритмы. Практика. Динамические структуры данных. Основы Структуры данных и алгоритмы. Практика. Контейнеры »