Шаг 12.
Удаление элемента однонаправленного списка

    На этом шаге мы рассмотрим удаление элемента однонаправленного списка.

    Рассмотрим два случая.

    1. Удаление звена, следующего за звеном с заданным указателем pCKey.

 Procedure Delete_Element (pCKey: PtrRec);
      var pAux : PtrRec;
  Begin
      pAux := pCKey^.pNext;
      If pCKey^.pNext <> Nil
         Then  Begin
                  pCKey^.pNext := pCKey^.pNext^.pNext;
                  Dispose (pAux);
               End;
  End;

    2. Удаление звена, на который указывает указатель pCKey. Н. Вирт указывает: "Труднее удалить сам указанный элемент (а не следующий за ним), поскольку возврат к элементу, который предшествует указанному, невозможен. Hо можно удалить последующий элемент, предварительно переслав его значение ближе к началу списка. Это довольно очевидный и простой прием, но его можно применить только в случае, когда у pCKey^ есть последующий элемент, т.е. он не является последним элементом списка". Реализуем данный алгоритм:

 Procedure Delete (pCKey : PtrRec);
     var  pAux : PtrRec;
  Begin
   If pCkey^.pNext <> Nil 
     Then  begin
              pAux := pCKey^.pNext;
              pAux^.Element := pCKey^.pNext^.Element;
              pCKey^.pNext := pCKey^.pNext^. pNext;
              Dispose (pAux);
           End
     Else Writeln ('Последний элемент в списке не удален!');
  End;

    Возможен другой способ удаления. Изобразим общую схему процесса удаления из списка компоненты, ссылка на который есть pCKey (см.рис.1).


Рис.1. Удаление компоненты из списка

    Процедура, исключающая из списка элемент, ссылка на который есть pCKey:

 Procedure Exclude_List (var pBegin: PtrRec; pCKey: PtrRec);
 {pCKey - указатель на исключаемый элемент}
    var pAux: PtrRec; 	{текущий указатель}
 Begin
     If pBegin = pCKey {Если ключ совпадает с первым элементом}
        Then
            pBegin := pCKey^.pNext
         Else 
              Begin
                  pAux := pBegin; 
                  While pAux^.pNext <> pCKey Do
                            pAux := pAux^.pNext;
                  pAux^.pNext := pCKey^.pNext;
              End; 
     Dispose(pCKey);	pCKey := Nil; 
 End;

    На следующем шаге мы рассмотрим получение копии однонаправленного списка.




Предыдущий шаг Содержание Следующий шаг