Предыдущая страница реферата | 22  23  24  25  26  27  28  29  30  31  32 | Следующая страница реферата

Некоторым программам требуется только половина элементов в двумерном массиве. Предположим, что мы располагаем картой, на которой 10 городов обозначены цифрами от 0 до 9. Можно использовать массив для создания матрицы смежности (adjacency matrix), показывающей наличие автострады между парами городов. Элемент A(I,J) равен True, если между городами I и J есть автострада.
В этом случае, значения в половине матрицы будут дублировать значения в другой ее половине, так как A(I, J)=A(J, I). Также элемент A(I, I) не имеет смысла, так как бессмысленно строить автостраду из города I в тот же самый город. В действительности потребуются только элементы A(I,J) из верхнего левого угла, для которых I > J. Вместо этого можно также использовать элементы из верхнего правого угла. Поскольку эти элементы образуют треугольник, этот тип массивов называется треугольным массивом (triangular array).
На рис. 4.1 показан треугольный массив. Элементы со значащими данными обозначены буквой X, ячейки, соответствующие дублирующимся элементам, оставлены пустыми. Незначащие элементы A(I,I) обозначены тире.
Для небольших массивов потери памяти при использовании обычных двумерных массивов для хранения таких данных не слишком существенны. Если же на карте много городов, потери памяти могут быть велики. Для N городов эти потери составят N*(N-1)/2 дублирующихся элементов и N незначащих диагональных элементов A(I,I). Если карта содержит 1000 городов, в массиве будет более полумиллиона ненужных элементов.

====67

@Рис. 4.1. Треугольный массив

Избежать потерь памяти можно, создав одномерный массив B и упаковав в него значащие элементы из массива A. Разместим элементы в массиве B по строкам, как показано на рис. 4.2. Заметьте, что индексы массивов начинаются с нуля.
Это упрощает последующие уравнения.
Для того, чтобы упростить использование этого представления треугольного массива, можно написать функции для преобразования индексов массивов A и B.
Уравнение для преобразования индекса A(I,J) в B(X) выглядит так:

X = I * (I - 1) / 2 + J ' Для I > J.

Например, для I=2 и J=1 получим X = 2 * (2 - 1) / 2 + 1 = 2. Это значит, что A(2,1) отображается на 2 позицию в массиве B, как показано на рис. 4.2.
Помните, что массивы нумеруются с нуля.
Уравнение остается справедливым только для I > J. Значения других элементов массива A не сохраняются в массиве B, потому что они являются избыточными или незначащими. Если вам нужно получить значение A(I,J) при I < J, вместо этого следует вычислять значение A(J,I).
Уравнения для обратного преобразования B(X) в A(I,J) выглядит так:

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

@Рис. 4.2. Упаковка треугольного массива в одномерном массиве

=====68

Подстановка в эти уравнения X=4 дает I = Int((1 + Sqr(1 + 8 * 4)) / 2) = 3 и J = 4 – 3 * (3 - 1) / 2 = 1. Это означает, что элемент B(4) отображается на позицию A(3,1). Это также соответствует рис. 4.2.
Эти вычисления не слишком просты. Они требуют нескольких умножений и делений, и даже вычисления квадратного корня. Если программе придется выполнять эти функции очень часто, это внесет определенную задержку скорости выполнения. Это пример компромисса между пространством и временем.
Упаковка треугольного массива в одномерный массив экономит память, хранение данных в двумерном массиве требует больше памяти, но экономит время.
Используя эти уравнения, можно написать процедуры Visual Basic для преобразования координат между двумя массивами:

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

If I = J Then ' Незначащий элемент.

X = -1

Exit Sub

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

I = J

J = tmp

End If

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

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
End Sub

Программа Triang использует эти подпрограммы для работы с треугольными массивами. Если вы нажмете на кнопку A to B (Из A в B), программа пометит элементы в массиве A и скопирует эти метки в соответствующие элементы массива B. Если вы нажмете на кнопку B to A (Из B в A), программа пометит элементы в массиве B, и затем скопирует метки в массив A.
Программа Triangc использует класс TriangularArray для работы с треугольным массивом. При старте программы, она записывает в объект TriangularArray строки, представляющие собой элементы массива. Затем она извлекает и выводит на экран элементы массива.

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

Некоторые программы используют треугольные массивы, которые включают диагональные элементы 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. Трехмерная прямая звезда

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.



Предыдущая страница реферата | 22  23  24  25  26  27  28  29  30  31  32 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки