Динамическая реализация линейных списков
Динамическая реализация линейного списка, также как стека и очереди, основана на динамическом выделении и освобождении памяти для элементов списка. Логическая последовательность элементов списка создается ссылочными переменными с адресами последующих элементов (последний элемент имеет пустую ссылку nil).
Опять же для удобства реализации будем считать, что список ВСЕГДА содержит хотя бы один элемент-заголовок с адресом первого реального элемента списка. Это позволяет унифицировать процедуры добавления и удаления крайних элементов и устранить некоторые проверки. Адрес элемента-заголовка задается переменной-указателем pHead. Эта переменная устанавливается при первоначальном создании списка и в дальнейшем НЕ изменяется. Для реализации основных действий используются вспомогательные ссылочные переменные.
Необходимые объявления:
type pDinItem = ^ TDinItem; {ссылочный тип для адресации элементов списка}
TDinItem = record
{базовый тип, определяющий структуру элемента списка}
inf : <тип информационной части>;
next : pDinItem; {адрес следующего элемента}
end;
var pHead : pDinItem;
Создание пустого списка включает:
· выделение памяти под заголовок: new(pHead);
- установку пустой ссылочной части заголовка: pHead^.next := nil;
Проход по списку от первого элемента к последнему практически не отличается от прохода по очереди.
Поиск заданного элемента включает:
· установку вспомогательного указателя в адрес первого элемента списка
· организацию цикла прохода по списку с завершением либо по совпадению информационной части элемента с заданным значением, либо по достижению конца списка
- после завершения цикла проверить значение вспомогательного указателя и сделать вывод об успешности поиска
pCurrent := pHead^.next;
while (pCurrent <> nil) and (pCurrent^.inf <> ‘заданное значение’)
do pCurrent := pCurrent^.next;
if pCurrent = nil then ‘Элемента нет’ else ‘элемент найден’;
Удаление заданного элемента включает:
· поиск удаляемого элемента с определением адреса элемента-предшественника (для этого вводится еще одна вспомогательная ссылочная переменная pPrev, инициированная адресом заголовка и изменяющая свое значение внутри цикла)
· если удаляемый элемент найден, то изменяется ссылочная часть его предшественника:
pPrev^.next := pCurrent^.next
· удаляемый элемент обрабатывается необходимым образом, т.е. либо освобождается занимаемая им память, либо он включается во вспомогательный список
Добавление нового элемента ПОСЛЕ заданного включает:
· поиск заданного элемента с помощью вспомогательного указателя pCurrent
· выделение памяти для нового элемента с помощью еще одного указателя pTemp
· формирование полей нового элемента, в частности – настройка ссылочной части
pTemp^.next := pCurrent^.next;
· изменение ссылочной части текущего элемента на адрес нового элемента
pCurrent^.next := pTemp;
Добавление нового элемента ПЕРЕД заданным включает:
· поиск заданного элемента с одновременным определением элемента-предшественника (используются указатели pCurrent и pPrev)
· выделение памяти для нового элемента с помощью еще одного указателя pTemp
· формирование полей нового элемента, в частности – настройка ссылочной части: pTemp^.next := pCurrent;
· изменение ссылочной части элемента-предшественника на адрес нового элемента: pPrev^.next := pTemp;
Если при использовании списка часто приходится добавлять или удалять элементы в конце списка, то для уменьшения расходов на просмотр всего списка можно ввести второй основной указатель - на последний элемент списка. Это потребует изменения процедур удаления и добавления для отслеживания этого указателя.
Довольно часто используется упорядоченная разновидность линейного списка, в котором элементы выстраиваются в соответствии с заданным порядком, например – целые числа по возрастанию, текстовые строки по алфавиту. Для таких списков изменяется процедура добавления – новый элемент должен вставляться в соответствующее место для сохранения порядка элементов. Например, если порядок элементов определяется целыми числами по возрастанию, то при поиске подходящего места надо найти первый элемент, больший заданного и выполнить вставку ПЕРЕД этим элементом.
Дата добавления: 2020-07-18; просмотров: 467;