2.1. Многомерные массивы

Многомерный массив– это массив, элементами которого являются массивы. Массив, элементы которого не являются массивами (обычный массив), называетсяодномерныммассивом. Массив, элементы которого – одномерные массивы, называетсядвумерныммассивом. Вообще, массив, элементы которого являютсяn-мерными массивами, называется(n+1)-мерныммассивом.

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

Прямоугольная матрица	Квадратная матрица	Ступенчатый массив
[[00, 01, 02, 03], [10, 11, 12, 13], [20, 21, 22, 23]]	[[00, 01, 02], [10, 11, 12], [20, 21, 22]]	[[00, 01, 02], [10, 11, 12, 13], [20, 21]]

Если двумерный массив присвоить переменной A, тоA[i]–i-я строка,A[i][j]–j-й элементi-й строки, аj-й столбец – это элементыA[0][j],A[1][j],A[2][j], …. Они не образуют никакого массива.

На рис. 2.11 приведено представление квадратной матрицы в памяти.

Рисунок 2.11. Графическое представление квадратной матрицы.

Ниже с помощью литерала представлен трёхмерный массив – кубразмером 333 (первая цифра элемента массива – номер плоского слоя, вторая – номер строки в слое, третья – номер элемента строки):

[[[000, 001, 002], [010, 011, 012], [020, 021, 022]], //0-й слой

[[100, 101, 102], [110, 111, 112], [120, 121, 122]], //1-й слой

[[200, 201, 202], [210, 211, 212], [220, 221, 222]]] //2-й слой.

Если трёхмерный массив присвоить переменной A, тоA[i]–i-й слой,A[i][j]–j-я строкаi-го слоя,A[i][j][k]–k-й элементj-й строкиi-го слоя. На рис. 2.12 приведено представление этого куба в памяти.

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

Рисунок 2.12. Графическое представление трёхмерной матрицы-куба.

2.2. Рекурсивные структуры объектов

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

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

Списки

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

Т → {info:любой тип, next:Т}│null

В этой формуле указано, что элемент списка должен быть либо объектом с указанными свойствами, либо значением nullв качестве признака отсутствия элемента. Согласно этой формуле, список можно создать с помощью следующего оператора (графическое представление списка на рис 2.13):

List={info:1,next:{info:2,next:{info:3,next:null}}}

Рисунок 2.13. Графическое представление списка.

Тогда оператор alert(List.info) напечатает 1,

alert(List.next.info) напечатает 2,

alert(List.next.next.info) напечатает 3, а

alert(List.next.next.next) напечатает null, а

alert(List.next.next.next.info)выдаст ошибку, так какnull– это признак отсутствия объекта и не имеет никаких свойств.

Выполняя этот оператор присваивания, JavaScriptдействует в следующей последовательности:

1. Начинает создавать первый объект, обрабатывает 1.

2. Начинает создавать второй объект, обрабатывает 2.

3. Создаёт третий объект {info:3, next:null}.

4. Завершает создание второго объекта.

5. Завершает создание первого объекта.

6. Присваивает ссылку на первый объект переменной List.

Можно создать тот же список последовательностью операторов:

List={info:3, next:null};

List={info:2, next:List};

List={info:1, next:List}

Здесь первый оператор создаёт третий объект и список из одного этого элемента. Второй оператор создаёт второй объект и вставляет его в начало списка. Третий оператор создаёт первый объект и также вставляет его в начало списка.

Следующий ниже оператор создаёт новый объект и вставляет его в список после первого элемента (т.е., между первым и вторым):

List.next={info:4,next:List.next}

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

Полученный список обозначим (1, 4, 2, 3).

Удаление первого элемента: List=List.next(переменной присваивается ссылка на второй элемент).

Удаление второго и третьего элемента:

List.next=List.next.next (первому элементу присваивается ссылка на третий элемент).

List.next.next=List.next.next.next (второму элементу присваивается ссылка на четвёртый элемент).

Оператор List.next.next.next=List.nextпревращает список (1, 4, 2, 3) вциклическийсписок (1, 4, 2, 4, 2, 4, 2, 4, 2, …), так как теперь третий элемент (2) ссылается на второй (4), образуяцикл(в графическом представлении списка), из которого нет выхода (на элемент{info:3, next: null}ссылки теперь нет, он пропал из списка).

Рассмотренные списки называются односвязными, так как элементы содержат только одну ссылку – на следующий элемент. Поэтому двигаться по этому списку удобно только в одну сторону. Если в элементы списка включить ещё одно свойствоpredдля ссылки на предыдущий элемент, получитсядвухсвязныйсписок, по которому удобно двигаться в обе стороны (рис. 2.14). В отличие от односвязного списка, одним литералом двухсвязный список записать невозможно.

Рисунок 2.14. Графическое представление двухсвязного списка.