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

Схематические пояснения к алгоритму формирования цепочки с заглавным звеном представляет рисунок 7.2.

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

Рисунок 7.2 – Схематические пояснения
к алгоритму формирования цепочки

Пример 7.2.

Формирование цепочки. Ввод исходной строки и представление ее в виде цепочки. Признак окончания строки – точка. Раздел типов соответствует примеру 7.1.

…

Var

       Adr1, Adrzv: Adr; {Adr1 – адрес заглавного звена, Adrzv – адрес текущего звена}

       Simv: Char;

Begin

       {Формирование заглавного звена цепочки}

       New (Adr1); {Отводится место в памяти для заглавного звена цепочки}

       Adrzv := Adr1; {Формируется адрес текущего звена}

       Adrzv^.Adrcled := Nil; {При формировании цепочки текущее звено всегда является последним, поэтому адрес следующего звена – Nil}

       Read (Simv); {Читается первая буква исходного текста}

       {Формирование текущих звеньев цепочки}

       While Simv <> ’.’ Do

               Begin

{1}                New (Adrzv^.Adrcled);

{2}                Adrzv := Adrzv^.Adrcled;

{3}                Adrzv^.Element := Simv;

{4}                Adrzv^.Adrcled := Nil;

{5}                Read (Simv);                

               End

…

Номера {1} – {5} операторов программы, приведенной в данном примере, соответствуют номерам этапов алгоритма формирования цепочки.

Над динамическими цепочками определены три операции:

поиск; вставка; удаление.

7.1.3. Поиск элемента в цепочке

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

Adrzv:= Adrzv^.Adrcled,

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

Данный оператор присваивания является аналогом оператора

I := I+1,

выполняемого для получения номера I следующего элемента при векторном представлении строки типа Array Of Char или String.

Пример 7.3.

Поиск элемента в строке-цепочке (в продолжение примеров 7.1, 7.2). Подсчет числа его вхождений в строку.

…

Var

       K: Integer;

       Bykva: Char;

Begin

       …

       Adrzv := Adr1; {Адресу текущего звена присваивается значение адреса нулевого звена (заглавного)}

       K := 0; {Счетчик числа вхождений искомого элемента}

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

       While Adrzv^.Adrcled <> Nil Do {Пока не конец строки}

               Begin

                       Adrzv := Adrzv^.Adrcled; {Указателю присваивается значение адреса следующего звена}

                       If Adrzv^.Element = Bykva {Сравнивается содержимое поля элемента текущего звена с заданной буквой}

                               Then K := K+1;

               End;

       …

7.1.4. Удаление элемента из цепочки

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

Например, в исходной цепочке (рисунок 7.3) необходимо удалить элемент 2. Для этого нужно, чтобы звено 1 ссылалось на звено 3 (рисунок 7.4).

Рисунок 7.3 – Фрагмент исходной цепочки

Рисунок 7.4 – Результат удаления элемента 2

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

Пример 7.4.

Удаление из цепочки второго элемента (в продолжение примеров 7.1 – 7.3, см. рисунок 7.3, рисунок 7.4).

Для удаления необходимо использовать оператор

Adrzv^.Adrcled:=Adrzv^.Adrcled^.Adrcled

Поле адреса        Поле адреса элемента 2

элемента 1        (исключаемого)

В этом случае в указателе текущего звена Adrzv должен находиться адрес элемента 1 (предшествующего исключаемому).

Пример 7.5.

Процедура удаления элемента из цепочки (в продолжение примеров 7.1 – 7.3).

Procedure Udal (Zv: Adr);

       Var A: Adr;        {A – вспомогательная переменная}

Begin

       A := Zv^.Adrcled;        {В А заносится адрес удаляемого звена}

       Zv^.Adrcled := Zv^.Adrcled^.Adrcled;        {Удаление звена из цепочки}

       {или равноценно Zv^.Adrcled := А^.Adrcled;}

       Dispose (A)                {Освобождение памяти, занимаемой удаленным звеном}

End;

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

В примере 7.4 удаление элемента из цепочки выполняется быстрее, но память расходуется неэффективно (так как отсутствует процедура Dispose).

В примере 7.5 удаление звена из цепочки прооисходит медленнее, но память расходуется эффективнее.

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

7.1.5. Вставка элемента в цепочку

Вставка элемента в цепочку основывается на объединении отдельных звеньев в единую цепочку.

Пусть в исходную цепочку (рисунок 7.5) после элемента 1 необходимо вставить элемент 4.

Рисунок 7.5 – Фрагмент исходной цепочки

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

Рисунок 7.6 – Результат вставки элемента 4

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

Создать новую динамическую переменную (запись типа Zveno), которой будет представленно вставляемое звено. В поле Element этой пременной занести вставляемый элемент (символ). В поле Adrcled этой переменной занести ссылку, взятую из поля Adrcled предшествующего звена. В поле Adrcled предшествующего звена занести ссылку на это вставляемое звено.

Номерами 3), 4) (см. рисунок 7.6) обозначены действия, соответствующие третьему и четвертому этапам алгоритма.

Пример 7.6.

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

Procedure Vstav (Zv: Adr; El: Char); {Zv – адрес звена, предшествующего вставляемому}

       Var

               Q: Adr;

       Begin

{1}                New (Q);

{2}                Q^.Element := El;

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

{4}                Zv^.Adrcled := Q

       End;

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

7.1.6. Линейный однонаправленный список

Динамическая строка-цепочка является частным случаем линейного однонаправленного списка. В случае строки информационными элементами списка являются символы (тип Char). В общем случае информационными элементами списка могут быть значения любого типа – числа, массивы, записи и т. п. Принцип организации информационных элементов в список – тот же: информационный элемент очередного звена снабжается ссылкой на следующее звено.

Пример 7.7.

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

Type Adres1 = ^Zveno1;

               Zveno1 =        Record

                       Adrcled: Adres1;

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

                       End;

Элементами списка являются значения одного и того же типа.

Недостаток однонаправленного списка – по нему можно двигаться только в одном направлении, от заглавного звена к последнему звену списка. Это замедляет работу с ним.

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

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

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

Структура звена двунаправленного списка определяется описанием типа, приведенным в примере 7.8.