Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Линеііный односвязный список является самым простым видом связных списков. Такой список можно определить, в том числе, с помощью приведённого выше описания типа.
Процедуры работы с линейным односвязным списком на языке Паскаль.

Type
rell = ’elem; (* Указатель на запись *) elem = record

next: rell;

end; var
U: rell;

Структура такого списка показана на рисунке

nil
U
next

data
next

data
next

data
nil

Рис. 9.1 Односвязный линейный список

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

92

3BéHO — CIlMOé Hé]3BOé 3BéHO CnHCKI1, B KoTopoM He ci6R3I1HI›I X]3I1-
HHTI›GII HOJIé3HI›Ié QtlHHI›Ié. Ero cO3,QIIHHé ,QJIII OQHOCBII3HOFO CHHCKt1
MOWHo ocy ecTBHTb GuepyioiuriM o6]3I13OM!

var a, L1: listl; begin

new(L1);
L1’.next := nil; a L1;

YKtl3tlT III› HH HtlUOJIO CHHCKI1 L 1, 3HtlU HH M KOTO]3OFO IIBJIII T-
cp appeC Bepy erO 3BéHa, npepGTIIBJIIIéT CHHCOK KIIK é,QHHI›I H]3O-
F]3t1MMHI›I €I6T› KT.
YKtl3tlTéJII› HH Gneayio H 3JIéMéHT B HOcJIé@HéM 3BéHé GHHCKI1 HM T 3Hi1U HH n i 1 (NULL HHH H]3OCTO B FH/CH++ , CTO IIBJIII T- CEI H)3H3HtlKOM H FH HH ONO CHHGKtl.

procedure insert1(link: rell; info: ); var q: rell;

begin
new(q);
q’.data := info; q’.next := link’.next; link’.next := q
end;

procedure deleted(link:rell); var q: rell;

begin
if link’.next <> nil then begin
q := link’.next;
link’.next := link’.next’.next; dispose(q);
end end;

93
function search1(l: rell; info: <Тип>; var г: rell) :boolean;

var q: rell; begin
searchl := false; г nil;
q := l’.next;
while (q <> nil) and (г <> nil) do begin
if q’.data = info then begin
search := true; г q
end;
q := q’.next end
end;

Процедуры добавления и удаления звеньев являются кри- mпчecкuж u с точки зрения сохранения целостности списка. При неправильном выполнении этих процедур (т.е. при неправильной очерёдности выполнения операций присваивания) возможны 2 ошибочные ситуации:

1. 
   Список «рвётся» по месту вставки или удаления звена, и звено, оказавшее последним, замыкается либо само на себя (чаще всего) (т.е. указатель next или аналогичный ему в этом звене получает значение адреса этого же звена), либо на одно из пред- шествующих звеньев (в зависимости от неправильной реализации операций вставки или удаления звена). При попытке просмотра списка процедура просмотра зацикливается и бесконечно выво- дит содержимое одного и того же звена (или нескольких звеньев).
   
2. 
   Список так же «рвётся» по месту вставки или удаления звена, но указатель в звене, ставшем последним, получает какое- то произвольное значение, которое трактуется как адрес следую- щего звена (реально не существующего), у которого также есть указатель next, содержащий какой-то адрес, и так далее, до тех пор, пока случайно не попадётся блок данных, для которого ука- затель next не будет равен пулю. При попытке просмотра списка на дисплей сначала выводятся правильные данные, а затем слу-
   

94
чайный набор символов.

В обоих случаях к звеньям в «оторвавшейся» части («хво- сте») списка больше нет доступа, и хранящиеся в них данные можно считать потерянными.
Для предотвращения возникновения таких ошибок следует соблюдать правильный порядок проведения связей (т.е. при- сваивания указателей) при вставке нового звена и удалении су- ществующего (очерёдность операций указана в комментариях к листингу процедуры).