На этом шаге мы рассмотрим как вставить за ключом новый элемент в однонаправленный список.
Пусть 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
На следующем шаге мы рассмотрим удаление элемента однонаправленного списка.