В некоторых языках программирования допускаются массивы, элементы которых снова могут быть массивами и т. д. Подобные структурные образования данных называются вложенными (гнездовыми, вставленными) массивами.
Пример 1. Ниже в первой строке определяется вложенный массив v, а во второй строке выводятся его элементы. В векторе v в фигурных скобках указаны размеры соответствующих элементов-массивов ({строк, столбцов}), а сами элементы приведены справа от v:s := 1..3, vs-1 := identity(s).
Вложенные массивы можно интерпретировать в виде деревьев с корнем, являющимся основным массивом. От него идут дуги к массивам-элементам и т.д. Листьями подобного дерева являются массивы или скаляры, не имеющие ссылок на последующие массивы.
Высотой вложенного массива назовем высоту соответствующего ему дерева (максимум из количества дуг по каждому из путей от корня до листа).
На рисунке 12 указано дерево составного массива, определенного в примере 2.
Пример 2.
w0 := identity(3), w1 := ("no", "yes", w0);
M := (v2, 7, w1)T.
Рис. 12. Схема дерева составного массива M (пример 2)
В связи с вложенными массивами решим следующую задачу.
адача
51. Высота составного массива. Составить
рекурсивную программу-функцию,
подсчитывающую высоту вложенного массива.
Решение. Для единообразия удобно считать векторы длины n двумерными массивами размера n´1. В этом случае нам придется иметь дело только с матрицами или скалярами. Заметим, что для опознания скаляров M в программе можно использовать встроенные функции rows(M) или cols(M), возвращающие для них нуль. Для матриц M rows(M) и cols(M) возвращают соответственно количество строк и столбцов M. С учетом сказанного рекурсивная функция нахождения высоты составного массива могла бы выглядеть так:
Аргументом hei(M) является скаляр или матрица. Если M - скаляр, то hei(M) возвращает - 1. В противном случае первое рекурсивное обращение направляет вычисления по всем дугам дерева, порожденным каждым из элементов M. Углубление на каждый следующий уровень дерева в отложенных вычислениях приводит к увеличению h на 1. Но поскольку начальное значение h=-1, то, в конце концов, h примет значение не количества уровней дерева, а его высоты. В частности, если исходный массив не является вложенным, то есть состоит из скаляров, то h=0.
Контрольные примеры:
A. Для вектора v из примера 1: hei(v)=1;
B. Для матрицы M из примера 2: hei(M)=3.
Замечание. При дополнительных сведениях о вложенных массивах программу hei() можно упростить. Например, если известно, что на любом уровне вложенного массива M элементами могут быть только скаляры или векторы длины 2, то M порождает бинарное дерево и его высота может быть найдена с помощью такой простой рекурсивной функции:
Кстати, сгенерировать случайный вложенный массив со скалярами или векторами длины 2 на всех уровнях, порождающий бинарное дерево, можно по такой рекурсивной программе:
Величина параметра p (0<p<1) вероятностно влияет на высоту формируемого массива. Как правило, чем больше p, тем больше высота массива. Обычно при p³0.7 она уже становится запредельной, то есть бинарное дерево массива сильно разрастается и происходит останов вычислений по переполнению стека рекурсивных вызовов. При первом обращении к tree(p) формируется основной массив (корень дерева). Каждая его компонента генерируется независимо от другой и фактически по одной и той же схеме:
0£rnd(1)<p « создается ссылка вида {2,1}, то есть составной массив;
p£rnd(1)<1 « создается скаляр - 0, то есть ветвь обрывается.
Этот процесс рекурсивно продолжается с каждым из компонентов основного массива и т. д. Необычность такой рекурсии в том, что функция обращается сама к себе с тем же самым значением аргумента, а проблема перемещения по рекурсивным уровням решается не за счет изменения её аргумента, а за счет полученного значения от датчика случайных чисел. Это достаточно типичный случай для "вероятностной" рекурсии.
