Занимательные факты о представителях фауны (стр. 24 )

Пример 7.8.

Описание типа звена двунаправленного списка.

Type 

       Adr2 = ^Zveno2;

       Zveno2 = Record

                                               Adrcled: Adr2;

                                               Adrpred: Adr2;

                                               Element: <Тип элемента-списка>

       End;

Схематично двунаправленный список с заглавным звеном изображает рисунок 7.7.

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

На данном рисунке «элем. i» (элемент i) представляет собой информационную часть i-ого звена.

У заглавного звена списка нет предыдущего элемента. У последнего звена списка нет последующего элемента. Поэтому в поле Adrcled последнего звена и в поле Adrpred заглавного звена двунаправленного списка должна быть пустая ссылка Nil.

На основе двунаправленного списка могут быть организованы двунаправленные кольцевые списки.

В кольцевом списке значением поля Adrcled последнего звена является ссылка на заглавное звено, значением поля Adrpred заглавного звена является ссылка на последнее звено (рисунок 7.8).

Рисунок 7.8  – Представление двунаправленного кольцевого списка
с заглавным звеном
(первый способ организации кольца)

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

При втором способе способ организации кольцевого списка заглавное звено списка в кольцо не включается (рисунок 7.9).

Рисунок 7.9 – Представление двунаправленного кольцевого списка
с заглавным звеном
(второй способ организации кольца)

Достоинство первого способа организации кольцевого списка – просто реализуется вставка нового звена как в начало списка, так и в конец.

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

У второго способа организации кольцевого списка данный недостаток отсутствует, но труднее реализовывается добавление звена в конец списка.

Над двунаправленными списками определены те же три операции, что и над строкой-цепочкой:

поиск элемента в списке; вставка элемента в указанное место списка; удаление из списка заданного элемента.

Для работы сдвунаправленными списками необходимо использовать два указателя – на заглавное звено и на текущее звено.

Ниже рассмотрена их реализация для первого способа организации кольцевого списка.

7.2.1. Вставка элемента

Пусть в программе имеется описание типа, приведенное в примере 7.8.

Алгоритм вставки элемента в указанное место двунаправленного кольцевого списка:

Порождение нового звена. Занесение вставляемого элемента в информационное поле порожденного звена. Занесение в поле Adrcled порожденного звена ссылки на следующий элемент из звена, предшествующего вставляемому. Занесение в поле Adrpred порожденного звена ссылки на предыдущий элемент из звена, следующего за вставляемым. Занесение в поле Adrpred следующего за вставляемым звена ссылки на вставляемое звено. Занесение в поле Adrcled предшествующего звена ссылки на вставляемое звено.

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

Фрагмент исходного списка иллюстрирует рисунок 7.10.

Рисунок 7.10 – Фрагмент исходного двунаправленного списка

Пусть в исходный список после элемента 1 вставляется элемент 3. Соответствующий фрагмент результирующего списка будет иметь вид, который изображает рисунок 7.11.

Рисунок 7.11 – Фрагмент результирующего двунаправленного списка

На данном рисунке номера 1) – 6) соответствуют номерам этапов алгоритма вставки.

Пример 7.9.

Процедура вставки.

Procedure Vstav (Elem: <Тип_элемента_списка>; Predzv: Adr2); {Elem – вставляемый элемент, Predzv – ссылка на предшествующий элемент}

       Var Q: Adr2;

       Begin

{1}        New (Q);

{2}        Q^.Element := Elem;

{3}        Q^.Adrcled := Predzv^.Adrcled;

{4}        Q^.Adrpred := Predzv;

{5}        Predzv^.Adrcled^.Adrpred := Q;

{6}        Predzv^.Adrcled := Q;

End;

В данном примере номера операторов, приведенные в комментариях, соответствуют номерам этапов алгоритма вставки. Реализация этапа 4 в примере отличается от этапа 4 алгоритма вставки, поскольку ссылка на предшествующее звено в процедуру Vstav передается в качестве параметра.

7.2.2. Создание двунаправленного кольцевого списка
с заглавным звеном

Пусть в программе имеется описание типа, приведенное в примере 7.8.

Для создания кольцевого списка можно использовать процедуру вставки, приведенную в примере 7.9. При этом на каждом шаге создания список должен быть закольцован.

Пример 7.10.

Ввод исходного текста и представление его в виде двунаправленного кольцевого списка с заглавным звеном. Признак окончания текста – точка. Раздел типов соответствует примеру 7.8.

Var

       Ring: Adr2; {Адрес заглавного звена кольца}

       Bykva: Char; {Символ исходного текста}

Begin

{7}        New (Ring); {Отведено место в памяти для заглавного звена}

{8}        Ring^.Adrcled := Ring; {Закольцовывается заглавное звено, так как}

{9}        Ring^.Adrpred := Ring; {на каждом промежуточном этапе список должен быть кольцом}

       Read (Bykva); {Чтение первой буквы текста}

       While Bykva <> ’.’ Do        

               Begin

                       Vstav (Bykva, Ring^.Adrpred); {Вызов процедуры вставки. Адрес предыдущего созданного звена (последнего звена кольца) всегда хранится в заглавном звене в поле Adrpred}

                       Read (Bykva) {Чтение очередной буквы текста}

               End

End.

Схематические пояснения к данной программе содержит рисунок 7.12.

Рисунок 7.12 – Схематические пояснения
к программе примера 7.10

На данном рисунке цифрами 1) – 6) обозначены номера этапов алгоритма вставки, приведенного в предыдущем подразделе, цифрами 7) – 9) – номера соответствующих операторов из примера 10.

Напомним, что список закольцовывается после добавления каждого нового звена.

7.2.3. Удаление элемента

Пусть в программе имеется описание типа, приведенное в примере 7.8.

Алгоритм удаления элемента:

Занесение в поле Adrpred следующего за удаляемым звена ссылки на предшествующее удаляемому звено из поля Adrpred удаляемого звена; Занесение в поле Adrcled предшествующего удаляемому звена ссылки на следующее за удаляемым звено из поля Adrcled удаляемого звена; Уничтожение удаляемого звена.

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

Пусть в изображенном фрагменте исходного списка удаляется звено 2 (рисунок 7.13).

Рисунок 7.13 – Фрагмент исходного двунаправленного списка

Результат удаления звена 2 выглядит так, как иллюстрирует рисунок 7.14.

Номера связей на данном рисунке соответствуют номерам этапов алгоритма удаления.

Рисунок 7.14 – Результат удаления звена 2

Пример 7.11.

Процедура удаления звена из двунаправленного списка. Номера операторов соответствуют номерам этапов алгоритма удаления звена.

Procedure Udalen (Udzv: Adr2); {Udzv – ссылка на удаляемое звено}

       Begin

{1}        Udzv^.Adrcled^.Adrpred := Udzv^.Adrpred;

{2}        Udzv^.Adrpred^.Adrcled := Udzv^.Adrcled;

{3}        Dispose (Udzv);

       End;

7.2.4. Поиск элемента

Поиск элемента в двунаправленном кольцевом списке аналогичен поиску элемента в цепочке (см. п. 7.1.3).

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

Пример 7.12.

Логическая функция поиска элемента в двунаправленном кольцевом списке с заглавным звеном. Если искомый элемент в списке есть, возвращаемое значение функции равно True, а параметру Iskadr присваивается ссылка на звено, содержащее данный элемент.

Function Poisk (Adr: Adr2; Elem: <Тип_элемента_списка>; Var Iskadr: Adr2):

       Boolean; {Adr – ссылка на заглавное звено; Elem – искомый элемент; Iskadr – адрес искомого элемента}

       Var