Динамические структуры данных

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

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

Задачи, обрабатывающие данные, которые по своей природе являются динамическими, удобно решать с помощью динамических структур. Именно с этим интересным средством мы будем учиться работать.

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

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

• Стек С/C++
• Простая очередь - динамическая структура. Очередь, так же как и стек можно реализовывать на практике с помощью массива. Очередь — это последовательный набор элементов с переменной длиной. При этом, добавление элементов в очередь происходит с одной стороны, а удаление — с другой стороны. Данная конструкция функционирует по идеологии FIFO (First In — First Out), то есть "первым пришел — первым вышел". Для очереди принято выделять конечную последовательность элементов, из которых в каждый текущий момент времени элементами очереди заняты лишь часть последовательных элементов. В принципе, с простой очередью вы сталкиваетесь постоянно. Вот лишь некоторые из примеров:очередь в мавзолей, очередь печати принтера, даже действия линейного алгоритма выполняются по очереди.
• Кольцевая очередь. Кольцевая очередь очень похожа на простую очередь. Она тоже построена на идеологии FIFO, напоминаем - элемент, который добавили в очередь первым, первым ее и покинет. Разница лишь в том, что элемент, который выходит из начала очереди, будет перемещён в её конец. В качестве самого простого примера, можно привести известный вам с детства круговорот воды в природе, или трамваи, курсирующие по круговому маршруту.
• Очередь с приоритетом C++, C# (си шарп).
• Односвязный список - - это совокупность нескольких объектов, каждый из которых представляет собой элемент списка, состоящий из двух частей. Первая часть элемента - значение, которое он хранит, вторая - информация о следующем элементе списка. Характер информации о следующем элементе зависит от того, где конкретно хранится список. Например, если это оперативная память, то информация будет представлять собой адрес следующего элемента, если файл - позицию следующего элемента в файле.
• Реализация двусвязного списка на c. Отличие от односвязанного списка состоит в том, что в двусвязном (или двунаправленном списке) узел состоит не из двух, а из трех частей. В третьем компоненте хранится указатель на предыдущий элемент.
• Бинарное дерево С++ (binary tree) - это упорядоченная древовидная динамическая структура.