Динамические структуры данных | Связные списки

1  Связное представление данных в памяти

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

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

Достоинства связного представления данных - в возможности обеспечения значительной изменчивости структур;

• размер структуры ограничивается только доступным объемом машинной памяти;
• при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей.

Вместе с тем связное представление не лишено и недостатков, основные из которых:

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

2 Связные линейные списки

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

2.1  Машинное представление связных линейных списков

На рис. 5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка

Рис.5.1.  Структура односвязного списка

Обработка односвязного списка не всегда удобна,  так как отсутствует возможность продвижения в противоположную  сторону.  Такую  возможность  обеспечивает двухсвязный список,  каждый элемент которого содержит два указателя:  на следующий и предыдущий элементы списка. В линейном двухсвязном списке имеется поле NEXT - указатель на следующий элемент и поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil.

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

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

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

2.2  Реализация операций над связными линейными списками

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

1). Указатель текущего элемента устанавливается на начало списка.
2). Если указатель текущего элемента пустой – конец перебора.
2). Обрабатывается информационная часть текущего элемента., на который
3). из текущего элементата выбирается указатель на следующий элемент и следующий элемент становится текущим.
4). Повторяются децствия с п.2.

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

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

Вставка элемента в список. Вставка элемента в середину  односвязного списка реализуется следующим алгоритмом.
1). Выделяется память для нового элемента и записывается его информационная часть
2). Значение указателя next предшествующего элемента переносится в поле next нового элемента.
2). В поле next предшествующего элемента заносится адрес нового элемента.
Приведенные алгоритмы обеспечивают вставку в  середину списка, но не могут быть применены для вставки в начало списка.  При вставке в начало списка должен модифицироваться указатель на  начало  списка.

Удаление элемента из списка. При удалении элемента из односвязного достаточно значение из поля next удаляемого элемента перенести в поле next предыдущего элемента.

Перестановка элементов списка. Изменчивость динамических структур данных предполагает не только изменения размера структуры,  но и изменения связей между элементами. Для связных структур изменение  связей не требует пересылки данных в памяти,  а только изменения указателей в элементах связной  структуры.  В  качестве примера приведена перестановка двух соседних элементов списка.  В алгоритме перестановки в односвязном списке (рис.5.9, пример 5.5) исходили  из того,  что известен адрес элемента,  предшествующего паре, в которой производится перестановка. В приведенном алгоритме  также  не  учитывается  случай перестановки первого и второго элементов.
1). В поле next 1-го элемента пары переносится значение из поля next 2-го элемента
2). В поле next 2-го элемента пары заносится адрес 1-го элемента
3). В поле next элемента, предшествующего паре, заносится адрес 2-го элемента

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

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

3. Нелинейные разветвленные списки

3.1  Основные понятия

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

В обработке  нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект,  который при обработке отличается от списка тем, что он структурно неделим.
Если мы заключим списки в круглые скобки, а элементы списков разделим запятыми,  то в качестве списков можно рассматривать такие последовательности:
(a,(b,c,d),e,(f,g))                   ( )                          ((a))
Первая из приведенных последовательностей показана на рис. 5.2.
 

Рис.5.2. Нелинейный список

Разветвленные списки описываются тремя характеристиками: порядком, глубиной и длиной.

Порядок. Над  элементами  списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка.  В списке (x,y,z) атом x предшествует y, а y предшествует z.  При этом подразумевается,  что x предшествует z. Данный  список не эквивалентен списку (y,z,x).  При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом:  элемент из которого исходит стрелка, предшествует  элементу, на который она указывает.
Глубина. Это максимальный уровень,  приписываемый  элементам внутри списка или внутри любого подсписка в списке.  Уровень элемента  предписывается  вложенностью  подсписков  внутри   списка, т.е. числом  пар  круглых скобок,  окаймляющих элемент.

Длина - число элементов уровня  1  в  списке. 

3.2  Представление списковых структур в памяти.

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

Рис.5.3. Структура элемента разветвленного списка
Элементы списка  могут  быть двух видов:  атомы - содержащие данные и узлы - содержащие указатели на подсписки.  В  атомах  не используется  поле  down элемента списка,  а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно,  как показано на рис.5.4.

Рис.5.4. Структура элемента разветвленного списка
Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти.  В этом случае теряется незначительный объем памяти в элементах списка,  для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла представленный на рис.5.5.

     Рис. 5.5. Структура элемента разветвленного списка
В этом  случае  указатель  down  указывает  на данные или на подсписок. Поскольку списки могут составляться из данных  различных типов, целесообразно адресовать указателем down не непосредственно данные,  а их дескриптор,  в котором может быть описан тип данных, их длина и т.п.  Само описание того, является ли адресуемый указателем данных объект атомом или узлом также  может  находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же,  как и элемента списка. 

3.3  Операции обработки списков

Базовыми операциями при обработке списков  являются операции (функции): car, cdr, cons и atom.
Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент).

Операция cdr  в качестве аргумента также получает список. Ее возвращаемым значением является остаток  списка  -  указатель  на список после удаления из него первого элемента. Например:
Операция cons имеет  два  аргумента:  указатель  на  элемент списка и указатель на список.  Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель  на получившийся список.

Операция atom выполняет проверку типа элемента  списка.  Она должна возвращать  логическое  значение:  true - если ее аргумент является атомом или false - если ее аргумент является подсписком.