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

Динамическая структура характеризуется следующими чертами.

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

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

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

Односвязные списки

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

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

Поле указателя хранит адрес следующего элемента списка. Пользуясь указателем, можно получить доступ к следующему элементу списка, а из следующего элемента к очередному элементу и т.д., пока не будет достигнут последний элемент. Поле указателя последнего элемента должно содержать специальный признак нулевого, или пустого указателя, свидетельствующий о конце списка. Линейность односвязного списка вытекает из линейной логической упорядоченности его элементов: для каждого элемента (кроме первого и последнего) имеются единственный предыдущий и единственный следующий элементы. На рис. 4.1 приведена логическая структура односвязного списка, состоящего из некоторого числа элементов. Как видно из этого рисунка, частью логической структуры односвязного списка служит указатель начала списка. На рисунке также показано, что в поле указателя последнего элемента списка находится специальный признак 0, свидетельствующий о конце списка.

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

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

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

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

Двусвязные списки

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

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

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

ставляет собой в общем случае запись, причем структура этой записи одинакова для каждого элемента списка. В элементе односвязного списка единственный указатель следующего элемента будем обозначать LINK, а в элементе двусвязного списка указатели следующего и предыдущего элементов - соответственно SLINK и PLINK. Указателю начала списка, применительно к которому будет исследоваться та или иная операция, назначим имя START. Отметим, что указатель START хранится в дескрипторе списка. Кроме указателя START в процессе обработки списка может потребоваться рабочий указатель, который принимает значение адреса того или иного элемента списка. Дадим рабочему указателю имя PNTER.

Если указатель не адресует никакой элемент списка, будем полагать, что его значение, как обычно, равно Æ.

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

Обозначим указатель начала свободного списка идентификатором FREE. Условимся также считать, что выражение DATA (PNTER) представляет данные того элемента списка, который адресуется указателем PNTER. Соответственно выражение LINK (PNTER) имеет значение адреса, или связки, элемента, адресуемого указателем PNTER. И, наконец, запись PNTER LINK (PNTER) выражает присваивание указателю PNTER значение связки LINK того элемента, который в данный момент адресуется указателем PNTER (это соответствует перемещению указателя на следующий элемент списка).

Обратимся теперь к первой из двух основных операций над списком - операции включения элемента в список - и проиллюстрируем ее для случая односвязного списка. Список, в который надлежит включить новый элемент, может быть пуст или содержать один, два элемента и более. Новый элемент может включаться в начало списка, в конец или куда-нибудь внутрь списка. В зависимости от этого операция включения имеет свои особенности выполнения. Предположим, что обрабатываемый функциональный список может содержать произвольное конечное число элементов и требуется включить в него новый элемент вслед за элементом того же списка, адресуемым рабочим указателем PNTER. Допустим, что новый элемент уже взят из свободного списка и его данные DATA сформированы должным образом. Указатель NEW адресует этот элемент. Исходная ситуация показана на рис.4.5, на которой пунктирная стрелка указывает связку, подлежащую разрыву.

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

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