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

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

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

structnode{

int data;

struct node *nextptr;

};

описывает тип structnode. Структура типаstructnodeсостоит из двух элементов – целогоdataи указателяnextPtr. ЭлементnextPtrуказывает на структуру типаstructnode– структур того же самого типа, что и только объявленная. ЭлементnextPtrиногда называют связкой, т.е.nextPtrможно использовать для того, чтобы связать структуру типаstructnodeс другой структурой того же типа.

Динамическое распределение памяти. Создание и использование динамических структур данных требует динамического распределения памяти – возможности получать в процессе исполнения дополнительную память для хранения новых узлов и освобождать блоки памяти, ставшие ненужными. Максимальный размер выделяемой динамической памяти определяется доступной физической памятью компьютера или доступным виртуальным адресным пространством в системе с виртуальной памятью. Для динамического распределения памяти необходимо применение функцийmallocиfree, а также операцияsizeof. Функцияmallocпринимает в качестве аргумента число байт, которое необходимо выделить, и возвращает указатель на выделенную память типаvoid*. Указательvoid* можно присвоить любой переменной-указателю. Функцияmallocобычно используется совместно с операциейsizeof. Если необходимого количества памяти нет в наличии,mallocвозвращает указательNULL. Функцияfreeосвобождает память, т.е. память возвращается системе, и в дальнейшем ее можно выделить снова.

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

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

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

Деревья.Дерево является нелинейной структурой, двумерной структурой данных с особыми свойствами. Узлы дерева содержат две или более связей. Двоичные деревья – деревья, узлы которых содержат только две связки. Первый узел дерева называется корневым. Каждая связь корневого узла ссылается на потомка. Левый потомок – первый узел левого поддерева, а правый потомок – первый узел правого поддерева. Потомки одного узла называются узлами-сиблингами. Двоичное дерево поиска (с неповторяющимися значениями в узлах) устроено так, что значения в любом левом поддереве меньше, чем значение в родительском узле, а значение в любом правом поддерево больше, чем значение в родительском узле.

Основная литература: 1осн[457-479]

Дополнительная литература:9доп[212-223], 11доп[13-16]

Контрольные вопросы:

1. Назовите линейные динамические структуры данных?

2. В чем заключается различие между связанным списком и стеком?

3. Откуда удаляются узлы в очереди?

4. Куда вставляются узлы в стеках?

5. Какое дерево является двоичным деревом поиска?