Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Динамические структуры данных. Стек. Очередь

Данная тема продолжает знакомство с динамическими структурами данных (стек, очередь).

1) После того как на предыдущем задании вы реализовали класс стека попробуйте с его помощью решить классическую задачу о упорядоченности строки. Дана строка текста которая в том числе содержит множество скобок: “(”, “{”, “[” как открывающихся так и закрывающихся. Строка считается корректной в том случае если всем открывающим скобкам есть соответствующие им закрывающие скобки. Например, строка “abc(as)[]{aa[z]}” – считается корректной, а строка ”[[09]({]})” – не является таковой.

2) На занятии мы рассматривали линейные списки. Каждый узел подобного списка содержал две компоненты: информационный элемент и ссылка на следующий элемент. В рассматривавшейся схеме последний элемент списка ссылался на NULL. “LastElement->next == NULL”. Существует понятие кольцевого списка в данном виде списка последний элемент ссылается на первый. Вам необходимо использую данную концепцию решить задачу Иосифа: задано N предметов расположенных по кругу, начинается отсчет с некоторого элемента под номером X, каждый M-ый элемент вычеркивается из списка. После удаления элемента процесс отсчета и вычеркивания продолжается до тех пор пока не останется только один элемент. Вам необходимо создать класс RoundedQuenue который и будет контейнером в виде циклического списка. Для данного контейнера предусмотреть наличие следующего набора методов:

• push_back – метод для добавления нового узла в конец очереди.
• delete_current – данный метод должен служить для удаления текущего элемента. Признак для указания того “текущий ли элемент” может быть реализован или в виде порядкового номера элемента (для этого часто в состав узла вводят служебное поле unique_index) или в виде ссылки на его узел.

• calculate_n – данный метод должен возвращать ссылку или порядковый номер на n – по счету элемент начиная от текущего. Относительно способа задания текущего элемента (см. предыдущий пункт задания).

Обязательным является реализация конструкторов копирования и деструкторов, операцию присвоения запретить.

3) В практике программирования создание линейных списков с однонаправленными связями является не достаточным. Поэтому используются двунаправленные списки. Информация об устройстве и принципах работы излагалась в методическом пособии. Мы попробуем снова вернуться к задачам сортировки данных. Как вы помните, мы стремились к уменьшению количества перестановок элементов и для этого или увеличивали количество сравнений, использовали прием с индексацией. Сейчас вы должны создать класс DoubleQuenue который будет представлять список с двунаправленными списками. Информационная часть подобного списка может быть сколь угодно сложной, но при этом реализовать перестановку местами элементов можно сильно упростить за счет того, что будут не перемещаться элементы (узлы), а только меняться порядок ссылок. В качестве основы алгоритма сортировки используйте любой из простейших приемов (пузырек, обмен, вставка). Основное внимание обратить на создание контейнера данных.

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

5) Большой интерес для хранения сложно организованных наборов данных имеет понятие мультисписков. В простейшем случае информационная компонента списка хранит скалярный тип: число, буква. Более интересна ситуация когда в качестве информационной компоненты выступает еще один список. Каждый элемент данного списка в свою очередь способен хранить еще один список. Таким образом мы приходим к понятию не однородных структур данных. В качестве примера можно привести:

 <strong>(A, (B, C), (D, (E, F), (K, (L))))</strong>. 

Создайте класс MultiList, который будет способен для хранения подобных структур данных. Интерфейс продумайте самостоятельно, это задача более творческая, чем отчетная. Продумайте, каким образом можно будет использовать данный класс. Посоветуйтесь со мной. Придумывайте.

« Структуры данных и алгоритмы. Практика. Рекурсия и исключения

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