Фундаментальные структуры данных

При решении разнообразных прикладных задач программирования часто возникает необходимость агрегирования элементов простейших скалярных, а в общем случае и объектных типов данных в единые информационные структуры. Обработка данных в таких структурах проще формализуема на основе различных типовых алгоритмов и, кроме того, с помощью агрегированных структур данных в программе могут быть представлены разнообразные комплексные информационные сущности, моделирующие объекты и отношения реального мира.

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

Массив (array) является базовой структурой данных во всех ЯП, которая поддерживается на уровне встроенных примитивов. Массив является в общем случае линейной и статической структурой данных, которая может быть представлена как последовательность ячеек памяти, с которыми ассоциировано одинаковое имя и сопоставлен одинаковый тип данных. Для ссылки на одну из ячеек такой структуры необходимо указать имя массива и номер соответствующей ячейки. Такой номер называется индексом (index) элемента массива.

Основным назначением такой структуры данных, как массив в ЯП является то, что с помощью массивов в значительной степени упрощается обработка потоков данных в программе, код программы делается более компактным, а большинство операций над данными структурированными в виде массива формализуются в виде циклических алгоритмов.

Каждый массив имеет определенную верхнюю и нижнюю границы (high and low bounds), и элементы массива находятся в этих четко заданных границах. Во всех ЯП пространство памяти под массив выделяется при его определении, даже если он не содержит ни одного элемента. В этом и проявляется статичная природа массива, делая его в некоторых случаях непригодным для решения задач связанных с обработкой больших объемов данных переменной длины. Однако массив идеально подходит для работы с данными небольшой и фиксированной длины.

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

Массивы в VB

В VB имеется два типа массивов: статические массивы (fixed-size arrays) и динамические массивы (dynamic arrays). Статические массивы содержат всегда одинаковое число элементов, тогда как для динамических массивов есть возможность изменить число элементов во время исполнения программы.

Массивы также как и обычные переменные в VB могут быть объявлены тремя способами в зависимости от области видимости:

• открытые массивы (public), которые используют оператор PUBLIC в определении в разделе объявлений модуля (до определения подпрограмм модуля);

• массивы уровня модуля, которые используют оператор PRIVATE при их объявлении в модуле;

• локальные массивы, которые объявлены в области видимости подпрограммы с помощью оператора DIM.

При объявлении массива, вслед за именем массива указывается верхняя граница массива, она может лежать в диапазоне соответствующему типу Long (-2147483648 … 2147483647). Например:

Dim Counters(14) As Integer ' 15 элементов

Dim Sums(20) As Double  ' 21 элемент

По умолчанию нижняя граница массива в VB равна нулю, поэтому число элементов массива определяется как значение верхней границы плюс один элемент. При объявлении массивов в области видимости модуля оператор DIM заменяется на PUBLIC или PRIVATE.

Для явного задания индекса нижней границы используется ключевое слово TO в объявлении:

Dim Counters (1 To 15) As Integer ' 15 элементов

Dim Sums (100 To 120) As String     ' 21 элемент

Массивы могут быть не только одномерные, но и многомерные. Для задания многомерного массива необходимо указать список верхних границ, каждой из размерностей. Например, объявление локального статического двумерного массива с размерностью 10 ´ 10 выглядит следующим образом:

Static MatrixA (9, 9) As Double

Также как и для одномерного массива, здесь также могут быть заданы в явном виде нижние границы для каждой из размерностей:

Static MatrixA (1 To 10, 1 To 10) As Double

Общее число элементов такого массива определяется произведением числа элементов в каждой размерности, т.е. в последнем примере массив будет иметь 100 элементов. 

В VB возможно задание значения по умолчанию нижней границы массива с помощью оператора OPTION BASE:

Option Base 0

Option Base 1

Его использование возможно на уровне модуля, при этом массивы объявленные в подпрограммах этого модуля принимают установленное значение по умолчанию. Явное указание нижней границы размерности массива с помощью оператора TO перекрывает действие оператора OPTION BASE.

Наряду с выше перечисленными операторами для работы с массивами в VB имеется ряд вспомогательных функций.

Для определения нижней и верхней границ ранее объявленного массива в арсенале средств VB имеет две функции LBound и UBound, которые возвращают наименьший и наибольший возможные индексы для размерности массива:

Option Base1 ' Устанавливаем по умолчанию нижнюю границу в 1

DimLower as Long,Upper as Long

DimMyArray(20), TwoDArray(3, 4) ' объявляем массивы

DimZeroArray(0 To 5)             ' перекрываем базу

Lower = LBound(MyArray)           ' возвращает 1.

Lower = LBound(TwoDArray, 2)       ' возвращает 1.

Lower = LBound(ZeroArray)   ' возвращает 0.

Dim A(1 To 100, 0 To 3, -3 To 4)  

Upper = UBound(A, 1)           ' возвращает 100

Upper = UBound(A, 2)                                                   ' возвращает 3

Upper = UBound(A, 3)                                                   ' возвращает 4

Кроме специальных функций в VB имеется особый оператор FOR EACH, который позволяет циклически перебирать элементы массива. На каждом шаге цикла оператор выбирает в заданную вариантную переменную <element> очередной элемент из массива или коллекции <group>:

For Each <element> In <group>

[<statements>]

[Exit For]

[<statements>]

Next [element]

Например:

Dim A(2) As Integer          ' массив из трех элементов

Dim element        ' вариантная переменная

A(0) = 5                 ' инициализируем массив

A(1) = 10

A(2) = 30

For Each element In A

Debug.Print element ' выводим в окно отладки

Next

Для понимания специфики использования массивов в VB, а также особенностей языка в целом, важным является понятие о специальном типе данных, который получил название вариантного типа (variant data type). Как уже отмечалось ранее, этот тип данных в VB определен для реализации возможности автоматического взаимного преобразования объектов различного типа, а также возможности неявного определения переменных при их первом упоминании в программе, то есть фактически для совместимости с ранее разработанными программами в Microsoft QuickBASIC.

Вариантный тип автоматически назначается любой переменной, тип которой не был явно указан в операторах DIM, PRIVATE, PUBLIC или STATIC, а также для переменных, которые используются в программе без явного объявления. Вариантная переменная, также может быть объявлена явно с указанием идентификатора вариантного типа – VARIANT. Например:

DimSomeValue        ' вариантная переменная по молчанию

SomeValue = "17"        ' содержит строчное значение "17"

SomeValue = SomeValue - 15 ' содержит числовое значение 2

SomeValue = "U" & SomeValue ' содержит строку "U2"

Если вариантной переменной еще не было задано какое-либо определенное значение, то по умолчанию с ней ассоциировано специальное значение, которое обозначается в VB идентификатором EMPTY. Для проверки наличия этого значения в вариантной переменной служит логическая функция IsEmpty, возвращающая истинное значение, в случае если вариантная переменная, переданная в качестве фактического параметра содержит такое значение:

Dim z As Variant

If IsEmpty(z) Then

Debug.Print "Вариантная переменная пустая"

Else

Debug.Print z

End If

Вариантная переменная может также содержать другое специальное значение: NULL, которое обычно используется при работе с БД, когда в том или ином поле записи отсутствует значение. Для проверки этого факта в VB имеется функция IsNull:

If IsNull(X) And IsNull(Y) Then

Z = Null

Else

Z = 0

End If

Мощной и интересной является также возможность создания вариантных массивов. Каждый элемент такого массива сам может быть массивом:

DimintX As Integer    ' объявляем счетную переменную

' объявляем и заполняем массив целых чисел

DimcountersA(5) As Integer

ForintX = 0 To 4

countersA(intX) = 5

NextintX

' объявляем и заполняем массив строк

DimcountersB(5) As String

For intX = 0 To 4

countersB(intX) = "hello"   

NextintX

DimarrX(2) As Variant   ' вариантный массив из двух переменных

arrX(1) = countersA() ' назначаем первому элементу countersA

arrX(2) = countersB()   ' назначаем второму элементу countersB

MsgBox arrX(1)(2)     ' выводим на экран число 5

MsgBox arrX(2)(3)       ' выводим на экран строку "hello"

В некоторых случаях при создании программного обеспечения возникают задачи организации линейных или нелинейных структур данных, число элементов которых заранее неизвестно. В VB имеется возможность изменения размера массива по время исполнения программы. Такие массивы, как уже отмечалось, называются динамическими.

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

Динамические массивы создаются также, как и статические только без указания размерности:

DimDynArray() As Integer

Объявление динамического массива, в отличие от статического, не приводит к резервированию физических ячеек памяти для элементов массива. Такая декларация определяет только адрес, с которого будет выделена память под элементы массива. Для распределения же памяти под элементы динамического массива в VB реализован отдельный оператор REDIM:

ReDimDynArray(x + 1)   ' резервируем x + 1 ячейку под массив  

Данный оператор может быть использован только в исполняемой области подпрограммы, так в отличие от декларативных операторов DIM, PUBLIC, PRIVATE и STATIC он является исполняемым операторов. Оператор REDIM может использоваться для изменения нижней и верхней границ статического массива.

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

ReDim PreserveDynArray(UBound(DynArray) + 1)

Важным следствием наличия динамических массивов в VB является возможность передачи в подпрограмму переменного числа аргументов, которые определяются в виде формального параметра являющегося динамическим массивом. Такой параметр начинается с ключевого слова PARAMARRAY:

Function SumEx(ParamArray intNums())

Dim x As Variant

Dim y As Integer

  ' находим сумму элементов динамического массива intNums

   For Each x In intNums

       y = y + x

   Next x

   SumEx = y

End Function

Private SubCallingProc()

' вывод в окно отладки значение 24

Debug.Print SumEx( 1, 3, 5, 7, 8)

End Sub

Как уже отмечалось массив является мощным средством хранения, представления и упорядочения однотипных элементов данных и обеспечивает простые подходы к решению задач обработки информации, представленной на их основе. Рассмотрим типовые задачи, связанные с перебором элементов массива, поиском элементов удовлетворяющих определенному критерию, сортировкой элементов, а также их преобразованием.

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

 задание массива нерегулярными значениями произвольного характера с использованием функции Array, которая возвращает вариантный массив, состоящий из элементов, перечисленных в качестве параметров данной функции:

DimMyWeek, MyDay ' объявляем два варианта 

MyWeek = Array("Пн", "Вт", "Ср", "Чет", "Пят", "Суб", "Вс")

MyDay = MyWeek(2) ' MyDay содержит "Вт"

MyDay = MyWeek(4) ' MyDay содержит "Чет"

или простым перечислением элементов массива 

Dim x (1 To 5) As Integer

x(1) = 11 : x(2) = 123

x(3) = 34 : x(4) = 2

x(5) = 56

        ввода значений пользователем интерактивно в программе, например с помощью средств встроенной в VB функции InputBox:

DimA(10) AsInteger

Fori = 0 To10

A(i) = CInt(InputBox (“Введите элемент массива”, 0))

Nexti

 заданием элементов массива регулярными значениями на основе заданного алгоритма. Например, заполнение массива результатами табуляции математической функции: 

DimC(1 To100) As Double

Fori = 1 ToUBound(C)

x = x + 0.001

C(i) = Sin (x) / Ln(10) + x ^ 2

Nexti

 определение массива в виде последовательности псевдослучайных чисел с помощью функции генерации псевдослучайного числа Rnd

DimA(10) AsInteger

Fori = 0 To10

A(i) = CInt(Rnd * 10 + 1) ‘ от 1 до 10

Nexti

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

‘Массив представляет матрицу из пяти строк и двух столбцов

DimA(1 To 5, 1 To 2) As Double

Dimi as Integer, j As Integer

Fori = 1 toUBound(A, 1)

Forj = 1 toUBound(A, 2)

       A(i, j) = CInt(Rnd * 5 – 10)

Nextj

Nexti

Схема заполнения элементов такого двумерного массива выполняется построчно. На очередном шаге внешнего цикла (счетная переменная i) задается значение номера строки (счетная переменная i). Далее в ходе итераций вложенного цикла перебираются номера столбцов (счетная переменная j), и формируются элементы массива заданной строки.

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

DimS As Integer 

Fori = 1 toUBound(A, 1)

Forj = 1 toUBound(A, 2)

       IfA(i, j) Mod2 <> 0 Then

             S = S + A(i, j)

       End if

Nextj

Nexti

Debug.Print“Сумма = ”; S

В теории программирования огромное число разнообразных задач формализуется на основе преобразования различных массивов. Типичной и весьма распространенной задачей преобразования массива является его сортировка ­– упорядочивание элементов в соответствии с заданным критерием (лексикографический порядок строк, значения чисел). Методы сортировки в линейных структурах данных являются предметом изучения отдельного раздела программирования. В современном программировании существуют большое количество различных по своим характеристикам (временная и пространственная сложность) методов сортировки.

Наиболее простым и интуитивно ясным методом сортировки является так называемый метод пузырьковой сортировки, основная идея которого основана на повторной последовательной перестановке соседних элементов массива. Сущность пузырьковой сортировки легко проиллюстрировать на примере одномерного массива (рис. 14)

Рис. 14. Метод пузырьковой сортировки

В самом примитивном варианте алгоритма предполагается, что элементы массива перебираются n раз, где n – число элементов массива. Тогда как число возможных перестановок элементов в самом наихудшем равно n – 1. Решение задачи сортировки на основе алгоритма пузырьковой сортировки основана на использовании двух вложенных циклов, один из которых (внешний) обеспечивает повторный перебор элементов, а второй (внутренний) – последовательную перестановку соседних элементов в зависимости от критерия сортировки. Ниже приведен исходный текст примера пузырьковой сортировки одномерного целочисленного массива:

Sub BubbleSort()

Dim A(1 To 5) As Integer

A(1) = 5: A(2) = 6: A(3) = 4: A(4) = 3: A(5) = 7

Dim i As Integer, j As Integer, T As Integer

For i = 1 To 5

   For j = 1 To 4

              ' если текущий больше следующего 

       If A(j) > A(j + 1) Then

                       'переставляем их местами

           T = A(j)

           A(j) = A(j + 1)

           A(j + 1) = T

       End If

   Next j

 Next i

For i = 1 To 5

   Debug.Print A(i)

Next i

End Sub

Анализ алгоритма пузырьковой сортировки позволяет заметить, что число шагов перебора элементов не может быть более чем n / 2. Это позволяет оптимизировать данный алгоритм и свести к минимуму число итераций циклов до n²/ 2.

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