Лекция
Привет, сегодня поговорим про динамические структуры данных, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое динамические структуры данных , настоятельно рекомендую прочитать все из категории Структуры данных.
До сих пор мы рассматривали только статические программные объекты. Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но также и того, будет ли существовать этот объект или нет. Такого рода программные объекты, которые возникают уже в процессе выполнения программы или размер значений которых определяется при выполнении программы, называются динамическими объектами.
динамические структуры данных имеют 2 особенности:
Чтобы связать элементы динамических структур между собой в состав элементов помимо информационных полей входят поля указателей (рис. 3.1) (связок с другими элементами структуры).
P1 и P2 это указатели, содержащие адреса элементов, с которыми они связаны. Указатели содержат номер слота.
Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки.
В линейных списках связи строго упорядочены: указатель предыдущего элемента содержит адрес последующего элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки. К нелинейным - многосвязные.
Элемент списка в общем случае представляет собой поле записи и одного или нескольких указателей.
Элемент односвязного списка содержит два поля (рис. 3.2): информационное поле (INFO) и поле указателя (PTR).
Особенностью указателя является то, что он дает только адрес последующего элемента списка. Поле указателя последнего элемента в списке является пустым (NIL). LST - указатель на начало списка. Список может быть пустым, тогда LST будет равен NIL.
Доступ к элементу списка осуществляется только от его начала, то есть обратной связи в этом списке нет.
Кольцевой односвязный список получается из обычного односвязного списка путем присваивания указателю последнего элемента списка значение указателя начала списка (рис 3.3).
Простейшие операции, производимые над односвязными списками
Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенерировать пустой элемент (P=GetNode). Информационному полю этого элемента присвоить значение D (INFO(P)=D), значению указателя на этот элемент присвоить значение указателя на начало списка (Ptr(P) = Lst), значению указателя начала списка присвоить значение указателя P (Lst = P).
Реализация на Паскале:
type
PNode = ^TNode;
TNode = record
Info: Integer; {тип элементов списка - может быть любым}
Next: PNode;
end;
var Lst: PNode; {указатель на начало списка}
P: PNode;
Вставка в начало
New(P); {создание нового элемента}
P^.Info:=D;
P^.Next:=Lst; {P указывает на начало списка, но Lst не указывает на P - новое начало}
Lst:=P; {Lst указывает на новое начало списка}
Надо удалить первый элемент списка, но запомнить информацию, содержащуюся в поле Info этого элемента. Для этого введем указатель P, который будет указывать на удаляемый элемент (P = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).
Реализация на Паскале:
Удаление из начала
P:=Lst;
X:=P^.Info;
Lst:=P^.Next;
Dispose(P); {Удаляет элемент из динамической памяти}
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от заглавного звена к последнему звену списка. Между тем нередко возникает необходимость произвести какую-либо обработку элементов, предшествующих элементу с заданным свойством. Однако после нахождения элемента с этим свойством в односвязном списке у нас нет возможности получить достаточно удобный и быстрый доступ к предыдущим элементам- для достижения этой цели придется усложнить алгоритм, что неудобно и нерационально.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено списка. Динамическая структура, состоящая из элементов такого типа, называется двунаправленным или двусвязным списком.
Двусвязный список характеризуется тем, что у любого элемента есть два указателя. Один указывает на предыдущий элемент (обратный), другой указывает на следующий элемент (прямой) (рис. 3.4).
Фактически двусвязный список это два односвязных списка с одинаковыми элементами, записанных в противоположной последовательности.
В программировании двусвязные списки часто обобщают следующим образом: в качестве значения поля Rptr последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Lptr заглавного звена- ссылку на последнее звено. Список замыкается в своеобразное кольцо: двигаясь по ссылкам, можно от последнего звена переходить к заглавному и наоборот.
О
перации над двусвязными списками:
- cоздание элемента списка;
- поиск элемента в списке;
- вставка элемента в указанное место списка;
- удаление из списка заданного элемента.
Любой односвязный список может рассматриваться в виде стека. Об этом говорит сайт https://intellect.icu . Однако список по сравнению со стеком в виде одномерного массива имеет преимущество, так как заранее не задан его размер.
Стековые операции, применимые к спискам
1). Чтобы добавить элемент в стек, надо в алгоритме заменить указатель Lst на указатель Stack (операция Push(S, X)).
P = GetNode
Info(P) = X
Ptr(P) = Stack
Stack = P
If Stack = Nil then Print “Стек пуст”
Stop
P = Stack
X = Info(P)
Stack = Ptr(P)
FreeNode(P)
Реализация на Паскале:
Стек
Вместо указателя Lst используется указатель Stack
Процедура Push (S, X)
procedure Push(var Stack: PNode; X: Integer);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=Stack;
Stack:=P;
end;
Проверка на пустоту (Empty)
function Empty(Stack: PNode): Boolean;
begin
If Stack = nil then Empty:=True Else Empty:=False;
end;
Процедура Pop
procedure Pop(var X: Integer; var Stack: PNode);
var
P: PNode;
begin
P:=Stack;
X:=P^.Info;
Stack:=P^.Next;
Dispose(P);
end;
Операции с очередью, применимые к спискам.
Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка - за указатель конца очереди.
Операция удаления из очереди должна проходить из ее начала.
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
If F = Nil then Print “Очередь пуста”
Stop
Операция вставки в очередь должна осуществляться к ее концу.
P = GetNode
Info(P) = X
Ptr(P) = Nil
Ptr(R)= P
R = P
Реализация на Паскале:
procedure Remove(var X: Integer; Fr: PNode);
var
P: PNode;
begin
New(P);
P:=Fr;
X:=P^.Info;
Fr:=P^.Next;
Dispose(P);
end;
function Empty(Fr: PNode): Boolean;
begin
If Fr = nil then Empty:=True Else Empty:=False;
end;
procedure Insert(X: Insert; var Re: PNode);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=nil;
Re^.Next:=P;
end;
Для более эффективного использования памяти компьютера (для исключения мусора, то есть неиспользуемых элементов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функциональных списков.
Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.
Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек. При этом создание (GetNode) нового элемента эквивалентно выборке элемента свободного стека, а операция FreeNode - добавлению в свободный стек освободившегося элемента.
Пусть нам необходимо создать пустой список по типу стека (рис. 3.6) с указателем начала списка - AVAIL. Разработаем процедуры, которые позволят нам создавать пустой элемент списка и освобождать элемент из списка.
Разработаем процедуру, которая будет создавать пустой элемент списка с указателем Р.
Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу.
P = Avail
Avail = Ptr(Avail)
Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка.
If Avail = Nil then Print “Переполнение” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
При освобождении элемента Nod(P) из функционального списка операцией FreeNode(P), он заносится в свободный список.
Ptr(P) = Avail
Avail = P
Стандартные операции возвращения освободившегося элемента списка в пул свободных элементов не всегда дают эффект, если используются нелинейные многосвязные списки.
Первый способ утилизации - метод счетчиков. В каждый элемент многосвязного списка вставляется поле счетчика, который считает количество ссылок на данный элемент. Когда счетчик элемента оказывается в нулевом состоянии, а поля указателей элемента находятся в состоянии nil, этот элемент может быть возвращен в пул свободных элементов.
Второй способ - метод сборки мусора (метод маркера). Если с каким-то элементом установлена связь, то однобитовое поле элемента (маркер) устанавливается в “1”, иначе - в “0”. По сигналу переполнения ищутся элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером.
Просмотр односвязного списка может производиться только последовательно, начиная с головы (с начала) списка. Если необходимо просмотреть предыдущий элемент, то надо снова возвращаться к началу списка. Это - недостаток односвязных списков по сравнению со статическими структурами типа массива. Списковая структура проявляет свои достоинства, когда число элементов списка велико, а вставку или удаление необходимо произвести внутри списка.
Пример:
Необходимо вставить в существующий массив элемент X между 5 и 6 элементами.
Для проведения данной операции в массиве нужно “опустить” все элементы, начиная с X6 - увеличить их индексы на единицу. В результате вставки получаем следующий массив (рис. 3.7, 3.8):
Данная процедура может занимать очень значительное время. В противоположность этому, в связанном списке операция вставки состоит в изменении значения 2-х указателей и генерации свободного элемента. Причем время, затраченное на выполнение этой операции, является постоянным и не зависит от количества элементов в списке.
Определяем элемент, после которого необходимо вставить элемент в список. Вставка производится с помощью процедуры InsAfter(Q, X), а удаление - DelAfter(Q, X).
При этом рабочий указатель P будет указывать на элемент, после которого необходимо произвести вставку или удаление (рис 29).
Пример:
Пусть необходимо вставить новый элемент с информационным полем X после элемента, на который указывает рабочий указатель P.
Для этого:
1) Необходимо сгенерировать новый элемент.
Q = GetNode
2) Информационному полю этого элемента присвоить значение X.
Info(Q) = X
3) Вставить полученный элемент.
Ptr(Q) = Ptr(P)
Ptr(P) = Q
Это и есть процедура InsAfter(Q, X).
Пусть необходимо удалить элемент списка, который следует после элемента, на который указывает рабочий указатель P.
Для этого:
Q = Ptr(P)
2) В переменную X сохраняем значение информационного поля удаляемого элемента.
X = Info(Q)
3) Меняем значение указателя на удаляемый элемент на значение указателя на следующий элемент и производим удаление .
Ptr(P) = Ptr(Q)
FreeNode(Q)
Это и есть процедура DelAfter(P, X).
На языке Паскаль вышеописанные процедуры будут выглядеть следующим образом:
procedure InsAfter(var Q: PNode; X: Integer);
var
Q: PNode;
begin
New(Q);
Q^.Info:=X;
Q^.Next:=P^.Next;
P^.Next:=Q;
procedure DelAfter(var Q: PNode; var X: Integer);
var
Q: PNode;
begin
Q:=P^.Next;
P^.Next:=Q^.Next;
X:=Q^.Info;
Dispose(Q);
end;
Задача 1.
Требуется просмотреть список и удалить элементы, у которых информационные поля равны 4.
Обозначим P - рабочий указатель, в начале процедуры P = Lst. Введем также указатель Q, который отстает на один элемент от P. Когда указатель P найдет элемент, последний будет удален относительно указателя Q как последующий элемент.
Q = Nil
P = Lst
While P <> Nil do
If Info(P) = 4 then
If Q = Nil then
Pop(Lst)
FreeNode(P)
P = Lst
Else
DelAfter(Q, X)
EndIf
Else
Q = P
P = Ptr(P)
EndIf
EndWhile
Задача 2.
Дан упорядоченный по возрастанию Info - полей список. Необходимо вставить в этот список элемент со значением X, не нарушив упорядоченности списка.
Пусть X = 16. Начальное условие: Q = Nil, P = Lst. Вставка элемента должна произойти между 3 и 4 элементом (рис.3.10).
Q =Nil
P = Lst
while (P <> Nil) and (X > Info(P)) do
Q = P
P = Ptr(P)
EndWhile
if Q = Nil then
Push(Lst, X)
EndIf
InsAfter(Q, X)
Реализация примеров на языке Паскаль:
Задача 1:
Q:=nil;
P:=Lst;
While P <> nil do
If P^.Info = 4 then
begin
If Q = nil then
begin
Pop(Lst);
P:=Lst;
end
Else Delafter(Q,X);
End;
Else
begin
Q:=P;
P:=P^.Next;
end;
end;
Задача 2:
Q:=nil;
P:=Lst;
While (P <> nil) and (X > P^.Info) do
begin
Q:=P;
P:=P^.Next;
end;
{В эту точку производится вставка}
If Q = nil then Push(Lst, X);
InsAfter(Q, X);
End;
Для создания списка с заголовком в начало списка вводится дополнительный элемент, который может содержать информацию о списке (рис. 3.11).
В заголовок списка часто помещают динамическую переменную, содержащую количество элементов в списке (не считая самого заголовка).
Если список пуст, то остается только заголовок списка (рис. 3.12).
Также удобно занести в информационное поле заголовка значение указателя конца списка. Тогда, если список используется как очередь, то Fr = Lst, а Re = Info(Lst).
Информационное поле заголовка можно использовать для хранения рабочего указателя при просмотре списка P = Info(Lst). То есть заголовок - это дескриптор структуры данных.
Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.3.13).
LST1 - указатель на начало 1 - ого списка (ориентированного указателем P1). Он линейный и состоит из 5-и элементов.
2-ой список образован из этих же самых элементов, но в произвольной последовательности. Началом 2-ого списка является 3-ий элемент, а концом 2-ой элемент.
В общем случае элемент списочной структуры может содержать сколь угодно много указателей, то есть может указывать на любое количество элементов.
Можно выделить 3 признака отличия нелинейной структуры:
1) Любой элемент структуры может ссылаться на любое число других элементов структуры, то есть может иметь любое число полей-указателей.
2) На данный элемент структуры может ссылаться любое число других элементов этой структуры.
3) Ссылки могут иметь вес, то есть подразумевается иерархия ссылок.
Представим, что имеется дискретная система, в графе состояния которой узлы - это состояния, а ребра - переходы из состояния в состояние (рис. 3.14).
Входной сигнал в систему это X. Реакцией на входной сигнал является выработка выходного сигнала Y и переход в соответствующее состояние.
Граф состояния дискретной системы можно представит в виде двусвязного нелинейного списка. При этом в информационных полях должна записываться информация о состояниях системы и ребрах. Указатели элементов должны формировать логические ребра системы (рис. 3.15).
Для реализации вышесказанного:
1) должен быть создан список, отображающий состояния системы (1, 2, 3);
2) должны быть созданы списки, отображающие переходы по ребрам из соответствующих состояний .
В общем случае при реализации многосвязной структуры получается сеть.
Контрольные вопросы
На этом все! Теперь вы знаете все про динамические структуры данных, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое динамические структуры данных и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных