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

procedure destruct(L: list);
 { разрушает список L,освобождая память, занимаемую
   звеньями }
 var q: link;
  begin
    while L < > nil do
      begin q:=L;
             L:=L↑.next;
             dispose(q)
      end
  end; {destruct}
      Формальный параметр процедуры destruct описан как параметр-
значение. Следовательно, на месте фактического параметра при обращении к
этой процедуре может быть любое ссылочное выражение. Например, вызов
функции, которая возвращает ссылку на первое звено списка или nil.
      Пусть переменные L1 и L2 имеют одинаковые значения – ссылку на
первое звено некоторого списка. Чтобы сделать список L1 (и L2) пустым,
понадобится такой фрагмент: destruct(L1); L1:=nil; L2:=nil. После
выполнения оператора destruct(L1) значения обеих переменных L1 и L2 не
определены, но после операторов присваивания их значением становится пустая
ссылка, т.е. L1 (и L2) представляют теперь пустой список.
       Как уже отмечалось, операции вставки и удаления при реализации
списков цепочками требуют меньше действий, чем при реализации массивами,
так как не требуется перемещать элементы, следующие за вставляемым (или
удаляемым). Поэтому данная реализация больше подходит для задач, в которых
изменения в списках происходят часто. Кроме того, в ней нет ограничения на
длину списка (максимальная длина зависит только от ресурсов вычислительной
системы); эффективнее используется память (занимаемый объём памяти
пропорционален текущей длине списка).
       Недостатками данной реализации являются необходимость хранить в
звеньях дополнительную информацию – ссылки, а так же отсутствие прямого
доступа к i-му элементу списка. Если нужно присвоить переменной x значение
i-го элемента списка L, то в случае реализации массивами это делается одним
оператором x:=L.elems[i], а при реализации цепочками понадобится
фрагмент, содержащий цикл: p:=L; for k:=1 to i-1 do p:=p↑.next;
x:= p↑.elem. По этой причине в задачах, где списки меняются сравнительно
редко, а просмотр элементов осуществляется часто, выгоднее использовать
реализацию с помощью массивов.
       Цепочку динамических объектов, реализующую список, называют
однонаправленным списком. В литературе по программированию под термином
«список» часто подразумевается именно однонаправленный список. Данное
значение термина обычно имеется в виду и тогда, когда употребляют
выражение «звено списка». В некоторых задачах важно уметь продвигаться по
списку не только от начала к концу, но и в обратном направлении. Для этого
используются двунаправленные списки. Звено двунаправленного списка
содержит две ссылки – на следующее и на предыдущее звенья. Эта особенность

                                   - 19 -