Лекция №10.4: Адреса и указатели. Списочные структуры данных

страницы: 1 2 3 4

Содержание

Оперирование элементами списка

Обращение к элементам списка

Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 10.2):

pадрес текущего элемента списка;
p^— запись из нескольких полей, хранящаяся по адресу p;
p^.znachenie— значение первого поля этой записи;
p^.next_element— значение второго поля этой записи, являющееся адресом следующего элемента списка;
p^.next_element^.znachenie— значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р.

Правила обращения к элементам списка

Рис. 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.  Очередной шаг процесса генерации списка «от головы к хвосту»

Просмотр элементов списка

Для того чтобы распечатать значения, хранящиеся в элементах линейного односвязного списка, заданного указателем на голову, годится такая программа:

p := head;      {начать просмотр с головы списка}
while p <> nil do
begin
 WriteLn(p^.znach);
  p := p^.next;   {переход к следующему элементу списка}
end;

Замечание: Для того, чтобы во время работы со списком не произошло выхода за его пределы, любой список обязательно должен оканчиваться «нулевым» указателем nil.

Удаление элементов списка

Для того, чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента «остановиться» за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален (см. рис. 10.5):

p := head;                               {начать с головы списка}
while p^.next^.zhach <> x do
  p := p^.next;                          {поиск}
q := p^.next;                            {удаляемый элемент}
p^.next := q^.next;                      {связка «через один»}
Dispose(q);                              {освобождение памяти}

Перестройка списков

Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге «Алгоритмы и структуры данных». Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.

Представим обычную очередь у прилавка в магазине. Первый покупатель — это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним — второй, за вторым — третий и т. д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперёд, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики «А вас тут не стояло!»), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.

10-40.gif

10-41.gif

Теперь возьмем другую очередь: в приёмной у зубного врача. Во–первых, посетители уже не привязаны так жёстко к линии прилавка: они сидят в креслах, расположенных там и сям, где только нашлось удобное место. Во–вторых, каждому вновь пришедшему нет необходимости знать, кто в этой очереди первый, а кто второй: достаточно лишь выяснить, кто последний. И вовсе не обязательно садиться рядом с последним пациентом: вновь пришедший может занять любое свободное кресло в приёмной. А если у кого–то вдруг перестали болеть зубы и он радостно уходит из очереди, то «стоявшему» за ним достаточно спросить: — «А вы за кем занимали?» При этом физического перемещения пациентов в пространстве не происходит. Аналогично, если вдруг появляется пациент с талончиком на более раннее время, «задние» пропускают его вперёд, не сдвигаясь со своих кресел. Именно так ведут себя и элементы динамических списков1.

10-42.gif

Примеры перестройки линейных списков

На рис. 10.5 приведены четыре примера перестройки односвязных списков. Пунктирами изображены указатели, получающие новые значения в процессе работы программ.

  1. Удаление всех нулей из списка.
  2. Вставка в список, хранящий все нечётные числа от 1 до 11, трёх новых элементов — 0, 8 и 12 — с сохранением его упорядоченности.
  3. Обмен второго и третьего элементов списка.
  4. Обращение порядка всех чётных элементов списка.
Реализация

Приведём фрагменты программ, решающих первую и третью задачи:

  1. {- голову списка обрабатываем отдельно -}
    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;
  1. p := head^.next;
    head^.next := p^.next;
    p^.next := p^.next^.next;
    head^.next^.next := p;

Примеры перестройки односвязных списков

Рис. 10.5.  Примеры перестройки односвязных списков

страницы: 1 2 3 4

Примечания

  1. ^ Предположим, что в нашем примере каждый пациент приходит со своим креслом — это будет аналогом динамического выделения памяти под переменные.
Код для вставки: :: :: :: ::
Поделиться: // //