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

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

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 .58) необходимо удалить элемент 2. Для этого нужно, чтобы звено 1 ссылалось на звено 3 (Рисунок 7 .59).

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

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

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

Пример 7.4.

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

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

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 удаление звена из цепочки прооисходит медленнее, но память расходуется эффективнее.

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