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

Итак, в цепочке для каждого элемента надо знать, где находится следующий. Чтобы реализовать эту идею, следует представить каждый элемент (звено) связанного списка (цепочки) в виде записи, состоящей из двух полей. В первом поле находится сам элемент (данное какого-то типа, в нашем случае - типа CHAR), второе содержит ссылку на следующее звено цепочки (тип - ссылка). Конец списка (цепочки) помечается указателем NIL, а начало формируется переменной типа указатель, содержащей ссылку на первый элемент списка.

Пусть в памяти ЭВМ находится цепочка (строка) 'PASCAL', которая инициализируется (связывается) с переменной-ссылкой STR. Это можно представить в виде схемы:

1) CHAR - для обозначения самого элемента цепочки;

2) RECORD - для образования звеньев цепочки из двух полей;

3) ссылку (^) - для установления связи между звеньями.

Обозначим тип ссылочной переменной через SVYAZ, а тип динамической переменной через ZVSTR (звено строки). Этот факт описывается следующим образом: type SVYAZ = ^ZVSTR. Говорят, что тип SVYAZ указывает (ссылается) на компоненты типа ZVSTR, или тип SVYAZ связан с типом ZVSTR.

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

type ZVSTR = record

elem: char;

sled: SVYAZ;

end.

Мы видим, что здесь при описании типов происходит перекрытие имен. Возникает вопрос, какой тип поставить первым и возможно ли это в принципе, ведь прежде чем упомянуть идентификатор, необходимо описать его тип. Однако правила языка Паскаль делают исключение при описании ссылок, поэтому допускается использование идентификатора ZVSTR до его описания:

type SVYAZ = ^ZVSTR;

ZVSTR = record

elem: char;

sled: SVYAZ;

end.

Теперь остается с помощью VAR ввести ссылочную переменную (в нашем примере STR), в которую нужно записать ссылку на первое звено цепочки. Следовательно, эта переменная также должна иметь тип SVYAZ.

Итак, VAR STR: SVYAZ.

С точки зрения техники программирования выход на цепочку осуществляется через его заглавное (нулевое) звено. Отсюда имеем:

STR - ссылочная переменная, указывающая на первое звено;

STR^- сама динамическая переменная;

STR^.elem - поле символьного значения (информационное поле);

STR^.sled - поле ссылки.

ПРИМЕР 7. Схема образования цепочки динамических данных

1. Зарезервировать место в памяти для указателей

2. Зарезервировать место в памяти для значений динамических переменных и поместить их адреса в указатели UKZV и UKSTR:

NEW(UKZV); NEW(UKSTR);

3. Заполнить поля ELEM значениями UKSTR^.ELEM:='P';

UKZV^.ELEM:='A':

4. Заполнить поля SLED значениями UKSTR^.SLED:=UKZV;

UKZV^.SLED:=NIL:

Это пример построения цепочки из двух звеньев. Если же звеньев много, то все следует делать в цикле. Рассмотрим пример образования и распечатки цепочки, состоящей из последовательности букв и заканчивающейся ".".

Несколько предварительных соображений по данному примеру:

1) для ссылки на цепочку как единое целое введен указатель UKSTR;

2) для ссылки на очередное звено в цепочке введен указатель UKZV;

3) для продвижения по цепочке от одного звена к другому нужно текущему указателю UKZV присваивать в качестве значения ссылку на это следующее звено: UKZV:= UKZV^.SLED;

4) т.к. поле SLED имеет тип SVYAZ, т.е. ссылку на запись, то можно записать UKZV^.SLED^.SLED, что означает переход на звено, находящееся через звено от исходного;

5) при организации цепочки будем использовать "нулевое" (заглавное) звено, которое указывает на первое звено цепочки и не содержит никакого элемента. Так поступают для удобства обработки цепочки в цикле.

ПРИМЕР 8. Формирование и распечатка цепочки символов

program SOZDANIE_ZEPOCHKI;

type SVYAZ = ^ZVSTR;

ZVSTR = record

elem: char; sled: SVYAZ;

end;

var UKSTR, UKZV: SVYAZ; SYM: char;

begin { Создание головного (нулевого) звена }

¦ new(UKSTR); UKZV:= UKSTR; UKZV^.sled:= nil;

¦ read(SYM);

¦ { Создание всей цепочки}

¦ while SYM <> '.' do

¦ begin

¦ ¦ new(UKZV^.sled); UKZV:= UKZV^.sled;

¦ ¦ UKZV^.elem:= SYM; UKZV^.sled:= nil;

¦ ¦ read(SYM);

¦ end;

¦ UKZV:= UKSTR^.sled; writeln; {Печать цепочки}

¦ while UKZV <> nil do

¦ begin

¦ ¦ write(UKZV^.elem,' ');

¦ ¦ UKZV:= UKZV^.sled;

¦ end;

end.

ПРИМЕР 9. Процедура удаления из списка SP элемента, содержащего в качестве данных некоторую букву

procedure UDALENIE_VNUTRI(var SP: SVYAZ; BUKVA: char);

var ZV: SVYAZ;

begin

¦ if SP = nil then writeln('Нет такого элемента!') else

¦ if SP^.elem <> BUKVA then UDALENIE(SP^.sled, BUKVA)

¦ else begin ZV:=SP; SP:=SP^.sled;

¦ dispose(ZV); end;

end.

ПОЯСНЕНИЕ. Данная процедура является рекурсивной. Выход из рекурсии осуществляется либо по нахождению и удалению соответствующей буквы, либо по достижению конца цепочки (обнаружение ссылки NIL). При удалении звена освобождается место в памяти с помощью DISPOSE.

Последний пример показывает, что для удаления одного элемента из цепочки достаточно применение одного оператора:

SP:= SP^.SLED.

И это действительно так, ибо устранение звена не есть его "физическое" уничтожение, а переброска ссылки на следующее звено, как это показано на схеме

ПРИМЕР 10. Процедура удаления первого элемента цепочки

procedure UDALENIE_NACHALO(var SP: SVYAZ);

var Q: SVYAZ;

begin

¦ if SP^.sled <> nil then

¦ begin

¦ ¦ Q:= SP;

¦ ¦ SP:= SP^.sled;

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39