 ñòåêè èëè î÷åðåäè êîìïîíåíòû ìîæíî äîáàâëÿòü òîëüêîâ êàêîé -
ëèáî îäèí êîíåö ñòðóêòóðû äàííûõ, ýòî îòíîñèòñÿ è ê èçâëå÷åíèþ êîìïî-
íåíò.
Ñâÿçíûé (ëèíåéíûé) ñïèñîê ÿâëÿåòñÿ ñòðóêòóðîé äàííûõ, â ïðîèçâîëü-
íî âûáðàííîå ìåñòî êîòîðîãî ìîãóò âêëþ÷àòüñÿ äàííûå, à òàêæå èçûìàòü-
ñÿ îòòóäà.
Êàæäàÿ êîìïîíåíòà ñïèñêà îïðåäåëÿåòñÿ êëþ÷îì.Îáû÷íî êëþ÷ - ëèáî
÷èñëî, ëèáîñòðîêà ñèìâîëîâ. Êëþ÷ ðàñïîëàãàåòñÿ â ïîëå äàííûõ êîìïî-
íåíòû, îí ìîæåò çàíèìàòü êàê îòäåëüíîå ïîëå çàïèñè, òàê è áûòü ÷àñòüþ
ïîëÿ çàïèñè.
Îñíîâíûå îòëè÷èÿ ñâÿçíîãî ñïèñêà îò ñòåêà è î÷åðåäè ñëåäóþùèå:
-äëÿ ÷òåíèÿ äîñòóïíà ëþáàÿ êîìïîíåíòà ñïèñêà;
-íîâûå êîìïîíåíòû ìîæíî äîáàâëÿòü â ëþáîå ìåñòî ñïèñêà;
-ïðè ÷òåíèè êîìïîíåíòà íå óäàëÿåòñÿ èç ñïèñêà.
Íàä ñïèñêàìè âûïîëíÿþòñÿ ñëåäóþùèå îïåðàöèè:
-íà÷àëüíîå ôîðìèðîâàíèå ñïèñêà (çàïèñü ïåðâîé êîìïîíåíòû);
-äîáàâëåíèå êîìïîíåíòû â êîíåö ñïèñêà;
-÷òåíèå êîìïîíåíòû ñ çàäàííûì êëþ÷îì;
-âñòàâêà êîìïîíåíòû â çàäàííîå ìåñòî ñïèñêà (îáû÷íîïîñëå êîìïî-
íåíòû ñ çàäàííûì êëþ÷îì);
-èñêëþ÷åíèå êîìïîíåíòû ñ çàäàííûì êëþ÷îì èç ñïèñêà.
Äëÿ ôîðìèðîâàíèÿ ñïèñêà è ðàáîòû ñ íèì íåîáõîäèìî èìåòü ïÿòü ïåðå-
ìåííûõ òèïà óêàçàòåëü,ïåðâàÿ èç êîòîðûõ îïðåäåëÿåòíà÷àëî ñïèñêà,
âòîðàÿ - êîíåö ñïèñêà, îñòàëüíûå- âñïîìîãàòåëüíûå.
Îïèñàíèå êîìïîíåíòû ñïèñêà è ïåðåìåííûõ òèïà óêàçàòåëü äàäèìñëå-
äóþùèì îáðàçîì:
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.