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

Тема 4.7

Алгоритмы обработки одномерных массивов

 

 

Структурированные данные

Средства описания и работы с одномерными массивами данных

 

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

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

Элементы управления для работы со списками

Тестовые задания

4.7.7. Лабораторная работа по теме «Программирование алгоритмов формирования и обработки одномерных массивов»

4.7.7.1. Вопросы, подлежащие изучению

 

4.7.7.2. Общее задание на разработку проекта

4.7.7.3. Варианты индивидуальных заданий

 

4.7.7.4. Содержание отчёта

 

4.7.7.5. Пример выполнения задания

 

4.7.7.6. Контрольные вопросы

 

 

Структурированные данные

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

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

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

Массив – это совокупность однотипных переменных (элементов массива). Имя у всех переменных одно и то же, а для доступа к конкретному элементу массива используется дополнительный идентификатор – его порядковый номер (индекс), который начинается с 0.

Кроме массивов в программировании для построения эффективных алгоритмов могут использоваться и другие стандартные структуры данных, такие структуры данных, как стеки, очереди, связанные списки и другие.

Наряду со стандартными структурами данных, могут использоваться структуры данных, определяемые пользователем. Эти структуры данных определяются средствами объектно-ориентированного программирования с помощью классов.

 

 

4.7.2. Средства описания и работы с одномерными
массивами данных

 

Массив – последовательность переменных одинакового типа, объединенных общим именем. Например: одномерный массив а(9) состоит из 10 элементов с общим именем а: a(0), a(1), a(2), a(3),..., a(9), упорядоченных по индексу i, который принимает значения от 0 до 9:

 

a(i)
i

 

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

При объявлении массива оператор объявления должен включать следующую информацию:

· имя массива – имя (идентификатор), которое используется для представления массива в программе;

· тип данных – тип данных, который имеют элементы массива;

· размерность (ранг) – количество измерений объявляемого массива (т.е. количество индексов при объявлении; одномерные массивы имеют одно измерение);

· количество элементов – количество элементов, которые будут содержаться в массиве.

 

Рассмотрим примеры некоторых описаний массивов:

 

 

В этих примерах объявлены следующие массивы:

· одномерный массив d, состоящий из 31 элемента типа Integer с индексами от 0 до 30;

· одномерный массив a, состоящий из 11 элементов типа Double с индексами от 0 до 10;

· двумерный массив b, состоящий из 14х11=151 элемента типа Single с индексами по строкам от 0 до 13 и по столбцам от 0 до 10.

Обратите внимание, что значением нижней границы массива в VB может быть только 0.

Таким образом, массив состоит из элементов, которые могут быть доступны при помощи индексов. При обращении к элементам массива индексы записываются вслед за именем в круглых скобках и могут представлять собой любое допустимое целочислен­ное выражение. Например, d(24), a(2*i+1).

Обратите внимание, что количество индексов указывает на размерность массива. Так, в приведенном выше примере размерность массива a(10) равна единице. Массив b(2,3) имеет размерность 2.

В отличие от размерности, размер массива – это количество элементов в массиве. В нашем примере размер массива, а(10) равен 11.

Перед использованием массива в программе его необходимо объявить с помощью оператора Dim, а элементам массива присвоить конкретные значения. Оператор Dim выделяет место в памяти компьютера для размещения элементов массива, обнуляет элементы числовых массивов или заполняет элементы строковых массивов пустыми строками ('''').

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

Заполнить элементы массива конкретными значениями можно с помощью ввода значений элементов массива, с помощью оператора присваивания или с помощью инициализации элементов массива.

Инициализация элементов массива – это поэлементное присваивание значения в операторе объявления массива. В этом случае размер массива не указывается в круглых скобках после имени массива, а определяется неявно размером списка значений. Список значений начинается с элемента с индексом 0 и заключается в фигурные скобки, например:

 

Dim Город () As String = {"Рязань", "Тула", "Калуга"}

 

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

 

Fori = 0 То КоличествоЭлементовМассива – 1 ИмяМассива (i) = выражение или Переменная = ИмяМассива (i) Next i

 

Чтобы облегчить работу с массивами в процедурах, для определения верхней границы массива используется встроенная функция
Bound (ИмяМассива).

Эта функция возвращает (определяет) номер последнего элемента массива и позволяет обрабатывать массивы в процедурах, не передавая в них в качестве параметра количество элементов массива. Например,

 

For i = 0 То UBound(ИмяМассива) ИмяМассива (i) = выражение или Переменная = ИмяМассива (i) Next i

Кроме того, для определения верхней границы одномерного массива можно использовать метод GetUpperBound(). Поскольку массив одномерный, то в скобках следует указывать значение 0. Например:

 

For i = 0 To a.GetUpperBound(0) sum = sum + a(i) Next i

 

Если имя массива, является формальным параметром процедуры, то после имени массива необходимо поместить пустые круглые скобки:

 

ByVal ИмяМассива ()As Тип или ByRef ИмяМассива ()As Тип

 

Кроме того, известно, что ключевое слово ByVal указывает передачу аргумента-массива по значению, а ключевое слово ByRef указывает, что аргумент-массив передается по ссылке. Заметим, что если ключевые слова ByVal или ByRef опущены, то аргумент-массив переда­ется по ссылке.

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

 

Sub Show1(ByRef Lines() As Single, ByVal NLines As Integer) … End Sub Function Sort(ByRef List() As String) NLines As Integer … End Sub

 

Обращение к этим процедурам может, например, быть следующим:

 

Show1(Lines, 5) N1 = Sort(List)

 

Обратите внимание на то, что после имени массива, который является фактическим параметром, скобки отсутствуют.

 

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

 

Пример 4.7.2-1. Написать процедуры ввода/вывода, которые могут использоваться в алгоритмах формирования и отображения одномерных массивов.

Процедуры ввода и вывода для одномерных массивов представлены на
рис. 4.7.2-1–4.7.2-3.

 

'Процедура ввода элементов массива типа Single с клавиатуры Sub vvodSngMac15(ByRef a() As Single, ByVal L As ListBox) Dim i As Integer For i = 0 To UBound(a) a(i) = CSng(Val(InputBox("Введите" & i & "-й элемент")) Next i End Sub

 

Рис. 4.7.2-1. Процедура ввода элементов массива Single с клавиатуры

Примера 4.7.2-1

 

 

'Процедура формирования массива случайным образом на интервале [2;4] Sub vvodSngRnd16(ByRef a() As Single) Dim i As Integer For i = 0 To UBound(a) a(i) = 2 + 2 * Rnd() Next i End Sub

Рис. 4.7.2-2. Процедура формирования массива случайным образом

Примера 4.7.2-1

'Процедура форматного вывода массива типа Single в ListBox Sub vivodSngMac17(ByRef a() As Single, ByVal L As ListBox) Dim i As Integer Dim m As String = "" For i = 0 To UBound(a) m = m + Format(a(i), "0.000") + Space(4) Next i If m ="" Then m = "массив пуст" L.Items.Add(m) End Sub

 

Рис. 4.7.2-3. Процедура форматного вывода массива Single в ListBox

Примера 4.7.2-1

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

 

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

 

Dim Sigma(5) As Integer, m(3) As Single

 

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

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

 

РазмерМассива = Выражение или РазмерМассива = 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-7, рис. 4.7.4-9 и рис. 4.7.4-10 приведены примеры программных кодов, использующие динамические массивы.

 

 

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

 

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

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

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

· Нахождение суммы значений элементов массива при заданных условиях (Пример 4.7.4-1).

· Нахождение произведения значений элементов массива при заданных условиях (Пример 4.7.4-2).

· Нахождение максимального и минимального значений элементов массива и их индексов (Пример 4.7.4-3).

· Формирование нового массива из элементов одного или нескольких массивов в соответствии с заданными критериями (Примеры 4.7.4-3 – 4.7.4-4).

· Формирование массива в соответствии с определенными правилами (Пример 4.7.4-7).

· Вставка элемента по заданному критерию в массив
(Пример 4.7.4-5).

· Удаление элемента по заданному критерию из массива
(Пример 4.7.4-6).

· Обмен значений элементов массива по заданному критерию
(Пример 4.7.4-8).

· Сортировка (упорядочивание) элементов массива (Пример 4.7.4-9).

 

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

Схема алгоритма и программный код процедуры приведены на
рис. 4.7.3-1.

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

 

Sub Pr741(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 End Sub   Private Sub Button1_Click(…) Dim s,p, a() As Single vvodSngMac15(а) vivodSngMac17(а, ListBox1) Pr741(а, s, p) vivod3(s, TextBox1): Vivod3(p, TexBox2) End Sub

 

Рис. 4.7.4-1. Схема алгоритма и программный код процедуры Pr741()

Примера 4.7.4-1