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

           { q↑.next:= L↑.next; L↑.next:=q }



                       'a'
       L                                    'c'    nil


       q
                       'd'


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

function is_empty(L: list):boolean;
 { возвращает истину, если список пуст, иначе – ложь}
  begin
    is_empty:= L = nil
  end; {is_empty}


function is_valid(L: list; i:integer):boolean;
 { возвращает истину,если в списке есть i-й элемент,
   иначе - ложь }
 var p: link; k:integer;
  begin
  p:=L; k:=1;
  while (p< > nil) and (k<=i) do
    begin p:=p↑.next; k:=k+1 end;
    is_valid:=(k>i) and (i>0)
  end; {is_valid}

Рассмотрим работу функции is_valid для разных случаев. Если список L
пуст (L = nil), цикл в теле функции не выполнится ни разу, так как условие
p < > nil ложно. Значение переменной k равно единице, поэтому выражение
(k>i) and (i>0) ложно для любого i. Функция возвратит значение «ложь».
Если i<1, то цикл также ни разу не выполнится, так как при начальном
значении k, равном единице, отношение k<=i ложно. Отношение i>0 также
ложно, следовательно, значением выражения (k>i) and (i>0) будет
«ложь», т.е. функция возвращает значение «ложь». Если i>=1 и в списке есть
i-й элемент, то тело цикла выполнится ровно i раз. Переменная k получит


                                   - 17 -