Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 14 стр.

условие not found станет ложным. Функция возвращает значение «истина».
Наконец, если элемент отсутствует в непустом списке, то значение переменной
found в цикле не изменится. Цикл завершится, поскольку на каждой итерации
значение p увеличивается, и условие p<=L.last станет ложным. Значением
функции будет «ложь».
       Отметим, что рассмотренная реализация списков посредством массивов
позволяет достаточно легко просматривать содержимое списка (есть
возможность непосредственного доступа к элементу по его индексу) и вставлять
новые элементы списка в его конец. Однако, при вставке элемента в середину
или при его удалении требуется перемещение всех последующих элементов.
Кроме того, длина списка ограничена константой maxlen. При достаточно
больших значениях maxlen нерационально используется оперативная память,
так как размер переменной, представляющей список, пропорционален константе
maxlen, а не фактической длине списка. Таким образом, пустой список
занимает столько же места в оперативной памяти, что и список максимальной
длины.


      Реализация списков посредством цепочек динамических объектов

      Другой подход к реализации списков на языке Паскаль заключается в
следующем. Для хранения отдельного элемента списка создается динамический
объект – запись из двух полей, называемая звеном. В одном из полей
(информационном) располагается сам элемент, а другое поле содержит ссылку
на звено, содержащее следующий элемент списка, или пустую ссылку, если
следующего элемента нет. С помощью ссылок звенья как бы сцеплены в
цепочку. Зная ссылку на первое звено можно добраться и до остальных звеньев,
то есть ссылка на первое звено задаёт весь список. Пустой список
представляется пустой ссылкой. Приведём соответствующие описания на языке
Паскаль.
type link=↑node; { ссылка на звено }
elemtype = … {подходящий для задачи тип элементов};
node= record                   {звено состоит из двух полей:}
          elem: elemtype; {элемент списка}
          next: link           {ссылка на следующее звено}
        end;
list=link; {список задаётся ссылкой на звено }
var L: list;{список}

      Обратим внимание на то, что в описании типа link используется имя
node, а в описании типа node используется имя link. По правилам Паскаля в
задании ссылочного типа можно укзывать имя, которое ещё не описано.
Поэтому тип link описывается раньше, чем node.

        Пример. Список символов <'a','b','c'>, представленный цепочкой
звеньев, изображается так (в переменной L – ссылка на первое звено):



                                   - 14 -