4.7.3. Динамические массивы

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

Dim Sigma(0 To 5) As Integer, m(3) As Integer

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

Одно из решений проблемы – выделять память под массив не в начале программы – статически, а после определения его размера – динамически. В качестве размера массива может быть использована переменная, значение которой вычисляется или вводится перед объявлением массива:

РазмерМассива = Выражение или РазмерМассива= Cint(TextBox1.Text)

Dim ИмяМассива(РазмерМассива) As ТипМассива

Другое решение проблемы – разделить в программе объявление массива и определение его размера – выделение памяти под него. Т.е. при объявлении массива в начале программы размер не указывается:

Dim ИмяМассива() As ТипМассива.

Причем значение размерности определяется позже (вычисляется или вводится) непосредственно перед его использованием и тогда для выделения памяти уже объявленному массиву с указанием конкретной размерности массива используется оператор ReDim или ReDim Preserve:

ReDim ИмяМассива (РазмерМассива),

ReDim Preserve ИмяМассива (РазмерМассива).

Таким образом, динамические массивы имеют весьма полезное свойство – их размеры могут изменяться в процессе выполнения программ. При этом, оператор ReDim изменяет размер массива и очищает его (обнуляет его элементы), а оператор ReDim Preserve, изменяет размер массива и сохраняет значения существующих элементов.

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

…

n = n + 1

ReDim Preserve Mas(n)

Mas(n) = n + 4

…

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

Dim Мас( )As String'объявление динамического массива строкового типа

Затем, в момент необходимости реально распределить под него память используется оператор ReDim. Например:

ReDim Мас(9)

' или

ReDim Preserve Мас(9)

Второй вариант используется для изменения размера массива и для сохранения содержимого.

4.7.4. Базовые алгоритмы обработки одномерных массивов

Типичными задачами работы с одномерными массивами являются определение факта наличия в них заданного элемента и отбор элементов, удовлетворяющих определённым условиям. В обоих случаях используется циклическое сравнение элементов массива с заданным образцом. Для определения факта наличия заданного образца в массиве достаточно единственного совпадения, после чего дальнейший просмотр прекращается. Если условие отбора может выполняться для нескольких элементов массива, то необходим просмотр всего массива до конца. Для досрочного прекращения просмотра используется один из циклов по условию или оператор Exit For.

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

Рассмотрим ряд примеров программирования базовых алгоритмов с использованием одномерных массивов.

Пример 4.7.4-1. Написать процедуру-Sub, в которой вводится массив a(6), состоящий из 7 вещественных чисел, и вычисляется произведение ненулевых элементов этого массива.

В процедуре, приведенной на рис. 4.7.4-1, объявлен вещественный массив a(6) с элементами а(0), а(1), ... , а(6). Поочередный ввод элементов массива выполняется в цикле. С помощью процедуры vvodSngMac15( ) на экран выводится запрос с указанием номера вводимого элемента, затем присваиваются вводимые числовые зна­чения соответствующим элементам массива a(6). Вывод на экран значений элементов массива a выполняется процедурой vivodSngMac17( ) также с использованием регулярного цикла.

Sub Pr4741(ByRef z As Single) Dim a(6) As Single Dim i As Integer vvodSngMac15(a) vivodSngMac17(a, ListBox1) z=1 'Вычисление произв.ненулевых элементов For i = 0 To 6 If a(i) <> 0 Then z = z * a(i) Next i vivodSng3(z, TextBox1) End Sub

Рис. 4.7.4-1

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

Если ввод элементов массива будет реализован вне процедуры, то программный код этой процедуры будет таким, как на рис. 4.7.4-2.

Sub Pr4742(ByRef a( ) As Single, ByRef z As Single)

Dim i As Integer

z=1

For i = 0 To UBound(a)

If a(i) <> 0 Then z = z * a(i)

Next i

End Sub

Рис. 4.7.4-2

Тогда событийная процедура, содержащая вызов процедуры Pr4742( ), может иметь следующий вид:

Private Sub Button1_Click(…)

Dim a(6) As Single

Dim z As Single

vvodSngMac15(a)

vivodSngMac17(a, ListBox1)

Pr4742(a, z)

vivodSng3(z, TextBox1)

End Sub

Пример 4.7.4-2. Написать процедуру-Sub, в которой необходимо из двух массивов p и r, каждый из которых состоит из 4-х элементов, получить третий массив v, путем последовательного попарного переписывания в него элементов массивов p и r. При этом элементы массива p(3) вводятся с клавиатуры, а элементы массива r(3) являются случайными числами, равномерно распределенными на отрезке [2;4].

Как и в предыдущем примере, на рис. 4.7.4-3приведены алгоритм и программа решения данной задачи с учетом, что ввод и вывод массивов осуществляется в процедуре, а на рис. 4.7.4-4 процедура без ввода и вывода массивов.

Sub Pr4743(ByRef v( )As Single) Dim p(3), r(3)As Single Dim i, k As Integer vvodSngMac15(p) vvodSngRnd16(r) k =0 For i =0 To UBound(p) v(k)=p(i) v(k+1)=r(i) k=k+2 Next i vivodSngMac17(p, ListBox1) vivodSngMac17(r, ListBox2) vivodSngMac17(v, ListBox3) End Sub

Рис. 4.7.4-3

Sub Pr4744(ByRef p( ) As Single, ByRef r( ) As Single, _

ByRef v( ) As Single)

Dim i, k As Integer

k=0

For i = 0 To UBound(p)

v(k) = p(i) : v(k+1) = r(i) : k=k+2

Next i

End Sub

Рис. 4.7.4-4

Для формирования массива v используется переменная k - но­мер очередного элемента массива v. В цикле одновременно заполняются два элемента массива v: в элемент с номером k переписывается i-й элемент из массива p, а в элемент с но­мером (k+1) переписывается i-й элемент из массива r.

Пример 4.7.4-3. Написать процедуру-Sub, в которой необходимо сформировать массив c(9), содержащий 10 элементов, по следующему пра­вилу:

В сформированном массиве переставить элементы с целыми значениями в начало массива.

Алгоритм и программа решения данной задачи приведены на рис. 4.7.4-5.

Для того, чтобы переписать це­лые элементы в начало массива, в переменной k хранится номер элемента, в который переписывается очередное целое значение. Чтобы определить, является ли очередной элемент массива целым, проведем сравнение разности значения целой части очередного элемента и значения очередного элемента массива c(i) с нулем. Целая часть значения c(i)выделяется с помощью функции Fix(). Если очередной элемент c(i) содержит целое значение, то произво­дится обмен значений двух элементов массива c(k) и c(i)c помощью переменной temp.

Sub Pr4745(ByRef с( ) As Single ) Dim temp As Single Dim i, k As Integer FormMas18(c) ’вывод исх. массива vivodSngMac17(c,ListBox1) k = 0 `Цикл обработки массива For i = 0 To UBound(c) If c(i) - Fix(c(i)) = 0 Then temp = c(k): c(k) = c(i) c(i)=temp : k = k + 1 End If Next i ’вывод изм.массива vivodSngMac17(c,ListBox2) End Sub Sub FormMas18(ByRef c( ) As Single) Dimi, k As Integer ` Цикл формирования массива For i = 0 To UBound( c ) If i < 5 Then c(i) = (i^3 - 4) / (i + 1) Else c(i) = (i^2 - 36) / i End If Next i End Sub

Рис. 4.7.4-5

Пример 4.7.4-4. Написать процедуру-Sub, в которой вычисляется произведение положительных и сумма неположительных элементов массива x(20).

Алгоритм и программа решения задачи приведены на рис. 4.7.4-6.

Накопление суммы и произведения в алгоритме осуществлено с использованием рекуррентных формул: s₀ = 0; s_i+1 = s_i + x_i+1;p₀ = 1; p_i+1 = p_i * x_i+1.

Sub Pr4746( ByRef x()As Single, _ ByRef s As Single, _ ByRef p As Single) Dim i As Integer s = 0 : p = 1 For i =0 To UBound( x ) If x(i) > 0 Then p = p* x(i) Else s= s + x(i) End If Next i End Sub

Рис. 4.7.4-6

Пример 4.7.4-5. Написать процедуру-Sub, в которой необходимо сформировать массив y(n), переписав в него положительные элементы массива x(100).

Алгоритм и программа решения задачи приведены на рис. 4.7.4-7.

Для решения поставленной задачи необходимо проверить знак у всех элементов массива х. При этом текущий индекс (n) формируемого массива y меняется независимо от индекса (i) массива х, так как он зависит от конкретного содержимого элемента x. Индекс n увеличивается на 1 только по мере появления положительного элемента массива х. Таким образом, после проверки всех элементов массива x, в переменной n будет содержаться число положительных элементов массива x, что соответствует количеству элементов массива y.

Sub Pr4747(ByRef x() As Single, _ ByRef y() As Single) Dim i, n As Integer n = -1 For i=0 To UBound(x) If x(i) > 0 Then n =n+1 ReDim Preserve y(n) y(n)=x(i) End If Next i End Sub

Рис. 4.7.4-7

Пример 4.7.4-6.Написать процедуру-Sub, в которой из массива х(n)удаляются отрицательные эле­менты.

Алгоритм, реализующий этот процесс, часто называют алгоритмом “сжатия“ (рис. 4.7.4-8). Метод заключается в поиске удаляемого элемента, фиксации его номера (например, i - й), а затем последовательной перезаписи всех последующих элементов массива так, что значение следующего i+1 элемента записывается на место i-го, на место (i+1)-го элемента – (i+2)-й и так далее до конца массива. Из последовательности исчезает значение удаляемого элемента, однако последний элемент повторяется дважды, поэтому после выхода из цикла по перезаписи элементов длина массива должна быть уменьшена на 1.

Так как отрицательные элементы могут идти подряд, то i+1 элемент, который встал на место i-го, тоже может быть меньше 0. Поэтому перед тем, как вернуться в цикл по параметру i (то есть увеличить i на 1), необходимо снова проверить текущий i-й элемент (бывший i+1) и, возможно, тоже удалить его “сжатием”. Возврат во внешний цикл по параметру I i можно осуществлять только тогда, когда очередной проверяемый элемент не будет меньше 0.

Sub Pr4748(ByRef x( ) As Single) Dim i, n, j As Integer i =0 : n= UBound(x) Do Do While i <= n AndAlso x(i)< 0 For j= i To n-1 x(j)= x(j+1) Next j n = n-1 ReDim Preserve x(n) Loop i = i +1 Loop Until i >n End Sub

Рис. 4.7.4-8

Пример 4.7.4-7. Написать процедуру-Sub, в которой необходимо удалить из массива x(n) одинаковые элементы.

Алгоритм «сжатия» для получения массива с уникальными элементами и программа, решающая настоящую задачу, приведены на рис. 4.7.4-9.

Метод заключается в последовательном сравнении каждого элемента исходного массива со всеми остальными. Если x(i)=x(j), то j-й элемент удаляется, а длина массива уменьшается на единицу.

Sub Pr4749(ByRef x( ) As Single) Dim i, n, j, k As Integer i =0 : n= UBound( x) Do While i < n j = i +1 Do If x(i)=x(j) Then For k =j To n-1 x(k)=x(k+1) Next k n =n-1 Else j =j+1 End If Loop While j<=n i = i +1 Loop ReDim Preserve x(n) End Sub

Рис. 4.7.4-9

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

Пример 4.7.4-8. Написать процедуру-Sub, в которой производится сортировка по убыванию массивах(0:n), состоящего из n+1 элемента, применяя «сортировку выбором» («прямого выбора»).

Алгоритм и программа сортировки массива по убыванию методом «прямого выбора» приведены на рис. 4.7.4-10.

Сортировка элементов массива по убыванию производится с помощью вложенных циклов. Суть метода “сортировки выбором” состоит в следующем.

Сначала осуществляется поиск наибольшего элемента массива и его индекса среди всех элементов, начиная с 1-го. Найденный максимальный элемент меняется с первым элементом. Затем вновь осуществляется поиск наибольшего элемента массива и его индекса, но уже со второго элемента, и найденный максимальный элемент обменивается со 2-м элементом и так далее. Таким образом, число найденных максимумов (поисков) равно n. При этом во внешнем цикле, начиная с первого и до предпоследнего элемента, сначала очередной элемент принимается за максимальный, а затем (после выполнения внутреннего цикла) обеспечи­вается заполнение этого очередного элемента массива наибольшим «среди оставшихся».

Внут­ренний цикл осуществляет перебор и сравнение последующих эле­ментов, начиная с (i+1)-го до последнего элемента массива. В результате выполнения внутреннего цикла, в переменной xmax фиксируется значение наибольшего элемента, а в переменной k - его номер. Далее, во внешнем цикле выполняется перестановка найденного максимального эле­мента на место очередного i-го элемента массива.

Sub Pr47410(ByRef x( )As Single) Dim i, n, j, k As Integer Dim xmax As Single n = UBound(x) ` Внешний цикл сортировки For i = 0 To n - 1 xmax = x(i) k = i `Поиск xmax и k For j = i + 1 To n If x(j) > xmax Then xmax = x(j) k = j End If Next j x(k)= x(i) x(i) = xmax Next i End Sub

Рис. 4.7.4-10

Пример 4.7.4-9.Написать процедуру-Sub, в которой необходимо упорядочить по возрастанию массив х(n)модифицированным методом «пузырька» (прямого обмена).

Алгоритм и программа упорядочения массива по модифицированному методу «пузырька» приведены на рис. 4.7.4-11.

Суть метода заключается в последовательном сравнении первого элемента массива со вторым, третьим и так далее. Если значения в паре расположены не в порядке возрастания (т.е. по убыванию), то их меняют местами. После первого просмотра элемент массива с наименьшим значением становится первым. Далее все элементы, начиная с третьего, сравниваются со вторым, в результате чего элемент со значением, следующим за минимальным элементом, становится на второе место.

Продолжая таким же образом, вплоть до предпоследнего элемента, сортируют весь массив.

Обратите внимание, что в схемах алгоритмов обмен значениями обозначается символом “↔”, а в примере обмен реализован через дополнительную переменную xx.

Sub Pr47411(ByRef x( ) As Single) Dim i, n,j As Integer Dim xx As Single n = UBound(x) For i = 0 To n-1 For j = i +1 To n If x(i) > x(j) Then xx=x(i) x(i)=x(j) x(j)=xx End If Next j Next i End Sub

Рис. 4.7.4-11