Организация и функционирование компьютеров

         

Использование указателей для обработки списков


Указатели оказываются незаменимыми в задачах, связанных с добавлением и корректировкой данных в структурно организованных системах данных. Дело в том, что хранение данных в массивах наталкивается на серьезные технические трудности. Добавление данных возможно только вконец массива. Если играет роль порядок данных, то при вставке элемента в середину массива необходимо сдвинуть все остальные элементы. Это очень неудобно или даже невозможно, если номера данных по одному массиву используются в других массивах.

Существует другая возможность описывать упорядоченную последовательность данных - списком. В наборе технологических средств программирования списком называется совокупность однотипных упорядоченнных данных, снабженных средствами, позволяющими переходить от предыдущего значения к последующему. Наиболее естественно обеспечивается переход с помощью указателей. Именно, элемент списка будет состоять из двух частей: первая часть состоит из содержательных данных списка, а вторая часть представляет собой указатель, ссылающийся на следующий элемент списка. Указатель на первый элемент списка хранится в фиксированной переменной. Если он неопределенный (равен Nil), то список пуст. Указатель следующего элемента в последнем элементе списка равен Nil. Общая схема списка такова:

 

    начальный                элемент1                 элемент2                    ...                   элементN                   NIL

    указатель                 указатель               указатель                                         указатель

Описание элемента списка в Паскале имеет одну особенность, которую мы поясним на примере. Пусть сами данные описываются как запись типа rec. Тогда элемент списка будет записью из двух полей: одно типа rec и другое типа указатель на элемент списка.

type

    rec = record  <поля данных>  end;          {запись данных}

    plist = ^list;                                                    {тип указателя на элемент списка }

    list =  record                                                 {тип элемента списка}


                    d: rec;                                                 {данные списка}

                    p: plist                                                {ссылка на следующий элемент}

                end;

var  p0: plist;                                                      {ссылка на первый элемент списка}

Особенность вышеприведенного описания в том, что при определении типа указателя с именем plist

испоьзуется тип list, определяемый ниже в тексте программы, а не выше, как того требует фундаментальное правило Паскаля. Разобранный случай - это единственное исключение из этого правила.

Список, устроенный так, как это было описано выше, называется линейным однонаправленным (или односвязным) списком. При работе с таким списком можно выделить три основные функции:

  • поиск элемента списка по критерию;


  • добавление элемента внутрь списка;


  • удаление элемента из списка.


  • Пусть функция:  {function  order (r1,r2: rec): integer;}  возвращает -1, 0 или +1 в зависимости от того, предшествует, совпадает или следует запись r1 за записью r2

    (порядок следования зависит от полей записи). Тогда поиск в линейном списке записи r заключается в последовательном переборе элементов списка и сравнении записи r с полем d элемента списка. Перебор начинается с элемента p0^ и заканчивается тогда, когда order(r,d)=0 (запись найдена), либо order(r,d)=1 (нужной записи не существует), либо указатель на следующую запись равен Nil (список кончился).

    function  find_in_list (r: rec): plist;   {возвращает указатель на элемент, Nil - неудача}

    var next: plist;

    begin

        find_in_list := Nil;

        next := po;  {Первый элемент списка}

        while  (next<>Nil) and (order (r, next^.d) >= 0) do

                {Cписок не кончился и исходная запись больше текущей}

            if  order (r, next^.d) = 0 

                then    begin  find_in_list := next;  break  end  {Записи совпадают}

                else    next := next.p;  {исходная больше текущей; продолжить поиск}

    end;

    Для того, чтобы добавить элемент в список, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после).


    В модифицированном списке элемент до должен указывать на вставленный элемент, а вставленный - на элемент после. Алгоритм обязан правильно обрабатывать случаи, когда элемент вставляется в начало или конец списка. Обратите внимание, что в процедуре вставки используется указатель на указатель, что совершенно законно.

    procedure  include_in_list (r: rec);

    var  next,curr: plist;  prev: ^plist;

    begin

        next := po;      {Первый элемент списка}

        prev := @p0;   {Сcылка на указатель первого элемента}

        while  (next<>Nil) and (order (r, next^.d) >= 0) do begin

            prev := @(next.p);        {Сcылка на указатель в предыдущем элементе}

            next := next.p                 {Переход к следующему элементу}

        end;    {Cписок кончился или последняя запись предшествует текущей}

        new (curr);                          {Создание копии элемента списка}

        curr^.d := r;                       {Заполнение элемента}

        curr^.p := prev^;               {Ссылка последующий элемент списка}

        prev^ := curr;                    {Ссылка в прдыдущем элементе на новый}

    end;

    Для того, чтобы удалить элемент из списка, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после). В модифицированном списке элемент до должен указывать на элемент после. Здесь тавже надо следить за правильностью удаления первого и последнего элемента.





    function  exclude_from_list (r: rec): boolean;

    var  next: plist;  prev: ^plist;

    begin

        exclude_from_list := false;

        next := po;      {Первый элемент списка}

        prev := @p0;   {Сcылка на указатель первого элемента}

        while  (next<>Nil) and (order (r, next^.d)  <= 0) do

            if  order (r, next^.d) = 0                                  {Уничтожить элемент списка}

                then  begin prev^ := next.p;                      {Ссылка в прдыдущем элементе на последующий}

                                      dispose (next);                        {Освободить ненужную память}

                                      exclude_from_list := true;  {Элемент удален}



                                      break

                         end

                else  begin  prev := @(next.p);                 {Сcылка на указатель в предыдущем элементе}

                                      next := next.p                          {Переход к следующему элементу}

                         end

    end;

      Кольцевой список отличается от линейного тем, что в нем указатель в последнем элементе не равен Nil, а указывает на первый элемент, то есть ссылки замыкают список в кольцо. Кольцевой список позволяет производить поиск не только с первого, но и с любого элемента. Процедуры поиска, добавления и уничтожения в кольцевом списке несколько отличаются за счет проверки условия окончания поиска (next <> p0  вместо  next <> Nil).

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


    Содержание раздела