Динамические структуры данных; списки: основные виды и способы реализации. Технологии программирования. Способы конструирования программ.
Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости. Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.
Каждой динамической структуре данных сопоставляется статическая переменная типа указатель (ее значение – адрес этого объекта), посредством которой осуществляется доступ к динамической структуре.
Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется. Во время компиляции память выделяется только под статические величины. Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями. Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти. Указатели – это статические величины, поэтому они требуют описания.
Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.
Порядок работы с динамическими структурами данных следующий:
создать (отвести место в динамической памяти);
работать при помощи указателя;
удалить (освободить занятое структурой место).
Элемент динамической структуры состоит из двух полей:
информационного поля (поля данных), в котором содержатся те данные, ради которых и создается структура. Поле данных может быть переменной, массивом или структурой;
адресного поля (поля связок), в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;
В общем случае запись может содержать не один, а несколько указателей и несколько полей данных.
Классификация динамических структур данных
однонаправленные (односвязные) списки;
двунаправленные (двусвязные) списки;
циклические (кольцевые) списки;
стек;
дек;
очередь;
бинарные деревья.
Они отличаются способом связи отдельных элементов и/или допустимыми операциями. Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Списки представляют собой способ организации структуры данных, при которой элементы некоторого типа образуют цепочку. В минимальном случае, любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что интерпретируется как конец списка. Структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранящихся в самих элементах, называют связанным списком. В связанном списке элементы линейно упорядочены, порядок определяется указателями, входящими в состав элементов списка. Каждый список имеет особый элемент, называемый указателем начала списка (головой списка), который обычно по содержанию отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка. Схематически он выглядит так:
Inf — информационная часть звена списка (величина любого простого или структурированного типа, кроме файлового), Next — указатель на следующее звено списка; First — указатель на заглавное звено списка.
При объявлении списка указатель на звено списка объявляется раньше, чем само звено. В общем виде объявление выглядит так.
Type U = ^Zveno;
Zveno = Record Inf : BT; Next: U End;
Здесь BT — некоторый базовый тип элементов списка.
Линейные связные списки являются простейшими динамическими структурами данных. Если указатель ссылается только на следующее звено списка (как показано на рисунке и в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья - двунаправленным списком. Если указатель в последнем звене установлен не в Nil, а ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки. Рассмотреть работу со связанными списками можно на примере однонаправленного некольцевого списка. Типовые операции над списками:
добавление звена в начало списка;
удаление звена из начала списка;
добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);
удаление звена из произвольного места списка, отличного от начала;
проверка, пуст ли список;
очистка списка;
печать списка.
Пусть список объявлен так, как было описано выше. (Язык Pascal)