Двунаправленные списки

   
На этом шаге мы рассмотрим двунаправленные списки..

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

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

   
Двунаправленный список отличается двумя основными преимуществами.

   
Во-первых, список может просматриваться в обоих направлениях.
Это не только упрощает сортировку списка, но также позволяет пользователям базы данных просматривать данные в обоих направлениях.

   
Во-вторых, список при нарушении одной из связей может быть восстановлен по другой связи. Это свойство имеет смысл использовать
при отказах оборудования, приводящих к нарушению списка.

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

   
1) информационного поля или поля данных;

   
2) ссылки на следующий элемент списка;

   
3) ссылки на предыдущий элемент списка.

   
Описание компоненты списка дадим следующим образом:

 Type
   PtrRec = ^Rec;
   Rec = record
       Element : TypeElement; 	{поле данных}
       pNext : PtrRec; 	{прямой указатель}
       pPrev : PtrRec; 	{обратный указатель}
     End;

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

   
Изобразим схематично случай, когда заглавное звено одно:


Рис.1. Двунаправленный список с одним заглавным звеном

   
Изобразим пустой двунаправленный список с одним заглавным звеном:


Рис.2. Пустой двунаправленный список с одним заглавным звеном

   
Приведем вариант структуры двунаправленного списка с двумя заглавными звеньями:


Рис.3. Двунаправленный список с двумя заглавными звеньями

   
Замечание.
В данном случае двунаправленный список стал симметричным.

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


Рис.4. Пустой двунаправленный список с двумя заглавными звеньями

   
Рассмотрим три свойства двунаправленных списков:

   
1) по списку можно двигаться в любом направлении;

   
2) если List есть указатель на любой элемент двунаправленного списка, то выполняются следующие свойства

 List = List^.pNext^.pPrev

и

 List = List^.pPrev ^.pNext

   
Данные свойства легко можно проиллюстрировать с помощью схемы:


Рис.5. Графическая иллюстрация свойств двунаправленного списка

   
3) возможность легкого исключения узла из списка, в котором он находится, по известному указателю на этот узел. Алгоритмы, в которых требуется исключать узлы из середины списка, встречаются достаточно часто, и как раз этим обстоятельством и объясняется распространенное использование списков с двумя связями.
  

    Над двунаправленными списками выполняются следующие операции:

  • начальное формирование списка (запись первой компоненты);
  • добавление компоненты в конец списка;
  • вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
  • определение первого или последнего элементов в двунаправленном списке;
  • чтение компоненты с заданным ключом; с заданным свойством;
  • исключение компоненты с заданным ключом из списка;
  • упорядочивание узлов линейного списка в определенном порядке.

   
Для формирования списка и работы с ним необходимо описать четыре переменных типа указатель, пусть: pBegin определяет начало списка, pEnd определяет конец списка, pCKey, pAux - вспомогательные:

 Var
   pBegin, pEnd, pCKey, pAux : PtrRec;

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

   
На следующем шаге мы рассмотрим двунаправленные списки с заглавным звеном.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий