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

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

В стеки или очереди компоненты можно добавлять только в какой -

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

нент.

Связный (линейный) список является структурой данных, в произволь-

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

ся оттуда.

Каждая компонента списка определяется ключом. Обычно ключ - либо

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

ненты, он может занимать как отдельное поле записи, так и быть частью

поля записи.

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

-для чтения доступна любая компонента списка;

-новые компоненты можно добавлять в любое место списка;

-при чтении компонента не удаляется из списка.

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

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

-добавление компоненты в конец списка;

-чтение компоненты с заданным ключом;

-вставка компоненты в заданное место списка (обычно после компо-

ненты с заданным ключом);

-исключение компоненты с заданным ключом из списка.

Для формирования списка и работы с ним необходимо иметь пять пере-

менных типа указатель, первая из которых определяет начало списка,

вторая - конец списка, остальные- вспомогательные.

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

дующим образом:

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.