Массивы

Размещено на http://www.allbest.ru/

Лекция №4. Массивы

Понятие массива

Одномерные массивы

Многомерные массивы

Инициализация элементов массива

Понятие массива

Как и любой язык программирования высокого уровня, язык С помимо простых обладает и сложными (векторными) типами данных. Значения сложного типа могут состоять из нескольких значений одного или различных типов данных (как простых, так и сложных). В языке С присутствуют следующие сложные типы: массивы, строки, перечисления, структуры, объединения, поля бит. Все перечисленные типы данных будут рассмотрены.

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

Упорядоченность проявляется в том, что доступ к каждому элементу массива осуществляется посредством его индекса (номера) в массиве. Индекс представляет собой одно или несколько целых чисел, в зависимости от размерности массива. В принципе в языке С поддерживается произвольная размерность массивов, но действует ограничение: размер всего массива не должен превышать 231-1 байт (для 32-ух разрядных x86 процессоров в ОС Windows). Это ограничение связано с архитектурой вычислительной машины и может отличаться в других семействах процессоров и операционных систем.

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

тип имя[предел №1][предел №2]...[предел №N];

Сначала указывается тип значений, которые будут храниться в массиве. Это может быть любой пользовательский или системный тип, объявленный ранее. Затем указывается имя массива, которое может быть любым доступным идентификатором. После имени массива в парных квадратных скобках указываются пределы размерностей массива. Пределы представляют собой целочисленные положительные значения. Количество пар квадратных скобок указывает на размерность массива. Примеры:

int a[10];

double b[5][20];

char c[5][5][10];

В первой строке объявлен целочисленный одномерный массив a из десяти элементов. Во второй строке объявлен вещественный двумерный массив b, в первой размерности предел 5, а во второй - 20, всего 100 элементов. Данный массив можно условно представить как пять одномерных вещественных массивов по 20 элементов в каждом из них. В третьей строке объявлен трехмерный символьный массив c с пределами 5, 5 и 10 в первой, второй и третьей размерностях соответственно (всего 250 элементов). По аналогии с предыдущим представлением, данный массив можно представить как пять двумерных символьных массивов с размерностями 5 и 10.

ПРИМЕЧАНИЕ: Объявление массива в языке С является обычным оператором объявления, поэтому в одном операторе допускается объявлять несколько массивов и обычных переменных, например:

double x[5][10], y[10][10];

int a[10], i,j;

Обращение к элементам массива в языке С осуществляется путем указания имени массива и, следом за ним, индексов элемента в парных квадратных скобках. Очень важно усвоить, что индексация в языке C, в отличие от некоторых других языков программирования, начинается с нуля, а не с единицы. Таким образом, в массиве a обращение к первому элементу будет иметь вид: a[0], а к последнему - a[9]. Соответственно в массиве b: b[0][0] и b[4][19]. Элемент массива в языке С при построении выражений может выступать и как RValue, и как LValue.

На практике наиболее часто используются только одномерные и двумерные массивы. Одномерные массивы называют векторами, а двумерные - матрицами.

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

тип имя[размер];

В качестве размера массива может указываться любое положительное целочисленное значение. В стандарте С89 значение могло являться только константой. В стандарте С99 было введено понятие динамического массива. Под динамическим массивом здесь имеется в виду массив, при создании которого в качестве размера указывается значение некоторого выражения, в которое входят переменные, объявленные и инициализированные ранее (выражение должно иметь положительный целочисленный результат). Например:

int n;

printf(“Введите размер массива: ”);

scanf(“%d”,&n);

double x[n];

В данном примере в последней строчке создается вещественный массив x, в качестве размера которого указывается переменная n, значение которой вводится пользователем.

ПРИМЕЧАНИЕ: Память под динамический массив выделяется в стеке, поэтому данный механизм применим только для относительно малых массивов. При создании динамических массивов большого размера рекомендуется использовать функции для работы с динамической памятью (будут рассмотрены в следующей главе).

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

тип имя[размер] = {значение №1, ... значение №N};

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

int a[5] = {1,2,3,4,5}, b[5] = {1,2};

double x[10] = {0.0};

В первой строчке создаются два целочисленных массива по пять элементов в каждом. Элементы массива a инициализированы значениями 1 2 3 4 5 соответственно, а элементы массива b - 1 2 0 0 0. Во второй строке объявлен вещественный массив x из десяти элементов, инициализированных нулями.

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

int a[5] = {1,2,,4,5};

Если массив объявляется с инициализацией, то допускается не указывать размер массива (указываются пустые квадратные скобки). В таком случае размер массива будет определен по числу инициализирующих значений. Например:

int a[] = {1,2,3,4,5};

char b[] = {'a','b','c'};

В первой строке объявлен целочисленный массив a с пятью инициализирующими значениями: размер массива - пять элементов. Во второй строке объявлен символьный массив b с тремя инициализирующими значениями: размер массива - три элемента.

ПРИМЕЧАНИЕ: В языке С инициализировать динамические массивы нельзя.

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

const int array[] = {1,2,3,4,5};

const double vector[5] = {1.0,2.0,3.0};

Обращение к элементу массива осуществляется путем указания имени массива, а после имени в квадратных скобках индекса элемента:

имя[индекс]

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

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

int a[10];

for(int i=0;i<10;i++) scanf(“%d”,&a[i]);

...

for(int i=0;i<10;i++) printf(“%d\t”,a[i]);

Присвоение массива массиву также осуществляется поэлементно. Например, необходимо присвоить вещественный массив x вещественному массиву y. Фрагмент программы:

double x[15], y[15];

...

for(int i=0;i<15;i++) y[i] = x[i];

...

ПРИМЕЧАНИЕ: В языке С во время выполнения программы не производится контроль за допустимыми значениями индексов элементов. Поэтому, если индекс элемента выходит за рамки массива, то в программе возможно появление ошибок. Ошибки могут быть: простыми (например «случайное» изменение переменных) и критическими (выход за пределы пространства памяти, отведенной для программы). Например, в результате выполнения следующего фрагмента программы (индексная переменная i выходит за пределы допустимых значений) будет выведено сообщение о некорректном обращении к памяти:

int a[10];

for(int i=0;i<=10;i++) a[i] = i;

Предотвращение таких ситуаций в языке С в основном возложено на плечи программистов.

Объявление двумерного массива (далее матрица) имеет следующий синтаксис:

тип имя[размер №1][размер №2];

Размеры матрицы указываются в отдельных парных квадратных скобках после имени и могут быть любыми положительными целочисленными значениями. На практике принято значение первой размерности называть строками, а второй - столбцами. Как и в случае одномерного массива, в стандарте С89 регламентируется, что размеры матрицы должны быть целочисленными константами. Стандарт С99 допускает объявление динамических матриц, путем использования выражений при указании размеров матрицы, если в это выражение входят значения определенных ранее переменных (выражение должно иметь положительный целочисленный результат). Например:

int n,m;

printf(“Введите размеры матрицы: ”);

scanf(“%d %d”,&n,&m);

double a[n][m];

В данном примере в последней строчке создается вещественная матрица a, в качестве размеров которой указываются переменные n и m, значения которых вводятся пользователем.

ПРИМЕЧАНИЕ: Как и для одномерных динамических массивов, для матриц память в таком случае выделяется в стеке, поэтому данный механизм применим только для относительно малых матриц.

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

тип имя[размер №1][размер №2] = {

{значение № 11, ... значение № 1N},

...

{значение № M1, ... значение № MN}

};

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

int a[2][4] = { //Объявлена матрица

{1,2,3,4}, // 1 2 3 4

{5,6} // 5 6 0 0

};

double b[3][5] = { //Объявлена матрица

{1.0, 2.0, 3.0, 4.0, 5.0}, // 1 2 3 4 5

{6.0, 7.0} // 6 7 0 0 0

}; // 0 0 0 0 0

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

int a[3][5] = {{1,2,3,4,5},,{6,7,8,9,0}};

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

double b[][4] = {{1,2,3,4},{5,6,7,8}};

В данном примере создается вещественная матрица b из двух строк и четырех столбцов.

ПРИМЕЧАНИЕ: В языке С инициализировать динамические матрицы, как и массивы, нельзя.

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

const int matrix[][5] = {

{1,2,3,4,5},

{6,7,8,9}};

Обращение к элементу матрицы осуществляется путем указания имени матрицы, а после имени в отдельных парных квадратных скобках индексы элемента (строка и столбец):

имя[строка][столбец]

Как уже отмечалось, индексация в языке С начинается с нуля, поэтому для матрицы размером, например, пять строки и десять столбцов правильными будут индексы строк от нуля до четырех, а столбцов - от нуля до девяти включительно. Каждый отдельный элемент матрицы может рассматриваться как простая переменная и, соответственно, выступать в выражениях в качестве RValue или LValue значений.

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

double a[5][10];

for(int i=0;i<5;i++) for(int j=0;j<10;j++)

scanf(“%lf”,&a[i][j]);

...

for(int i=0;i<5;i++){

for(int j=0;j<10;j++)

printf(“%8.2lf\t”,a[i][j]);

printf(“\n”);

}

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

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

int x[5][10], y[5][10];

...

for(int i=0;i<5;i++) for(int j=0;j<10;j++)

y[i][j] = x[i][j];

...

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

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

int a[2][2][2]={ {{1,2},{3,4}},

{{5,6},{7,8}}

};

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

Одномерные (линейные) массивы

Линейным массивом в программе на C++ называется упорядоченный набор однотипных переменных, которые располагаются в памяти последовательно

Размещено на http://www.allbest.ru/

Массив является простейшей структурой данных, облегчающей работу с большими объемами информации путем их упорядочения. В случае с массивами, упорядочение происходит за счет индексирования элементов, то есть обращения к каждому из них по порядковому номеру. Показанный на рисунке массив состоит из n элементов с индексами от 0 до n-1, в который записаны числа 5, 21, 0, 12 и т.д.

Любой массив в C++ характеризуется тремя параметрами: именем, типом элементов и размером. Как и обычная переменная, перед использованием массив должен быть объявлен. Общая форма записи объявления:

тип_элементов имя_массива[размер_массива];

Здесь тип_элементов - это любой из известных стандартных типов (int, float, double, char и т.д.), имя_массива - уникальное имя (идентификатор), используемое для обращения к массиву, размер_массива - количество его элементов. В качестве последнего параметра в объявлении может быть использована только целочисленная константа или константное выражение. Примеры объявлений

int A[15]; // массив из 15 целочисленных элементов с именем A

float x[3]; // массив x из 3-х элементов типа float

Объявление массива является командой компилятору на выделение памяти для хранения его элементов. Общее количество выделенной памяти зависит не только от числа элементов, но и от размера каждого элемента, то есть от его типа. Например, текстовая строка из 1000 символов (тип char) займет P = 1000*sizeof(char) = 1000 байтов, а массив из такого же количества вещественных чисел двойной точности (тип double) займет уже в восемь раз больше - P = 1000*sizeof(double) = 8000 байтов.

Нумерация элементов в массиве начинается с нуля. Таким образом, первый элемент массива имеет индекс 0, а последний - индекс n-1, где n - размер массива. Обращение к элементу производится с использованием имени массива и индекса элемента в квадратных скобках. Например, запись “x[0] = 5.5;” означает “присвоить значение 5.5 нулевому элементу массива x”.

Для работы с массивами характерным является использование итерационных циклов for. С их помощью организуется выполнение однотипных операций со всеми элементами массива, в частности, поэлементный ввод-вывод, поэлементные арифметические операции и др. Рассмотрим это на следующем примере.

Пример 1. Напишите программу, запрашивающую у пользователя 10 целых чисел, и выводящую ее на экран их сумму.

Решение. Будем использовать массив с именем A и размером 10 для хранения введенных чисел. Ввод данных и суммирование организуем поэлементно с помощью циклов for.

#include <iostream.h>

void main()

{

int A[10]; // объявляем массив из 10 целых

for(int i=0; i<10; i++) // организуем цикл по i от 0 до 9

{

cout << "input A[" << i << "] = "; // приглашение

cin >> A[i]; // вводим A[i]

}

int sum = 0; // объявляем переменную

for(i=0; i<10; i++) // организуем цикл

{sum = sum + A[i];} // в цикле суммируем элементы

cout << "\nSumma: " << sum; // выводим результат на экран

// задержка

}

Многомерные массивы

Массивы в программах C++ могут быть не только линейными. Довольно частым является использование двух - (и более) -мерных структур. К примеру, прямоугольная матрица - типичная структура, представимая с помощью двумерного массива.

Многомерный массив в C++ организован по принципу «массива массивов». Общий формат его объявления

тип имя[N1][N2]…[NM];

Размещено на http://www.allbest.ru/

Здесь M - число индексов (или размерность) массива. Индексы изменяются в пределах от 0 до N1 - 1, от 0 до N2 - 1, от 0 до N3 - 1, ..., от 0 до NM - 1, соответственно.

К примеру, запись int G[5][4]; означает объявление двумерного массива целых чисел с именем G и размерами 54. На рис. справа такой массив представлен в виде таблицы. Здесь первый индекс является номером строки, второй - номером столбца таблицы, с диапазонами изменения от 0 до 4, и от 0 до 3, соответственно.

Доступ к элементам многомерного массива в программе производится так же, как и в одномерном случае, то есть путем указания имени массива и набора индексов в квадратных скобках. Например, операция присваивания значения 0 последнему элементу будет записана как G[4][3] = 0.

При работе с многомерными массивами удобно использовать вложенные циклы for. С их помощью можно выполнить заданное действие с каждым из элементов массива путем перебора всех значений индексов. Приведенный ниже фрагмент программного кода выводит на экран все элементы массива G.

for(int i=0; i<5; i++) // цикл по строкам i

{

for(int j=0; j<4; j++) // цикл по строкам j

cout << G[i][j] << “\t”; // выводим G[i][j]

cout << endl; // перевод на новую строку

}

Алгоритм работы этого фрагмента иллюстрируется следующей блок-схемой

Размещено на http://www.allbest.ru/

Здесь внешний цикл по I последовательно пробегает все значения от 0 до 5. При каждом i запускается внутренний цикл по j от 0 до 4. В теле этого цикла на экран выводятся значение элемента G[i][j] и знак табуляции (горизонтальный отступ). Внутренний цикл продолжается до тех пор, пока не будут перебраны все значения j, то есть не будет выведена вся i-я строка. По завершении внутреннего цикла, экранный курсор перемещается на новую строку манипулятором endl, и далее внешний цикл продолжает свою работу, последовательно выводя на экран другие строки массива.

Пример 2. Имеется вещественная квадратная матрица размером 44. Напишите программу, вычисляющую произведение элементов в каждой ее строке. Матрица вводится с клавиатуры.

Решение. Условимся использовать для хранения матрицы массив float X[4][4]. Расчет произведения реализуем согласно следующему алгоритму. Введем вспомогательную переменную (к примеру, float P).

#include <iostream.h>

int main(int argc, char* argv[])

{

float X[3][3]; // объявляем массив 4 4

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

for(int j=0; j<3; j++)

{

cout << "input X[" << i <<

"," << j << "] = ";

cin >> X[i][j]; // вводим элементы матрицы

}

cout << "\n Results:\n";

for(i=0; i<3; i++) // цикл по строкам

{

float P = 1.0; // вспомогательная переменная

for(int j=0; j<3; j++) // цикл по элементам в строке

P = P * X[i][j]; // домножаем P на X[i][j]

cout << "\n proizvedenie " << i

<< "-i stroki = " << P; // выводим результат на экран

}

return 0;

}

Инициализация элементов массива

В рассмотренных выше примерах начальные значения элементов массива задавались пользователем с клавиатуры. Можно поступить иначе и каждому из элементов присвоить начальное значение с помощью оператора «=». Это потребует довольно большого количества записей - по отдельному оператору для каждого из элементов. C++ дает программисту еще один, более удобный, способ. Массив может быть инициализирован при объявлении. Для этого в строке объявления сразу вслед за указанием типа элементов, имени массива и его размеров, записывается знак присваивания, и далее в фигурных скобках задаются значения элементов через запятую

тип имя[размерN] = { знач1, знач2, знач3, ..., значN };

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

В следующем примере

float mark[5] = { 7.3, 4.0, 2.2, 12.1, 8.9 };

создается массив с именем mark, состоящий из 5 чисел типа float, которые инициализируются значениями 7.3, 4.0, 2.2 и т.д. Это эквивалентно следующему набору операторов

float mark[5]; mark[0]=7.3; mark[1]=4.0; mark[2]=2.2 и т.д.

Многомерный массив также может быть инициализирован в строке объявления. Для этого достаточно помнить о том, что многомерный массив в C++ - это «массив массивов», о чем уже говорилось выше. Пример

int F[3][3] = { {3, 0, 2} , (1, 9, 8}, {5, 7, 4} };

Здесь создается двумерный массив с именем F и размерами 33, элементы которого получают начальные значения F[0][0] = 3, F[0][1] = 0, F[0][2] = 2, F[1][0] = 1 и т.д.

Пример 3. Пусть и - две квадратные матрицы размером 33. Требуется написать программу, рассчитывающую их произведение

#include <iostream.h>

const int N = 3; // используем константу N=3

int main(int argc, char* argv[])

{

float A[N][N] = { {1, 1, 1},

{2, 2, 2},

{3, 3, 3} }; // исходная матрица A

float B[N][N] = { {1, 2, 3},

{1, 2, 3},

{1, 2, 3} }; // исходная матрица B

float C[N][N]; // матрица произведения С

for(int i=0; i<N; i++) // цикл по строкам С

{

for(int j=0; j<N; j++) // цикл по столбцам С

{

float s = 0.0; // вспомогательная переменная

for(int k=0; k<N; k++) // цикл суммирования по k

s += A[i][k]*B[k][j]; // добавляем к s новое слаг-ое

C[i][j] = s; // записываем s в C[i][j]

}

}

cout << " Results: \n"; // далее выводим C на экран

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

{

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

cout << C[i][j] << "\t";

cout << endl;

}

return 0;

}

Задачи:

массив матрица цикл

Дана линейная таблица А[N], N <=10. Найти наименьший положительный и наибольший отрицательный ее элементы.

Дана линейная таблица А[N], N <=10. Определить количество различных элементов таблицы (встречающихся хотя бы один раз).

Дана прямоугольная таблица A[N, N], N <=5. Найти номер столбца, в котором находится минимальный элемент.

Дана прямоугольная таблица A[N, N], N <=5. Удалить строку, содержащую максимальный элемент таблицы путем сдвига остальных строк вверх.

1. Размещено на www.allbest.ru