Удаление некоторого элемента из списка, сформированного по принципу стека, и удаление элемента из списка, сформированного по принципу «очереди», программно реализуется одинаково. Единственное отличие – способ формирования списка, который определяет местоположение указателя списка (указатель указывает на последний элемент списка в случае стека и на первый элемент списка в случае «очереди»).
| 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 будет иметь первый элемент списка после формирования) – рисунки те же, что и в случае г) для «очереди»;
д) список существует, но искомый элемент в нем не найден – то же, что и для «очереди» в этом случае.