<< Пред. стр. 4 (из 19) След. >>
If F = Nil then Print “Очередь пуста”Stop
3) Операция вставки в очередь. (Insert(Q, X))
Операция вставки в очередь должна осуществляться к ее концу.
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;
3.3 Организация операций Getnode, Freenode и утилизация освободившихся элементов
Для более эффективного использования памяти компьютера (для исключения мусора, то есть неиспользуемых элементов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функциональных списков.
Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.
Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек. При этом создание (GetNode) нового элемента эквивалентно выборке элемента свободного стека, а операция FreeNode - добавлению в свободный стек освободившегося элемента.
Пусть нам необходимо создать пустой список по типу стека (рис. 3.6) с указателем начала списка - AVAIL. Разработаем процедуры, которые позволят нам создавать пустой элемент списка и освобождать элемент из списка.
3.3.1 Операция GetNode
Разработаем процедуру, которая будет создавать пустой элемент списка с указателем Р.
Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу.
P = Avail
Avail = Ptr(Avail)
Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка.
If Avail = Nil then Print “Переполнение” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
3.3.2 Операция FreeNode
При освобождении элемента Nod(P) из функционального списка операцией FreeNode(P), он заносится в свободный список.
Ptr(P) = Avail
Avail = P
3.3.3 Утилизация освободившихся элементов в многосвязных списках
Стандартные операции возвращения освободившегося элемента списка в пул свободных элементов не всегда дают эффект, если используются нелинейные многосвязные списки.
Первый способ утилизации - метод счетчиков. В каждый элемент многосвязного списка вставляется поле счетчика, который считает количество ссылок на данный элемент. Когда счетчик элемента оказывается в нулевом состоянии, а поля указателей элемента находятся в состоянии nil, этот элемент может быть возвращен в пул свободных элементов.
Второй способ - метод сборки мусора (метод маркера). Если с каким-то элементом установлена связь, то однобитовое поле элемента (маркер) устанавливается в “1”, иначе - в “0”. По сигналу переполнения ищутся элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером.
3.4 Односвязный список, как самостоятельная структура данных
Просмотр односвязного списка может производиться только последовательно, начиная с головы (с начала) списка. Если необходимо просмотреть предыдущий элемент, то надо снова возвращаться к началу списка. Это - недостаток односвязных списков по сравнению со статическими структурами типа массива. Списковая структура проявляет свои достоинства, когда число элементов списка велико, а вставку или удаление необходимо произвести внутри списка.
Пример:
Необходимо вставить в существующий массив элемент X между 5 и 6 элементами.
Для проведения данной операции в массиве нужно “опустить” все элементы, начиная с X6 - увеличить их индексы на единицу. В результате вставки получаем следующий массив (рис. 3.7, 3.8):
Данная процедура может занимать очень значительное время. В противоположность этому, в связанном списке операция вставки состоит в изменении значения 2-х указателей и генерации свободного элемента. Причём время, затраченное на выполнение этой операции, является постоянным и не зависит от количества элементов в списке.
3.4.1 Вставка и извлечение элементов из списка
Определяем элемент, после которого необходимо вставить элемент в список. Вставка производится с помощью процедуры 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.
Для этого:
1) Присваиваем Q значение указателя на удаляемый элемент.
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;
3.4.2 Примеры типичных операций над списками
Задача 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.4.3 Элементы заголовков в списках
Для создания списка с заголовком в начало списка вводится дополнительный элемент, который может содержать информацию о списке (рис. 3.11).
В заголовок списка часто помещают динамическую переменную, содержащую количество элементов в списке (не считая самого заголовка).
Если список пуст, то остается только заголовок списка (рис. 3.12).
Также удобно занести в информационное поле заголовка значение указателя конца списка. Тогда, если список используется как очередь, то Fr = Lst, а Re = Info(Lst).
Информационное поле заголовка можно использовать для хранения рабочего указателя при просмотре списка P = Info(Lst). То есть заголовок - это дескриптор структуры данных.
3.5 Нелинейные связанные структуры
Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.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) должны быть созданы списки, отображающие переходы по ребрам из соответствующих состояний .
В общем случае при реализации многосвязной структуры получается сеть.
Контрольные вопросы
1. Какие динамические структуры Вам известны?
2. В чем отличительная особенность динамических объектов?
3. Какой тип представлен для работы с динамическими объектами?
4. Как связаны элементы в динамической структуре ?
5. Назовите основные особенности односвязного списка..
6. В чем отличие линейных списков от кольцевых ?
7. Зачем были введены двусвязные списки ?
8. В чем разница в операциях, производимых над односвязными и двусвязными списками ?
9. Какой список является более удобным в обращении, односвязный или двусвязный ?
10. Что такое указатель?
11. Какие стековые операции можно производить над списками ?
12. Какие операции, производимые над очередью, можно производить над списками ?
13. Почему можно производить все эти операции над списками ?
14. Для чего предназначены операции Getnode и Freenode?
15. Какие методы утилизации вы знаете ?
16. Перечислите элементы заголовков в списках.
17. Зависит ли время, затраченное на вставку элемента в односвязный список, от количества элементов в списке ?
18. Где процесс вставки и удаления эффективнее, в списке или в массиве ?
19. Как можно производить просмотр односвязного списка?
20. Что означает AVAIL?
21. Какой недостаток односвязных списков по сравнению с
22. массивом?
23. Какие структуры являются нелинейными ?
24. Каковы признаки отличия нелинейных структур?
25. Как можно создать нелинейную связную структуру?
26. Что такое граф состояния ?
4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ
Рассмотрим рекурсивные алгоритмы и рекурсивные структуры данных.
Рекурсия - процесс, протекание которого связано с обращением к самому себе (к этому же процессу).
Пример рекурсивной структуры данных - структура данных, элементы которой являются такими же структурами данных (рис. 4.1).
4.1 Деревья
Дерево - нелинейная связанная структура данных
(рис. 4.2).
Дерево характеризуется следующими признаками:
- дерево имеет 1 элемент, на которого нет ссылок от других элементов. Этот элемент называется корнем дерева;
- в дереве можно обратиться к любому элементу путем прохождения конечного числа ссылок (указателей);
- каждый элемент дерева связан только с одним предыдущим элементом, Любой узел дерева может быть промежуточным либо терминальным (листом). На рис. 4.2 промежуточными являются элементы M1, M2, листьями - A, B, C, D, E. Характерной особенностью терминального узла является отсутствие ветвей.
Высота - это количество уровней дерева. У дерева на рис. 4.2 высота равна двум.
Количество ветвей, растущих из узла дерева, называется степенью исхода узла (на рис. 4.2 для M1 степень исхода 2, для М2 - 3). По степени исхода классифицируются деревья:
1) если максимальная степень исхода равна m, то это - m-арное дерево;
2) если степень исхода равна либо 0, либо m, то это - полное m-арное дерево;
3) если максимальная степень исхода равна 2, то это - бинарное дерево;
4) если степень исхода равна либо 0, либо 2, то это - полное бинарное дерево.