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



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


                    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;

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


    Содержание  Назад  Вперед