Пояснения к программе
В разделе описания типов объявлен тип Zveno, содержащий следующие поля: Elem – элемент звена (информационное поле), Next – указатель на следующее звено.
Формирование списка из трёх звеньев по принципу «очереди»:
а) L1:=Nil; в) New(X);
New(X); Pr^.Next:=X;
Readln(X^.Elem);
Pr:=X;
б) L1:=X; г) New(X);
Readln(X^.Elem); Pr^.Next:=X;
Pr:=X; Readln(X^.Elem);
Pr:=X;
X^.Next:=Nil;
В процедуре Form вначале переменная L1 полагается равной Nil, и выделяется динамическая память под 1-ое звено (переменная Х – указатель на 1-ое звено). Далее, если L1 равно Nil, в L1 заносится указатель на первое звено, т. е. в L1 будет находиться указатель на начало списка. В поле Elem этого звена с клавиатуры вводится 1-й элемент. В переменной Pr запоминается указатель на 1-ое звено.
После этого выделяется память под 2-ое звено (переменная Х – указатель на 2-ое звено). В поле Next 1-ого звена копируется значение переменной Х, т. е. в это поле заносится указатель на 2-ое звено. Затем заполняется поле Elem 2-ого звена. После этого в переменной Pr запоминается указатель на 2-ое звено.
Аналогично формируется 3-е звено. В поле Next последнего звена заносится Nil. Таким образом, список будет содержать звенья, связанные между собой, причем, 1-ое звено будет стоять в начале списка, а последнее – в конце. В переменной L1 будет находиться указатель на начало списка.
В процедуре Search осуществляется последовательный перебор элементов списка, пока не будет найден искомый элемент или не достигнут конец списка. В конце процедуры на экран выводится соответствующее сообщение.
Процедура Wywod выводит элементы всех звеньев списка до и после удаления. Для вывода списка используется переменная L1, при этом адрес начала не изменяется, т. к. L1 – параметр–значение.
Удаление элемента из линейного однонаправленного списка
Удаление некоторого элемента из списка, сформированного по принципу стека, и удаление элемента из списка, сформированного по принципу «очереди», программно реализуется одинаково. Единственное отличие – способ формирования списка, который определяет местоположение указателя списка (указатель указывает на последний элемент списка в случае стека и на первый элемент списка в случае «очереди»).
Program Primer1; Uses Crt; Type Spisok = ^ Zveno; Zveno = Record Elem : Integer; Next : Spisok; End; Var L : Spisok; E : Integer; Procedure Form(Var L1 : Spisok); … Procedure Delete(Var L1: Spisok; E1: Integer); Label 1; Var X, Pr : Spisok; Flag : Boolean; Begin Flag:=False; X:=L1; If L1 <> Nil Then If L1^.Elem = E Then Begin Flag:=True; L1:=L1^.Next; Dispose(X); End Else Begin Pr:=X; X:=X^.Next; End Else Begin Writeln(‘Пустой список’); Goto 1; End; While (X <> Nil) and (not Flag) Do Begin If X^.Elem = E Then Begin Flag:=True; Pr^.Next:=X^.Next; Dispose(X); End Else Begin Pr:=X; X:=X^.Next; End; End; If Flag Then Writeln(‘Е=’,E,’ удален’); Else Writeln(‘Е=’,E,’ не найден’); 1: End; Procedure Wywod(L1 : Spisok); … |
{тип – указатель на тип-запись} {тип - запись} {информационное поле записи} {указатель на следующее звено списка}
{указатель} {искомый элемент списка} {процедура формирования списка}
{процедура поиска и удаления элемента Е}
{X – рабочая переменная} {Pr –указатель на предыдущее звено} {флаг того, что Е был найден и удален}
{элемент Е еще не найден} {инициализация рабочей переменной} {если список не пустой} {то если последний элемент равен Е}
{то установка флага} {предпосл. элемент теперь последн. в списке} {удаление бывшего последнего элемента - } {возврат памяти в кучу}
{иначе} {текущий указатель перемещаем на} {предпоследний элемент} {если список пустой, то} {вывод сообщения «Пустой список»} {переход на метку 1 и выход из п/п}
{пока не достигнут конец списка} { и не найден элемент Е} {если текущий элемент равен Е}
{то установка флага}
{изменение указателя следующего элемента} {удаление Е из списка – возврат памяти}
{иначе текущий элемент теперь следующий} {а предыдущий теперь текущий} {конец цикла} {если Е был найден} {то вывод «Элемент Е удален»} {иначе вывод «Элемент Е не найден»} {конец процедуры Delete} {процедура вывода списка на экран} |
В процедуре Delete осуществляется удаление звена с элементом Е. При удалении звена рассматриваются пять случаев: а) список не существует; б) удаление первого звена; в) удаление среднего звена; г) удаление последнего звена; д) элемент Е не найден. Выход из процедуры происходит, как только звено Е удалено (по флагу Flag=True) или если достигнут элемент списка, у которого в поле Next записано значение Nil (первый элемент стека или последний элемент «очереди»), но элемент Е не найден. Для определенности пусть список сформирован по принципу «очереди».
Случай а) Если список не существует (список пустой), то на экран выводится сообщение «Пустой список» и происходит выход из процедуры Delete.
Рассмотрим работу процедуры Delete в случаях б) – г) на примере списка из 3-х звеньев.
Пусть исходный список имеет вид:
Случай б) Удаление первого звена списка:
1) Flag:=False;
X:=L1;
…
2) If L1 <> Nil
Then If L1^.Elem = E
Then Begin
Flag:=True;
L1:=L1^.Next;
…
3) Dispose (X);
Случай в) Удаление среднего звена:
1) Flag:=False;
X:=L1;
2) If L1 <> Nil
Then …
Else Begin
Pr:=X;
X:=X^.Next;
End
3) While (X <> Nil) and (not Flag)
Do Begin
If X^.Elem = E
Then Begin
Flag:=True;
Pr^.Next:=X^.Next;
…
4) Dispose(X);
Случай г) Удаление последнего звена:
1) Flag:=False;
X:=L1;
2) If L1 <> Nil
Then …
Else Begin
Pr:=X;
X:=X^.Next;
End
3) Pr:=X;
X:=X^.Next;
4) If X^.Elem = E
Then Begin
Flag:=True;
Pr^.Next:=X^.Next;
4) Dispose(X);
Случай д) Если список существует, но искомый элемент в нем не найден, то на экран выводится сообщение «Элементе Е не найден».
Примечание. Если рассматривать вышесказанное (удаление элемента из списка) в отношении списка, сформированного по принципу стека, то все рисунки будут те же, но формулировки различных случаев изменяться так:
а) список не существует - то же, что и для «очереди» в этом случае;
б) удаление последнего звена (т. к. в случае стека, L1 будет указывать на последний элемент списка после формирования) – рисунки те же, что и в случае б) для «очереди»;
в) удаление среднего звена (аналогично случаю в) для «очереди») - рисунки те же, что и в случае б) для «очереди»;
г) удаление первого звена (т. к. в случае стека, указатель Nil будет иметь первый элемент списка после формирования) – рисунки те же, что и в случае г) для «очереди»;
д) список существует, но искомый элемент в нем не найден – то же, что и для «очереди» в этом случае.