Правила форума
Лекция №10.4: Адреса и указатели. Списочные структуры данныхСодержание
Оперирование элементами списка
Обращение к элементам списка
Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 10.2):
| p | — адрес текущего элемента списка; |
| p^ | — запись из нескольких полей, хранящаяся по адресу p; |
| p^.znachenie | — значение первого поля этой записи; |
| p^.next_element | — значение второго поля этой записи, являющееся адресом следующего элемента списка; |
| p^.next_element^.znachenie | — значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р. |
/10%2D2.gif)
Рис. 10.2. Правила обращения к элементам списка
Создание списков
Предположим, что есть некоторый набор значений (например, в файле), которые необходимо записать в создаваемый односвязный список. Тогда у нас есть две возможности создавать этот список: от хвоста к голове или от головы к хвосту.
Мы приведём здесь обе программы, позволив себе для краткости опустить описания типов, воспользовавшись описанием, показанным в табл. 1 (a):
var head, p : ukazatel; f : Text; begin {...} head := nil; while not Eof(f) do begin New(p); Read(f, p^.znach); p^.next := head; head := p; end; end. |
Рис. 10.3. Очередной шаг процесса генерации списка «от хвоста к голове» |
var head, p, q : ukazatel; f : Text; begin {...} if Eof(f) then head := nil else begin New(head); {головной элемент создаётся отдельно} Read(f, head^.znach); head^.next := nil; q := head; while not Eof(f) do begin New(p); Read(f, p^.znach); p^.next := nil; q^.next := p; q := q^.next; end; end; end. |
Рис. 10.4. Очередной шаг процесса генерации списка «от головы к хвосту» |
/10%2D3.gif)
/10%2D4.gif)
Просмотр элементов списка
Для того чтобы распечатать значения, хранящиеся в элементах линейного односвязного списка, заданного указателем на голову, годится такая программа:
while p <> nil do
begin
WriteLn(p^.znach);
p := p^.next; {переход к следующему элементу списка}
end;
Замечание: Для того, чтобы во время работы со списком не произошло выхода за его пределы, любой список обязательно должен оканчиваться «нулевым» указателем nil.
Удаление элементов списка
Для того, чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента «остановиться» за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален (см. рис. 10.5):
while p^.next^.zhach <> x do
p := p^.next; {поиск}
q := p^.next; {удаляемый элемент}
p^.next := q^.next; {связка «через один»}
Dispose(q); {освобождение памяти}
Перестройка списков
Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге «Алгоритмы и структуры данных». Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.
Представим обычную очередь у прилавка в магазине. Первый покупатель — это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним — второй, за вторым — третий и т. д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперёд, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики «А вас тут не стояло!»), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.
/10%2D40.gif)
/10%2D41.gif)
Теперь возьмем другую очередь: в приёмной у зубного врача. Во–первых, посетители уже не привязаны так жёстко к линии прилавка: они сидят в креслах, расположенных там и сям, где только нашлось удобное место. Во–вторых, каждому вновь пришедшему нет необходимости знать, кто в этой очереди первый, а кто второй: достаточно лишь выяснить, кто последний. И вовсе не обязательно садиться рядом с последним пациентом: вновь пришедший может занять любое свободное кресло в приёмной. А если у кого–то вдруг перестали болеть зубы и он радостно уходит из очереди, то «стоявшему» за ним достаточно спросить: — «А вы за кем занимали?» При этом физического перемещения пациентов в пространстве не происходит. Аналогично, если вдруг появляется пациент с талончиком на более раннее время, «задние» пропускают его вперёд, не сдвигаясь со своих кресел. Именно так ведут себя и элементы динамических списков1.
/10%2D42.gif)
Примеры перестройки линейных списков
На рис. 10.5 приведены четыре примера перестройки односвязных списков. Пунктирами изображены указатели, получающие новые значения в процессе работы программ.
- Удаление всех нулей из списка.
- Вставка в список, хранящий все нечётные числа от 1 до 11, трёх новых элементов — 0, 8 и 12 — с сохранением его упорядоченности.
- Обмен второго и третьего элементов списка.
- Обращение порядка всех чётных элементов списка.
Реализация
Приведём фрагменты программ, решающих первую и третью задачи:
- {- голову списка обрабатываем отдельно -}
while (head <> nil) and (head^.znach = 0) do
begin
p := head;
head := head^.next;
Dispose(p);
end;
{- середина и конец списка обрабатываются вместе -}
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;
- p := head^.next;
head^.next := p^.next;
p^.next := p^.next^.next;
head^.next^.next := p;
/10%2D5.gif)
Рис. 10.5. Примеры перестройки односвязных списков
Примечания
- ^ Предположим, что в нашем примере каждый пациент приходит со своим креслом — это будет аналогом динамического выделения памяти под переменные.
::
::
::
