Файл: Алгоритмы, их свойства.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например,

int A[10];

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

Рисунок 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.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;

}

Заключение

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

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

В языке С++ под массивом понимается упорядоченный набор фиксированного количества однотипных данных.

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

Список использованных источников

1. Джесс Либерти. Освой самостоятельно С++ за 21 день. Издательский дом «Вильямс». – 2014. – 230 с.
2. Борис Пахомов. С/С++ и MS Visual C++ 2010 для начинающих. БХВ-Петербург. – 2013. – 436 с.
3. Бьерн Страуструп. Программирование. Принципы и практика использования С++. Издательский дом «Вильямс». – 2016. – 258 с.
4. Айвор Хортон. Visual C++ 2010. Полный курс. Издательский дом «Вильямс». – 2015. – 300 с.
5. Дэвид Гриффитс, Дон Гриффитс. Изучаем программирование на С. Издательство «Эксмо». – 2013. – 400 с.
6. Прата С. Язык программирования С++. Издание 6. Издательский дом «Вильямс» – 2015. – 304 с.
7. Брайан Керниган, Деннис Ритчи. Язык программирования С++. Издательство «Невский диалект». – 2015. – 320 с.
8. Р. Лафоре. Объектно-ориентированное программирование в С++. Издательство «Питер». Издание 4. – 2014. – 628 с.
9. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб. пособие. – Финансы и статистика, 2014. – 464с.
10. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. – СПб.: БХВ-Петербург, 2014. – 464с.
11. Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Седжвик Роберт. К.: Издательство «ДиаСофт», – 2014. – 500 с.
12. Язык С++: Учеб. Пособие /И.Ф. Астахова, С.В. Власов, В.В. Фертиков, А.В. Ларин. – Мн.: Новое знание, 2013. – 203 с.
13. Лаптев В.В., Морозов А.В., Бокова А.В. С++. Объектно-ориентированное программирование. Задачи и упражнения. – СПб.: Питер. 2017. – 288 с.
14. Кнут, Дональд, Эрвин. Искусство программирования. Том 1. Основные алгоритмы. 3-е изд. Пер. с англ. –: Уч. пос. М.: Издательский дом. «Вильямс», 2014. – 720с.
15. С++ Стандартная библиотека. Для профессионалов. /Н. Джосьютис. – СП Питер, 2015. – 350 с.
16. Динман М.И. С++. Освой на примерах. – СПб.: БХВ-Петербург, 2016. – 260 с.
17. Харви Дейтел, Пол Дейтел. Как программировать на С++. Пер. с англ. – М.: ЗАО «Издательство БИНОМ», 2015. – 430 с.
18. Майерс С. Эффективное использование С++. 50 рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М.: ДМК Пресс; – СПб.: Питер. 2016. – 240с.
19. Штерн Виктор. Основы С++: Методы программной инженерии. – Издательство «Лори», 2013. – 860с.
20. Скляров В.А. Язык С++ и объектно-ориентированное программирование. Справочное пособие. – Минск. «Вышейшая школа». – 2014. – 478с.