Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Чтобы построить разреженный массив в 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
ReDim Preserve RowHead(1 To r)
' Инициализировать метку для каждой новой строки.
For i = NumRows + 1 To r
Set RowHead(i) = New SparseArrayCell
Next i
End If
' Если нужно, добавить столбцы.
If c > NumCols Then
ReDim Preserve ColHead(1 To c)
' Инициализировать метку для каждой новой строки.
For i = NumCols + 1 To c
Set ColHead(i) = New SparseArrayCell
Next i
NumCols = c
End If
' Попытка найти элемент.
Set cell = RowHead(r)
Set nxt = cell.NextInRow
Do
If nxt Is Nothing Then Exit Do
If nxt.Col >= c Then Exit Do
Set cell = nxt
Set nxt = cell.NextInRow
Loop
' Проверка, найден ли элемент.
If nxt Is Nothing Then
found_it = False
Else
found_it = (nxt.Col = c)
End If
' Если элемент не найден, создать его.
If Not found_it Then
Set new_cell = New SparseArrayCell
' Поместить элемент в список строки.
Set new_cell.NextInRow = nxt
Set cell.NextInRow = new_cell
' Поместить элемент в список столбца.
Set cell = ColHead(c)
Set nxt = cell.NextInCol
Do
If nxt Is Nothing Then Exit Do
If nxt.Col >= c Then Exit Do
Set cell = nxt
Set nxt = cell.NextInRow
Loop
Set new_cell.NextInCol = nxt
Set cell.NextInCol = new_cell
new_cell.Row = r
new_cell.Col = c
' Поместим значение в элемент nxt.
Set nxt = new_cell
End If
' Установим значение.
nxt.Data = new_value
End Property
Программа Sparse, показанная на рис. 4.10, использует классы SparseArray и SparseArrayCell для работы с разреженным массивом. Используя программу, можно устанавливать и извлекать элементы массива. В этой программе значение NoValue равно нулю, поэтому если вы установите значение элемента равным нулю, программа удалит этот элемент из массива.
Очень разреженные массивы
Некоторые массивы содержат так мало непустых элементов, что многие строки и столбцы полностью пусты. В этом случае, лучше хранить заголовки строк и столбцов в связных списках, а не в массивах. Это позволяет программе полностью пропускать пустые строки и столбцы. Заголовки строки и столбцов указывают на связные списки элементов строк и столбцов. На рис. 4.11 показан массив 100 на 100, который содержит всего 7 непустых элементов.
@Рис. 4.10. Программа Sparse
=====76-78
@Рис. 4.11. Очень разреженный массив
Для работы с массивами этого типа можно довольно просто доработать предыдущий код. Большая часть кода остается неизменной, и для элементов массива можно использовать тот же самый класс SparseArray.Тем не менее, вместо хранения меток строк и столбцов в массивах, они записываются в связных списках.
Объекты класса HeaderCell представляют связные списки строк и столбцов. В этом классе определяются переменные, содержащие число строк и столбцов, которые он представляет, сигнальная метка в начале связного списка элементов строк или столбцов, и объект HeaderCell, представляющий следующий заголовок строки или столбца.
Public Number As Integer ' Номер строки или столбца.
Public Sentinel As SparseArrayCell ' Метка для строки или
' столбца.
Public NextHeader As HeaderCell ' Следующая строка или
' столбец.
Например, чтобы обратиться к строке I, нужно вначале просмотреть связный список заголовков HeaderCells строк, пока не найдется заголовок, соответствующий строке I. Затем продолжается работа со строкой I.
Private Sub PrintRow(r As Integer)
Dim row As HeaderCell
Dim cell As SparseArrayCell
' Найти правильный заголовок строки.
Set row = RowHead. NextHeader ' Список первой строки.
Do
If row Is Nothing Then Exit Sub ' Такой строки нет.
If row.Number > r Then Exit Sub ' Такой строки нет.
If row.Number = r Then Exit Do ' Строка найдена.
Set row = row.NextHeader
Loop
' Вывести элементы в строке.
Set cell = row.Sentinel. NextInRow ' Первый элемент в строке.
Do While Not (cell Is Nothing)
Print Format$(cell.FromCity) & " -> " & Format$(cell.ToCity)
Set cell = cell.NextInRow
Loop
End Sub
Резюме
Некоторые программы используют массивы, содержащие только небольшое число значащих элементов. Использование обычных массивов Visual Basic привело бы к большим потерям памяти. Используя треугольные, нерегулярные, разреженные и очень разреженные массивы, вы можете создавать мощные представления массивов, которые требуют намного меньших объемов памяти.
Страницы: 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
