Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
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. Трехмерная прямая звезда
На рис. 4.6 показано представление в виде прямой звезды с рис. 4.4 после добавления одной точки к первому многоугольнику. Элементы, которые были изменены, закрашены серым цветом. Как видно из рисунка, почти все элементы в обоих массивах были изменены.
Нерегулярные связные списки
Другим методом создания нерегулярных массивов является использование связных списков. Каждая ячейка содержит указатель на следующую ячейку на том же уровне иерархии, и указатель на список ячеек на более низком уровне иерархии. Например, ячейка многоугольника может содержать указатель на следующий многоугольник и указатель на ячейку, содержащую координаты первой точки.
Следующий код приводит определения переменных для классов, которые можно использовать для создания связного списка рисунков. Каждый из рисунков содержит связный список многоугольников, каждый из которых содержит связный список точек.
В классе PictureCell:
Dim NextPicture As PictureCell ' Следующий рисунок.
Dim FirstPolygon As PolyfonCell ' Первый многоугольник на этом рисунке.
В классе PolygonCell:
Dim NextPolygon As PolygonCell ' Следующий многоугольник.
Dim FirstPoint As PointCell ' Первая точка в этом многоугольнике.
В классе PointCell:
@Рис. 4.6. Добавление точки к прямой звезде
======72
Dim NextPoint As PointCell ' Следующая точка в этом многоугольнике.
Dim X As Single ' Координаты точки.
Dim Y As Single
Используя эти методы, можно легко добавлять и удалять рисунки, многоугольники или точки в любом месте структуры данных.
Программа Poly на диске содержит связный список многоугольников. Каждый многоугольник содержит связный список точек. Когда вы закрываете форму, ссылка на список многоугольников из формы уничтожается. Это уменьшает счетчик ссылок на верхнюю ячейку многоугольников до нуля. Она уничтожается, поэтому ее ссылки на следующий многоугольник и его первую точку также уничтожаются. Счетчики ссылок на эти ячейки также уменьшаются до нуля, и они тоже уничтожаются. Уничтожение каждой ячейки многоугольника или точки приводит к уничтожению следующей ячейки. Этот процесс продолжается до тех пор, пока все многоугольники и точки не будут уничтожены.
Разреженные массивы
Во многих приложениях требуются большие массивы, которые содержат лишь небольшое число ненулевых элементов. Матрица смежности для авиалиний, например, может содержать 1 в позиции A(I, J) если есть рейс между городами I и J. Многие авиалинии обслуживают сотни городов, но число существующих рейсов намного меньше, чем N2 возможных комбинаций. На рис. 4.8 показана небольшая карта рейсов авиалинии, на которой изображены только 11 существующих рейсов из 100 возможных пар сочетаний городов.
@Рис. 4.7. Программа Poly
====73
@Рис. 4.8. Карта рейсов авиалинии
Можно построить матрицу смежности для этого примера при помощи массива 10 на 10 элементов, но этот массив будет по большей части пустым. Можно избежать потерь памяти, используя для создания разреженного массива указатели. Каждая ячейка содержит указатели на следующий элемент в строке и столбце массива. Это позволяет программе определить положение любого элемента в массиве и обходить элементы в строке или столбце. В зависимости от приложения, может оказаться полезным также добавить обратные указатели. На рис. 4.9 показана разреженная матрица смежности, соответствующая карте рейсов с рис. 4.8.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82
