Раздел 7.Динамические структуры данных Динамические цепочки Структура динамической цепочки
Динамические цепочки являются аналогами строк текущей длины.
В строке каждый следующий элемент занимает ячейку памяти со следующим по порядку адресом.
Элементы строки можно размещать в памяти произвольно, если каждый элемент снабдить явным указанием места, где находится следующий за ним элемент. В этом случае каждый элемент строки должен состоять из двух полей: в одном поле (Element) – символ сроки, в другом (Adrcled) – ссылка на следующий элемент строки (адрес следующего элемента).
Каждая такая пара называется звеном. Ссылки сцепляют звенья в одну цепочку.
Такой способ представления упорядоченной последовательности элементов называется сцеплением. Сцепление применяется для представления любых сложных динамических структур данных – строк, списков, деревьев и так далее. В этом случае звено всегда состоит из двух частей – тела звена (элемента последовательности) и справочной части (ссылки на другие элементы структуры).
Таким образом, для представления звена необходимо использовать запись, состоящую из двух полей.
Пример 7.1.
Объявление звена цепочки.
Type
Adr = ^Zveno;
Zveno = Record
Element: Char;
Adrcled: Adr
End;
В примере 7.1 тип Adr представляет собой ссылки на программные элементы типа Zveno.
В данном примере имя типа Zveno используется до его описания при описании типа Adr (ссылочного типа). Ссылочный тип – единственный тип, где можно использовать имя до его описания. Обратную последовательность объявлений (вначале описать тип Zveno, а потом – тип Adr) в примере 7.1 использовать было бы нельзя (так как в типе Zveno используется неописанный тип Adr, а Zveno не является ссылочным типом).
Последнее звено цепочки должно быть снабжено ссылкой Nil (это признак конца цепочки).
Для работы с цепочкой необходимо использовать два указателя: ссылку на ее первое звено (Adr1) и ссылку на текущее звено (Adrzv). Ссылки должны иметь тип Adr. Например,
Var Adr1, Adrzv: Adr;
Схематично цепочка может быть представлена так, как изображает Рисунок 7 .56.
Рисунок 7.56 – Схематическое представление цепочки
Для удобства работы с цепочкой в нее обычно включается заглавное «нулевое» звено (хотя это и не обязательно). В поле Adrcled данного звена содержится ссылка на первое звено цепочки (его адрес). Поле Element может быть использовано для хранения какой-либо информации о строке.
Формирование цепочки
Пусть имеется объявление звена цепочки, соответствующее примеру 7.1.
Алгоритм формирования цепочки:
Отвести область памяти для очередного звена. Его адрес занести в поле Adrcled текущего звена.
Новое звено сделать текущим (занести его адрес в указатель текущего звена Adrzv).
В поле Element текущего звена занести очередной символ.
В поле Adrcled текущего звена занести Nil.
Прочитать следующий символ исходного текста.
Повторить этапы алгоритма, начиная с первого этапа.
Предварительно перед выполнением этапов 1 – 6 алгоритма необходимо сформировать заглавное звено.
Схематические пояснения к алгоритму формирования цепочки с заглавным звеном представляет Рисунок 7 .57.
На данном рисунке номерами в фигурных скобках представлены действия соответствующих этапов алгоритма.
Рисунок 7.57 - Схематические пояснения к алгоритму формирования цепочки
Пример 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} операторов программы, приведенной в данном примере, соответствуют номерам этапов алгоритма формирования цепочки.
Над динамическими цепочками определены три операции:
поиск;
вставка;
удаление.