Нелинейные структуры данных
 

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

В данной теме мы с Вами достаточно полно рассмотрим способы построения и представления деревьев и основные операции над ними. Вопросы представления графов и алгоритмы на графах рассмотрим позже.

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

В программировании рекурсии находят двоякое применение — для определения некоторых объектов и при разработке алгоритмов.

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

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

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

Следуя Вирту , скажем, что рекурсивную процедуру Р можно представить как некоторую композицию Р из множества операторов S, не содержащих Р, и самой Р:
Р => P[S,P].

Для того чтобы рекурсивная процедура не привела к не заканчивающимся вычислениям, необходимо наличие в процедуре P некоторого условия В обращения к самой себе. Тогда схему рекурсивной процедуры можно представить так:
Р => if В then P[S,P] или Р => P[S, if В then P].

Использование любой процедуры требует организации связи по управлению и связи по данным между вызывающей процедурой А и вызываемой процедурой В. Связь по управлению обеспечивает передачу управления вызываемой процедуре В и возврат в вызывающую процедуру А после завершения выполнения процедуры В. Вызов процедуры осуществляется посредством оператора вызова по имени вызываемой процедуры.

Связь по данным обеспечивает передачу в вызываемую процедуру фактических параметров и адреса точки возврата в процедуру А, т.е. адреса оператора, следующего за оператором вызова. В качестве фактических параметров могут быть переданы либо значения определенного типа, либо адреса переменных (данных). Адреса переменных передаются тогда, когда в ходе своего выполнения процедура В изменяет значения этих переменных либо когда объем передаваемых данных велик (например, массив данных). Результаты выполнения процедуры В могут быть возвращены в процедуру А несколькими способами:
 1.  возврат значения определенного типа через имя вызываемой процедуры: тип «имя процедуры» (фактические параметры);
 2.  возврат по адресам, переданным фактическими параметрами;
 3.  через глобальные переменные, регистры и т.д.

Конкретные механизмы реализации связи по управлению и связи по данным зависят от системы программирования и операционной системы. Эти механизмы скрыты от программиста, ему доступны лишь оператор вызова — <имя(фактические параметры)>, и оператор возврата — . Наиболее широкое применение находит организация связи с использованием стеков. При вызове процедуры В из процедуры А в стек помещаются фактические параметры (значения или адреса) и адрес точки возврата в вызывающую процедуру А. После этого осуществляется передача управления процедуре В. В процедуре В порождаются ее локальные переменные, место для них также отводится в стеке.

Таким образом, к началу выполнения процедуры В в стеке оказываются фактические параметры, адрес точки возврата и локальные переменные, которые сохраняются там до завершения процедуры В. 1

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

В рекурсивной процедуре (рис.) каждый рекурсивный вызов, естественно, осуществляется с новыми фактическими параметрами, порождается новое множество локальных перемени а адресом возврата является внутренний адрес в самой процедуре ( точка С: на рис.). Таким образом, если будет выполнено n рекурсивных вызовов, то в стеке образуется (n +1) совокупностей данных, причем еще ни одного возврата из курсивной процедуры не будет. Если условие рекурсивного вызова не будет удовлетворяться, то выполняются окончательные вычисления и происходит возврат, причем n возвратов осуществляются во внутреннюю точку рекурсивной процедуры (точку С:), а последний, (n + 1)-й — в процедуру, откуда 6ыла вызвана рекурсивная процедура.

Итак, выполнение рекурсивной процедуры распадается два периода. Сначала (n + 1) раз выполняется часть процедуры от начала до точки рекурсивного вызова, затем столько же раз от точки возврата (точка С:) до конца процедуры. Важно знать, что вторая часть сначала выполняется с данными последнего рекурсивного вызова, затем — предпоследнего и т.д. Последний, (п + 1)-й раз эта часть выполняется с данными, полученными при начальном вызове рекурсивной процедуры. Возврат осуществляется в вызывающую процедуру, ей же возвращаются и результаты.

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

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

Пример.

Рассмотрим процедуру вычисления факториала:
n! = n*(n - 1)*(n - 2)*...*2*1. Очевидно, что n! можно представить в виде n!= n*(n - 1)!, в свою очередь, (n - 1)! можно представить как (n - 1)! = (n-1)*(n - 2)! и т.д., а 0! = 1. Тогда рекурсией функция вычисления факториала на Си может выглядеть так:
 double fact(int n)
{if (n<0) return n; /* Признак ошибки отрицательное число */
    if (n==0) return 1;
      else return (n*fact(n - 1)
}

Проследим, как же выполняется эта функция при задании конкретного значения n, обеспечив вывод значения фактического параметра n в начале функции и значения n*fact(n - 1) после курсивного обращения функции к самой себе: double fact(int n)
  {double f;
    printf (" %d ",n);
    if (n<0) return n;
    if (n==0) return 1;
       else
           {f = n*fact(n- 1);
              printf(“n=%d f=%lf ",n,f);
              return f ;
         }
}

При вычислении 4!, т.е. при обращении к функции fact(4), будут напечатаны:
4 3 2 1 0 n = 1 f = 1.000000е+0001 n = 2 f = 2.000000e+0001
n=3 f = 6.000000е+0001 n = 4 f= 2.400000е+0011

Таким образом, глубина рекурсии равна 5, при каждом обращении к функции с аргументами 4, 3, 2, 1 осуществляется сохранение аргумента, локальной переменной f и адреса точки возврата, после чего происходит рекурсивное обращение к самой себе с аргументом, уменьшенным на единицу. При последнем вызове функции с аргументом 0 значению факториала присваивается 1 и оно возвращается на предыдущий, четвертый уровень. Сохраненное на этом уровне значение n=1 умножается на возвращенное значение 1, полученное значение 1 возвращается на третий уровень с n = 2. Произведение 1*2 = 2 возвращается на второй уровень, где вычисляется 2*3 = 6, на первом уровне получается окончательный результат 4*6 = 24, он и возвращается в основную программу.

Вычисление факториала с использованием не рекурсивной функции гораздо экономнее по времени и по памяти:
double factn(n)
{double f=1;
   if (n<0) return n;     /* Ошибка в параметре */
   if (n==0) return 1;
   for (i=1; i<=n; i + +)
         f = f * i;
         return f; }

В рассмотренных функциях возвращаемые значения имеют тип double, использование long int при n᝼ приводит к ошибкам вычислений из-за переполнения.