Понятие динамических структур данных. Организация односвязных и двусвязных списков. Простейшие операции над односвязными списками.

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

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

Динамические структуры данных имеют две особенности:

1. Заранее не определено количество элементов в структуре.

2. Элементы динамических структур физически не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.

 

P1 и P2 это указатели, содержащие адреса элементов, с которыми связаны соответствующие элементы структуры. Указатели содержат номер ячейки памяти, с которой начинается соответствующий элемент структуры.

Связные списки

С точки зрения логического представления различают линейные и нелинейные списки.

К линейным спискам относятся односвязные и двусвязные списки. К нелинейным - многосвязные.

Элемент списка в общем случае представляет собой информационное поле и одно или несколько полей указателей.

Данные динамические структуры наиболее распростанены.

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

Элемент односвязного списка содержит, как минимум, два поля: информационное поле (info) и поле указателя (ptr).

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

При дальнейшем изучении односвязных списков мы будем использовать следующую терминологию:

p - указатель

node(p) – узел, на который ссылается указатель p (при этом неважно в какое место изображения элемента (узла) списка он направлен на рисунке)

ptr(p) – ссылка на последующий элемент узла node(p)

ptr(ptr(p)) – ссылка последующего для node(p) узла на последующий для него элемент.

 

Кольцевой односвязный список

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

Двусвязный список

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

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

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

Один указывает на предыдущий (левый) элемент (L), другой указывает на последующий (правый) элемент (R).

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

Кольцевой двусвязный список

Кольцевые двусвязные списки получают следующим образом: в качестве значения поля R последнего элемента принимают ссылку на первый элемент, а в качестве значения поля L первого элемента - ссылку на последний элемент.