<< Пред.           стр. 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, то это - полное бинарное дерево.

<< Пред.           стр. 4 (из 19)           След. >>

Список литературы по разделу