- •Лекция №10. Адреса и указатели. Списочные структуры данных
- •Содержание
- •Статически выделяемая память
- •Указатели
- •Описание указателей
- •Операции с указателями Определение адреса
- •Разыменование
- •Присваивания
- •Сравнения
- •Динамически распределяемая память
- •Динамическое выделение памяти Типизированные указатели
- •Нетипизированные указатели
- •Динамическое освобождение памяти Типизированные указатели
- •Нетипизированные указатели
- •Списочные структуры
- •Структура списков
- •Описание списков
- •Оперирование элементами списка Хранение списка
- •Обращение к элементам списка
- •Создание списков
- •Просмотр элементов списка
- •Удаление элементов списка
- •Перестройка списков
- •Примеры перестройки линейных списков
- •Реализация
Удаление элементов списка
Для того чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента "остановиться" за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален (см. рис. 10.5):
p:= head; {начать с головы списка}
while p^.next^.zhach<>х do p:= p^.next; {поиск}
q:= p^.next; {удаляемый элемент}
p^.next:= q^.next; {связка "через один"}
dispose(q); {освобождение памяти}
Перестройка списков
Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге "Алгоритмы и структуры данных". Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.
Представим обычную очередь у прилавка в магазине. Первый покупатель - это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним - второй, за вторым - третий и т.д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперед, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики "А вас тут не стояло!"), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.
Теперь возьмем другую очередь: в приемной у зубного врача. Во-первых, посетители уже не привязаны так жестко к линии прилавка: они сидят в креслах, расположенных там и сям, где только нашлось удобное место. Во-вторых, каждому вновь пришедшему нет необходимости знать, кто в этой очереди первый, а кто второй: достаточно лишь выяснить, кто последний. И вовсе не обязательно садиться рядом с последним пациентом: вновь пришедший может занять любое свободное кресло в приемной. А если у кого-то вдруг перестали болеть зубы и он радостно уходит из очереди, то "стоявшему" за ним достаточно спросить: - "А вы за кем занимали?" При этом физического перемещения пациентов в пространстве не происходит. Аналогично, если вдруг появляется пациент с талончиком на более раннее время, "задние" пропускают его вперед, не сдвигаясь со своих кресел. Именно так ведут себя и элементы динамических списков.
Примеры перестройки линейных списков
На рис. 10.5 приведены четыре примера перестройки односвязных списков. Пунктирами изображены указатели, получающие новые значения в процессе работы программ.
Удаление всех нулей из списка.
Вставка в список, хранящий все нечетные числа от 1 до 11, трех новых элементов - 0, 8 и 12 - с сохранением его упорядоченности.
Обмен второго и третьего элементов списка.
Обращение порядка всех четных элементов списка.
Реализация
Приведем фрагменты программ, решающих первую и третью задачи:
1. {- голову списка обрабатываем отдельно -}
while (head<>nil)and(head^.znach =0)do
begin p:= head;
head:= head^.next;
dispose(p);
end;
2. {- середина и конец списка обрабатываются вместе -}
p:= head;
while p^.next <> nil do
if p^.next^.znach = 0
then begin q:= p^.next;
p^.next:= p^.next^.next;
dispose(q);
end
else
p:= p^.next;
3. p:= head^.next;
head^.next:= p^.next;
p^.next:= p^.next^.next;
head^.next^.next:= p;
Рис. 10.5. Примеры перестройки односвязных списков