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

      Рассмотрим ещё одну задачу: «Не используя операторов цикла и
перехода, описать функцию sum(L), вычисляющую сумму элементов списка
целых чисел L. Считать, что сумма пустого списка равна нулю, и что список
представлен цепочкой звеньев без заглавного звена».
      Поскольку циклы запрещены условием задачи, для прохода по списку
воспользуемся рекурсией (как в реализации процедуры print1). Дадим
рекурсивное определение суммы списка. Сумма пустого списка равна нулю,
сумма непустого списка есть результат сложения «головы» с суммой «хвоста»:

                           0, если L пуст,
             sum(L)=
                           L↑.elem+sum(L↑.next),иначе.

Теперь запишем определение функции на Паскале.

function sum(L:list):integer;
begin
  if L = nil then sum:= 0
             else sum:= L↑.elem +
                     sum(L↑.next)
end;{sum}

Параметр L передаётся по значению. Поэтому при каждом вызове этой
функции создаётся локальная (по отношению к данному вызову) переменная L,
и ей присваивается значение фактического параметра. При выходе из функции
локальная переменная исчезает, и значение функции возвращается в точку
обращения к ней. При рекурсивном обращении могут одновременно
существовать несколько (различных !) локальных переменных с именем L (по
одной для каждого вызова). Рисунок 1 иллюстрирует выполнение оператора
write(sum(Z))основной программы, где Z представляет список <5,-3>.



                           Очереди и стеки

       В повседневной жизни часто приходится иметь дело с хранилищами
различных объектов. В библиотеке хранятся книги; в автоматическом оружии
есть магазин, в котором хранятся патроны; в холле парикмахерской «хранятся»
клиенты, ожидающие своей очереди на обслуживание. Хранилище может быть
пустым, если в данный момент никаких объектов в нём нет. Независимо от
того, как устроено хранилище, и какие объекты в нём хранятся, можно выделить
два основных действия для работы с ним: 1) добавить объект (положить на
хранение); 2) взять объект (изъять из хранилища). Если потребовать, чтобы
операции добавления и изъятия объектов удовлетворяли некоторым условиям,
можно выделить два особых типа хранилищ: очередь и стек.



                                   - 22 -