Линейные динамические структуры

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

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

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

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

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

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

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

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

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

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

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

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

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

Важнейшие операции над связными списками — включение и исключение элементов.

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