|
Разделы сайта
|
Главнаяwm-help.net -> Электронная библиотека -> Pascal -> Pascal. Курс лекций. -> 40. Линейные списки
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є ЪДєДД* є
ИНННННј і єНННННє єНННННє єНННННє єНННННє і ИНННННј
pBegin АДД>є *ДДєДДД>є *ДДєД....Д>є*ДДєДДД>є NIL є<ДЩ pEnd
ИНННННј ИНННННј ИНННННј ИНННННј
Для чтения и вставки компоненты по ключу необходимо выполнить по-
иск компоненты с заданным ключом:
pCKey:=pBegin;
while (pCKey<>NIL) and (Key<>pCKey^.D) DO
pCKey:=pCKey^.pNext;
Здесь Key - ключ, тип которого совпадает с типом данных компоненты.
После выполнения этих операторов указатель pСKey будет определять
компоненту с заданным ключом или такая компонента не будет найдена.
Пусть pCKey определяет компоненту с заданным ключом. Вставка новой
компоненты выполняется следующими операторами:
New(pAux); ЙННН»
pAux^.D:= DK1; ЪДДєД* є
і ИНННј
і pCKey
і
ЙННН» ЙННН» ЙННН» ЙННН» ЙННН» ЙННН»
є *ДєДДїєD1 є єKeyє єKK1є єDN є ЪДДєД* є
ИНННј і єНННє єНННє єНННє єНННєі ИНННј
pBegin АД>є *ДєД...Д>є *ДєДДДД>є *ДєД...Д>єNILє<ДЩ pEnd
ИНННј ИНННј ИНННј ИНННј
ЙННН» ЙННН»
єDK1єЪДДєД* є
єНННєі ИНННј
є є<ДЩ pAux
ИНННј
pAux^.pNext:=pCKey^.pNext;
pCKey^.pNext:=pAux;
ЙННН»
ЪДДєД* є
і ИНННј
і pCKey
і
ЙННН» ЙННН» ЙННН» ЙННН» ЙННН» ЙННН»
є *ДєДДїєD1 є єKeyє єKK1є єDN є ЪДДєД* є
ИНННј і єНННє єНННє єНННє єНННєі ИНННј
pBegin АД>є *ДєД...Д>є * є є *ДєД...Д>єNILє<ДЩ pEnd
ИНННј ИНННј ИНННј ИНННј
і ^
і і ЙННН» ЙННН»
і і єDK1єЪДДє-* є
і АДДДДДДДДДДєНННє і ИНННј
АДДДДДДДДДДДДДДДДДДД>єД* є<ДЩ pAux
ИНННј
Для удаления компоненты с заданным ключом необходимо при поиске
нужной компоненты помнить адрес предшествующей:
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
ЙННН» ЙННН»
є * є є * є
ИНННј ИНННј
і і
і і
і і
ЙННН» ЙННН» ЙННН» ЙННН» ЙННН» ЙННН» ЙННН»
є *ДєДДїєD1 є єKK1є єKeyє єKK2є єDN єЪДДєД* є
ИНННј і єНННє єНННє єНННє єНННє єНННє і ИНННј
pBegin АД>є *ДєД...Д>є *ДєДї є *ДєДДД>є *ДєД...Д>єNILє<ДЩ pEnd
ИНННј ИНННј і ИНННј ИНННј ИНННј
і ^
і і
АДДДДДДДДДДДДДДЩ
Пример. Составить программу, которая формирует список, добавляет в
него произвольное количество компонент, выполняет вставку и удаление
компоненты по ключу,а затем читает и выводит весь списокна экран
дисплея. В качестве данных взять строку символов.Ввод данных - с
клавиатуры дисплея, признак конца ввода - строка символов 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.