Шаг 11.
Вставка за ключом нового элемента в список

    На этом шаге мы рассмотрим как вставить за ключом новый элемент в однонаправленный список.

    Пусть pCKey определяет ссылку на компоненту с заданным ключом Key и нам требуется вставить элемент с информационным полем Elem за указатель pCKey.

    Рассмотрим алгоритм с помощью диаграмм "до и после" Д. Кнута:

    1 шаг. В динамической область памяти резервируем место для динамического объекта pNew:

 New(pNew);


Рис.1. Определение места для объекта pNew

    2 шаг. В информационное поле нового объекта помещаем значение элемента Elem, который необходимо вставить:

 pNew^.Element := Elem;


Рис.2. Помещение значения Elem в информационное поле pNew

    3 шаг. В поле ссылки на следующий элемент указателя pNew помещаем адрес элемента, следующего за компонентом, на которое указывает pCKey:

 pNew^.pNext := pCKey^.pNext;


Рис.3. Результат присваивания

    4 шаг. В поле ссылки на следующий элемент указателя pCKey помещаем адрес элемента pNew:

 pCKey^.pNext := pNew;


Рис.4. Результат вставки

    Оформим алгоритм в виде процедуры:

 Procedure Insert_Element2(Elem : Integer; pCKey : PtrRec);
   var pNew : PtrRec;
 Begin
   New(pNew);
   pNew^.Element := Elem;
   If pCKey <> Nil Then     	       {Если pCKey не последний в списке,}
          pNew^.pNext := pCKey^.pNext	{то разрываем старую связь}
       Else	                            {pCKey - последний в списке}
          pNew^.pNext := Nil;
   pCKey^.pNext := pNew;	             {образовали новую связь}
 End;

    Итак, приведем общую схему процесса вставки элемента в список за ключом Key:


Рис.5. Общая схема вставки в список новой компоненты за ключом Key

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




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