ЛИНЕЙНЫЕ СПИСКИ

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

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

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

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

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

Над списками выполняются следующие операции:

начальное формирование списка (запись первой компоненты);
добавление компоненты в конец списка;
чтение компоненты с заданным ключом;
вставка компоненты в заданное место списка (обычно после компо- ненты с заданным ключом);
исключение компоненты с заданным ключом из списка.

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

Описание компоненты списка и переменных типа указатель дадим сле- дующим образом:

type PComp= ^Comp; Comp= record D:T; pNext:PComp end; var pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

где pBegin - указатель начала списка, pEnd - указатель конца списка, pCKey, pPreComp, pAux - вспомогательные указатели.

Начальное формирование списка, добавление компонент в конец списка выполняется так же, как и при формировании очереди.

г===== г===== г===== г===== г===== г=====¦ *--¦- ¦ D1 ¦ ¦ D2 ¦ ¦ DN1 ¦ ¦ DN ¦ --¦--* ¦L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-pBegin L-->¦ *--¦--->¦ *--¦-....->¦ *--¦--->¦ NIL ¦<-- pEnd L=====- L=====- L=====- L=====-

Для чтения и вставки компоненты по ключу необходимо выполнить по- иск компоненты с заданным ключом:

pCKey:=pBegin; while (pCKey<>NIL) and (Key<>pCKey^.D) DO pCKey:=pCKey^.pNext;

Здесь Key - ключ, тип которого совпадает с типом данных компоненты.

После выполнения этих операторов указатель pСKey будет определять компоненту с заданным ключом или такая компонента не будет найдена.

Пусть pCKey определяет компоненту с заданным ключом. Вставка новой компоненты выполняется следующими операторами:

New(pAux); г=== pAux^.D:= DK1; ---¦-* ¦ ¦ L===- ¦ pCKey ¦г=== г=== г=== г=== г=== г===¦ *-¦-- ¦D1 ¦ ¦Key¦ ¦KK1¦ ¦DN ¦ ---¦-* ¦L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-pBegin L->¦ *-¦-...->¦ *-¦---->¦ *-¦-...->¦NIL¦<-- pEnd L===- L===- L===- L===- г=== г=== ¦DK1¦ ---¦-* ¦ ¦===¦ ¦ L===- ¦ ¦<-- pAux L===- pAux^.pNext:=pCKey^.pNext; pCKey^.pNext:=pAux; г=== ---¦-* ¦ ¦ L===- ¦ pCKey ¦г=== г=== г=== г=== г=== г===¦ *-¦-- ¦D1 ¦ ¦Key¦ ¦KK1¦ ¦DN ¦ ---¦-* ¦L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-pBegin L->¦ *-¦-...->¦ * ¦ ¦ *-¦-...->¦NIL¦<-- pEnd L===- L===- L===- L===- ¦ ^ ¦ ¦ г=== г=== ¦ ¦ ¦DK1¦ ---¦-* ¦ ¦ L----------¦===¦ ¦ L===- L------------------->¦-* ¦<-- pAux L===-

Для удаления компоненты с заданным ключом необходимо при поиске нужной компоненты помнить адрес предшествующей:

pCKey:=pBegin; while (pCKey<>NIL) and (Key<>pCKey^.D) do begin pPreComp:=pCKey; pCKey:=pCKey^.pNext end;

Здесь указатель pCKey определяет компоненту с заданным ключом, указа- тель pPreComp содержит адрес предыдущей компоненты.

Удаление компоненты с ключом Key выполняется оператором:

pPreComp^.pNext:=pCKey^.pNext; pPreComp pCKey г=== г=== ¦ * ¦ ¦ * ¦ L===- L===- ¦ ¦ ¦ ¦ ¦ ¦г=== г=== г=== г=== г=== г=== г===¦ *-¦-- ¦D1 ¦ ¦KK1¦ ¦Key¦ ¦KK2¦ ¦DN ¦ ---¦-* ¦L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-pBegin L->¦ *-¦-...->¦ *-¦- ¦ *-¦--->¦ *-¦-...->¦NIL¦<-- pEnd L===- L===- ¦ L===- L===- L===- ¦ ^ ¦ ¦ L---------------

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

Program LISTLINKED; uses Crt; type Alfa= String[10]; PComp= ^Comp; Comp= record sD:Alfa; pNext:PComp end; var pBegin, pEnd, pAux, pCKey, pPreComp: PComp; sC, sKey: Alfa; bCond: Boolean; Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa); begin New(pBegin); pBegin^.pNext:=NIL; pBegin^.sD:=sC; pEnd:=pBegin end; Procedure AddLL(var pEnd: PComp; var sC: Alfa); var pAux: PComp; begin New(pAux); pAux^.pNext:=NIL; pEnd^.pNext:=pAux; pEnd:=pAux; pEnd^.sD:=sC end; Procedure Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp; var bCond: Boolean); begin pCKey:=pBegin; while (pCKey <> NIL) and (sKey <> pCKey^.D) do begin pPreComp:=pCKey; pCKey:=pCKey^.pNext end; if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE else bCond:=TRUE end; Procedure InsComp(var sKey,sC: Alfa); var pAux:PComp; begin Find(sKey,pBegin,pCKey,pPreComp,bCond); New(pAux); pAux^.sD:=sC; pAux^.pNext:=pCKey^.pNext; pCKey^.pNext:=pAux end; Procedure DelComp(var sKey: Alfa; var pBegin: PComp); begin Find(sKey,pBegin,pCKey,pPreComp,bCond); pPreComp^.pNext:=pCKey^.pNext end; begin ClrScr; writeln(' ВВЕДИ СТРОКУ '); readln(sC); CreateLL(pBegin,pEnd,sC); repeat writeln('ВВЕДИ СТРОКУ '); readln(sC); AddLL(pEnd,sC) until sC='END'; writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****'); pAux:=pBegin; repeat writeln(pAux^.sD); pAux:=pAux^.pNext; until pAux=NIL; writeln; writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ'); readln(sKey); writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ'); readln(sC); InsComp(sKey,sC); writeln; writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ'); readln(sKey); DelComp(sKey,pBegin); writeln; writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****'); pAux:=pBegin; repeat writeln(pAux^.sD); pAux:=pAux^.pNext; until pAux=NIL end.