Диагональные элементы

Некоторые программы используют треугольные массивы, которые включают диагональные элементы A(I, I). В этом случае необходимо внести только три изменения в процедуры преобразования индексов. Процедура преобразования AtoB не должна пропускать случаи с I=J, и должна добавлять к I единицу при подсчете индекса массива B.

=====69

Private Sub AtoB(ByVal I As Integer, ByVal J As Integer, X As Integer)

Dim tmp As Integer

If I < J Then ' Поменять местами I и J.

tmp = I

I = J

J = tmp

End If

I = I + 1

X = I * (I - 1) / 2 + J

End Sub

Процедура преобразования BtoA должна вычитать из I единицу перед возвратом значения.

Private Sub BtoA(ByVal X As Integer, I As Integer, J As Integer)

I = Int((1 + Sqr(1 + 8 * X)) / 2)

J = X - I * (I - 1) / 2

I = J - 1

End Sub

Программа Triang2 аналогична программе Triang, но она использует для работы с диагональными элементами в массиве A эти новые функции. Программа TriangC2 аналогична программе TriangC, но использует класс TriangularArray, который включает диагональные элементы.

Нерегулярные массивы

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

Массивы в Visual Basic не могут иметь такие неровные края. Можно было бы использовать массив, достаточно большой для того, чтобы в нем могли поместиться все строки, но при этом в таком массиве было бы множество неиспользуемых ячеек. Например, массив на рис. 4.3 мог бы быть объявлен при помощи оператора Dim Polygons(1 To 3, 1 To 6), и при этом четыре ячейки останутся неиспользованными.

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

@Рис. 4.3. Нерегулярный массив

=====70

Прямая звезда

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

Для упрощения определения в массиве B положения точек, соответствующих каждой строке, в конец массива A можно добавить сигнальную метку, которая указывает на точку сразу за последним элементом в массиве B. Тогда точки, образующие многоугольник I, занимают в массиве B позиции с A(I) до A(I+1)-1. Например, программа может перечислить элементы, образующие строку I, используя следующий код:

For J = A(I) To A(I + 1) - 1

‘ Внести в список элемент I.

:

Next J

Этот метод называется прямой звездой (forward star). На рис. 4.4 показано представление нерегулярного массива с рис. 4.3 в виде прямой звезды. Сигнальная метка закрашена серым цветом.

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

На рис. 4.5 схематически представлена трехмерная структура данных в виде прямой звезды. Две сигнальных метки закрашены серым цветом. Они указывают на одну позицию позади значащих данных в массиве.

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

При использовании структуры данных прямой звезды легко и быстро можно перечислить точки, образующие многоугольник. Так же просто сохранять такие данные на диске и загружать их обратно в память. С другой стороны, обновлять массивы, записанные в формате прямой звезды, очень сложно. Предположим, вы хотите добавить новую точку к первому многоугольнику на рис. 4.4. Для этого понадобится сдвинуть все элементы справа от новой точки на одну позицию, чтобы освободить место для нового элемента. Затем нужно добавить по единице ко всем элементам массива A, которые идут после первого, чтобы учесть сдвиг, вызванный добавлением точки. И, наконец, надо вставить новый элемент. Сходные проблемы возникают при удалении точки из первого многоугольника.

@Рис. 4.4. Представления нерегулярного массива в виде прямой звезды

=====71

@Рис. 4.5. Трехмерная прямая звезда

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