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

На рис. 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.
Чтобы построить разреженный массив в Visual Basic, создайте класс для представления элементов массива. В этом случае, каждая ячейка представляет наличие рейсов между двумя городами. Для представления связи, класс должен содержать переменные с индексами городов, которые связаны между собой. Эти индексы, в сущности, дают номера строк и столбцов ячейки. Каждая ячейка также должна содержать указатели на следующую ячейку в строке и столбце.
Следующий код показывает объявление переменных в классе ConnectionCell:

Public FromCity As Integer ' Строка ячейки.
Public ToCity As Integer ' Столбец ячейки.
Public NextInRow As ConnectionCell
Public NextInCol As ConnectionCell

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

Private Sub PrintRow(I As Integer)
Dim cell As ConnectionCell

Set Cell = RowHead(I).Next ' Первый элемент данных.

Do While Not (cell Is Nothing)

Print Format$(cell.FromCity) & " -> " & Format$(cell.ToCity)

Set cell = cell.NextInRow

Loop
End Sub

====74

@Рис. 4.9. Разреженная матрица смежности

Индексирование массива

Нормальное индексирование массива типа A(I, J) не будет работать с такими структурами. Можно облегчить индексирование, написав процедуры, которые извлекают и устанавливают значения элементов массива. Если массив представляет матрицу, могут также понадобиться процедуры для сложения, умножения, и других матричных операций.
Специальное значение NoValue представляет пустой элемент массива.
Процедура, которая извлекает элементы массива, должна возвращать значение
NoValue при попытке получить значение элемента, не содержащегося в массиве.
Аналогично, процедура, которая устанавливает значения элементов, должна удалять ячейку из массива, если ее значение установлено в NoValue.
Значение NoValue должно выбираться в зависимости от природы данных приложения. Для матрицы смежности авиалинии пустые ячейки могут иметь значение False. При этом значение A(I, J) может устанавливаться равным
True, если существует рейс между городами I и J.
Класс SparseArray определяет процедуру get для свойства Value для возвращения значения элемента в массиве. Процедура начинает с первой ячейки в указанной строке и затем перемещается по связному списку ячеек строки.
Как только найдется ячейка с нужным номером столбца, это и будет искомая ячейка. Так как ячейки в списке строки расположены по порядку, процедура может остановиться, если найдется ячейка, номер столбца которой больше искомого.

=====75

Property Get Value(t As Integer, c As Integer) As Variant
Dim cell As SparseArrayCell

Value = NoValue ' Предположим, что мы не найдем элемент.

If r < 1 Or c < 1 Or _ r > NumRows Or c > NumCols _

Then Exit Property

Set cell = RowHead(r).NextInRow ' Пропустить метку.

Do

If cell Is Nothing Then Exit Property ' Не найден.

If cell.Col > c Then Exit Property ' Не найден.

If cell.Col = c Then Exit Do ' Найден.

Set cell = cell.NextInRow
Loop

Value = cell. Data
End Property

Процедура let свойства value присваивает ячейке новое значение. Если новое значение равно NoValue, процедура вызывает для удаления элемента из массива. В противном случае, она ищет требуемое положение элемента в нужной строке. Если элемент уже существует, процедура обновляет его значение.
Иначе, она создает новый элемент и добавляет его к списку строки. Затем она добавляет новый элемент в правильное положение в соответствующем списке столбцов.

Property Let Value (r As Integer, c As Integer, new_value As Variant)
Dim i As Integer
Dim found_it As Boolean
Dim cell As SparseArrayCell
Dim nxt As SparseArrayCell
Dim new_cell As SparseArrayCell

' Если value = MoValue, удалить элемент из массива.

If new_value = NoValue Then

RemoveEntry r, c

Exit Property

End If

' Если нужно, добавить строки.

If r > NumRows Then

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





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