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

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


        Списки с заглавным звеном

      Если в начало обычного однонаправленного списка добавить
дополнительное звено, не содержащее элемента (т.е. поле elem в этом звене не
определено), то получим список с заглавным звеном. Пример:
                                                           'b'     nil
    L                                    'a'

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

procedure insert1(var L: list; x: elemtype);
 { вставляет в конец списка L без заглавного звена
   элемент x}
 var p,q: link;
  begin
    new(q); q↑.elem:= x; q↑.next:= nil;
    {q указывает на созданное для вставляемого элемента
      звено }
    if L = nil then L:= q {случай пустого списка
                         обрабатывается отдельно}
              else
      begin p:= L;
        while p↑.next< > nil do p:= p↑.next;
          {p указывает на последнее звено в списке}
        p↑.next:= q
          {присоединили в конец списка новое звено}
      end
  end; {insert1}


procedure insert2(L: list; x: elemtype);
 { вставляет в конец списка L с заглавным звеном
   элемент x}
 var p,q : link;
  begin
    new(q); q↑.elem := x; q↑.next:= nil; p:= L;
    while p↑.next< > nil do p:= p↑.next;
     {p указывает на последнее звено в списке}

                                    - 20 -