[усть ТИП Т описан, как показано в (4.11). Каждая пере-яная этого типа состоит из трех компонент: идентифици-щего ключа, ссылки на следующий элемент и, возможно, РУ!пй информации, не указанной в (4.11).

;ругой

type Т = record key: integer, next: t T;

(4.11)

гпйсок элементов типа Т показан на рис. 4.6. Переменная-улка р указывает на первую компоненту списка. По-види-мому, самое простое действие, которое можно выполнить со

Рис. 4.6. Пример списка.

СПИСКОМ, показанным на рис. 4.6, - вставить в его начало некоторый элемент. Прежде всего этот элемент типа Т размещается в памяти, ссылка на него присваивается вспомогательной ссылочной переменной q. После этого ссылкам присваиваются новые значения, как показано в (4.12):

new{q); q\.next:=p; p:=q (4.12)

Заметим, что здесь важен порядок следования этих трех операторов.

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

р := nil; [начало с пустого списка} while и > О do

begin new(q); q\.next := p; p := q; q\.key n; nx n-l

(4.13)

0 - самый простой способ построения списка. Но при этом олуценный порядок элементов обратен порядку их поступ-ения . В некоторых случаях это нежелательно; следова-ьно, новые элементы должны добавляться в конец списка.

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

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

Рис. 4.7. Включение в список после р\.

и удаление элементов (выборочное изменение списка) и, разумеется, просмотр списка. Вначале мы рассмотрим включение в список.

Предположим, что элемент, на который указывает ссылка q, нужно включить в список после элемента, на который указывает ссылка р. Необходимые присваивания значений ссылкам показаны в (4.14), а их результат изображен на рис. 4.7.

q\.next .= р\.next; p\.next:=q (4.14)

Если требуется включение перед элементом, указанным р\, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет прохода к элементам, предшествующим данному. Однако простой трюк позволяет решить эту проблему, он показан в (4.1-5) и на рис. 4.8. Допустим, что ключ нового элемента есть

пет; 9t:=pt; ,5)

p\.key := k; pf.next:- q

Трюк состоит в том, что новая компонента в действитель' ности вставляется после р|, но затем происходит обмен значениями между новым элементом и р\.

Теперь мы рассмотрим процесс удаления из списка. УД ление элемента, следующего за р|, очевидно. В (4.16) оН показано в комбинации с Одновременным добавлением УД

ого элемента в начало другого списка (на которое ука-jgaeT д), Причем г - вспомогательная переменная типа Г.

- r:=::p\.next; p\.next ,- r\.next\

r\.next:=q; q:=r (4-16)

рйс. 4.9 иллюстрирует процесс (4.16) и показываот, что он достоит из циклического обмена значениями трех ссылок.

Г

Рис. 4.8. Включение в список перед р\.

Труднее удалить сам указанный элемент (а не следующий за ним), поскольку мы сталкиваемся с той же проблемой, что и при включении перед р\: возврат к элементу, который

Рис. 4.9. Удаление из списка и включение в другой список.

Предшествует указанному, невозможен. Но можно удалить последующий элемент, предварительно переслав его значение лиже к началу списка. Это довольно очевидный и простой рием, но его можно применить только в случае, когда у pf сть последующий элемент, т. е. он не является последним ЗДементом списка.

Теперь мы перейдем к основной операции прохода по иску. Предположим, что операция Р{х) должна выполняться с каждым элементом списка, первый элемент которого *сть р|. Эту задачу можно выразить следующим образом:

while список, на который указывает р, непуст do begin выполнить операцию Р;

перейти К следующему элементу

Ш end