\documentstyle[11pt]{book}
\textheight 23.5cm
\textwidth 16.3cm
\hoffset=-1.6cm
\voffset=-2cm

\begin{document}
\def\ul{\underline}
\def\fb{\framebox}


\def\bc{\begin{center}}
\def\ec{\end{center}}
\def\lb{\linebreak}
%\font\vova=wncyr10 at 9pt

%\lineskip=0.78cm

\title{\huge\yb ВВЕДЕНИЕ В НЕЧИСЛОВОЕ ПРОГРАММИРОВАНИЕ (часть 1)}
\author{\Large\yr В.Б.ИЛЬИН, А.Д.ПОЛОЖЕНЦЕВ}
\vfill
\date{\large\yr С.-Петербург  1994}
\maketitle
\tableofcontents

\newpage
\bc{\Large\yr Аннотация}\ec

\large\yr

   Данное пособие написано на основе  курса  программирования,
читавшегося в течение нескольких лет студентам  второго  курса
математико-механического    факультета    Ленинградского
государственного университета.

   Kурс представлял  собой  дополнение  к  стандартному  курсу
программирования,   где   рассматривается   какой-либо    язык
программирования и даются основы методов вычислений.

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

%%%%%%%%%%%%%%%%%%%%%%
\chapter{\yb Введение}

\section{\yr Понятие нечислового программирования}

   Среди  встречающихся  в  программировании  задач   проведем
разделяющую черту (безусловно сильно расплывчатую), и  отделим
алгоритмы, где основные трудности вызваны значительным  числом
арифметических (алгебраических) операций от задач, где главным
является  не  это,  а  организация  данных  и  другие  вопросы
(например логика в сильно запутанных алгоритмах, представление
данных, существенно отличающихся от числовых и т.д.).  Решения
на  ЭВМ  задач  первого   рода   будем   называть   "числовым"
программированием, второго рода - соответственно  "нечисловым"
программированием.

   В чем же различие этих  двух  видов  программирования ?   В
числовом  программировании  главная  трудность  заключается  в
адекватном  применении  соответствующей  методики  из  области
"методов  вычислений"  и  в   борьбе   с   потерей   точности,
возникающей при большом числе последовательных  арифметических
операций, вследствие приближенного представления  вещественных
чисел в ЭВМ.

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

\section{\yr Задачи нечислового программирования}

   Перечислим основные  задачи  нечислового  программирования,
возникающие на границе информатики и астрономии.

   Большую часть данных, как известно, астрономия  получает  в
экспериментах. Среди  программ,  обеспечивающих  автоматизацию
экспериментов, подавляющее число составляют задачи нечислового
программирования:  программы   управления   работой   приборов
(телескопы, приемники и т.д.), первичной обработки  информации
(введение  поправок  за   эффекты,   вносимые   приборами)   и
организации информации (т.е. кодировка,  упаковка,  распаковка
информации и  т.д.).  Примером  управлящих  программ  являются
программы автоматического гидирования объектов на  телескопах,
управление   многокомпонентными   радиотелескопами   (например
РАТАН-600)   и   др.;   первичной   обработки   ---   вычитание
инструментального профиля  в  спектроскопии,  вычитание  помех
вносимых космическими лучами в наблюдениях с  ПЗС-матрицами  и
т.д.; организация информации --- упаковка двухмерных изображений
астрономических  объектов  для  экономии  памяти  ЭВМ  при  их
хранении и т.п.


   Следующий  этап  работы   с   результатами   наблюдений   в
астрономии  ---  обработка  данных.  Здесь  задачи   нечислового
программирования возникают реже и в основном  в  тех  случаях,
когда объем данных велик (например, при обработке изображений)
или  когда  повышаются  требования  к  сервису  (для   больших
программ,   предназначенных   для   длительного   и   широкого
использования).

   Некоторая (хотя и  не  очень  большая)  часть  обработанных
данных, предлагаемая для использования широкой астрономической
общественностью, передается для включения  в  банки  данных  в
центры данных (например ЦАД при астрономическом совете АН СССР
в Москве и/или международный ЦАД в Страссрбурге). При работе с
банками  данных  основными  являются   программы   нечислового
программирования.  В   простейшем   случае   каталога   данных
встречаемость нечисловых программ существенно ниже  и  зависит
обычно от объема каталога и назначения комплексов программ.

   Присутствуют  задачи  нечислового  программирования   и   в
теоретических   исследованиях.   В    частности    специальные
трансляторы, интерпретаторы и т.п. Позволяют  автоматизировать
кодировку (обычно крупных, однообразных) программ. Например, в
физико-химии атмосфер планет и межзвездной  химии  применяются
интерпретаторы,  воспринимающие  близкую  к   обычной   запись
химических  реакций  и  строящие  соответствующие  программные
модули. Относительное число таких программ очень мало,  но  их
объем и растущая  нелинейно  с  ним  трудоемкость  создания  и
отладки,  приводят  к  тому,  что  затраты  на   их   создание
(длительность создания и неизбежных модификаций годы !)  могут
составить  значительную  долю  времени  работы   программистов
(астрономов).

   Наивысшим   достижением    нечислового    программирования,
являются, по-видимому, системы  для  работы  с  аналитическими
выражениями.  Такие  системы  в   настоящий   момент   "умеют"
производить интегрирование, не говоря о дифференцировании  или
приведении подобных членов,  любых  алгебраических  выражений,
включающих как полиномы,  так  и  все  алгебраические  функции
вплоть до  специальных  (система {\rm MACSIMA}).  Специальные  виды
таких систем ({\rm SCHOOLSHIP, REDUCE} и т.д.) используются в физике
элементарных  частиц,  релятивисткой  квантовой   механике   и
небесной механике.

   На всех этапах  деятельности  астрономов  иногда  возникает
необходимость создания сервисных программ,  т.е.~программ  на
которые  налагаются  особо  жесткие  требования  (что  конечно
приводит  к  модификации  исходного  алгоритма).  Обычно   эти
требования таковы: усиленная  защита  от  ошибок,  надежность,
документированность, улучшенная  форма  выдачи  результатов  и
т.д. Отличный пример сервисных программ - игровые программы !

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

   В  заключении,  стоит  отметить  вероятно  неожиданный  для
многих факт, что  астрономия  и  программирование  связаны  не
столь слабо, как кажется на первый взгляд.  Примерами  влияния
астрономии на программирование может служить  то,  что  именно
астрономические  потребности   привели   к   созданию   первых
вычислительных машин или же широкая  распространенность  языка
{\rm "FORTH"}, созданного для управления  радиотелескопом;  обратное
влияние -  некоторые  изменения  образа  жизни  астрономов,  в
частности  в  ряде  стран  астрономы  не  ездят  наблюдать   в
обсерватории, а подают со  своего  терминала  заявку  и  через
некоторое  время  получают  на  него   результаты   наблюдений
(трансконтинентальная  связь  европейская  южная  обсерватория
({\rm ESO}) в Чили - Англия).


%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{\yb Типы данных}

   В данной  главе  рассматриваются  различные  группы  (типы)
данных,   которые   присутствуют    в    современных    языках
программирования (а не только в Паскале или
Фортране!)\footnote{\yr Эта глава имеет характер "ликбеза".
Основное  содержание курса находится в Главе 3 и иллюстрирующей ее
Главе 4 (Глава 4 приведена в сокращенном варианте).}.

   Сначала обсуждаются обычные, элементарные типы  данных
(п.~2.2--2.3), встречающиеся во всех  языках.  Затем  описываются
составные типы данных  (п.~2.4),  в  которых  каждый  элемент
данных есть  некоторая  совокупность  объектов.  Использование
данных  этих  типов  оказывается  удобным   при   "нечисловом"
программировании.   В   заключение   (п.~2.5)    обсуждается
существенный    для    многих    аспектов    "нечислового"
программирования   тип   данных   ---   ссылочный.   Этот    тип
исключительно важен при  построении  в  программах  нелинейных
структур данных (например, ветвящихся  или  с  большим  числом
связей).

   Отметим,  что  пункты,  в  которых  обсуждаются   известные
читателю типы, могут быть пропущены, исключая п.~2.4.1 и  2.5,
где излагаются сведения, необходимые для понимания Главы 3.

\section{\yr  Данные и типы данных}

   Любой  алгоритм  (программа)  для   вычислительной   машины
состоит из двух основных частей:  описание  действий,  которые
предстоит выполнить, и описания объектов, над  которыми  будут
выполняться эти действия. Обычно при обучении программированию
основное внимание уделяется первой  части,  мы  рассмотрим  не
менее важную, вторую часть.

   Объекты,  которыми  оперирует  программа,  будем   называть
данными. Важной особенностью данных является то, что они имеют
два атрибута: имя и значение. Если перейти  на  язык  машинных
команд,  то  имени  будет  соответствовать  номер  ячейки,   а
значению --- содержимое ячейки.  В  аппаратуре  ЭВМ  все  данные
представляют  собой  последовательность  двоичных  цифр,
т.е.~ряды, состоящие из нулей и единиц. Такие данные использовались
в прошлом при программировании на  языке  машинных  команд  (в
машинах   первого   поколения:   Урал-1    и    др.).    Языки
программирования  высокого  уровня  (Алгол,  Фортран  и   др.)
позволяют абстрагироваться от неудобных деталей  представления
данных и происходит это в основном за счет введения  концепции
типов данных.

\ul{Определение}: типом данных будем  называть  класс
(группу) объектов, значения которых принадлежат  определенному
множеству.

   Например, целый тип  данных,  встречающийся  почти  во  всех
языках программирования, объединяет объекты, значения  которых
являются целыми числами.

   Обычно  введением  типов  данных  объекты,  используемые  в
алгоритмах  (программах)  в  виде  переменных  или   констант,
разбиваются на несколько групп по общим областям значений. При
этом  каждая  переменная   сопровождается   спецификацией   ее
возможных  значений.  Это  делается  по  следующим   причинам:
во-первых, количество элементов в памяти ЭВМ, необходимое  для
хранения значений переменной зависит от диапазона ее значений.
Так для хранения переменной,  принимающей $N$  целых  значений,
необходимо примерно $\log N$ битов. В частности для переменной,
значениями которой могут быть 0, 1 и 2 необходимо два бита  (в
двоичном  коде  значения  есть  00,  01  и   10).   Во-вторых,
реализация действий, описанных в  алгоритме,  в  командах  ЭВМ
часто (почти всегда) зависит от количества  элементов  памяти,
которое  занимает  объект,  так  как  используются   различные
регистры машинных команд  (по  крайней  мере,  в  одноадресных
серии EС ЭВМ и др.)

   И  так  множество   значений,   которое   может   принимать
переменная играет важнейшую роль  для  характеристики  данных.
Поэтому, обычно,  все  переменные  в  программах  должны  быть
описаны   (исключая   правило   умолчания   некоторых   языков
программирования) или иными словами отнесены к какому-то  типу
данных\footnote{\yr Описание  переменных  в  языке  Паскаль  имеет  вид:
{\rm VAR v1, v2, ..., vn: T},  где {\rm  VAR}  ---  служебное
слово  языка  Паскаль; {\rm v1, v2, ..., vn} --- имена переменных
(индентификаторы); {\rm  T}  ---  имя типа данных.}.

   Типы данных разделяются на простые и составные.

\ul{Определение}:  простые  типы  данных  ---   классы
объектов, каждый из которых представляет собой  единое  целое,
т.е.~атом.

\ul{Определение}:  составные  типы  данных  ---  классы
объектов,  каждый  из  которых  включает  в   себя   несколько
элементов.

   Примером простого типа является целый, вещественный тип и т.п.,
а составного --- массивы.

\section{\yr Простые типы данных}

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


\subsection{\yr Скалярный тип данных}

\ul{Определение} :  скалярный  тип  данных  ---   класс
объектов,  которые  могут   принимать   значения   только   из
некоторого заданного упорядоченого множества.

   Определение  скалярного  типа  в  языке  Паскаль   выглядит
следующим образом:

\bc\fb{\rm TYPE  Ts = (w1, w1, ..., wn)}\ec

где {\rm TYPE} --- служебное слово языка Паскаль;

  {\rm Ts} --- имя скалярного типа данных;

   {\rm w1, w2, ..., wn} --- константые индетификаторы.

   Константные  индентификаторы  должны  быть   различны;   их
упорядочиваемость  задается  порядком  следования   так,   что
считается {\rm w1 $<$ w2 $<$ ... $<$ wn}.

   На переменных скалярного типа определены операции:\\
           отношения: $< , > , =$  и  $<>$; \\
           и функции получения следующего и предыдущего
           элемента {\rm SUCC} и {\rm PRED} (например, результат
           {\rm SUCC(w2)} есть {\rm w1} и т.д.).

\ul{Пример}. Определим скалярный тип, перечисяющий  планеты
Солнечной системы,  и  выполним  ряд  тривиальных  операций  с
перемеными данного типа.
\begin{verbatim}
      TYPE  Planets = (me, v, e, ma, j, s, u, n, p); ...
      VAR   planet1, planet2: Planets;  l: BOOLEAN; ...
        ... planet1:= e;  planet2:= V;
            l:= planet1 >= planet2; ...
\end{verbatim}
В данном случае переменная {\rm l} примет значение {\rm FALSE}.

\medskip
   Отметим, что целью введения скалярных типов данных является
абстрагирование  от  машинно  ориентированного   представления
данных (ряды 0 и 1) так, чтобы работать с объектами в  удобной
человеку форме,  т.е.  максимально  приближенной  к  реальной.
Следующий шаг в этом  направлении  ---  определение  специальных
операций на новых типах. В некоторых языках (Алгол-68, {\rm FORTH}  и
др.) это можно делать  явно.  В  языке  Паскаль  это  делается
косвенно, через подпрограммы.

\subsection{\yr Ограниченный тип данных}

   На определении скалярного типа базируется  определение  его
части, называемой ограниченным типом.

\ul{ Определение}: ограниченный  тип  данных  ---  класс
объектов,  которые  могут  принимать  значения  из  указанного
связного  подмножества   некоторого   множества   (задаваемого
определением базового скалярного типа).

   В языке Паскаль определение данного типа имеет вид:

\bc\fb{\rm  TYPE  To = wi .. wl     }\ec

где .. (две точки!) --- специальный знак языка;\\
  {\rm wi} и {\rm wl} -- константные индентификаторы, входящие в  базовый
     скалярный тип (заданый выше).

   Переменные  ограниченного  типа  могут  принимать  значения
константных идентификаторов скалярного типа {\rm Ts} в интервале  от
{\rm wi} до {\rm wl} включительно.

   На ограниченном типе разрешены те же  операции,  что  и  на
базовом скалярном типе.

\ul{Пример}.  В  массиве   индексы   элементов   ограничены
некоторым целым числом. Ограниченный тип, удобный для описания
индексов массива в 100 элементов, может быть определен
на стандартном скалярном типе (целом типе) так
\bc{\rm               TYPE  Index = 1 .. 100}\ec

\section{\yr Стандартные типы данных}

   Некоторые  скалярные  типы  используются  столь  часто  (и
давно!), что соответствующее определения типа и его стандартное
имя заложены  в  языке. В  Паскале   стандартными   скалярными
типами являются: логический, целый, литерный и
вещественный\footnote{\yr Вещественный тип, стоит особняком
среди скалярных  типов,
т.к.~на нем нельзя определить ограниченный  тип.  Накладывание
такого ограничения в языке, связано  с  тем,  что  определение
ограниченного типа на вещественном на разных машинах будет  не
однозначно (зависит от разрядности машины).}.
Эти типы  присутствуют  и  в   большинстве    других    языках
программирования.


\subsection{\yr Логический тип данных}

\ul{Определение}:  логический  (или  булевский)  тип
данных --- класс объектов,  которые  могут  принимать  лишь  два
значения: {\rm FALSE} (ложь) и {\rm TRUE} (истина).

   В языке Паскаль подразумевается следующее описание  данного
типа, имеющего стандартное фиксированное имя {\rm BOOLEAN}:
\bc{\rm  TYPE BOOLEAN = (FALSE, TRUE)}\ec
   и для данного типа определены следующие операции: \\
                   логические {\rm OR, AND, NOT};    \\
                   отношения  $<, >, =, <>$;\\
   тип результата этих операций всегда {\rm BOOLEAN}.

\ul{Пример}. Следущие операторы программы:
\begin{verbatim}
           ... VAR  x, y, z, u: BOOLEAN;
                    y:= FALSE;  z:= TRUE;
                    x:= Y > Z;  u:= y OR z; ...
\end{verbatim}
   приведут к тому, что  переменная {\rm x}  будет  иметь  значение
{\rm FALSE}, а {\rm u --- TRUE}.

   Отметим, что тип {\rm BOOLEAN} вызван (связан)  существованием  в
алгоритмах структур (действий) типа развилка: {\rm IF ... THEN  ...
ЕLSE ...} .

\subsection{\yr Целый тип данных}

   Для  каждой  вычислительной  машины  определено   некоторое
подмножество целых чисел, таких с которыми  ее  арифметическое
устройство  может  оперировать.  В  ЕС  ЭВМ  на  целое   число
отводиться  4  байта $=$ 32  битам   и   следовательно   можно
представлять числа в интервале [$-2^{31},2^{31}$].

\ul{Определение}: целый тип данных --- класс  объектов,
которые могут принимать значения из множества  целых  машинных
чисел.

   Подразумевается следующее  (очень  длинное!)  описание  в
Паскале данного типа (стандартное имя {\rm INTEGER}):

\bc{\rm TYPE  INTEGER = (minint, minint+1, minint+2, ...,
                       maxint-1, maxint),}\ec

   где  {\rm minint}  и {\rm maxint}  ---  соответственно  максимальное   и
минимальное число из множества машинных целых чисел.

   Разрешены следующие операции для целых чисел:\\
 арифметические $+, -, *$, {\rm DIV} (деление), {\rm MOD} (взятие остатка)
              --- результат операций типа {\rm INTEGER};        \\
 отношения $<, >, <=, =>, =, <>$ --- результат {\rm BOOLEAN}.

   Существует и ряд встроенных функций.

   Подчеркнем, что обычные аксиомы арифметики  могут  быть  не
верны для машинной арифметики. Например для машинного сложения
двух целых чисел {\rm x} и {\rm y}, результат  будет  не  определен,  если
{\rm (x+y) $<$ minint} или {\rm (x+y) $>$ maxint}\footnote{\yr  Отметим,
что  целый  тип  часто  связан  с  конструкциями
программ типа цикла (счетчик цикла) {\rm FOR ... DO ...}}.


\subsection{\yr Символьный тип данных}

\ul{Определение}:  символьный  тип  данных  ---  класс
объектов, которые могут принимать значения литер: 26 латинских
букв, 10  арабских  цифр  и  несколько  специальных  символов,
включая пробел (для ЕС ЭВМ).

   Подразумевается следующее описание в Паскале:

\bc{\rm TYPE  Char = ('a','b','c',...,'Z','0',...'9',' ','/','*',...)}\ec

   т.е. литеры упорядочены некоторым образом.

   Разрешены следующие операции:
       отношения: $<, >, <=, =>, <>$ --- результат {\rm BOOLEAN}.

   Отметим,  что  символьный  тип  обычно   используется   при
операциях ввода/вывода в программах.


\subsection{\yr  Вещественный тип данных}

   В вычислительной машине можно представить числа  достаточно
разреженного  конечного  подмножества  вещественных  чисел.  В
современных  цифровых  машинах,   используется   представление
вещественного  числа  с  "плавающей   точкой",   т.е.   каждое
вещественное  число  $x$  представляется  парой  чисел  $m$  и $i$:
$x = m \cdot b^i,  i = [-K, K],  m = [-N, N]$,  где  $b$  ---  основание,
$i$  --- порядок, а $m$ --- мантисса числа $x$.
Если $1 > |m| > 0.1$,  то  форма
представления  числа  называется  нормализованной.  В  машинах
серии ЕС ЭВМ для $b =$ 10,  $m$ ---  приблизительно  семь  десятичных
знаков, а $i = [-79, 75]$.

   Очевидно,  что  при  использовании   такого   представления
плотность  "машинных"  вещественных  чисел  уменьшается  с  их
ростом:  в  интервале  0.1--1.0   содержится   столько   же
вещественных "машинных" чисел, сколько и в  отрезке  1000.0--10000.0!
Трудно предсказать к чему это может привести  в  той
или иной программе.

\ul{ Определение}:  вещественном  типом  данных  будем
называть класс объектов, которые могут принимать  значения  из
множества "машинных" вещественных чисел.

   Подразумевается  очень-очень  длинное  описание  (в   языке
Паскаль)

\bc{\rm   TYPE  REAL = (minreal, ..., maxreal), }\ec

   где должны  быть  перечислены  в  порядке  возрастания  все
"машинные" вещественные числа.

   Разрешены следующие операции:\\
      арифметические: $+, -, *, /$  --- результат типа {\rm REAL};\\
      отношения: $<, >, <=, =>, =, <>$ --- результат {\rm BOOLEAN}.

   Доступен  обычно  и  ряд  широко  используемых   встроенных
функций.

   Отметим, что как и в случае целого типа, аксиомы арифметики
могут быть не выполнимы для переменных вещественного  типа.  В
частности, нет законов ассоциативности и дистрибутивности, что
связано с ограничением длины мантисы у "машинных" вещественных
чисел. Из-за этого  особую  опасность  представляет  вычитание
двух  примерно  равных  чисел.  При  этом  большое  количество
значащих цифр  уничтожается  и  в  полученной  разности  может
оказаться очень мало верных цифр. Например, вычитание из числа
0.2013 числа 0.2008, на  машине  с  длиной  мантиссы  4  будет
происходит следующим образом:

\begin{verbatim}
                   0.2013    10**0
                  -0.2008    10**0
                 --------------------
                       .5xxx 10**(-3)
\end{verbatim}

и в мантису результата  попадет  5  и  еще  три  цифры {\rm (xxx)},
которые, например, машины серии ЕС ЭВМ "выдумают" сами. Т.о.~в
результате останется лишь одна верная цифра!

   Отметим, что вещественный тип данных необходим в  программе
для вычислений.

\bc\ul{Упражнения}\ec

1. Определен скалярный тип имен спектральных классов звезд:
\bc{\rm   TYPE  Spectral = (O, B, A, F, G, K, M)}\ec
   известно, что в переменных этого типа  {\rm s1}  и  {\rm s2}  находятся
   имена спектральных  классов  двух звезд. Написать оператор,
   проверяющий: являются ли классы звезд соседними.

2. Добавить описание переменных к имеющейся программе:
\bc{\rm          b:= a=1 OR c=1.0}\ec

3. Дано описание переменных:
\bc{\rm                VAR  х, y, z: REAL; i, j, k: INTEGER}\ec
   Проверить правильно ли записаны выражения:
\bc{              а) {\rm x + y * i} \\
                  б) {\rm x + k $<$ i + j} \\
                  в) {\rm i DIV j + x} }\ec

4. Описать типы данных, удобные для работы:  \\
\indent\indent   а)  с  хабловской классификацией галлактик; \\
\indent\indent   б) с оценками учащихся в школе.



\section{\yr  Составные типы данных}

   Выше мы рассмотрели простые типы элементарных данных,  т.е.
данных, значения которых  являются  неделимыми.  Однако,  часто
приходится  работать  с   объектами,   представляющими   собой
некоторую  совокупность  данных   ("классический"   пример   ---
массив). При  этом  может  потребоваться  совокупность  данных
разного типа, с  которыми  необходимо  работать  как  с  одним
целым. Например, с датой или со сведениями о каком-то объекте:
человеке, звезде и т.п. В этих случаях удобно использовать так
называемый комбинированный тип данных.


\subsection{\yr  Комбинированный тип данных}

\ul{Определение}:  комбинированный  тип  данных  (или
записи) --- класс объектов, которые  состоят  из  фиксированного
числа элементов разного типа.

   На  записях  разрешены  только  операции  присваивания,  но
нужные нам операции могут быть  определены  дополнительно  (по
крайней мере, через подпрограммы, как в  языке  Паскаль).  Для
компонентов записи определены все операции, разрешенные для их
типов данных.

   Описание в языке Паскаль имеет вид:

\bc\fb{\rm  TYPE  Tс = RECORD p1: T1;  p2: T2; ...; pn: TN END}\ec

где   {\rm Tc} --- имя комбинированного типа; \\
      {\rm RECORD} и {\rm END} --- зарезервированные слова Паскаля; \\
      {\rm T1, T2, ..., TN} --- имена типов компонентов записи; \\
      {\rm p1, p2, ..., pN} --- имена полей, необходимые для работы
                     с компонентами.

Для переменной s комбинированого типа {\rm Tс} (описание: {\rm VAR  s: Tс})
{\rm s.p1} --- есть компонент типа {\rm T1; s.p2} --- компонент типа {\rm T2} и т.д.

\ul{Пример}. Определим комбинированный тип  с  именем  {\rm Date}
для  представления  даты   и   присвоим   некоторые   значения
компонентам переменной {\rm today} данного типа.

\begin{verbatim}
        TYPE  Tdate = 1..31;
              Tmonth = (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,
                        SEP, OCT, NOV, DEC);
              Tyear = 0..2005;
              Date = RECORD day: Tdate;
                            mon: Tmonth;
                           year: Year
                     END;
        VAR   today: Date;
        BEGIN
           today.day:= 23; today.mon:= MAR; today.year:= 1995
        END.
\end{verbatim}


\subsection{\yr  Регулярный тип данных}

   Часто встречается  частный  случай  комбинированного  типа,
когда компоненты переменной имеют одинаковый тип. Этот  случай
выделен особо в так называемый регулярный тип.

\ul{Определение}: регулярный тип данных (или массивы)
--- класс объектов,  которые  состоят  из  фиксированного  числа
элементов одного и того  же  типа  (в  отличие  от  записей,  у
которых тип элементов может быть разным!)

   Описание на языке Паскаль данного типа есть:

\bc\fb{\rm  TYPE  Tr = ARRAY [Ti] OF Tk }\ec

где     {\rm Tr} --- имя регулярного типа;\\
     {\rm ARRAY} и {\rm OF} --- зарезервированные слова в языке Паскаль;\\
     {\rm Ti} --- имя типа данных индексов массива --- обязательно
             какой-либо скалярный тип (кроме вещественного)! \\
     {\rm Tk} --- имя типа компонентов.

   Так же, как и для записей, определена лишь одна операция  ---
присваивание   (однако   можно   косвенно   вводить   и   свои
специфические),  а  для  компонентов  массива  разрешенны  все
операции их типа.

   Описание переменной регулярного  типа  в  языке  Паскаль  и
работа с ее компонентами выглядит следующим образом:

\begin{verbatim}
           ... VAR  b,a: Tr;  i,j: Ti;  c: Tk;...
           ... c:= a[i];  a[i]:= a[j];  a[j]:= c;  b:= a...
\end{verbatim}

   Возможна работа и  с  многомерными  массивами  (тоже  часто
встречается на практике). В  языке  Паскаль  двумерный  массив
описывается так:
\bc{\rm            TYPE  Ta = ARRAY [Ti,Tj] OF Tk}\ec
   где {\rm Ti} и {\rm Tj} --- типы индексов (первого и второго).

\ul{Пример}. Для представления даты и работы  с  ней  можно
использовать не только записи (см. комбинированный тип в п.~1.4.1),
но  и массивы:

\begin{verbatim}
         TYPE   Ti = 1..3; Tk = 0..2005;
                Data = ARRAY [Ti] OF Tk;
         VAR    tomorow: Data;
         BEGIN
            tomorow[1]:= 24;
            tomorow[2]:= 3;
            tomorow[3]:= 1995
         END.
\end{verbatim}

\ul{Примечание}.
   Ясно, что работа с записями в данном  случае  нагляднее  и,
следовательно,   их   использование   предпочтительнее   (если
постановка задачи не требует использования массивов).



\subsection{\yr  Множественный тип данных}

   Иногда (не так редко!) возникает необходимость работать  с
множеством  (объектов)  и  тогда  удобно  воспользоваться  так
называемым множественным типом.

\ul{Определение}: множественный тип --- класс объектов,
значениями   которых    являются    подмножества    некоторого
фиксированного   множества   (последнее   задается   описанием
скалярного типа). Описание типа в языке Паскаль выглядит так:

\bc{\rm        TYPE   Bset = (b1, b2, ..., bn);}\ec

\bc\fb{\rm    Tm = SET OF Bset   }\ec

где  {\rm Bset} --- имя базового скалярного(!) типа;\\
     {\rm b1, b2, ..., bn} --- константные идентификаторы типа {\rm Bset};\\
     {\rm SET OF} --- зарезервированные слова языка Паскаль.

    Определены следующие операции: \\
        а) отношения: $<=, =>$ (включение множеств!) и
                      $=, <>$ (тождество и различие) --- тип результата {\rm BOOLEAN};\\
        б) над множествами: $+$ (объединение); $*$ (пересечение); \\
                         {\rm IN} (принадлежность элемента множеству) ---
                          тип результата {\rm BOOLEAN}.

Описание  переменных  множественного  типа  и  работа  с  ними
выглядит следующим образом:
\begin{verbatim}
           VAR  t1, t2: Tm;  L: BOOLEAN;
           BEGIN
              t1:= [b2, b5, b8];
              l:= b5 IN t1
           END.
\end{verbatim}
где {\rm t1} --- подмножество из трех  элементов,  а  {\rm l}  в  результате
работы данной программы будет иметь значение {\rm TRUE}.

\ul{Пример}.   Два   объекта   наблюдались   в    различных
фотометрических   полосах   {\rm (U,B,V,R)}.   Программа,    которая
определяет имеются ли наблюдения  объектов  хотя  бы  в  одной
общей полосе может быть следующей:
\begin{verbatim}
           TYPE  Phband = (U, B, V, R);  Obj = SET OF Phband;
           VAR   obj1, obj2: Obj;  L: BOOLEAN;
           BEGIN
              L:= NOT( (obj1 * obj2) = [])
           END.
\end{verbatim}
где $[]$ --- пустое множество.


\section{\yr  Ссылочный тип данных}

   Как  отмечалось  выше,  вся   информация   в   памяти   ЭВМ
представляется в виде множества нулей и  единиц,  т.к.  память
состоит из элементов, хранящих по 1 биту  информации  (элемент
имеет  только  два  состояния,  одному  приписывается  "0",  а
второму  "1").  Однако  обмен  информацией  между  памятью   и
арифметическим устройством ЭВМ происходит не по  1  биту  (это
очень медленно), а группами бит ---  словами  (и  даже  группами
слов). В ЕС ЭВМ, например, 32 разрядное слово, т.е. содержащее
32 бита (или 4 байта).  Для  возможности  обращения  к  словам
(ячейкам памяти, как говорили раньше), каждое слово имеет свой
номер --- адрес. Таким  образом  с  любым  объектом,  с  которым
оперирует ЭВМ и который располагается в ее памяти, связано два
числа:  адрес  ячейки,  в  которой  хранится  информация   (об
объекте),  и  содержимое  ячейки,  т.е.  непосредственно  сама
информация. Язык Паскаль (как и многие другие языки) позволяют
хранить в качестве информации адреса ячеек.  Объекты  значения
которых есть адреса ячеек называются ссылками.

\ul{Определение}:  ссылочный  тип  данных  ---   класс
объектов, которые могут иметь значения всех возможных  адресов
(в памяти машины) объектов некоторого типа.

   Описание ссылочного типа в языке Паскаль:

\bc\fb{\rm   TYPE  Tl=@T  }\ec

где    {\rm TL} --- имя ссылочного типа;\\
       {\rm T}  --- имя типа, на данные которого определяются ссылки. \\
          Этот тип может быть как простым, так и составным; \\
       $@$ --- специальный символ языка Паскаль, для определения
       ссылочного типа (символ зависит от версии).

Описание переменных выглядит обычно: \\
\bc{\rm      VAR s, p, q: Tl;  a, b: T; }\ec

   Разрешенными операциями на ссылочном типе являются:\\
                а) проверка тождества или неравенства: $=$ и $<>$; \\
                б) разименование: $@$ это унарная операция (как
                    логическое отрицание {\rm .NOT.} для булевского
                   типа),  однако  ее  знак ставится не перед
                   операндом, а после него: {\rm S@}.  Это означает
                   переход от  адреса (ссылки) к содержимому
                   ячейки. Т.е., если {\rm s} --- является  переменной
                   ссылочного  типа,   то  результат  операции
                   разименования {\rm s@} --- того же типа, на котором
                            определены ссылки (в примере --- {\rm T}).

\ul{Примеры}. Поясним что означают следующие операторы:

а) {\rm s@:= b}   ---  адрес,  содержащийся  в {\rm s}  остается  прежним,   а   вот
     содержимое ячейки по этому адресу,  бывшее  ранее  равным
     {\rm s@}, теперь будет равно значению переменной {\rm b}.

                  До операции

%\begin{figure}[h]
\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(75,16)
\put( 0,11){\makebox(0,0)[bl]{s:}}
\put( 5,10){\framebox(15,5)[l]{     k}}
\put(15,12){\circle*{1}}
\put(15,12){\line(0,-1){4}}
\put(15,8){\vector(1,0){15}}

\put(30,10){\framebox(15,5)[l]{     ?}}
\put(30,10){\line(0,-1){4}}
\put(28,2){\makebox(0,0)[bl]{(k)}}

\put(50,11){\makebox(0,0)[bl]{b:}}
\put(55,10){\framebox(15,5)[l]{     w}}
\put(55,10){\line(0,-1){4}}
\end{picture}
\ec}
%\caption{Fig.1a}
%\end{figure}

%\begin{verbatim}
%        _________         _________       _________
%      s I___k___I         I___?___I    b  I___w___I
%                I___----->!
%\end{verbatim}
                     где {\rm (k)} --- адрес ячейки

           и  после операции {\rm s@ := b}

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(75,18)
\put( 0,11){\makebox(0,0)[bl]{s:}}
\put( 5,10){\framebox(15,5)[l]{     k}}
\put(15,12){\circle*{1}}
\put(15,12){\line(0,-1){4}}
\put(15,8){\vector(1,0){15}}

\put(30,10){\framebox(15,5)[l]{     w}}
\put(30,10){\line(0,-1){4}}
\put(28,2){\makebox(0,0)[bl]{(k)}}

\put(50,11){\makebox(0,0)[bl]{b:}}
\put(55,10){\framebox(15,5)[l]{     w}}
\put(55,10){\line(0,-1){4}}
\end{picture}
\ec}
%\caption{Fig.1b}
%\end{figure}

%\begin{verbatim}
%        _________         _________         _________
%      s I___k___I         I___w___I      b  I___w___I
%                I___----->!
%                         (k)
%\end{verbatim}

б) {\rm a:= s@}   --- переменной {\rm а} присваивается значение, хранящееся в  ячейке
     с адресом равным значению находящемуся в переменной {\rm s}.

                     До операции

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(75,18)
\put( 0,11){\makebox(0,0)[bl]{s:}}
\put( 5,10){\framebox(15,5)[l]{     k}}
\put(15,12){\circle*{1}}
\put(15,12){\line(0,-1){4}}
\put(15,8){\vector(1,0){15}}

\put(30,10){\framebox(15,5)[l]{     w}}
\put(30,10){\line(0,-1){4}}
\put(28,2){\makebox(0,0)[bl]{(k)}}

\put(50,11){\makebox(0,0)[bl]{a:}}
\put(55,10){\framebox(15,5)[l]{     ?}}
\put(55,10){\line(0,-1){4}}
\end{picture}
\ec}
%\caption{Fig.1c}
%\end{figure}

%\begin{verbatim}
%        _________         _________       _________
%      s I___k___I         I___w___I    a  I___?___I
%                I___----->!
%                         (k)
%\end{verbatim}

           и  после операции {\rm a:= s@}

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(75,18)
\put( 0,11){\makebox(0,0)[bl]{s:}}
\put( 5,10){\framebox(15,5)[l]{     k}}
\put(15,12){\circle*{1}}
\put(15,12){\line(0,-1){4}}
\put(15,8){\vector(1,0){15}}

\put(30,10){\framebox(15,5)[l]{     w}}
\put(30,10){\line(0,-1){4}}
\put(28,2){\makebox(0,0)[bl]{(k)}}

\put(50,11){\makebox(0,0)[bl]{a:}}
\put(55,10){\framebox(15,5)[l]{     w}}
\put(55,10){\line(0,-1){4}}
\end{picture}
\ec}
%\caption{Fig.1d}
%\end{figure}

%\begin{verbatim}
%        _________         _________         _________
%      s I___k___I         I___w___I      a  I___w___I
%                I___----->!
%                         (k)
%\end{verbatim}

в) {\rm s:= q}   --- в переменной {\rm s} хранился  некий  адрес,  теперь  он  будет
     будет заменен на адрес, храняшийся в {\rm q}.

        До операции     {\rm s := q} \hspace{3cm}  и  после операции

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(120,35)
\put( 0,11){\makebox(0,0)[bl]{q:}}
\put( 5,10){\framebox(15,5)[l]{     m}}
\put(15,12){\circle*{1}}
\put(15,12){\line(0,-1){4}}
\put(15,8){\vector(1,0){15}}

\put(30,10){\framebox(15,5)[l]{     g}}
\put(30,10){\line(0,-1){4}}
\put(27,2){\makebox(0,0)[bl]{(m)}}

\put( 0,28){\makebox(0,0)[bl]{s:}}
\put( 5,27){\framebox(15,5)[l]{     k}}
\put(15,29){\circle*{1}}
\put(15,29){\line(0,-1){4}}
\put(15,25){\vector(1,0){15}}

\put(30,27){\framebox(15,5)[l]{     w}}
\put(30,27){\line(0,-1){4}}
\put(28,19){\makebox(0,0)[bl]{(k)}}

\put(70,11){\makebox(0,0)[bl]{q:}}
\put(75,10){\framebox(15,5)[l]{     m}}
\put(85,12){\circle*{1}}
\put(85,12){\line(0,-1){4}}
\put(85,8){\vector(1,0){15}}

\put(100,10){\framebox(15,5)[l]{     g}}
\put(100,10){\line(0,-1){4}}
\put(97,2){\makebox(0,0)[bl]{(m)}}

\put(70,28){\makebox(0,0)[bl]{s:}}
\put(75,27){\framebox(15,5)[l]{     m}}
\put(85,29){\circle*{1}}
\put(85,29){\line(0,-1){4}}
\put(85,25){\line(1,0){10}}
\put(95,25){\line(0,-1){16}}
\put(95,9){\vector(1,0){5}}

\put(100,27){\framebox(15,5)[l]{     w}}
\put(100,27){\line(0,-1){4}}
\put(98,19){\makebox(0,0)[bl]{(m)}}

\end{picture}
\ec}
%\caption{Fig.2a}
%\end{figure}

%\begin{verbatim}
%  _________        _________  I    _________        _________
%s I___k___I        I___w___I  I  s I___m___I        I_______I
%          I___---->!          I            I____    !
%                  (k)         I                I   (k)
%  _________        _________  I    _________   I    _________
%q I___m___I        I___g___I  I  q I___m___I   I    I___g___I
%          I___---->!          I            I___I===>!
%                  (m)         I                    (m)
%\end{verbatim}

г) {\rm s@:= р@}  --- в переменных {\rm s} и {\rm р} хранятся разные адреса,
но значения  в   ячейках по этим адресам теперь будут одинаковыми.

       До операции {\rm s@ := р@} \hspace{3cm} и  после операции

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(120,35)
\put( 0,11){\makebox(0,0)[bl]{p:}}
\put( 5,10){\framebox(15,5)[l]{     n}}
\put(15,12){\circle*{1}}
\put(15,12){\line(0,-1){4}}
\put(15,8){\vector(1,0){15}}

\put(30,10){\framebox(15,5)[l]{     y}}
\put(30,10){\line(0,-1){4}}
\put(27,2){\makebox(0,0)[bl]{(n)}}

\put( 0,28){\makebox(0,0)[bl]{s:}}
\put( 5,27){\framebox(15,5)[l]{     m}}
\put(15,29){\circle*{1}}
\put(15,29){\line(0,-1){4}}
\put(15,25){\vector(1,0){15}}

\put(30,27){\framebox(15,5)[l]{     g}}
\put(30,27){\line(0,-1){4}}
\put(28,19){\makebox(0,0)[bl]{(m)}}

\put(70,11){\makebox(0,0)[bl]{p:}}
\put(75,10){\framebox(15,5)[l]{     n}}
\put(85,12){\circle*{1}}
\put(85,12){\line(0,-1){4}}
\put(85,8){\vector(1,0){15}}

\put(100,10){\framebox(15,5)[l]{     y}}
\put(100,10){\line(0,-1){4}}
\put(97,2){\makebox(0,0)[bl]{(n)}}

\put(70,28){\makebox(0,0)[bl]{s:}}
\put(75,27){\framebox(15,5)[l]{     m}}
\put(85,29){\circle*{1}}
\put(85,29){\line(0,-1){4}}
\put(85,25){\vector(1,0){15}}

\put(100,27){\framebox(15,5)[l]{     y}}
\put(100,27){\line(0,-1){4}}
\put(98,19){\makebox(0,0)[bl]{(k)}}

\end{picture}
\ec}
%\caption{Fig.2b}
%\end{figure}

%\begin{verbatim}
%  _________        _________  I    _________        _________
%s I___m___I        I___g___I  I  s I___m___I        I___y___I
%          I___---->!          I            I___---->!
%                  (m)         I                    (m)
%  _________        _________  I    _________        _________
%p I___n___I        I___y___I  I  p I___n___I        I___y___I
%          I___---->!          I            I___---->!
%                  (n)                              (n)
%\end{verbatim}

Существует стандартная ссылка в "никуда": {\rm NIL}. Если {\rm s:= NIL}, то
переменной  {\rm s}  будет   присвоена   ссылка   на   определенный,
"известный" машине, но фиктивный адрес.

   Важная  стандартная  процедура:  {\rm NEW(p)},  где  {\rm NEW} ---  имя
процедуры, {\rm p} --- параметр ссылочного типа. В  результате  работы
этой процедуры переменной  {\rm p}  будет  присвоен  адрес  (первого
слова) участка памяти, отведенного ЭВМ для  размещения  одного
объекта  некоторого  заданного  типа.   Тип   определяется   в
соответствии  с  ссылкой {\rm p}.  Таким  образом  отводится  место
достаточное для  размещения  объекта,  на  который  определена
ссылка {\rm p}. Обратная процедура --- {\rm DISPOSE (p)}.

\ul{Пример}. Отведем в памяти место для  размещения  целого
числа и зашлем в ячейку цифру "5":
\begin{verbatim}
         TYPE  ref = @INTEGER;
         VAR   p: ref;
         BEGIN
            NEW(p); p@:= 5
         END.
\end{verbatim}

\medskip
\bc\ul{Упражнения}\ec

1. Что напечатает программа:
\begin{verbatim}
         TYPE  ref= @REAL;
         VAR   s, q: ref
         BEGIN
            NEW(s); NEW(q)
            q@:= 4.0;  s:= q;
            WRITE ( s@);
            q@:= 5.0
            WRITE ( s@)
         END.
\end{verbatim}

2. Создать структуру в виде стека (по принципу --- первый пришел
и  последний  ушел)  для  запоминания   заранее   неизвестного
количества пар целых чисел, используя следующие типы данных:
\begin{verbatim}
      TYPE  Stack = @Elem
            Elem = RECORD n: T1;
                          m: T2;
                          ref: Stack
                   END;
              T1 = 1..200;
              T2 = -200..200;
\end{verbatim}

Стек на рисунке для данной задачи будет выглядить так:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(120,20)

\put(7,16){\makebox(0,0)[bl]{n}}
\put(14,16){\makebox(0,0)[bl]{m}}
\put(20,16){\makebox(0,0)[bl]{ref}}

\put( 5,10){\framebox(21,5)[l]{     }}
\put(12,10){\line(0,1){5}}
\put(19,10){\line(0,1){5}}
\put(26,10){\line(0,1){5}}

\put(23,12){\circle*{1}}
\put(23,12){\line(0,-1){4}}
\put(23,8){\vector(1,0){12}}

\put(37,16){\makebox(0,0)[bl]{n}}
\put(44,16){\makebox(0,0)[bl]{m}}
\put(50,16){\makebox(0,0)[bl]{ref}}
\put(35,10){\framebox(21,5)[l]{     }}
\put(42,10){\line(0,1){5}}
\put(49,10){\line(0,1){5}}
\put(56,10){\line(0,1){5}}
\put(35,10){\line(0,-1){4}}

\put(53,12){\circle*{1}}
\put(53,12){\line(0,-1){4}}
\put(53,8){\vector(1,0){12}}

\put(70,12){\circle*{0.5}}
\put(72,12){\circle*{0.5}}
\put(74,12){\circle*{0.5}}

\put(78,8){\vector(1,0){7}}
\put(87,16){\makebox(0,0)[bl]{n}}
\put(94,16){\makebox(0,0)[bl]{m}}
\put(100,16){\makebox(0,0)[bl]{ref}}
\put(85,10){\framebox(21,5)[l]{     }}
\put(92,10){\line(0,1){5}}
\put(99,10){\line(0,1){5}}
\put(106,10){\line(0,1){5}}
\put(85,10){\line(0,-1){4}}

\put(103,12){\circle*{1}}
\put(103,12){\line(0,-1){4}}
\put(103,8){\vector(1,0){12}}
\put(116,8){\circle*{0.3}}
\put(117,8){\circle*{0.3}}
\put(118,8){\circle*{0.3}}

\end{picture}
\ec}
%\caption{Fig.3}
%\end{figure}
%     n   m  ref         n    m  ref            n   m  ref
%   _____________       _____________         _____________
%   I___I___I___I       I___I___I___I         I___I___I___I
%             I........>!         I.....  ...>!         I.....>

3.  Аналогично  упр.~2  написать  программу,  компактно
хранящую разреженную матрицу, т.е.~матрицу, содержащую  очень
много нулевых элементов.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{\yb Структуры данных}

\ul{Определение}:  Под  структурой  данных   мы   будем
понимать не только множество каких-то объектов, но и множество
связей между этими объектами.

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

   Структуры данных и их  представление  ---  один  из  наиболее
важных   вопросов   нечислового   программирования.   Понимание
некоторых аспектов этого вопроса требует  обычно  значительных
усилий  и  усложняется  отсутствием  их  ясного   описания   в
существующей литературе.

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


\section{\yr Динамические структуры данных}

   Отметим, что как число объектов в структурах данных, так  и
связи между этими объектами могут изменяться со временем.

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

\ul{Определение}:  Динамическими   структурами   данных
будем называть структуры, которые могут создаваться,  меняться
и уничтожаться в процессе выполнения программы.

   Очевидно, такие структуры наиболее  часто  встречаются  при
работе программ в реальном времени.

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


\section{\yr  Линейные списки}

\subsection{\yr Определения и основные операции}

\ul{Определение}:   Линейный   список   ---    множество,
состоящее из $n$ элементов ($n \geq 0$), со следующими свойствами:

   1) существует первый элемент (при $n > 0$);

   2) для любых не крайних элементов существует  предыдущий  и
     последующий;

   3) существует последний элемент (при $n > 0$).

   Иными словами, объекты линейного списка связаны лишь с двумя
соседними.  Данная  структура  поэтому  хорошо  представляется
спрямленной последовательностью связей (отсюда и ее название):

%\begin{figure}[h]
\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(115,5)

\put( 5,0){\framebox(15,4)[l]{  }}
\put(20,2){\line(1,0){10}}

\put(30,0){\framebox(15,4)[l]{  }}
\put(45,2){\line(1,0){10}}

\put(55,0){\framebox(15,4)[l]{  }}
\put(70,2){\line(1,0){7}}

\put(81,2){\circle*{0.5}}
\put(83,2){\circle*{0.5}}
\put(85,2){\circle*{0.5}}

\put(95,2){\line(-1,0){7}}
\put(95,0){\framebox(15,4)[l]{  }}

\end{picture}
\ec}
%\caption{Fig.4}
%\end{figure}

%\begin{verbatim}
%  _________      _________     _________           _________
%  I_______I------I_______I-----I_______I---.....---I_______I
%\end{verbatim}
   Примеры групп объектов, подпадающих под данное определение,
многочислены  и  многообразны,  в  частности:   стопка   любых
предметов (например, подносов),  книги,  тетради  (как  список
листов) и т.д.

   Подробнее рассмотрим очередь к врачу. Очевидно,  что  здесь
имеем множество пациентов, причем  множество  может быть  и  пустым.
Также ясно, что есть первый и последний элемент, и для любых не
крайних существует предыдущий и последующий.

   Операции,  которые  чаще  всего  производят  над  линейными
списками, являются:

   1) просмотр списка и поиск элемента;

   2) включение нового элемента;

   3) исключение элемента;

   4) объединение двух списков в один;

   5) копирование списка и другие операции.

   В нашем примере очереди к врачу эти операции означают:

   1) Кто-то хочет узнать, как далеко он находится от начала и
     опрашивает  людей  (с  начала  или  от  себя  к  началу).
     Фактически просматривая очередь.

   2) Пришел еще один больной (и встал в  конец  очереди  или,
     если "по номеркам", то в середину!).

   3) Кто-то отчаялся ждать и ушел домой (или пошел к врачу).

   4) Было два врача и две очереди, но один врач ушел ...

   5) Оставшийся после окончания приема врача народ скопировал
     свой порядок в список, чтобы в следующий  раз  восстановить
     порядок или  медицинская  сестра  всех  переписала  перед
     началом приема врача в порядке очереди.

   Возратимся к программированию.  Отметим,  что,  по-видимому
невозможно найти представление (структурированных) данных, при
которых  все  возможные  операции  выполнялись  бы   одинаково
эффективно. Однако, к  счастью,  в  редких  случаях  требуется
выполнение   всех   операций,   чаще   необходимо   обеспечить
эффективность работы лишь нескольких операций.  В  зависимости
от этого выбирают как способ представления структуры данных (в
частности, линейного списка), так и конкретный подвид структур
(например, для линейных  списков  ---  стеки,  очереди,  деки  и
т.п.).


\subsection{\yr   Способы представления списков}

   Существует  два  основных  способа  представления  списков:
последовательный и связный. При  последовательном  ---  элементы
списка располагаются в  памяти  ЭВМ  последовательно  друг  за
другом;  при  связном  ---  информация   группируется   в   пары
(например, записи), где один  компонент  ---  очередной  элемент
списка, а второй --- ссылка (адрес) на пару  со  следующим  (или
предыдущим)  элементом.  Т.е.  расположение   в   памяти   ЭВМ
элементов линейного списка может быть представленно  следующим
образом:

   а) при последовательном представлении (таблично и рисунком):

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(100,32)

\put(3,1){\shortstack[l]{address\\  \\m\\m+c\\m+2c\\...\\m+i*c\\...}}
\put(25,1){\shortstack{info.\\ \\a1\\a2\\a3\\...\\ai\\...}}
%\put(44,1){\shortstack{right\\ \\3\\0\\6\\0\\0\\0}}
\put(0,0){\line(0,1){24}}
\put(19,0){\line(0,1){24}}
\put(38,0){\line(0,1){24}}
\put(0,0){\line(1,0){38}}
\put(0,24){\line(1,0){38}}
\put(0,18){\line(1,0){38}}

\put(82,27){\makebox(0,0){m}}
\put(84,27){\vector(1,0){6}}
\put(90,25){\framebox(10,5){a1}}
\put(90,20){\framebox(10,5){a2}}
\put(90,15){\framebox(10,5){a3}}
\put(90,10){\framebox(10,5){...}}
\put(90,5){\framebox(10,5){ai}}
\put(90,0){\framebox(10,5){...}}

\end{picture}
\ec}
%\caption{Fig.5x}
%\end{figure}

%\begin{verbatim}
%___________________________  :     ______ ______ ______ ___
%I  адрес в    I  информа- I  :    I      I      I      I
%I памяти ЭВМ  I    ция    I  :    I  A1  I  A2  I  A3  I...
%I-------------I-----------I  :    I______I______I______I___
%I   L         I    A1     I  : L->!
%I   L+c       I    A2     I  :
%I   L+2*c     I    A3     I  :        ____ ______ _____
%I   .....     :   ....    I  :            I      I
%I   L+I*c     I    Ai     I  :         ...I  Ai  I.....
%I   .....     :   ....    I  :        ____I______I_____
%I_____________I___________I  :
%                             :
%\end{verbatim}

{\rm a1, a2, a3}, ...  --- элементы списка;\\
{\rm m} --- адрес первого эелемента ({\rm а1});\\
{\rm c} --- объем памяти, отводимый для размещения одного элемента.

   б) при связном представлении (таблично  и  рисунком):

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(112,32)

\put(3,1){\shortstack{address\\  \\m1\\ \\m2\\ \\m3\\ \\...\\mi-1\\...}}
\put(25,1){\shortstack[b]{inform.\\ \\a1,m2\\a2,m3\\a3,m4\\...\\ai,mi\\...}}
%\put(44,1){\shortstack{right\\ \\3\\0\\6\\0\\0\\0}}
\put(0,0){\line(0,1){27}}
\put(19,0){\line(0,1){27}}
\put(41,0){\line(0,1){27}}
\put(0,0){\line(1,0){41}}
\put(0,27){\line(1,0){41}}
\put(0,21){\line(1,0){41}}

\put(80,27){\makebox(0,0){m2}}
\put(84,27){\vector(1,0){6}}
\put(90,25){\framebox(20,5){a2,m3}}

\put(90,20){\makebox(20,5){...}}

\put(80,17){\makebox(0,0){m1}}
\put(84,17){\vector(1,0){6}}
\put(90,15){\framebox(20,5){a1,m2}}

\put(90,10){\makebox(20,5){...}}

\put(80,7){\makebox(0,0){m3}}
\put(84,7){\vector(1,0){6}}
\put(90,5){\framebox(20,5){a3,m4}}

\put(90,0){\makebox(20,5){...}}

\end{picture}
\ec }
%\caption{Fig.5y}
%\end{figure}

%\begin{verbatim}
%___________________________ :      _______ _   _ _______ ___
%I   адрес в   I  информа- I :     I       I     I       I
%I  памяти ЭВМ I   ция     I :     I A2,L3 I ... I A3,L4 I...
%I-------------I-----------I :     I_______I_   _I_______I___
%I    L1       I   A1,L2   I : L2->!         L3->!
%I    L2       I   A2,L3   I :
%I    L3       I   A3,L4   I :         ____ _______ _____
%I    .....    :   ....    I :             I       I
%I    LI       I AI,L(i+1) I :          ...I A1,L2 I.....
%I    .....    :   ....    I :         ____I_______I_____
%I_____________I___________I :         L1->!
%                            :
%\end{verbatim}

где  {\rm m1, m2, m3}, ... --- адреса памяти в ЭВМ соответствующих пар,
     в которых находится информация об элементе и адресе
     следующего элемента. При этом адреса {\rm m1, m2, m3}, ...
     могут быть не упорядочены.

   В подробно рассматриваемом нами примере --- очереди к  врачу,
последовательное представление означает, что  люди  в  очереди
сидят на линейно расположенных стульях  в  правильном  порядке
(причем подряд!). При связном представлении этого  нет,  т.е.
народ сидит  как  попало,  но  у  каждого  имеется  ссылка  на
предыдущуего (иначе анархия, приводящая обычно к скандалу);
эта  ссылка  в данном случае существует  в  памяти  человека  в
виде  образа впереди стоящего пациента.

   Отметим, что  в  поликлиниках,  если  очередь  длинная,  то
стихийно  (но  далеко  не  случайно!)  реализуется   связной
представление,   а, например, в    магазине    ---    обычно
последовательное.  Связано  это  скорее  всего  с   тем,   что
перемещаться  стоя  легко,  а  сидя   сложно.   Также   и   в
программировании   при    некоторых    условиях    оказывается
предпочтительнее  один  вид  представления,  а  при  других  ---
другой.

\ul{Упражнение.}   Привести  примеры,  когда   удобнее   пользоваться   связным
представлением линейного списка, а когда последовательным.

   Рассмотрим  несколько  подробнее  последовательный   способ
представления  (линейных)  списков.  Стандартный  способ   его
реализации ---  использование  массива,  длина  которого  больше
предполагаемой длины списка (хорошо задать  эту  длину  иногда
бывает трудно!).

   Напишем программу, которая  будет  вводить  последовательно
объекты (даты\footnote{\yr Определение данных типа 'дата' разобрано в
предыдущей главе в разделе "Составные типы данных".})
и строить из них линейный список,  пока  они
не кончатся в файле {\rm datafile}.
\begin{verbatim}
     TYPE Typeofdata = ARRAY [1..3] OF 0..2005;
          Seqreprs = ARRAY [1..m] OF Typeofdata;
     VAR  a: Typeofdata;  list: Seqrepres;  n: 1..m;
     BEGIN
         n:= 0;
         WHILE  NOT eof(datafile) DO
         BEGIN
            n:= n + 1;  READ (datafile, a);
            list[n]:= a
         END;
     END.
\end{verbatim}
   После этих операций  линейный  список  будет  расположен  в
первых {\rm n}--элементах массива {\rm list}.

   Рассмотрим как программно можно  реализовать  перечисленные
выше операции.

   1. Просмотр --- поиск элемента. Пусть нужно узнать,  есть  ли
(и какой от начала) элемент, значение которого равно  значению
переменной indata (типа {\rm Typeofdata}, т.е.~найти заданную дату).
План работы следующий: если  элементов  в  списке  нет,  то  и
делать ничего не надо, иначе необходимо  просмотреть  линейный
список с начала, пока не найдем нужный элемент,  или  пока  не
дойдем до последнего элемента. Оформим поиск элемента  в  виде
процедуры так:
\begin{verbatim}
  PROCEDURE  Find (n: INTEGER; list: Seqrepres; indata: Typeofdata);
    VAR  yes: BOOLEAN;  k: INTEGER
    BEGIN
      yes:= FALSE;
      IF n=0
        THEN WRITE ('list is empty')
        ELSE
          BEGIN
            k:= 0;
            WHILE  (NOT yes) AND k<=N  DO
              BEGIN
                k:= k + 1;
                yes:= (list [k] = indata)
              END; (* while *)
          END (* else *)
      IF  NOT yes  THEN k:=0;
      WRITE  ( yes, 'k=', k);
    END; (* Find *)
\end{verbatim}
({\rm list is empty }$=$ список пуст)

\medskip
   В результате, если в списке элементов нет, то  подпрограмма
напечатает "список пуст", в  противном  случае,  если  элемент
будет  найден,  то  напечатает  "{\rm TRUE  k $=$}
"порядковый   номер элемента"", если
элемент не будет найден, то --- "{\rm FALSE k $=$ 0}".

   2. Включение нового элемента. Пусть  нужно  вставить  между
$k$-ым и ($k+1$)-ым элементами еще один ($k<n$),  при  этом  следует
проверить не будет ли  список  переполнен,  т.е.~ выходить  за
границы массива. В  иллюстративном  примере  очереди  алгоритм
будет  выглядеть  следующим  образом:  проверить,  если  новое
число человек ($n+1$) станет  больше  числа  стульев,  то  лучше
ничего не делать, иначе попросим  людей  с  конца  очереди  до
($k+1$)-ого человека пересаживаться на соседний  освобождающийся
стул  (в   обратном   направлении   не   выйдет).   Затем   на
освободившийся в середине стул посадим новенького.

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(110,12)

\thicklines
\put(29,10){\makebox(0,0){O}}
%\put(3,10){\line(1,0){27}}
\put(30,10){\vector(2,-1){4}}

\thinlines
\put( 5,0){\makebox(0,0){1}}
\multiput( 5,7)(10,0){8}{\makebox(0,0){O}}
\multiput( 3,5)(10,0){11}{\line(0,-1){2}}
\multiput( 7,5)(10,0){11}{\line(0,- 1){2}}
\multiput( 3,5)(10,0){11}{\line(1,0){4}}

\put(15,0){\makebox(0,0){2}}
\put(25,0){\makebox(0,0){...}}
\put(35,0){\makebox(0,0){k}}
\multiput(36,8)(10,0){3}{\line(2,1){4}}
\multiput(40,10)(10,0){3}{\vector(2,-1){4}}

\put(45,0){\makebox(0,0){k+1}}
\put(55,0){\makebox(0,0){k+2}}
\put(65,0){\makebox(0,0){...}}
\put(75,0){\makebox(0,0){n}}
\put(85,0){\makebox(0,0){n+1}}
\put(95,0){\makebox(0,0){...}}
\multiput(66,8)(10,0){2}{\line(2,1){4}}
\multiput(70,10)(10,0){1}{\vector(2,-1){4}}
\put(80,10){\vector(2,-1){4}}

\put(105,0){\makebox(0,0){m}}


%\put(85,2){\circle*{0.5}}

\end{picture}
\ec }
%\caption{Fig.5z}
%\end{figure}

%\begin{verbatim}
%   &_>_____________  _>__  _>__  _>_       _>__
%                   \ !   \ !   \ !         !   \
%   __&__ __&__     __&__ __&__ __&__     __&__ _____     _____
%   I   I I   I ... I   I I   I I   I ... I   I I   I ... I   I
%     1     2         k    k+1   k+2        n    n+1        m
%\end{verbatim}

Оформим алгоритм в виде процедуры {\rm Putin}:
\begin{verbatim}
  PROCEDURE  Putin (VAR k,n, m: INTEGER;  list: Seqrepres;
                                          indata: Typeofdata);
    VAR I: INTEGER;
    BEGIN
      IF (n + 1) > m
         THEN WRITE ('list is full')
         ELSE
           BEGIN
             FOR  I:= n  DOWNTO  k+1  DO
               list [I+1]:= list [I];
             list [k+1]:= indata;
             n:= n + 1
           END (* else *)
    END;
\end{verbatim}
({\rm list is full} $=$ список заполнен)

\medskip
   3. Исключение элемента. Пусть необходимо исключить $k$-ый  с
начала очереди элемент $(k\leq{n})$.

   В нашей иллюстрации это будет означать, что кто-то  ушел  и
освободился стул. Чтобы его не заняли,  "народ"  сдвигается  к
началу на одно место.

Оформим в виде процедуры {\rm Exlcude}:
\begin{verbatim}
  PROCEDURE  Exlcude (VAR k, n: INTEGER;  list: Seqrepres;
                                          out: Typeofdata);
    VAR i: INTEGER;
    BEGIN
       out:= list [k];
       FOR  i:= k+1 TO  n  DO
         list [i-1]:= list [i];
       n:= n - 1
    END;
\end{verbatim}

   4. Объединение двух списков.  Пусть  необходимо  объединить
два списка {\rm list1} и {\rm list2}
(два массива размерности  $m1$  и  $m2$).
Число элементов в первом списке  --- $n1$,  а  во  втором  --- $n2$.
Объединение произведем в один массив {\rm list1}.

   Примером слияния очередей к врачу может быть  присоединение
одной к другой, если хватит стульев,  т.е.~$n1+n2$  меньше  или
равно $m1$. Если стульев не хватит, то тогда ...!  В программе
же, если этот случай не предусмотреть, то произойдет выход  за
рамки массива, что приведет к ее аварийному завершению\footnote{\yr
Если программа будет написана на Фортране,  то  выход  за
границы массива может привести к потере информации соседних  с
массивом  полей  и  продолжением   работы   вашей   программы.
Аварийный останов программы возможен  совсем  в  другой  части
программы и поиск этой ошибки довольно сложен.}.

   Оформим данную операцию в виде процедуры {\rm Unit}:
\begin{verbatim}
  PROCEDURE  Unit (VAR n1, n2, m1: INTEGER;
                       list1, list2: Seqrepres);
    VAR i: INTEGER
    BEGIN
      IF  n1+n2 > m1
        THEN  WRITE ('merging is impossible')
        ELSE
          BEGIN
            FOR  i:= n1+1  TO  n1+n2  DO
              list1 [i]:= list2 [i-n1];
            n1:= n1 + n2
          END (* else *)
    END;
\end{verbatim}
({\rm merging is impossible} $=$ объединение не возможно)

\medskip
   5. Копирование списков --- печать. В  примере,  если  очереди
нет, то врач свободен, в противном случае  медицинская  сестра
перепишет людей в порядке очереди.

   Оформим это в виде подпрограммы {\rm Copylist}:
\begin{verbatim}
  PROCEDURE  Copylist (n: INTEGER;  list: Seqrepres);
    VAR i: INTEGER
    BEGIN
      IF  n = 0
        THEN  WRITE ('list is empty')
        ELSE
          FOR  i:= 1  TO  n  DO
            WRITE (list [i])
    END;
\end{verbatim}
({\rm list is empty} $=$ список пуст)

\medskip
   Заметим,   что   копирование    (печать)    массива    (для
последовательного  представления  линейного  списка)  возможно
лишь указанным образом, т.е.~по элементам.

   Подведем итоги рассмотрения последовательного представления
списков. Основные трудности возникают при неопределенной длине
списка, т.к.~в этом случае не  ясно  какой  размерности  брать
массив.  Также  следует  отметить,  что  основная  операция   ---
пересылка. При длинных списках эта операция может  потребовать
много процессорного времени ЭВМ.

   Теперь рассмотрим связный способ представления списков. Как
отмечалось в начале п.~3.2.2, нужно создать пары: элемент $+$ ссылка
на следующий (или предыдущий).  Для  этого  обычно  используют
записи и ссылки на них следующим образом:
\begin{verbatim}
      TYPE  Typeofdata = ARRAY [1..3] OF 0..2005;
            Relrepes = @Element;
            Element = RECORD  data: Typeofdata;
                              link: Relrepes
                      END;
      VAR  list, ref: Relrepes;  a: Typeofdata;
\end{verbatim}

В переменной {\rm list} будем хранить ссылку  на  последний  элемент
линейного списка (аналог  переменной  {\rm n}  при  последовательном
представлении).

   Создание  списка,   аналогичное   выполненному   выше   для
последовательного представления, будет иметь вид:
\begin{verbatim}
      BEGIN
         list:= NIL;
         WHILE  eof (file)  DO
          BEGIN
             NEW (ref);  READ (a);
             ref@.data:= a;  ref@.link:= list;
             list:= ref
          END (* while *)
      END.
\end{verbatim}

   Теперь у нас есть линейный связный  список,  который,  чтобы
его не потерять, "зацеплен за конец" переменной {\rm link}.

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(130,12)

\put(0,2.5){\makebox(0,0)[l]{link}}
\put(7,2){\vector(1,0){5}}

\put(12,4){\line(0,-1){4}}
\put(12,4){\framebox(14,5)[l]{  }}
\put(19,4){\line(0,1){5}}
\put(23,6){\circle*{1}}
\put(23,6){\line(0,-1){4}}
\put(23,2){\vector(1,0){12}}

\put(35,4){\line(0,-1){4}}
\put(35,4){\framebox(14,5)[l]{  }}
\put(42,4){\line(0,1){5}}
\put(46,6){\circle*{1}}
\put(46,6){\line(0,-1){4}}
\put(46,2){\vector(1,0){12}}

\put(61,2){\circle*{0.4}}
\put(62,2){\circle*{0.4}}
\put(63,2){\circle*{0.4}}

\put(65,2){\vector(1,0){5}}
\put(70,4){\line(0,-1){4}}
\put(70,4){\framebox(14,5)[l]{  }}
\put(77,4){\line(0,1){5}}
\put(81,6){\circle*{1}}
\put(81,6){\line(0,-1){4}}
\put(81,2){\vector(1,0){12}}

\put(93,4){\line(0,-1){4}}
\put(93,4){\framebox(14,5)[l]{  }}
\put(100,4){\line(0,1){5}}
\put(104,6){\circle*{1}}
\put(104,6){\line(0,-1){4}}
\put(104,2){\vector(1,0){12}}
\put(117,2.5){\makebox(0,0)[l]{nil}}

%\put(50,11){\makebox(0,0)[bl]{b:}}
%\put(55,10){\framebox(15,5)[l]{     w}}
%\put(55,10){\line(0,-1){4}}
\end{picture}
\ec}
%\caption{Fig.6}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{verbatim}
%        _________   _________         _________   _________
%        I___I___I   I___I___I         I___I___I   I___I___I
%link--->!     I__-->!     I__-->...-->!     I__-->!     I_-->n
%\end{verbatim}

   Рассмотрим  программную  реализацию   перечисленных   ранее
операций.  Как  и  при  последовательном  представлении
оформим  их  в  виде процедур.

   1. Поиск элемента --- просмотр. Делается  также,  как  и  при
последовательном представлении.
\begin{verbatim}
     PROCEDURE  Findconn (list: Relrepes;  indata: Typeofdata);
       VAR  ref: Relrepes;
       BEGIN
         ref= list;
         IF  ref=NIL
           THEN WRITE ('list is empty')
           ELSE
             WHILE (ref@.data <> indata)  OR  (ref <> NIL)  DO
               ref:= ref@.link;
\end{verbatim}
     (* {\rm ref:= ref@.link} --- очень важная операция --
     аналог {\rm i:= i+1}, \\
         означающая переход к следующему элементу *)
\begin{verbatim}
           IF  ref@.data <> NIL
             THEN  WRITE ('element is found')
             ELSE  WRITE ('no such element in the list')
       END;
\end{verbatim}
({\rm list is empty} $=$  список пуст; \\
{\rm element is found} $=$ элемент найден; \\
{\rm no such element in the list} $=$ элемента в списке нет)

\medskip
   Вставить новый элемент за элементом, на  который  указывает
ссылка {\rm here}. Сделаем это так, если использовать  наш пример очереди
к врачу: спросим у  отмеченного,  кто  находится  перед  ним  и
новенькому скажем, что он за этим  человеком,  а  отмеченному,
что он за новеньким.

%---> старая связь   ...> новая  связь

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(90,20)

\put(11,6){\circle*{0.5}}
\put(12,6){\circle*{0.5}}
\put(13,6){\circle*{0.5}}

\put(4,1.6){\makebox(0,0)[l]{here}}
\put(13,1.2){\vector(1,0){7}}

\put(20,4){\line(0,-1){4}}
\put(20,4){\framebox(14,5)[l]{  }}
\put(27,4){\line(0,1){5}}
\put(31,6){\circle*{1}}
\put(31,6){\line(0,-1){4}}
%\put(31,2){\vector(1,0){15}}

\thicklines
\put(31,2){\line(1,0){9}}
\put(40,2){\line(0,1){9}}
\put(40,11){\vector(1,0){6}}

\thinlines
\put(31,12.6){\makebox(0,0)[l]{new}}
\put(39,12.2){\vector(1,0){7}}

\put(46,14){\line(0,-1){4}}
\put(46,14){\framebox(14,5)[l]{  }}
\put(53,14){\line(0,1){5}}
\put(57,16){\circle*{1}}

\thicklines
\put(57,16){\line(0,-1){14}}
\put(57,2){\vector(1,0){15}}

\thinlines
\put(31,2){\line(0,-1){2}}
\put(31,1){\vector(1,0){41}}

\put(72,4){\line(0,-1){4}}
\put(72,4){\framebox(14,5)[l]{  }}
\put(79,4){\line(0,1){5}}
\put(83,6){\circle*{1}}
\put(83,6){\line(0,-1){4}}
\put(83,2){\vector(1,0){15}}

\put(90,6){\circle*{0.5}}
\put(91,6){\circle*{0.5}}
\put(92,6){\circle*{0.5}}

\put(100,2){\circle*{0.2}}
\put(101,2){\circle*{0.2}}
\put(102,2){\circle*{0.2}}

\end{picture}
\ec }
%\caption{Fig.7}
%\end{figure}
%                                 _________
%                                 I___I___I
%                       NEW....::>!     :
%                    _________ :        :   _________
%             ...    I___I___I.:        :..>I___I___I   ...
%            НERE--->!     I_____------->!

\begin{verbatim}
    PROCEDURE  Putinconn (VAR here: Relrepes;  indata: Typeofdata);
      VAR  new, next: Relrepes;
      BEGIN
        NEW (elnew);  elnew@.data:= indata;
        next:= here@.link;
        elnew@.link:= next;
        here@.link:= elnew
      END;
\end{verbatim}

   3. Исключение  элемента.  Исключим  элемент,  следующий  за
элементом указанном в ссылке {\rm here}. Как это  сделать,  очевидно
из следующего рисунка:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(90,20)

\put(11,6){\circle*{0.5}}
\put(12,6){\circle*{0.5}}
\put(13,6){\circle*{0.5}}

\put(4,1.6){\makebox(0,0)[l]{here}}
\put(13,1.2){\vector(1,0){7}}

\put(20,4){\line(0,-1){4}}
\put(20,4){\framebox(14,5)[l]{  }}
\put(27,4){\line(0,1){5}}
\put(31,6){\circle*{1}}
\put(31,6){\line(0,-1){4}}
\put(31,2){\vector(1,0){15}}

\put(46,4){\line(0,-1){2.5}}
\put(46,4){\framebox(14,5)[l]{  }}
\put(53,4){\line(0,1){5}}
\put(57,6){\circle*{1}}
\put(57,6){\line(0,-1){4}}
\put(57,2){\vector(1,0){15}}

\thicklines
\put(31,1){\line(0,1){5}}
\put(31,1){\vector(1,0){41}}

\thinlines
\put(72,4){\line(0,-1){4}}
\put(72,4){\framebox(14,5)[l]{  }}
\put(79,4){\line(0,1){5}}
\put(83,6){\circle*{1}}
\put(83,6){\line(0,-1){4}}
\put(83,2){\vector(1,0){15}}

\put(90,6){\circle*{0.5}}
\put(91,6){\circle*{0.5}}
\put(92,6){\circle*{0.5}}

\put(100,2){\circle*{0.2}}
\put(101,2){\circle*{0.2}}
\put(102,2){\circle*{0.2}}

\end{picture}
\ec}
%\caption{Fig.8}
%\end{figure}
%           _________   _________   _________
%    ...    I___I___I   I___I___I   I___I___I    ...
%   НERE--->!     I__-->!     I__-->!
%                 :................>!

\begin{verbatim}
         PROCEDURE  Exclconn (VAR here: Relrepes);
           VAR  next: Relrepes;
           BEGIN
             next:= here@.link;
             here@.link:= next@.link;
             DISPOSE (next)
           END;
\end{verbatim}

   4. Объединение двух списков. Пусть  в  переменных {\rm l1begin,
l1end} и {\rm l2begin,  l2end}  ---  ссылки  на  начало  и  конец  двух
списков. Следует выполнить следующее соединение:

%   <--- второй список ---I         I--- первый список --->
%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(130,16)

\put(1,9){\circle*{0.5}}
\put(2,9){\circle*{0.5}}
\put(3,9){\circle*{0.5}}

\put(8,7){\line(0,-1){3}}
\put(8,7){\framebox(14,5)[l]{  }}
\put(15,7){\line(0,1){5}}
\put(19,9){\circle*{1}}
\put(19,9){\line(0,-1){4}}
\put(19,5){\vector(1,0){17}}

\put(0,0.6){\makebox(0,0)[l]{l2begin}}
\put(12,0.2){\vector(1,0){24}}

\put(36,7){\line(0,-1){7}}
\put(36,7){\framebox(14,5)[l]{  }}
\put(43,7){\line(0,1){5}}
\put(47,9){\circle*{1}}

\thicklines
\put(47,9){\line(0,-1){4}}
\put(47,5){\vector(1,0){23}}

\thinlines
\put(47,5){\vector(0,-1){3}}
\put(45,0.5){\makebox(0,0)[l]{nil}}

\put(53,0.5){\makebox(0,0)[l]{l1end}}
\put(62,0){\vector(1,0){8}}


\put(70,7){\line(0,-1){7}}
\put(70,7){\framebox(14,5)[l]{  }}
\put(77,7){\line(0,1){5}}
\put(81,9){\circle*{1}}
\put(81,9){\line(0,-1){4}}
\put(81,5){\vector(1,0){17}}

\put(98,7){\line(0,-1){4}}
\put(98,7){\framebox(14,5)[l]{  }}
\put(105,7){\line(0,1){5}}
\put(109,9){\circle*{1}}
\put(109,9){\line(0,-1){4}}
\put(109,5){\vector(1,0){15}}

\put(114,9){\circle*{0.5}}
\put(115,9){\circle*{0.5}}
\put(116,9){\circle*{0.5}}

\put(125,5){\circle*{0.2}}
\put(126,5){\circle*{0.2}}
\put(127,5){\circle*{0.2}}

\end{picture}
\ec }
%\caption{Fig.9}
%\end{figure}
%     _________   _________         _________   _________
% ... I___I___I   I___I___I         I___I___I   I___I___I ...
%           I__-->!     I..........>!     I__-->!     I__--...
%     l2begin---->!     V   l1end-->!
%                      NIL

\begin{verbatim}
       PROCEDURE  Unitconn (VAR l2begin, l1end: Relrepes);
         BEGIN
           l2begin@.link:= l1end
         END;
\end{verbatim}

После выполнения этой процедуры списки будут связаны  в  один,
причем в {\rm l1begin} будет ссылка на начало, а в {\rm l2end}
--- на  конец объединенного списка.

   5. Копирование списка.
\begin{verbatim}
       PROCEDURE  Copyconn (list: Relrepes);
         VAR  next: Relrepes;
         BEGIN
            next:= list;
             IF  next = NIL
               THEN  WRITE ('list is empty')
               ELSE
                 REPEAT
                    WRITE (next@.data);  next:= next@.link
                 UNTIL  next = NIL
         END;
\end{verbatim}
({\rm list is empty} $=$ список пуст')

\medskip
   Резюмируем сравнительное рассмотрение  реализаций  операций
при различных представлениях списков:

   ---  просмотр  и  копирование  списков  реализуется  примерно
     одинаково;

   --- объединение списков существенно эффективнее можно сделать
     при связном их представлении (всего одна операция!)\footnote{\yr
     В  случае,     если  объединение  происходит  по  какому-то
правилу  (например  в  порядке  возрастания   элементов),   то
эффективность примерно одинаковая.};

   --- включение  и  исключение  элементов  в  некотором  смысле
     эффективнее   при   связном   представлении   (т.к.~нет
     многочисленных  пересылок  дачнных,  но   выгода   здесь,
     вероятно,   незначительно    превосходит    отрицательную
     сторону:   непривычность   и    неочевидность    связного
     представления);

   Можно сделать следующие выводы:

   1) Если  в  основном  предстоит  выполнять  операции   типа
     просмотра,  или  включения  и  исключения,  то   возможно
     использование любого представления.

   2) Если  операции   объединения   списков   или   некоторые
     модификации включения или исключения играют главную роль,
     то    использование    связного    представления    может
     способствовать  созданию  существенно  более  эффективных
     программ.

   Отметим, что в некоторых языках программирования  (Фортран,
Алгол-60 и др.) нет прямой возможности работы со ссылками,  но
связное представление, если немного потрудиться, смоделировать
можно.


\subsection{\yr  Частные случаи линейных списков:  стек, очередь, дек}

   В программировании наиболее  часто  используются  несколько
частных  случаев  линейных  списков,  когда  дополнительно   к
свойствам определения на структуры данных накладываются  новые
ограничения.

\ul{Определение}:  Стеком   будем   называть   линейный
список,  в  котором  все  включения  и  исключения   элементов
разрешено производить только на одном  конце  (считается,  что
включение и исключения самые частые (основные) операции!).

Примеры --- магазин    автомата    с    патронами,
железнодорожный состав вагонов в тупике и т.д.
%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(37,7)

\linethickness{0.5mm}
\multiput(0,0)(0,6){2}{\line(1,0){35}}
\multiput(0,0)(0,6){2}{\line(1,0){35}}
\put(0,0){\line(0,1){6}}

\thicklines
\multiput(3,3)(5,0){3}{\circle{5}}
\put(29,3){\circle{5}}

\thinlines
\put(29,3){\vector(-1,0){7}}
\put(29,3){\vector(1,0){7}}

\end{picture}
\ec}
%\caption{Fig.10a}
%\end{figure}
%                      I________________
%                      Iоооо     <--о-->
%                      I----------------

\ul{Определение}: Очередь --- линейный список, в  котором
все включения производятся на одном конце, а исключения  ---  на
другом.

Примером является любая очередь, если не  разрешено
новые элементы вставлять и исключать из середины.
%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(55,7)

\linethickness{0.5mm}
\multiput(0,0)(0,6){2}{\line(1,0){50}}
\multiput(0,0)(0,6){2}{\line(1,0){50}}

\thicklines
\multiput(20,3)(5,0){3}{\circle{5}}
\put(3,3){\circle{5}}
\put(43,3){\circle{5}}

\thinlines
\put(3,3){\vector(1,0){7}}
\put(43,3){\vector(1,0){7}}

\end{picture}
\ec}
%\caption{Fig.10b}
%\end{figure}
%                      __________________
%                      о--->  оооо  --->о
%                      ------------------

\ul{Определение}: Дек --- линейный список, где исключения
и включения производятся с обоих концов.

Пример простой и не  искусственный  привести  трудно,
некоторую аналогию имеет вход и выход из вагона электрички.
%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(68,7)

\linethickness{0.5mm}
\multiput(0,0)(0,6){2}{\line(1,0){65}}
\multiput(0,0)(0,6){2}{\line(1,0){65}}

\thicklines
\multiput(27,3)(5,0){3}{\circle{5}}
\put(7,3){\circle{5}}
\put(57,3){\circle{5}}

\thinlines
\put(7,3){\vector(1,0){7}}
\put(7,3){\vector(-1,0){7}}
\put(57,3){\vector(1,0){7}}
\put(57,3){\vector(-1,0){7}}

\end{picture}
\ec }
%\caption{Fig.10c}
%\end{figure}
%                    ______________________
%                    <--о-->  оооо  <--о-->
%                    ----------------------

   Отметим,  что  над   стеком,   очередью   и   деком   могут
производиться разнообразные  операции,  включая  перечисленные
выше для линейных списков. Однако, из данных определений ясно,
что данные частные случаи линейных списков  ориентированны  на
ситуации, когда в основном производятся операции  включения  и
исключения  элементов.  Специфичность  этих  операций   (место
выполнения) делает более удобным  связное  представление  (см.
выводы в п.~3.2.2),  хотя  последовательное  представление  не
исключено.

   Мы  рекомендуем  использовать   следующий   порядок   связи
элементов.

                          Для стека:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(140,15)

\thicklines
\put(0,6){\vector(1,0){5}}
\put(5,7){\vector(-1,0){5}}

\thinlines
\put(0,1.5){\makebox(0,0)[l]{p}}
\put(3,2){\vector(1,0){5}}

\multiput(8,4)(22,0){2}{\line(0,-1){4}}
\multiput(8,4)(22,0){2}{\framebox(14,5)[l]{ }}
\multiput(15,4)(22,0){2}{\line(0,1){5}}
\multiput(19,6)(22,0){2}{\circle*{1}}
\multiput(19,6)(22,0){2}{\line(0,-1){4}}
\multiput(19,2)(22,0){2}{\vector(1,0){11}}
\put(8,10){{x(n)}}
\put(30,10){{x(n-1)}}

\multiput(54,6)(1,0){3}{\circle*{0.5}}

\multiput(65,4)(22,0){3}{\line(0,-1){4}}
\multiput(65,4)(22,0){3}{\framebox(14,5)[l]{ }}
\multiput(72,4)(22,0){3}{\line(0,1){5}}
\multiput(76,6)(22,0){3}{\circle*{1}}
\multiput(76,6)(22,0){3}{\line(0,-1){4}}
\multiput(76,2)(22,0){3}{\vector(1,0){11}}
\put(65,10){{x(3)}}
\put(87,10){{x(2)}}
\put(109,10){{x(1)}}

\put(132,2.5){\makebox(0,0)[l]{nil}}

\end{picture}
\ec }
%\caption{Fig.11}
%\end{figure}
%     _________   _________   _________
%     I x I   I   I x I   I   I x I   I
%<--->I___I___I   I___I___I   I___I___I ....
%p--->!     I__-->!     I__-->!     I__-->
%
%                 _________   _________   _________
%                 I x I   I   I x I   I   I x I   I
%            .... I___I___I   I___I___I   I___I___I
%                 !     I__-->!     I__-->!     I__-->NIL
%
где {\rm p} --- переменная ссылочного типа, в которой  хранится  адрес
верхнего элемента стека, {\rm x} ---  данные  в  списке.  Включение  и
исключение  элементов   производится   со   стороны   верхнего
элемента, при помощи операторов:\\
          (включение) {\rm NEW(s);  s@.link:= p;  p:= s} \\
          (исключение) {\rm s:= p;  p:= p@.link;  DISPOSE (s)}

                       Для очереди\footnote{\yr
Отметим обратное направление связи элементов в очереди по
сравнению со стеком, что определяется  изменением  направления
"стока" элементов.}:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(156,13)

\thicklines
\put(0,6){\vector(1,0){5}}

\thinlines
\put(0,1.5){\makebox(0,0)[l]{pn}}
\put(5,2){\vector(1,0){5}}

\multiput(10,4)(22,0){3}{\line(0,-1){4}}
\multiput(10,4)(22,0){3}{\framebox(14,5)[l]{ }}
\multiput(17,4)(22,0){3}{\line(0,1){5}}
\multiput(21,7)(22,0){3}{\circle*{1}}
\multiput(43,7)(22,0){2}{\line(0,1){3}}
\multiput(43,10)(22,0){2}{\line(-1,0){15}}
\multiput(28,10)(22,0){3}{\line(0,-1){8}}
\multiput(28,2)(22,0){3}{\vector(-1,0){18}}

\put(21,7){\line(0,1){4}}
\put(21,11){\vector(-1,0){7}}
\put(13,11.5){\makebox(0,0)[r]{nil}}

\put(72,10){\line(1,0){3}}
\multiput(77,10)(1,0){3}{\circle*{0.3}}

\multiput(77,6)(1,0){3}{\circle*{0.3}}

\multiput(87,10)(1,0){3}{\circle*{0.3}}

\multiput(83,4)(22,0){3}{\line(0,-1){4}}
\multiput(83,4)(22,0){3}{\framebox(14,5)[l]{ }}
\multiput(90,4)(22,0){3}{\line(0,1){5}}
\multiput(94,7)(22,0){3}{\circle*{1}}
\multiput(116,7)(22,0){2}{\line(0,1){3}}
\multiput(116,10)(22,0){2}{\line(-1,0){15}}
\multiput(101,10)(22,0){2}{\line(0,-1){8}}
\multiput(101,2)(22,0){2}{\vector(-1,0){18}}

\put(94,7){\line(0,1){3}}
\put(94,10){\line(-1,0){3}}
\put(143,2){\vector(-1,0){16}}
\put(145,2){\makebox(0,0){p1}}

\thicklines
\put(146,6){\vector(1,0){5}}

\end{picture}
\ec }
%\caption{Fig.12}
%\end{figure}
%   NIL<---__    __________    __________
%     ______!__  I  ______!__  I  ______!__
%     I x I   I  I  I x I   I  I  I x I   I
% --> I___I___I  I  I___I___I  I  I___I___I ....
%pn-->!<-----____I  !<-----____I  !<-----___
%
%        ________    __________    __________
%         ______!__  I  ______!__  I  ______!__
%         I x I   I  I  I x I   I  I  I x I   I
%    .... I___I___I  I  I___I___I  I  I___I___I --->
%         !<-----____I  !<-----____I  !<-----___p1
где в переменных ссылочного типа {\rm p1} и {\rm pn} будем хранить  адреса
соответственно  первого   и   последнего   элемента   очереди.

Включение (со стороны последнего элемента)  и  исключение  (со
стороны первого) производится следующим образом: \\
           (включение) {\rm  NEW (s);  s@.link:= pn;  pn:= s} \\
         (исключение) {\rm s:= p1;  p1:= p1@.link;  DISPOSE (s)}  \\

                          Для дека:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(156,13)

\thicklines
\put(0,7){\vector(1,0){5}}
\put(5,6){\vector(-1,0){5}}

\thinlines
\put(0,1.5){\makebox(0,0)[l]{pl}}
\put(5,2){\vector(1,0){5}}

\put(10,4){\line(0,-1){4}}
\put(10,4){\framebox(21,5)[l]{ }}
\put(17,4){\line(0,1){5}}
\put(24,4){\line(0,1){5}}
\put(21,7){\circle*{1}}
\put(50,7){\line(0,1){3}}
\put(50,10){\line(-1,0){15}}
\put(35,10){\line(0,-1){8}}
\put(35,2){\vector(-1,0){25}}
\put(28,7){\circle*{1}}
\put(28,7){\line(0,-1){4}}
\put(28,3){\vector(1,0){11}}

\put(39,4){\line(0,-1){4}}
\put(39,4){\framebox(21,5)[l]{ }}
\put(46,4){\line(0,1){5}}
\put(53,4){\line(0,1){5}}
\put(50,7){\circle*{1}}
\put(69,10){\line(-1,0){5}}
\put(64,10){\line(0,-1){8}}
\put(64,2){\vector(-1,0){25}}
\put(57,7){\circle*{1}}
\put(57,7){\line(0,-1){4}}
\put(57,3){\line(1,0){10}}

\put(21,7){\line(0,1){4}}
\put(21,11){\vector(-1,0){7}}
\put(13,11.5){\makebox(0,0)[r]{nil}}

\multiput(70,10)(1,0){3}{\circle*{0.3}}
\multiput(88,10)(1,0){3}{\circle*{0.3}}

\multiput(75,6)(1,0){3}{\circle*{0.3}}

\multiput(68,3)(1,0){3}{\circle*{0.3}}
\multiput(77,3)(1,0){3}{\circle*{0.3}}

\put(80,3){\vector(1,0){5}}
\put(85,4){\line(0,-1){4}}
\put(85,4){\framebox(21,5)[l]{ }}
\put(92,4){\line(0,1){5}}
\put(99,4){\line(0,1){5}}
\put(96,7){\circle*{1}}
\put(96,7){\line(0,1){3}}
\put(96,10){\line(-1,0){5}}
\put(110,10){\line(0,-1){8}}
\put(110,2){\vector(-1,0){25}}
\put(103,7){\circle*{1}}
\put(103,7){\line(0,-1){4}}
\put(103,3){\vector(1,0){11}}

\put(114,4){\line(0,-1){4}}
\put(114,4){\framebox(21,5)[l]{ }}
\put(121,4){\line(0,1){5}}
\put(128,4){\line(0,1){5}}
\put(125,7){\circle*{1}}
\put(125,7){\line(0,1){3}}
\put(125,10){\line(-1,0){15}}

% \put(154,7){\line(0,1){3}}
% \put(154,10){\line(-1,0){15}}

\put(139,10){\line(0,-1){8}}
\put(139,2){\vector(-1,0){25}}
\put(139,10){\line(1,0){3}}
\put(145,10){\makebox(0,0){pr}}

\put(132,7){\circle*{1}}
\put(132,7){\line(0,-1){4}}
\put(132,3){\vector(1,0){11}}
\put(146,3){\makebox(0,0){nil}}

\thicklines
\put(148,6){\vector(1,0){5}}
\put(153,7){\vector(-1,0){5}}
\end{picture}
\ec }
%\caption{Fig.13}
%\end{figure}
%                   __________       ___________
%     _____________ I  ______!______ I   ______!______
%<--> I x I   I   I I  I x I   I   I I   I x I   I   I
%     I___I___I___I I  I___I___I___I I   I___I___I___I ....
%pl-->!<---_    I__-+->!<---_    I__-+-->!<-----________
%          I________I       I________I
%
%                   __________       ___________
%     _____________ I  ______!______ I   ______!______
%     I x I   I   I I  I x I   I   I I   I x I   I   I <-->
%.... I___I___I___I I  I___I___I___I I   I___I___I___I
%     !<---_    I__-+->!<---_    I__-+-->!<-_      I__-->NIL
%          I________I       I________I      I__--pr
где {\rm pl} и {\rm pr} --- ссылки на левый и  правый  конец  дека,  и
  т.к.~исключение и включение элементов возможно с обоих  концов,  то
приходится некоторым  образом  совместить  стек  и  очередь,
создавая так называемый 'двухсвязный' линейный список.

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

   Иная ситуация, когда программа работает в режиме  реального
времени. Часто здесь возникает необходимость  образовывать  из
объектов линейный список, причем так,  что  прибывший  первым
элемент уходил бы (обрабатывался) тоже  первым.  Этот  принцип
реализуется в очереди (в  стеке  правило  ---  первым  пришел  и
последним ушел).

   Т.о.~при работе  с  данными  большого  объема,  а  также  в
трансляторах,  текстовых  редакторах  и   во   многих   других
программных средствах используются стеки.

   Для функционирующей в реальном времени системной программы,
управляющей процессом обработки программ пользователей ЭВМ  (и
называемой операционной системой), создаются очереди:  очередь
заданий  для  выполнения  их  центральным   процессором   ЭВМ,
выходные очереди данных и т.п.

   Дек используется значительно реже, чем очередь и стеки.


\section{\yr Рекурсивный способ работы со списками}

   При работе со списками (с линейными в  меньшей  степени,  с
нелинейными  ---   в   большей)   оказывается   эффективным
%(в программировании)
использование  рекурсии.  Поясним,  что  это
означает. Отметим сначала, что  в  математике  довольно  часто
встречаются  рекуррентные  соотношения  последовательностей  и
функций.  Например,  функция  факториал   числа   может   быть
определена так:
\begin{equation}
n! = \left\{ \begin{array}{lll}
                    1 & {\yr при} & n=0    \\
                   n (n-1)! & {\yr при} & n>0
              \end{array} \right.   \nonumber
\end{equation}

   В некоторых языках программирования  (в  Паскале  ---  да,  в
Фортране --- нет!) допускается аналогичное действие, называемое
рекурсией и заключающееся в  обращении  подпрограммы  самой  к
себе. Таким образом, подпрограмма --- функция  вычисления  $n$-ого
числа Фибоначчи на языке Паскаль может иметь следующий вид:
\begin{verbatim}
      FUNCTION  Fib (n: INTEGER) : INTEGER;
        BEGIN
         IF  n=0
           THEN  Fib:= 0
           ELSE  IF  n=1
                   THEN  Fib:= 1
                   ELSE  Fib:= Fib(n-1) + Fib(n-2)
        END;
\end{verbatim}

   Отметим последний оператор присваивания,  где  слева  стоит
имя функции, вычисляемой с использованием  этой  же  процедуры-функции(!).

   Рассмотрим, как  будет  работать  данная  подпрограмма  при
таком  обращении  к  ней:  {\rm m:= Fib (4)}.   Начиная,   входим   в
подрограмму {\rm Fib} со значением формального параметра {\rm n} равным 4.
Встрчаем  обращение {\rm Fib (n-1)},  которое  снова  вызывает  нашу
подпрограмму. При этом ЭВМ  запомнит  адрес  точки  возрата  в
подрограмму {\rm Fib}, значения локальных для {\rm Fib} переменных  и  еще
кое-что и переходит снова на начало подпрограммы {\rm Fib},  но  уже
для нового значения {\rm n} $= 4-1 = 3$ и
%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(105,83)

\put(0,30){\framebox(10,15){ }}
\put(2,42){\makebox(0,0)[l]{Fib}}
\put(2,37){\makebox(0,0)[l]{n=4}}
\put(10,40){\vector(1,1){20}}
\put(10,35){\vector(4,-1){20}}

\put(30,45){\framebox(10,15){ }}
\put(32,57){\makebox(0,0)[l]{Fib}}
\put(32,52){\makebox(0,0)[l]{n=3}}
\put(40,55){\vector(1,1){20}}
\put(40,50){\vector(4,1){20}}
\put(30,45){\vector(-4,-1){20}}

\put(30,15){\framebox(10,15){ }}
\put(32,27){\makebox(0,0)[l]{Fib}}
\put(32,22){\makebox(0,0)[l]{n=2}}
\put(40,25){\vector(2,1){20}}
\put(40,20){\vector(4,-1){20}}
\put(30,15){\vector(-1,1){20}}

\put(60,60){\framebox(10,15){ }}
\put(62,72){\makebox(0,0)[l]{Fib}}
\put(62,67){\makebox(0,0)[l]{n=2}}
\put(70,70){\vector(2,1){20}}
\put(70,65){\vector(4,-1){20}}
\put(60,60){\vector(-4,-1){20}}

\put(60,40){\framebox(10,15){ }}
\put(62,52){\makebox(0,0)[l]{Fib}}
\put(62,47){\makebox(0,0)[l]{n=1}}
\put(60,40){\vector(-2,1){20}}

\put(60,20){\framebox(10,15){ }}
\put(62,32){\makebox(0,0)[l]{Fib}}
\put(62,27){\makebox(0,0)[l]{n=1}}
\put(60,20){\vector(-4,1){20}}

\put(60,0){\framebox(10,15){ }}
\put(62,12){\makebox(0,0)[l]{Fib}}
\put(62,7){\makebox(0,0)[l]{n=0}}
\put(60,0){\vector(-1,1){20}}


\put(90,65){\framebox(10,15){ }}
\put(92,77){\makebox(0,0)[l]{Fib}}
\put(92,72){\makebox(0,0)[l]{n=1}}
\put(90,65){\vector(-4,1){20}}

\put(90,45){\framebox(10,15){ }}
\put(92,57){\makebox(0,0)[l]{Fib}}
\put(92,52){\makebox(0,0)[l]{n=0}}
\put(90,45){\vector(-1,1){20}}


\end{picture}
\ec }
%\caption{Fig.14}
%\end{figure}
%                                                      _______
%                                              __----->I Fib I
%                                   _______   /        I n=1 I
%                                _->I Fib I  /         I   . I
%                               /   I n=2 I /          I     I
%                              /    I   ._L/           I   . I
%                   _______   /     I     I<-----------I_____I
%               _-->I Fib I  /      I   ._L________    _______
%              I    I n=3 I /  __---I_____I<--_   I_-->I Fib I
%              I    I   ._L/   I               \       I n=0 I
%              I    I     I<----    _______     \      I   . I
%              I    I   ._L______-->I Fib I      \     I     I
%   _______   /  _--I_____I<----    I n=1 I       \    I   . I
%==>I Fib I  /   I             I    I    .I        I_--I_____I
%   I n=4 I /    I             I    I     I
%   I   ._L/     I             I    I    .I
%   I     I<------             I_---I_____I
%   I   ._L______                   _______
%   I_____I<--_ I              __-->I Fib I
%             I I   _______   /     I n=1 I
%             I I_->I Fib I  /      I   . I
%             I     I n=2 I /       I     I
%             I     I   ._L/        I   . I
%             I     I     I<--------I_____I
%             I     I   ._L_____    _______
%             I__---I_____I<--- \_->I Fib I
%                             I     I n=0 I
%                             I     I   . I
%                             I     I     I
%                             I     I   . I
%                             I__---I_____I
и т.д. до {\rm n=1}. К этому моменту в памяти машине будет  записано
три точки возврата, три варианта значений локальных  переменных,
при которых произошло следующее обращение к {\rm Fib}, и еще  кое-что
тоже три раза (отметим, кстати,  что  операционная  система  при
орбаботке рекурсивной программы будет использовать стеки!).

   При {\rm n=1} подпрограмма-функция вычислит свое  значение  {\rm Fib}
без  нового  обращения  к  самой  себе  (т.к.  {\rm Fib(1) = 1})
возращается в третью точку возрата {\rm (n=2)}, после чего,  продолжив
оператор  сложения  {\rm (Fib(n-1) + Fib(n-2))},   произойдет   снова
обращение к {\rm Fib} (на третьем уровне вложения) с {\rm n=0}. Выйдя  из  этого
обращения  (т.к.  {\rm Fib(0) = 1}),   мы   произведем   сложение
{\rm Fib(1) + Fib(0)} и получим значение функции {\rm Fib} при {\rm n=2} и
выйдем из {\rm Fib} для {\rm n=2} и т.д., как это показано на рисунке.

   Из рассмотренного примера становятся ясными преимущества  и
недостатки    рекурсивного    способа    программирования.
Положительный момент состоит в  том,  что  программа  адекватно
отражает   алгоритм   решения   задачи    при    существовании
рекуррентных формул. И поэтому она проста  и,  как  следствие,
менее подвержена возможному привнесению программистом  ошибок.
Отрицательный момент в том, что при  большом  числе  обращений
подпрограммы самой к себе (большой так  называемая  'глубине  рекурсии')
может   происходить   неоправданное    и    очень    серьезное
(экспоненциальное!) увеличение затрат памяти  ЭВМ  и  времени
счета.

   Альтернативой рекурсии является итерация. Понятие  итерации
встречается достаточно часто и  определять  его,  по-видимому,
нет необходимости. Поясним лишь на  примере  вычисления  чисел
Фибоначчи:
\begin{verbatim}
        FUNCTION  Fib2 (m: INTEGER) : INTEGER;
          VAR  i, i1, i2, io: INTEGER;
          BEGIN
            IF  m=0
              THEN  Fib:= 0
              ELSE
                IF  m=1
                  THEN  Fib2:= 1
                  ELSE
                    BEGIN
                      i:= 1;  i1:= 1;  i2:= 0;
                      WHILE  i<m  DO
                        BEGIN
                          io:= i1 + i2;
                          Fib2:= io;
                          i2:= i1;  i1:= io;
                          i:= i + 1
                        END  (* while *)
                    END  (* else *)
          END;
\end{verbatim}

   Здесь  при  $m\geq{2}$  в  цикле  {\rm WHILE}  ровно  $m-2$  раза   будет
применятся рекуррентная  формула.  В  отличие  от  рекурсивной
подпрограммы, вычисления в {\rm Fib2} будут начинаться с  вычисления
первых членов последовательности  чисел  Фибоначчи,  т.е.~для
$i =$ 1, 2, 3 и т.д. до $m$. При этом  в  переменных  {\rm iо, i1} и {\rm i2}
будут запоминаться значения чисел {\rm Fib(i), Fib(i-1)} и {\rm Fib(i-2)}.

   Отметим, что итерационная версия {\rm (Fib2)} несколько сложнее и
существенно менее наглядна, чем рекурсивная {\rm Fib}.

   Однако ответ на общий вопрос --- какой из методов  вычислений:
рекурсию или итерацию использовать в том или ином случае?  ---
оказывается несколько неожиданным: рекурсии следует избегать в
тех случаях, когда есть очевидное итеративное решение задачи.

   Этот неблагоприятный для  рекурсии  вывод,  однако  смягчим
замечанием  о  том,  что  достаточно  часто  дать  итеративное
решение очень не просто. Примерами таких случаев являeтся
работа с нелинейными  (в  частности  ветвящимися)  структурами
(см. п.~3.4) или задачи типа  рассмотренной  ниже  "задачи  о
ханойской башне".

   Для  линейных  списков  использование   рекурсии   не   так
эффективно. Рассмотрим, например, операцию поиска  элемента  в
линейном списке. Итеративное решение дано выше.
Рекурсивное для  последовательного  и  связного  представления
выглядит следующим образом\footnote{\yr
Имена переменных использованы те же что и ранее.}:

       последовательное    \hspace{3cm}      связное
\begin{verbatim}
_____________________________I________________________________
                             I
  PROCEDURE                  I    PROCEDURE
    Search (n: INTEGER;      I      Search1 (x: Typeofdata;
            list: Seqrepres  I               ref: Relrepres;
            x: Typeofdata);  I           VAR here: Relrepres);
    VAR  k: INTEGER;         I
  BEGIN                      I    BEGIN
     IF list [k] = x         I      IF ref@.Data = x
       THEN  WRITE (k)       I        THEN s:= ref
       ELSE                  I        ELSE
         IF  k <= N          I          IF  ref@.link <> NIL
           THEN  Search (N,  I            THEN  Search1 (x,
              list, x, k-1)  I                ref@.link, here)
           ELSE WRITE ('no') I            ELSE WRITE ('no')
  END;                       I    END;
                             I
\end{verbatim}
    Обращение :
\begin{verbatim}
k:=1; Search (n, list, x, k);I    Search1 (ref, x, here);
_____________________________I_________________________________
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

   Теперь  рассмотрим  случай,  где  без   рекурсии   обойтись
чрезвычайно затруднительно --- задачу о "ханойской  башне".  Она
формулируется так:

   Согласно  древней  легенде,  в  некотором  храме  находится
бронзовая плита с тремя стержнями. На один из стержней Бог при
сотворении мира нанизал 64 диска разного диаметра  из  чистого
золота так, что наибольший диск находится на бронзовой  плите,
а остальные образуют пирамиду, сужающуюся к верху.

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(123,23)

\thicklines
\put(2,4){\line(1,0){120}}

\thinlines
\put(6,4){\framebox(28,2){ }}
\put(8,6){\framebox(24,2){ }}
\put(10,8){\framebox(20,2){ }}
\put(20,10){\line(0,1){1}}

\multiput(19,12)(1,0){3}{\circle*{0.5}}

\put(20,14){\line(0,-1){1}}
\put(16,14){\framebox(8,2){ }}
\put(18,16){\framebox(4,2){ }}

\put(20,20){\line(0,-1){2}}

\put(60,20){\line(0,-1){16}}

\put(100,20){\line(0,-1){16}}


\end{picture}
\ec }
%\caption{Fig.15}
%\end{figure}
%           _____
%           I_I_I                  I            I
%          . . . .                 I            I
%       ______I______              I            I
%      _I_____I_____I_             I            I
%     _I______I______I_            I            I
%   __I_______I_______I____________I____________I_______
%   I__________________________________________________I

   Работая день и ночь жрецы переносят диски с одного  стержня
на другой по следующим правилам:  диски  можно  перемещать  со
стержня   на   стержень  только  по  одному  и  нельзя  класть
больший диск на меньший. Известно, что когда  жрецы  перенесут
все 64 диска с одного  стержня  на  другой,  используя  третий
стержень, наступит конец света.

   Вопрос:  как  (в  какой  последовательности)  жрецы  должны
переносить диски (любопытно, также, оценить, когда можно ждать
окончания их работы!).

   Решение задачи итерациями отыскать совсем  непросто,  в  то
время как рекурсия дает чрезвычайно короткое (и элегантное!)
решение.  Оно  фактически  состоит  в  необходимости  переноса
пирамиды из $m-1$ диска (кстати, для  $m=2$  перенос  пирамиды  из
$m-1$ диска есть просто перенос диска!).

   Решение этой подзадачи таково:

   1) перенести пирамиду из $m-1$ диска с  иглы {\rm  A}  на  иглу {\rm  C},
     используя иглу {\rm B}.

   2) перенести оставшийся на игле {\rm A} нижний диск на иглу {\rm B}.

   3) перенести пирамиду из $m-1$ диска с иглы {\rm C} на иглу {\rm B}.

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(135,17)

\thicklines
\put(0,4){\line(1,0){56}}

\thinlines
\put(2,4){\framebox(12,2){ }}
\put(4,6){\framebox(8,2){ }}
\put(6,8){\framebox(4,2){ }}
\put(8,12){\line(0,-1){2}}
\put(7.5,14){\makebox(0,0){ A}}

\put(28,12){\line(0,-1){8}}
\put(27.5,14){\makebox(0,0){ B}}

\put(48,12){\line(0,-1){8}}
\put(47.5,14){\makebox(0,0){ C}}


\thicklines
\put(70,4){\line(1,0){56}}
\put(60,8){\vector(1,0){6}}


\thinlines
\put(72,4){\framebox(12,2){ }}
\put(78,12){\line(0,-1){6}}
\put(77.5,14){\makebox(0,0){ A}}

\put(98,12){\line(0,-1){8}}
\put(97.5,14){\makebox(0,0){ B}}

\put(114,4){\framebox(8,2){ }}
\put(116,6){\framebox(4,2){ }}
\put(118,12){\line(0,-1){4}}
\put(117.5,14){\makebox(0,0){ C}}

\thicklines
\put(128,8){\vector(1,0){6}}

\end{picture}


\begin{picture}(135,17)
\thicklines
\put(0,4){\line(1,0){56}}

\thinlines
\put(8,12){\line(0,-1){8}}
\put(7.5,14){\makebox(0,0){ A}}

\put(22,4){\framebox(12,2){ }}
\put(28,12){\line(0,-1){6}}
\put(27.5,14){\makebox(0,0){ B}}

\put(44,4){\framebox(8,2){ }}
\put(46,6){\framebox(4,2){ }}
\put(48,12){\line(0,-1){4}}
\put(47.5,14){\makebox(0,0){ C}}


\thicklines
\put(70,4){\line(1,0){56}}
\put(60,8){\vector(1,0){6}}

\thinlines
\put(78,12){\line(0,-1){8}}
\put(77.5,14){\makebox(0,0){ A}}

\put(92,4){\framebox(12,2){ }}
\put(94,6){\framebox(8,2){ }}
\put(96,8){\framebox(4,2){ }}
\put(98,12){\line(0,-1){2}}
\put(97.5,14){\makebox(0,0){ B}}

\put(118,12){\line(0,-1){8}}
\put(117.5,14){\makebox(0,0){ C}}
\end{picture}
\ec }
%\caption{Fig.16}
%\end{figure}
%     a        b    c   =====>       a        b      c  ===>
%   __I__      I    I                I        I      I
%  _I_I_I_     I    I                I        I    __I__
% _I__I__I_    I    I            ____I____    I   _I_I_I_
%_I___I___I____I____I__         _I___I___I____I___I__I__I_
%I____________________I         I________________________I
%
%=>a      b         c     =====>      a       b       c
%  I      I         I                 I     __I__     I
%  I      I       __I__               I    _I_I_I_    I
%  I  ____I____  _I_I_I_              I   _I__I__I_   I
%__I__I___I___I__I__I__I_         ____I___I___I___I___I_____
%I______________________I         I________________________I

   Нетрудно  написать  рекурсивную  подпрограмму,  реализующую
этот алгоритм\footnote{\yr Данная программа проверена на СМ-4.}:
\begin{verbatim}
   PROGRAM  Han;
     VAR  f: TEXT;  i: INTEGER;
\end{verbatim}
(* процедура переноса башни с $n$-кольцами с {\rm c1} на {\rm c2},
   пользуясь {\rm c3} *)
\begin{verbatim}
     PROCEDURE  Hanoi (n: INTEGER;  c1, c2, c3: CHAR);
       BEGIN
         IF  n <> 0  THEN
           BEGIN
\end{verbatim}
(* переносим башню из $n-1$ кольца с {\rm c1} на {\rm c3}, пользуясь {\rm c2} *)
\begin{verbatim}
             Hanoi (n-1, c1, c3, c2);
\end{verbatim}
(* переносим $n$-ое кольцо на {\rm c2}, т.е. на заданное место *)
\begin{verbatim}
             WRITE (f, 'ring n=', n:2, ' from ', c1, ' to ', c2);
\end{verbatim}
(* переносим башню из $n-1$ кольца с {\rm c3} на {\rm c2},  пользуясь {\rm c1} *)
\begin{verbatim}
             Hanoi (n-1, c3, c2, c1)
           END (* if *)
        END; (* Hanoi *)

      BEGIN
        REWRITE (f, 'Lр:');
        i:= 2;
        Hanoi (i, 'A', 'B', 'C')
      END.
\end{verbatim}

   Работа  данной  программы  приведет  к  тому,   что   будет
напечатано очевидное решение:
           кольцо {\rm n}= 1 перенести с иглы {\rm A} на иглу {\rm C}
           кольцо {\rm n}= 2 перенести с иглы {\rm A} на иглу {\rm B}
           кольцо {\rm n}= 1 перенести с иглы {\rm C} на иглу {\rm B}

   Напомним, что кольца мы  пронумеровали  сверху  вниз,  т.е.~номер 1
   имеет наименьшее кольцо.

   Стоит отметить, что при $n=2$  потребовалось  3  перемещения,
при $n=3$ потребуется уже 7 и т.д. Т.о., число перемещений равно
$2^n-1$. Следовательно, при $n=64$ число перемещений будет  равно
порядка $2^{64}$ или $10^{19}$ и  если  одно  кольцо  переносить  за  1
секунду, то работа потребует около $3\,10^{11}$ лет,  т.е.~ время,
большее возраста  Галактики  и  сравнимое  с  космологическим.
Поэтому пока можно жить спокойно, у жрецов впереди  еще  много
работы.


\section{\yr  Нелинейные  структуры  данных:  деревья  и графы}

   Не вызывает сомнения  тот  факт,  что  возможные  структуры
данных  не  ограничиваются  линейными,  рассмотренными   выше.
Реальные объекты могут потребовать создание достаточно сложных
структур  данных,  например,  при
представлении транспортных схем или сложных  молекул.  В  этих
случаях могут иметь место и такие нетривиальные структуры:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(30,19)

\put(0,0){\circle*{3}}
\put(0,16){\circle*{3}}
\put(24,0){\circle*{3}}
\put(16,8){\circle*{3}}
\put(16,16){\circle*{3}}

\put(0,0){\line(0,1){16}}
\put(0,0){\line(1,0){24}}
\put(0,0){\line(1,1){16}}
\put(0,16){\line(2,-1){16}}
\put(16,16){\line(0,-1){8}}
\put(24,0){\line(-1,1){8}}
\end{picture}
\ec }
%\caption{Fig.17a}
{\rm \bc
\begin{picture}(55,19)

\put(4,0){\circle*{3}}
\put(0,8){\circle*{3}}
\put(4,16){\circle*{3}}
\put(12,16){\circle*{3}}
\put(16,8){\circle*{3}}
\put(12,0){\circle*{3}}

\put(0,8){\line(1,2){4}}
\put(0,8){\line(1,-2){4}}
\put(4,0){\line(1,0){8}}
\put(4,16){\line(1,0){8}}
\put(12,0){\line(1,2){4}}
\put(12,16){\line(1,-2){4}}
\put(16,8){\line(1,0){8}}

\multiput(24,8)(8,0){3}{\circle*{3}}
\multiput(24,8)(8,0){3}{\line(1,0){8}}

\multiput(49,8)(1,0){3}{\circle*{0.5}}

\end{picture}
\ec }
%\caption{Fig.17b}
%\end{figure}
%    о_   о                 о--о
%    I \ / \               /    \
%    I _х__--о            о      о--о--о--о-....
%    I/_____/              \    /
%    о                      о--о

\ul{Определение}: Структуры  данных,  элементы  которых
связаны произвольным образом, будем называть графами.

   Линейные списки --- частный случай графа. Ниже мы  рассмотрим
и  другой  частный  случай  графов   ---   деревья,   являющиеся
нелинейными структурами. Несмотря на  то,  что  принцип  связи
между элементами структуры данных типа дерева легко понять  из
следующего рисунка,
%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(30,23)

\put(0,10){\circle*{2}}
\put(0,10){\line(1,-1){5}}
\put(0,10){\line(1,0){10}}
\put(0,10){\line(1,1){5}}

\put(5,5){\circle*{2}}

\put(5,15){\circle*{2}}
\put(5,15){\line(1,0){5}}
\put(5,15){\line(1,1){5}}
\put(10,20){\circle*{2}}
\put(10,15){\circle*{2}}

\put(10,10){\circle*{2}}
\put(10,10){\line(1,-1){5}}
\put(10,10){\line(1,1){5}}
\put(15,5){\circle*{2}}

\put(15,15){\circle*{2}}
\put(15,15){\line(1,-1){5}}
\put(15,15){\line(1,1){5}}
\put(20,20){\circle*{2}}

\put(20,10){\circle*{2}}
\put(20,10){\line(1,-1){5}}
\put(20,10){\line(1,0){5}}
\put(20,10){\line(1,1){5}}
\put(20,10){\line(0,-1){5}}
\put(25,15){\circle*{2}}
\put(25,10){\circle*{2}}
\put(25,5){\circle*{2}}
\put(20,5){\circle*{2}}
\end{picture}
\ec}
%
%              о         о
%             /         /
%           о<__о  о--о<    о
%          /      /     \  /   о
%        о<-----о<       о<===<
%          \      \        \   о
%           о      о        о
мы дадим строгое, формальное определение.

\ul{Определение}:  Деревом  будем  называть   структуру
данных, объединяющую конечное множество элементов {\rm T}, где {\rm T}
не пусто, так что:

   1) имеется выделенный элемент, называемый корнем;

   2) остальные  элементы  содержатся  в   $m\geq{0}$   попарно   не
     пересекающихся  множествах  {\rm T1, T2, T3, ..., Tm},  каждое   из
     которых является деревом (точнее поддеревом).

   Конечные элементы ветвей деревьев будем называть  листьями,
а остальные --- узлами.

   Отметим важную деталь определения --- использование  рекурсии
(дерево определяется через понятие дерева,  причем  достаточно
элегантно!). Поэтому неудивительно, что многие  операции  над
деревьями   эффективнее    реализуются    при    использовании
рекурсивных алгоритмов.

\ul{Примеры} деревьев:

   ---  генеалогические деревья, строящиеся от субъекта  (корень)
     с указанием двоих родителей, родителей родителей и т.д.;
{\rm \bc
\begin{picture}(20,30)
\put(0,8){\framebox(8,4){}}
\put(8,10){\line(1,-1){5}}
\put(8,10){\line(1,1){5}}

\put(13,3){\framebox(8,4){}}
\put(21,5){\line(1,-1){4}}
\put(21,5){\line(1,1){4}}

\put(13,13){\framebox(8,4){}}
\put(21,15){\line(1,-1){4}}
\put(21,15){\line(1,1){4}}

\multiput(26,19)(1,0){3}{\circle*{0.5}}
\multiput(26,11)(1,0){3}{\circle*{0.5}}
\multiput(26,9)(1,0){3}{\circle*{0.5}}
\multiput(26,1)(1,0){3}{\circle*{0.5}}

\end{picture}
\ec}
%\caption{Fig.17c}
%\end{figure}
%               ___
%               I_I<
%         ___  /
%         I_I <
%              \___
%               I_I<

   --- варианты возможных ходов в шахматах и других играх;

   ---  схема  вычисления  чисел   Фибоначчи   с   использованием
     рекурсивных подпрограмм.

   В первом и третьем  примере  используется  дерево,  имеющее
специальное название, а именно --- бинарное, т.е.~такое дерево, у
которого из каждого узла выходит не более двух ветвей. Ниже мы
в основном будем рассматривать именно этот вид деревьев.

   Как и линейные списки  деревья  могут  быть  реализованы  в
программировании путем  использования  как  последовательного,
так и связного представления.  Отметим,  что  последовательное
представление будет использовать  более  одного  массива.  Так
например бинарное дерево можно  реализовать  при  помощи  трех
массивов:

   1) массив, каждый элемент которого содержит  информацию  об
     одном узле дереве;

   2) массив, $k$-ый элемент которого содержит информцию (индексы
     первого массива) о нахождение левого узла $k$-ого  элемента
     первого массива;

   3) массив,  $k$-ый  элемент  которого  содержит  аналогичную
     информацию,  что  и  второй,  но  о  правом  узле  $k$-ого
     элемента.

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(120,36)

\put(5,1){\shortstack{knot\\  \\a1\\a2\\a3\\a4\\a5\\a6}}
\put(25,1){\shortstack{ left\\ \\2\\4\\5\\0\\0\\0}}
\put(44,1){\shortstack{right\\ \\3\\0\\6\\0\\0\\0}}
\put(0,0){\line(0,1){28}}
\put(19,0){\line(0,1){28}}
\put(38,0){\line(0,1){28}}
\put(57,0){\line(0,1){28}}
\put(0,0){\line(1,0){57}}
\put(0,28){\line(1,0){57}}
\put(0,22){\line(1,0){57}}

\put(100,20){\framebox(10,5){a1}}
\put(105,20){\vector(2,-1){10}}
\put(105,20){\vector(-2,-1){10}}

\put(90,10){\framebox(10,5){a2}}
%\put(95,10){\vector(2,-1){10}}
\put(95,10){\vector(-2,-1){10}}

\put(110,10){\framebox(10,5){a3}}
\put(115,10){\vector(2,-1){10}}
\put(115,10){\vector(-2,-1){10}}

\put(80,0){\framebox(10,5){a4}}
\put(100,0){\framebox(10,5){a5}}
\put(120,0){\framebox(10,5){a6}}

\end{picture}
\ec}
%\caption{Fig.18}
%\end{figure}
%                                              a1
% информ. Об узле I Left I Right I             о
%     a1          I  2   I  3    I      a2 о--/ \---о a(3)
%     a2          I  4   I  0    I        /       / \
%     a3          I  5   I  6    I       /       /   \
%     a4          I  0   I  0    I   a4 о    a5 о     о a6
%.................I......I.......I      ...... / \ ....\  ..

   Связное представление позволяет существенно более адекватно
представить дерево и в дальнейшем мы будем  использовать  лишь
этот вид  представления.  Бинарное  дерево  можно  представить
например так:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(80,21)

\put( 4,4){\framebox(21,5){  }}
\put(11,4){\line(0,1){5}}
\put(18,4){\line(0,1){5}}
\put(13,5){\makebox(0,0)[bl]{a2}}
\put( 4,4){\line(0,-1){3}}

\put(25,12){\vector(1,0){4}}
\put(23,12){\makebox(0,0){L}}
\put(29,14){\framebox(21,5){  }}
\put(36,14){\line(0,1){5}}
\put(43,14){\line(0,1){5}}
\put(38,15){\makebox(0,0)[bl]{a1}}
\put(29,14){\line(0,-1){3}}

\put(32,16){\circle*{1}}
\put(32,16){\line(-1,0){32}}
\put(0,16){\line(0,-1){14}}
\put(0,2){\vector(1,0){4}}

\put(46,16){\circle*{1}}
\put(46,16){\line(0,-1){14}}
\put(46,2){\vector(1,0){8}}

\put(54,4){\framebox(21,5){  }}
\put(61,4){\line(0,1){5}}
\put(68,4){\line(0,1){5}}
\put(63,5){\makebox(0,0)[bl]{a3}}
\put(54,4){\line(0,-1){3}}

\end{picture}
\ec }
%\caption{Fig.19}
%\end{figure}
%                   ______________
% _____-------------I___I_a1_I___I-_
% I            L--->!              I
% I   ______________               I   ______________
% I   I___I_a2_I___I               I   I___I_a3_I___I
% I_->!                            I_->!
%   ...........................................
где каждый узел содержит следующую  информацию:  об  элементах
дерева {\rm (а1, а2, ...)} и ссылки  на  соответствующие  узлы  левого
поддерева и правого поддерева. {\rm L} --- ссылка на корень  двоичного
дерева.

   Для    описания    информации,    по-видимому,    удобно
воспользоваться комбинированным типом (записями), где два поля
ссылочного типа (на эти записи), а одно  или  несколько  полей
отводятся для информации об элементах дерева. Тип  этих  полей
зависит от данных.

   Операции  над  деревьями  выполняются  те  же,  что  и  над
линейными списками, но наиболее важной  из  них  на  этот  раз
становиться частный случай просмотра --- обход дерева\footnote{\yr
В дальнейшем, все операции будут произволится с бинарными
деревьями и в целях краткости термин бинарные будет опущен.}.

\ul{Определение}: Обход дерева ---  такой  его  просмотр,
когда каждый узел дерева анализируется один  (и  только  один)
раз.

   Основную   часть    алгоритма    обхода дерева     удобно
сформулировать в рекурсивном виде:

%\begin{equation}
\hspace{2cm} {\yr обойти дерево} $=$
%\left\{\begin{array}{ll}

\hspace{3cm}  {\yr обойти левое поддерево}

\hspace{3cm}  {\yr проанализировать корень}

\hspace{3cm}  {\yr обойти правое поддерево}
%\end{array} \right.
%\end{equation}

Это так называемый "обратный" порядок обхода, но могут быть  и
другие.

   Покажем работу  алгоритма  на  примере  следующего  дерева,
представляющего некоторое алгебраическое выражение:

{\rm \bc
\begin{picture}(50,36)

\put(30,30){\framebox(10,5){$*$}}
\put(35,30){\vector(2,-1){10}}
\put(35,30){\vector(-2,-1){10}}

\put(20,20){\framebox(10,5){$/$}}
\put(25,20){\vector(2,-1){10}}
\put(25,20){\vector(-2,-1){10}}

\put(40,20){\framebox(10,5){w}}

\put(10,10){\framebox(10,5){x}}
\put(30,10){\framebox(10,5){$+$}}
\put(35,10){\vector(2,-1){10}}
\put(35,10){\vector(-2,-1){10}}

\put(20,0){\framebox(10,5){y}}
\put(40,0){\framebox(10,5){z}}
\end{picture}
\ec}
%                      _________
%                      I   *   I
%                      I_______I
%                  _______/\________
%              ____I____       ____I____
%              I   /   I       I   W   I
%              I_______I       I_______I
%              ____/\_______
%          ____I____   ____I____
%          I   X   I   I   +   I
%          I_______I   I_______I
%                  ________/\_______
%              ____I____       ____I____
%              I   Y   I       I   Z   I
%              I_______I       I_______I

   Если под анализом узла понимать печать узла, то  применение
алгоритма обхода даст выражение:
                       $ (X / (Y + Z)) * W$,
   где скобки означают уровень глубины рекурсии.

   Соответствующая программа на языке паскаль будет иметь вид:

   (*    процедура печати двоичного дерева   *)
\begin{verbatim}
           PROCEDURE  Pr (p: ref);
             BEGIN
               IF  p <> NIL  THEN
                 BEGIN
                   Pr (p@.left);
                   WRITE (f, p@.key: 4);
                   Pr (p@.right)
                 END (* if *)
             END;
\end{verbatim}

   Порядок   работы   этой   процедуры   аналогичен   подробно
рассмотренному нами для рекурсивной процедуры {\rm Fib}, вычисляющей
значения чисел Фибоначчи, и {\rm Hanоi}, решающей задачу о ханойской
башне.

   О других операциях заметим следующее:

   1) просмотр --- поиск элемента аналогичен обходу;

   2) включение нового элемента ---  замену  листа  поддерева
     сделать просто, а  добавление  нового  узла  ---  несколько
     сложнее;

   3) исключение элемента--листа ---  просто, а узла  из  середины ---
     сложно (причем нужно указать специальные правила как  это
     делать!);

   4) объединение деревьев  в  одно, если  включение  корня
     одного из деревьев в качестве листа другого возможно, сделать
     легко;

   5) копирование дерева --- эквивалентно обходу.

   Процесс включение новых листьев проиллюстрируем на  примере
следующей программы построения дерева. Пусть имеется некоторый
стек с целыми числами (грубо говоря файл). Напишем  программу,
строящую такое дерево, что в  левых  поддеревьях  будут  числа
меньшие, чем в корне, а в правом --- большие\footnote{\yr
Подобное  дерево  имеет  специальное  название  ---  дерево поиска.}.
Например  для
последовательности   5, 3, 9, 6, 4, 10   должно   быть    построено
следующее дерево:

%\begin{figure}[h]
%\setlength{\unitlength}{1mm}
{\rm \bc
\begin{picture}(50,36)
\put(25,20){\framebox(10,5){5}}
\put(25,22){\vector(-2,-1){14}}
\put(35,22){\vector(2,-1){14}}

\put(5,10){\framebox(10,5){3}}
\put(15,12){\vector(1,-1){7}}

\put(15,0){\framebox(10,5){4}}

\put(45,10){\framebox(10,5){9}}
\put(55,12){\vector(1,-1){7}}
\put(45,12){\vector(-1,-1){7}}

\put(35,0){\framebox(10,5){6}}
\put(55,0){\framebox(10,5){10}}
\end{picture}
\ec}
%\caption{Fig.20}
%\end{figure}
%                    _________
%        ____--------I___5___I--------____
%    ____I____                       ____I____
%    I___3___I--__               __--I___9___I--__
%            ____I____       ____I____       ____I____
%            I___4___I       I___6___I       I___10__I

Соответствующая программа может быть следующей:

(* программа создания двоичного дерева типа поиск *)
\begin{verbatim}
  PROGRAM  Buildtree;
    TYPE  Rootref = @Ntree;
    Typeofdata = ARRAY [1..3] OF 0..4005;
    Ntree = RECORD  key: INTEGER;
                    data: Typeofdata;
                    right, left: Rootref
            END;
    VAR  newkey: INTEGER;  newdata: Typeofdata;
         newroot: Rootref;  f: Text;
\end{verbatim}
(*    процедура построения дерева   *)
\begin{verbatim}
    PROCEDURE  Build (inkey: INTEGER;  indata: Typeofdata;
                      VAR root: Rootref);
      BEGIN
        IF root = NIL
          THEN
            BEGIN
              NEW (root);
              root@.left:= NIL;  root@.right:= NIL;
              root@.key:= inkey;  root@.data:= indata
            END
          ELSE
           IF  inkey < root.key
             THEN  Build (inkey, indata, root@.left)
             ELSE  Build (inkey, indata, root@.right)
      END; (* Build *)

    BEGIN
      newroot:=NIL; WRITELN ('Input data')
      WHILE  eof (f)  DO
        BEGIN
          READ (newkey, newdata);
          Build (newkey, newdata, newroot)
        END; (* while *)
   (*  Printtree (newroot)  *)
   END.
\end{verbatim}
({\rm input data } $=$ вводите данные)

\medskip
   Напомним, что в результате работы  программы  {\rm Buildtree}  мы
получим дерево, в  котором  в  левых  поддеревьях  будут  узлы
(записи) со значениями в поле {\rm key} меньшими,  чем  в  поле  {\rm key}
подкорня, а в  правых  ---  больше.  Отметим,  что  если  теперь
включить в эту программу подпрограмму {\rm Printtree} и обратиться к
ней, как показано в комментарии, то будут напечатаны  введенные
числа,  но  уже  упорядоченные  в  порядке  возрастания  (т.е.
3, 4, 5, 6, 9, 10).  Методы  сортировки,  основанные  на   подобном
алгоритме,   оказываются   достаточно    эффективными,    хотя
существует и более быстрый способ сортировки.

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{\yb Структуры и типы данных в работе}

\section{\yr Игровые задачи}

   Игровые задачи  являются  типичными  представителями  задач
нечислового программирования. Отметим, что  обычно  программы,
моделирующие игры, являются диалоговыми  системами.  Причем  в
отличие от других диалоговых  программ,  игровые  имеют  часто
простую формулировку условий при широком диапазоне сложности.

   Например, при создании программы игры в  шахматы  возникает
вопрос о создании искусственного интелекта, а игра в  "теннис"
требует усилий лишь при программировании графики.

   Это, а также занимательность  игровых  программ  делает  их
удобной   иллюстрацией   при   изучении   задач    нечислового
программирования.

   В качестве примера игровой  задачи  мы  рассмотрим  простую
программу, моделирующую игру в "орлянку".


\section{\yr Моделирование игры в "орлянку"}

\subsection{\yr Условие задачи}

   В игре участвует банкир  и  неопределенное  число  игроков,
которые делают ставки  на  "орел"  ("о")  или  "решку"  ("р").
Банкир бросает монету. В случае, если игрок угадал,  на  какую
сторону упадет монета,  ему  выплачивается  сумма  равная  его
удвоенной ставке. В противном случае игрок теряет ставку.


\subsection{\yr Постановка задачи для программиста}

   Программист  переформулирует  задачу   примерно   следующим
образом:

   1) задать некоторое число (сумму денег в банке);

   2) ввести: имя игрока, размер  ставки  и  признак,  на  что
     сделана ставка;

   3) повторить ввод, если играют несколько игроков;

   4) получить одно случайное число (т.е. смоделировать бросок
     монеты);

   5) определить  число  выигравших   игроков   и   произвести
     соответствующий расчет;

   6) если нужно, то вернуться ко второму  пункту  (произвести
     новый ввод), в противном случае - конец работы.

\subsection{\yr  Реализация алгоритма}

   Рассмотрим один из возможных  способов  реализации  данного
алгоритма.

1) Задать сумму денег в банке можно при помощи константы:

\bc{\rm      CONST bank = 1000}\ec

2) Для хранения вводимой информации можно использовать линеный
список,  представленный  связанным  образом.  Каждый   элемент
которого --- запись  с  четырьмя  полями:  имя  игрока,  ставка,
указание на что она сделана  и  ссылка  на  следующий  элемент
линейного списка.

   Для организации такого линейного списка  на  Паскале  можно
определить следующие типы данных (предполагаем,
что имя игрока не может быть более 20 символов):
\begin{verbatim}
       TYPE  References = @Records;
             Records = Record name: Arr;
                              stake: REAL;
                              what: CHAR
                              next: References
                       END;
             Arr = ARRAY [1..20] OF CHAR
\end{verbatim}

3) ввод информации будем производить следующим образом:
\begin{verbatim}
     VAR  ref, last: References;
          yes, answer: CHAR;
     BEGIN
       last:=NIL;
       REPEAT
         NEW (ref);
         WRITELN ('Give your name, count, and point');
         READLN (ref@.name, ref@.stake, ref@.what);
         ref@.next:= last;  last:= ref;
         WRITELN ('more players? (Y/N)');
         READLN (answer);
       UNTIL  answer = 'Y'
\end{verbatim}
({\rm Give your name, count, and point} $=$
сообщите имя, ставку и на что ставите;\\
{\rm more players?} $=$ еще игроки?).

\medskip
4) Моделирование броска монеты может быть произведено  вызовом
функции получения случайного числа в  диапозоне  [0--1].  В
случае, если случайное число $<$0.5,  то  считаем,  что  выпал
"орел". В противном случае --- "решка".

5)  Подсчет  числа  выигравших  и  расчет  со  всеми  игроками
производиться при помощи просмотра созданого  в  п.~3  связного
линейного списка (операция просмотра линейного списка подробно
была рассмотрена в предыдущей главе).

6) Для продолжения игры необходимо организовать  внешний  цикл
при помощи операторов {\rm REPEAT .... UNTIL} $<$условие$>$,
или  {\rm WHILE} $<$условие$>$ {\rm DO} ...
Условие  окончания  цикла  должно  быть
организовано, аналогично условию окончания в п.~3.

   Подчеркнем, что использование связного линейного списка для
хранения   ставок   в   данной   задаче   несколько    удобнее
использования массива, т.к.~наперед неизвестно число играющих.

   В случае же, например, игры в рулетку, где число  возможных
ставок одним игроком велико и число играющих  обычно  тоже  не
мало,  преимущества   использования   связного   представления
становятся ощутимыми.

   Отметим, что  данные  случаи  подпадают  под  отмеченные  в
резюме к п.~3.2.3  и  мы  очень  рекомендуем  снова
прочитать данное резюме.


%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{\yb Заключение}

   Поздравляем  читателей,  дочитавших  до  этого  пункта.  Вы
теперь можете относительно квалифицированно подойти к  решению
даже таких задач как моделирование искусственного интелекта, и
мы желаем вам всяческих удач.

   Что касается не дочитавших до конца, то можно начать читать
снова, а можно и бросить. Но в любом случае мы думаем,  что  у
вас осталось какое-то представление о том, из чего  состоят  и
что  лежит  в  основе  задач  "нечислового  программирования",
перечисленных во Введении.

%%%%%%%%%%%%%%%%%%%%%%%
\chapter{\yb Литература}

\medskip
   1. К.Йенсен, Н.Вирт "Паскаль." М.: Финансы и статистика. 1982\\
(второе  русское  издание  по   третьему  английскому
К.Йенсен, Н.Вирт "Паскаль. Руководство для пользователя."  М.:
Финансы и статистика,  1989 ---  на  наш  взгляд  несколько  хуже
первого).

   Стандартное и  наиболее  удачное  описание  языка  паскаль,
которое мы брали за основу при написании Главы  2  может  быть
заменено любым из имеющихся в настоящий момент большого  числа
учебников по  паскалю.  Среди  них  может  быть  рекомендована
(небольшая по обьему, но изданная относительно большим тиражем
(300 000  экз.))  брошюра:  Абрамов  С.А.,  Зима  Е.В.  Начала
программирования на языке паскаль" - М.:, Наука, 1987.

\medskip
   2. Н.Вирт "Алгоритмы + структура  данных  =  программы." М.: Mир., 1985 \\
     (второе  русское  издание:  Н.Вирт  "Алгоритмы  и
структуры   данных."  М.:  Мир,   1989    написано    для
"паскалеобразного" языка Модула-2).

   Содержит   несколько   подробных   иллюстраций   применения
различных структур  данных  при  программировании,  включающих
задачи  сортировки  и  оканчивающихся  подробным   обсуждением
создания  транслятора  для  языка  {\rm PL/0}.   Рекомендуется   для
дальнейшего чтения.

\medskip
   3. В.Б.Титов нечисловое программирование в задачах небесной
механики. Труды АО ЛГУ, Л., 1987.

   Дано краткое описание  большого  числа  структур  данных  и
конкретные  примеры  их  использования  в  небесной  механике.
Идеология именно этой статьи лежит в основе Главы 3.

\medskip
   4. Р.Форсайт "Паскаль для всех". М.: Машиностроение, 1986.

   Содержит  описание  языка  Паскаль  и  подробно   разобрано
несколько задач нечисловго программирования (среди них имеются
игровые задачи). Рекомендуется для дальнейшего чтения.


\end{document}



