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

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

Как и другие переменные, массив в программе должен быть объявлен. Синтаксис объявления массива:

[] [] где размер — количество элементов массива. Количество элементов указывается в квадратных скобках.

Массив может иметь любой класс памяти, кроме register.

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

// объявление одномерного массива из 10 целых чисел.

int а[10] ;

// объявление двумерного массива вещественных.

// чисел, состоящего из 3 строк и 4 столбцов.

float b[3][4];

Для обращения к конкретному элементу массива используется операция индексации «[]». Индекс — это порядковый номер элемента в массиве в соответствующем измерении. Индексация элементов начинается с 0.

Например, при объявлении массива int а[4] этот массив будет состоять из четырех элементов: а[0], а[1], а[2], а[3].

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

Например, Ь[1][3] — это элемент, находящийся на пересечении первой строки и третьего столбца двумерного массива b (номера строк и столбцов индексируются с 0).

Индекс, указываемый в операции индексации, может быть целой константой, целой переменной или любым выражением целого типа.

В памяти массив хранится в виде непрерывного блока данных размером (x₀-x^x₂-…-x_n,_x)-S байт, где п — количество измерений массива; х, — х_пЛ — количество элементов массива в каждом измерении; S — размер типа данных элементов массива. Например, массив int х[3][4] будет занимать в памяти 3−4-4 = 48 байт.

Так как память линейна, то массив любой размерности в памяти хранится как одномерный массив, состоящий из х₀ • х_{ -х₂ •… -х_пЛ элементов. Номер элемента в этом массиве можно вычислить по формуле.

где i_k — индекс элемента в k-u измерении. Например, в массиве х[2][4][3] элемент х[1][3][2] будет иметь номер

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

// элементы массива последовательно принимают // перечисленные значения int, а [5] ={5, 10, б, 7, 8};

// перечисленные значения присваиваются первым трем // элементам массива, последние два элемента // не определены int х[5]={4, 2, 12}.

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

При инициализации многомерных массивов разбиение элементов по размерностям происходит в соответствии с объявлением массива:

int, а [3] [5] = {1, 2, 3, 4, 5, б, 7, 8, 9, 10, 11}.

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

Можно объявить и инициализировать массив следующим образом:

int а[3][5]=^[1]

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

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

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

Пример 5.6.1

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

#include.

#define N 10 int main ().

{.

// объявление массива из 10 элементов int x[N];

// к — количество элементов, меньших среднего // арифметического int i, k=0; float sr=0;

// sr — среднее арифметическое элементов массива for (i = 0; i < N; i++).

{.

scanf («%d», &x[i]); // ввод и суммирование.

// очередного элемента.

sr + = х[i];

}.

sr /= N; // вычисление среднего арифметического for (i = 0; i < N; i++).

// сравнение очередного элемента со средним // арифметическим if (x[i] < sr).

{.

// обнуление элементов, меньших среднего // арифметического х [i] = 0;

k++; // увеличение количества замен.

}.

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

printf («%d «, x[i]); // вывод обновленного массива.

printf («%d %f», k, sr); // вывод количества замен return 0;

Пример 5.6.2

Ввести двумерный массив размером 3×4. Поменять местами первый максимальный и первый минимальный элементы массива. Полученный массив вывести.

#include int main ().

{.

int x[3][4];

int max, imx, jmx, min, imn, jmn, y; for (int i = 0; i < 3; i + +) for (int j = 0; j < 4; j++).

scanf («%d», &x[i][j]); // ввод элементов массива max =x[0][0]; imx = 0; jmx — 0;

/* за максимум принимается первый элемент массива. Запоминается номер строки и столбца, в которых расположен максимум */ min = х[0][0]; imn = 0;

j mn = 0 ;

/* за минимум принимается первый элемент массива. Запоминается номер строки и столбца, в которых расположен минимум */.

for (int i = 0; i < 3; i++) for (int j = 0; j < 4; j++).

// если очередной элемент больше максимума if (х [i] [ j ] > max).

{.

// меняется максимум и его расположение max = x[i][j]; imx = i; jmx = j;

}.

else.

// если очередной элемент меньше минимума if (х [i] [ j ] < min).

{.

// меняется минимум и его расположение min = х[i][j]; imn = i; jmn = j;

}.

у = x[imx][jmx];

// максимальный и минимальный элемент меняются // местами.

x[imx][jmx] = x[imn][jmn]; x[imn][jmn] = у; for (int i = 0; i< 3; i++).

//вывод обновленного массива.

{.

for (int j = 0; j < 4; j++) printf («%d «, x[i][j]); printf (««);

}.

return 0;

}.

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

int х[10]; // х является указателем на первый элемент.

// массива.

int j ;

int * р; р=х;

р =&х[0]; j = х [ 3 ] ;

j = * (р+3).

// эти два оператора.

// приведут к одинаковому результату // эти два оператора.

// приведут к одинаковому результату Дан одномерный массив, состоящий из пяти элементов. Все положительные элементы массива увеличить на 3, остальные уменьшить на 3. Вывести обновленный массив.

#include int main ().

// объявляем и инициализируем массив из пяти элементов int х[] = {5, -10, 15, -20, 25}; int i, *р, *pl;

pi = х; // указатель pi установлен на начало // массива х.

for (р = х; р < pi + 5; р++) // указатель р движется.

//по массиву х.

{.

if (*р>0) // если значение, записанное по // указателю, больше 0 *р = *р + 5; // оно увеличивается на 5 else.

*р ⁼ *Р ~ 5; // иначе уменьшается на 5.

}.

for (р = х; р < pl + 5; р++) printf («%d «, *р); return 0;

Различают статическое и динамическое выделение памяти.

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

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

Для управления динамическим выделением памяти используются функции, прототипы которых прописаны в файле alloc. h и stdlib. h: calloc, malloc, realloc, free.

Функция calloc динамически выделяет блок памяти и инициализирует его нулями. Синтаксис вызова функции: calloc (size_t n, size_t s),.

где n — количество элементов, иод хранение которых выделяется память; s — размер памяти в байтах для хранения одного элемента.

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

int *р;

р = calloc (5, sizeof (int));

выделяется память размером 5−4 = 20 байтов, в случае успешного выделения в р записывается адрес начала выделенного блока.

Функция malloc динамически выделяет блок памяти без инициализации его содержимого. Синтаксис вызова функции:

malloc (size_t s).

где s — размер выделяемого блока в байтах.

Так же, как и функция calloc, malloc возвращает указатель на начало выделенного блока памяти или NULL. Например:

int *р;

р = malloc (5*sizeof (int));

Функция realloc производит перераспределение уже выделенной памяти, увеличивая или уменьшая ее размер. Синтаксис вызова функции:

realloc (void *bl, size_t s).

где bl — указатель на блок предварительно выделенной динамической памяти; s — новый размер блока Ы.

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

Функция free освобождает блок памяти, выделенный функциями calloc, malloc или realloc. Синтаксис вызова функции:

free (void* bl);

где bl — указатель на освобождаемый блок памяти.

Пример 5.6.4.

Ввести динамический массив, состоящий из п элементов. Подсчитать количество элементов массива, меньших среднего арифметического.

#include.

#include int main () int n;

scanf («%d», &n); // ввод количества элементов.

int i, k = 0; float sr = 0;

// динамическое выделение памяти int *x = (int *) calloc (n, sizeof (int)); if (x) // если память выделилась успешно.

{.

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

{.

scanf («%d», &x[i]); // ввод очередного элемента sr += x[i]; // добавление элемента к сумме.

}.

sr /= n; // вычисление среднего арифметического for (i = 0; i < n; i++) if (x[i] < sr).

{.

k++; // подсчет количества элементов, меньших // среднего арифметического.

}.

printf<" % f %d", sr, k); // вывод результатов.

free (x);

}.

else.

printf («memory error «); // вывод сообщения об.

// ошибке выделения памяти.

return 0;

Пример 5.6.5

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

#include ttinclude int main{).

{.

int i, n, m, k, r;

scanf («%d», &n); // ввод количества элементов массива int *х = (int *)malloc (n*sizeof (int));

// динамическое выделение памяти для хранения массива if (х).

{.

for (i = 0; i.

scanf («%d», &x[i]); // ввод очередного элемента.

// массива.

1; i.

// элемента.

m = х [ 0 ]; к = 0; for (i = if (x[i]>m).

// и его места в массиве.

{.

m = х [ i ]; к = i;

}.

г = x [ 0 ] ;

for (i = 1; i < n; i++) // нахождение.

// минимального элемента.

if (x [ i ] < r) r = x [ i ] ;

// переопределение выделенной для хранения // массива памяти х = (int *) realloc (х, (n+m-r)*sizeof (int));

if (x) // если память выделена успешно.

{.

for (i = 0; i.

// элементы массива, расположенные после // максимального, сдвигаются вправо for (i = k+1; i.

// добавление в массив нулей x[i] = 0;

// вывод обновленного массива for < n+m-r; i++) printf («%d «, x[i]); free (x); // освобождение памяти

}

else

printf («memory error «);

}

else

printf («memory error «); return 0;

_}_

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

Пример 5.6.6

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

#include.

#include int main<).

{.

int n, m, s=0; int i, j;

int **x; // x — указатель на указатель.

scanf («%d %d», &n, &m) ;

// выделение памяти под хранение указателей х = (int **)calloc (n, sizeof (int)); for (i = 0; i < n; i + +).

{.

// выделение памяти под хранение каждой строки // массива.

x[i] = (int *)calloc (m, sizeof (int)); for (j = 0; j < m; j++).

{.

scanf («%d», &x (i][j]); s += x [ i ] [ j ] ;

}.

}.

printf («%f», (float)s/n*m); free (x); return 0;

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

Пример 5.6.7.

Листинг из примера 5.6.6 с представлением двумерного массива как одномерного выглядит так: ttinclude.

#include int main ().

{.

int n, m, s=0; int i, j; int *x;

scanf («%d %d», &n, &m) ;

// выделение памяти под хранение всего массива х = (int *)calloc (n*m, sizeof (int)); for (i = 0; i < n; i + +).

{.

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

{.

scanf («%d», &x[i*n+j]); // использование.

// пересчитанных.

s += x[i*n+j]; // индексов массива.

).

).

printf («%f», (float)s/n*m); free (x); return 0;

• [1] 1,2,3},{4,5,6,7,8},{9,10,11