Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования..pdf

2.2. Особенности обработки одномерных массивов

Часто, в процессе разработки программы, возникает потребность хранить большое количество однотипных значений, которые должны поддаваться одинаковым методам обработки. Например, экзаменационные оценки студентов, следует вводить, выводить, анализировать (сравнение с "2" или "5"), изменять при необходимости и тому подобное. Такие однотипные значения имеет смысл хранить в одной переменной, перенумеровать их внутри этой переменной, предоставить доступ к этим значениям по индексу и обрабатывать эти значения в цикле (номер индекса должен совпадать с значением параметра цикла).

Массив – это упорядоченная совокупность однотипных элементов. Массивы широко применяются для хранения и обработки однородной информации, например таблиц, векторов, матриц, коэффициентов уравнений и т.д. [16]

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

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

Различия массива от обычных переменных следующие:[14]

– общее имя для всех значений;

– доступ к конкретному значению по его номеру (индексу)

– возможность обработки в цикле.

Одномерный массив объявляется в программе следующим образом:

<тип данных> <имя_массива> [<размер массива>];

Тип данных задает тип элементов массива. Элементами массива не могут быть функции и элементы типа void. Размер массива в квадратных скобках задает количество элементов массива. В отличие от других языков, в C++ не проверяется выход за пределы массива, поэтому, чтобы избежать ошибок в программе, следует следить за размерностью объявленных массивов. Значение размера массива при объявлении может быть не указано в следующих случаях:[15]

---

– при объявлении массив инициализируется;

– массив объявлен как формальный параметр функции;

– массив объявлен как ссылка на массив, явно определенный в другом модуле.

Используя имя массива и индекс, можно обращаться к элементам массива:

<имя_массива> [<значение_ индекса>]

Значения индексов должны находиться в диапазоне от нуля до величины, на единицу меньше размера массива, который определен при его объявлении, поскольку в C ++ нумерация индексов начинается с нуля.

Например,

int A[10];

объявляет массив с именем А, содержащий 10 целых чисел; при этом выделяет и закрепляет за этим массивом оперативную память для всех 10-ти элементов соответствующего типа (int – 4 байта), то есть 40 байтов, следующим образом (рисунок 5):

A[0]

A[1]

A[2]

A[3]

A[4]

A[5]

A[6]

A[7]

A[8]

A[9]

Рисунок 5 ­ Изображение одномерного массива

Следовательно, при объявлении массива выделяется память, необходимая для размещения всех его элементов. Элементы массива с первого до последнего запоминаются в последовательно возрастающих адресах памяти. Между элементами массива в памяти промежутков нет. Элементы массива записываются один за другим поэлементно.[13]

Для получения доступа к i-му элементу массива А, можно написать А[і], где i – переменная цикла (счетчик цикла), которая может принимать значения от 0 до 9. При этом величина i умножается на размер типа int и представляет собой адрес i-го элемента массива А от его начала, после чего осуществляется выбор элемента массива А по сложившейся адресу.[12]

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

Например,

int a[5] = {9, 33, -23, 8, 1}; // а [0] = 9, а [1] = 33, а [2] = - 23, а [3] = 8, а [4] = 1;

float b[10] = {1.5, -3.8, 10}; // B [0] = 1.5, b [1] = - 3.8, b [2] = 10, b [3] = ... = b [9] = 0;

Все операции с массивами выполняются с помощью операторов цикла. Например, ввод информации в массив:

for (int i = 0; i <n; i ++)

cin >> a [i];

Вывод информации из массива:

for (int i = 0; i <n; i ++)

cout << a [i] << "";

---

2.3. Особенности обработки двумерных массивов

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

Как отмечалось в данном разделе, размерность массива определяется количеством индексов. Элементы одномерного массива имеют один индекс, двумерного массива (матрицы, таблицы) – два индекса: первый из них – номер строки, второй – номер столбца. При размещении элементов массива в памяти компьютера сначала меняется крайний правый индекс, затем остальные - справа налево. [11]

Многомерный массив объявляется в программе следующим образом:

<тип> <имя_массива> [<размерность1>] [<размерность2>] ... [<размерностьN>];

Количество элементов массива равна произведению количества элементов по каждому индексу. Например,

int a [3][4];

объявлено двумерный массив из 3-х строк и 4-х колонок (12-ти элементов) целого типа:

a [0] [0] a [0] [1], a [0] [2], a [0] [3],

a [1] [0], a [1] [1], a [1] [2], a [1] [3],

a [2] [0], a [2] [1], a [2] [2], a [2] [3];

Приведем еще несколько примеров объявления массивов:

float Mas1 [5] [5]; // Матрица 5х5 = 25 элементов вещественного типа.

char Mas2 [10] [3]; // Двумерный массив с 10х3 = 30 элементов символьного типа

double Mas3 [4] [5] [4]; // Трехмерный массив с 4х5х4 = 80 элементов вещественного типа

При объявлении массива можно присваивать начальные значения его элементов, причем необязательно всех, например:

1) int w [3] [3] = {{2, 3, 4}, {3, 4, 8}, {1, 0, 9}};

2) float C [4] [3] = {1.1, 2, 3, 3.4, 0.5, 6.8, 9.7, 0.9};

В первом примере объявлено и инициализирован массив целых чисел w[3][3]. Элементам массива присвоено значение из списка: w[0][0] = 2, w[0][1] = 3, w[0][2] = 4, w[1][0] = 3 и т.д.

Рассмотрим примеры для ввода и вывода элементов матрицы а.

Инициализировать матрицу a размерности nxm можно с помощью следующего кода:

for (i = 0; i <n; i ++)

for (j = 0; i <m; j ++)

cin >> a [i] [j];

Для вывода двумерного массива на экран используются следующие операторы:

for (i = 0; i <n; i ++)

{

for (j = 0; i <m; j ++)

cout << a [i] [j] << "";

cout << endl;

}

3. Типовые алгоритмы обработки массивов

---

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

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

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

– нахождение минимального или максимального элемента массива;

– нахождение суммы, произведения элементов и т.д.

Приведем типичные примеры для обработки каждого из этих типов алгоритмов.

Пример 1. Вывести на экран все четные числа массива и их количество.

int i, n, k = 0, a [10]; // Объявление переменных

cout << "n =";

cin >> n; // Введение размерности

cout << "Элементы массива:";

for (i = 0; i <n; i ++) // Введение элементов массива

cin>>a[i];

for (i = 0; i <n; i ++)

if (a [i]% 2 == 0) // Нахождение парных элементов

{

cout << a [i] << ""; //вывод на экран парного элемента

k ++; //вычисление количества парных элементов

}

cout << "k =" << k; //вывод количества парных элементов

Пример 2. Найти значение минимального элемента одномерного массива и его порядковый номер.

int i, n, p;

float min, a [10], d;

cout << "n ="; //ввод размерности

cin >> n;

cout << endl;

cout << "Элементы массива:";

for (i = 0; i <n; i ++) //ввод элементов массива

cin>>a[i];

min = a [0]; //присваивание начального значения для минимума

for (i = 1; i <n; i ++) //вычисляет минимум массива

if (a [i] <min)

{

min = a [i]; //присваиваем значение в переменную min

p = i; //запоминаем индекс минимального элемента

}

cout << endl;

cout << "min =" << min << "," << "p =" << p << endl; //выводим результат

Пример 3. Найти сумму элементов массива.

int i, n;

float sum = 0, a [10];

cout << "n ="; //вводим размерность массива

cin >> n;

cout << endl;

cout << "Элементы массива:"; //вводим элементы массива

for (i = 0; i <n; i ++)

cin>>a [i];

for (i = 0; i <n; i ++) //находим сумму элементов

sum + = a [i];

cout << endl;

cout << "Summa =" << sum; //выводим сумму

Приведенные выше алгоритмы обработки одномерных массивов будут использоваться на практике при написании программ для курсовой работы.

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

Приведем сначала перечень базовых операций над матрицами и их элементами. К таким операциям относятся:

– ввод и вывод матриц – рассматривался в разделе 2;

– создание новой матрицы по заданному алгоритму;

– поиск элементов матрицы по определенному критерию;

– выполнение определенных операций над компонентами матриц (перестановка строк и столбцов, умножение матриц и т.д.).

---

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

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

int k, i, j, N, a [20] [20];

cout << "N ="; //ввод размерности квадратной матрицы

cin >> N;

cout << "Input Matrix A" << endl; //ввод элементов матрицы А

for (i = 0; i <N; i ++)

for (j = 0; j <N; j ++)

cin >> a [i] [j];

// цикл прохода по главной и боковой диагоналям

for (i = k = 0; i <N; i ++)

{

if (a [i] [i]> 0)

k ++;

if (a [i] [N-i-1]> 0)

k ++;

}

// цикл прохода по периметру матрицы

for (i = 1; i <N-1; i ++)

{

if (a [0] [i]> 0)

k ++;

if (a [N-1] [i]> 0)

k ++;

if (a [i] [0]> 0)

k ++;

if (a [i] [N-1]> 0)

k ++;

}

// проверка, пересекаются ли диагонали, если размерность матрицы – нечетное число

if ((N% 2! = 0) && (a [N / 2] [N / 2]> 0))

k--;

cout << "k =" << k << endl; //вывод результат

Пример 5. Найти все элементы матрицы, значения которых больше нуля.

int k, i, j, N, a [20] [20];

cout << "N ="; //ввод размерности квадратной матрицы

cin >> N;

cout << "Input Matrix A" << endl; //ввод элементов матрицы А

for (i = 0; i <N; i ++)

for (j = 0; j <N; j ++)

cin >> a [i] [j];

// циклы прохода по элементах матрицы

for (i = 0; i <N; i ++)

for (j = 0; j <N; j ++)

if (a [i] [i]> 0)

cout<<a[i][j];

Пример 6. Вывести на экран транспонированную квадратную матрицу.

int i, j, N, a [20] [20];

cout << "N ="; //ввод размерности квадратной матрицы

cin >> N;

cout << "Input Matrix A" << endl; //ввод элементов матрицы А

for (i = 0; i <N; i ++)

for (j = 0; j <N; j ++)

cin >> a [i] [j];

// транспонирование матрицы

for (i = 0; i <N; i ++)

{

for (j = 0; j <N; j ++)

cout<<a[j][i];

cout<<endl;

}

Приведенные выше алгоритмы обработки двумерных массивов будут использоваться на практике при написании программ для курсовой работы.

Заключение

В данной работе рассмотрены циклические алгоритмы обеспечивающие выполнение многократно повторяющихся простых действий.

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

Проанализировано использование циклических алгоритмов в языках программирования.

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

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

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

Выполнен сравнительный анализ типов данных одномерных и многомерных массивов обрабатываемых рассмотренными циклическими алгоритмами на примере языков программирования FORTRAN и C++.

---