Двумерные массивы. Задачи поиска, замены и суммирования элементов двумерного массива

 

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

 

Теоретические сведения

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

Двумерные массивы состоят из строк и столбцов.

Объявление двумерных массивов

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

Тип ИмяМассива[ВыражениеТипаКонстанты][ВыражениеТипаКонстанты];

или

Тип ИмяМассива[][];

ИмяМассива – идентификатор массива.

Тип – тип элементов объявляемого массива. Элементами массива не могут быть функции и элементы типа void.

ВыражениеТипаКонстанты – задает количество элементов (размерность) массива. Выражение константного типа вычисляется на этапе компиляции. Данное константное выражение может быть опущено в случаях если:

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

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

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

Например:

1) int a[100][50];//массив из 100´50 элементов целого типа

2) double d[4][10];// массив из 4´10 элементов типа double

3) int t=5, k=8;

float wer[2*t+k][2*t+k];

//массив из (2*t+k)´(2*t+k) элементов вещественного типа

4) int sample[853][157];

//массив из 853 строк и 157 столбцов, элементы типа int

равносильно объявлению

const int N_max=853,

int M_max=157;

int sample[N_max][M_max];

 

равносильно объявлению

#define N_max 853

#define M_max 157

...

int sample[N_max][M_max];

 

Двумерные массивы располагаются в памяти в порядке быстрого изменения последнего индекса. Так, например, данные двумерного массива (состоящего из 3 строк и 10 столбцов и определенного как float A[3][10];), располагаются следующим образом:

 

Строки	Столбцы
	2 … 9
	A[0][0]	A[0][1] … A[0][9]
	A[1][0]	A[1][1] … A[1][9]
	A[2][0]	A[2][1] … A[2][9]

 

Инициализация двумерных массивов

Двумерные массивы инициализируются так же, как и одномерные.

Например:

int w[3][3]={

//инициализируется целочисленный массив размерностью 3´3

{2, 3, 4} //1-я строка

{3, 4, 8} //2-я строка

{1, 0, 9} //3-я строка

};

 

float w[2][3]={

//инициализируется вещественный массив размерностью 2´3

{2.1, 3.4, 4.5} //1-я строка

{5.0, 6.4, 3.9} //2-я строка

};

равносильно инициализации

float w[][3]={

{2.1, 3.4, 4.5} //1-я строка

{5.0, 6.4, 3.9} //2-я строка

};

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

 

int w[3][5]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

 

int w[3][5]={{1, 2, 3}, {4, 5, 6, 7, 8}, {9, 10, 11}};

 

Обращение к элементам двумерного массива

Обращение к элементам двумерного массива осуществляется так же, как и к элементам одномерного.

ИмяМассива[ВыражениеТипаКонстанты][ВыражениеТипаКонстанты];

или

ИмяМассива[ЗначениеИндекса][ЗначениеИндекса];

Например:

a[0][0] – индекс задается как константа,

d[55][5] – индекс задается как константа,

s[i][j] – индекс задается как переменная,

w[4*p][3+t] – индекс задается как выражение.

 

Определение размера памяти двумерных массивов

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

спецификатор-типа имя_массива [конст_выражение1] [конст_выражение2];

Например,

int a[2][3]; /* представлено в виде матрицы

a[0][0] a[0][1] a[0][2]

a[1][0] a[1][1] a[1][2]*/

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

Байты = sizeof (тип) * конст_выражение1* конст_выражение2

Если мы имеем дело с двумерным массивом B размерности M × N, расположенным в памяти по строкам, то адрес элемента B[i][j] вычисляется по формуле:

адрес(B[i][j]) = адрес(B[0][0]) + (i*N+j)*k

Так как массивы занимают непрерывный участок памяти, то двумерный массив можно рассматривать как одномерный, поэтому обращение к элементу B[i][j] равносильно обращению: B[i*N + j].

Пример 1. Определение размера памяти одномерного массива

#include <iostream.h>

#define v 4

#define p 3

void main() {

const int q=4, r=1;

int i_mas[10][10];

int k=sizeof(i_mas);

cout << "i_mas[10][10] занимает " << k << " байт\n";

 

float f_mas[3][5]={{2.0},{4.5,8.3},{7.0,1.0,5.5,7.8}};

int t=sizeof(f_mas);

cout << "f_mas[3][5]={{2.0},{4.5,8.3},{7.0,1.0,5.5,7.8}}

занимает " << t << " байт\n";

 

double d_mas[2*q-r][2*v/p];

int w=sizeof(d_mas);

cout << "d_mas[2*q-r][2*v/p] занимает " << w << "

байт\n";

 

int r_mas[][3]={{2,5,7},{-4,8,-3},{0,-1,1}};

int g=sizeof(r_mas);

cout << "r_mas[][3]={{2,5,7},{-4,8,-3},{0,-1,1}}

занимает " << g << " байт\n";

}

 

Результат выполнения программы:

i_mas[10][10] занимает 200 байт – 2 байта (тип int) * 10*10 (количество элементов массива)

f_mas[3][5]={{2.0},{4.5,8.3},{7.0,1.0,5.5,7.8}} занимает 60 байт – 4 байта (тип float) * 3*5 (объявленное количество элементов массива)

d_mas[2*q-r] [2*v/p] занимает 112 байт – 8 байта (тип double) * 7*2 (вычисленное через формулу количество элементов массива)

r_mas[][3]={{2,5,7},{-4,8,-3},{0,-1,1}} занимает 18 байт – 2 байта (тип int) * 3*3 (заданное количество элементов массива)

Указатели и двумерные массивы

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

int arr[m][n]:

Адрес (arr[i][j])= Адрес(arr[0][0]) + (i*n+j)*k,

где k – количество байтов, выделяемое для элемента массива (в зависимости от типа).

Указатели на многомерные массивы в языке С++ – это массивы массивов, т.е. такие массивы, элементами которых являются массивы. При объявлении таких массивов в памяти компьютера создается несколько различных объектов. Например, при выполнении объявления двумерного массива:

int arr [4][3]

1) В памяти выделяется участок для хранения значения переменной arr, которая является указателем на массив из четырех указателей.

2) Для этого массива из четырех указателей тоже выделяется память. Каждый из этих четырех указателей содержит адрес массива из трех элементов типа int.

3) Следовательно, в памяти компьютера выделяется четыре участка для хранения четырех массивов чисел типа int, каждый из которых состоит из трех элементов.

Схематично распределение памяти для данного двумерного массива выглядит так:

arr

¯

arr[0] ® arr[0][0] arr[0][1] arr[0][2]

arr[1] ® arr[1][0] arr[1][1] arr[1][2]

arr[2] ® arr[2][0] arr[2][1] arr[2][2]

arr[3] ® arr[3][0] arr[3][1] arr[3][2]

Таким образом, объявление arr[4][3] порождает в программе три разных объекта:

· указатель с идентификатором arr,

· безымянный массив из четырех указателей: arr[0], arr[1], arr[2], arr[3]

· безымянный массив из двенадцати чисел типа int.

1) Для доступа к безымянным массивам используются адресные выражения с указателем arr. Знаем, что доступ к элементам одномерного массива указателей осуществляется с указанием одного индексного выражения в форме arr[2] или *(arr+2).

2) Для доступа к элементам двумерного массива чисел типа int arr[i][j] должны быть использованы следующие выражения:

Например, пусть i=1, j=2, тогда

обращение к элементу arr[1][2]:

· arr[i][j] arr[1][2]=10

· *(*(arr+i)+j) *(*(arr+1)+2)=10

· (*(arr+i))[j] (*(arr+1))[2]=10

Например, с помощью указателя ptr:

int *ptr=arr обращение к элементу arr[1][2]:

· ptr[1*3 + 2]

/*здесь 1 и 2 это индексы используемого элемента,

а 3 это число элементов в строке*/

· ptr[5]

Причем внешне похожее обращение arr[5] выполнить невозможно, так как указателя с индексом 5 не существует.

· *(*(ptr + 1) + 2)

· *(ptr + 1*3 + 2)

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

#include <stdio.h>

#include <conio.h>

void main() {

int i, j;

int t[2][3]; // при вводе обращение с помощью индексов

// можно использовать адресные выражения

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

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

t[i][j]=i+j;

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

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

//при печати рассматриваем имя массива как указатель на начало

printf(" %d ", *(*(t + i) +j));

//или printf(" %d ", (*(t + i))[j]);

}

Пример 3. Демонстрация связи между матрицей и указателем на нее

#include <stdio.h>

void main(){

int i,j;

int t[2][3],*ptr;

ptr=&t[0][0];

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

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

t[i][j]=i+j;

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

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

printf(" %d ", *(ptr+i*3+j));

printf("\n\n");

//С матрицей так делать нельзя

/* for(i=0;i<2;i++)

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

printf(" %d ", *(t + i*3 +j)); */

//Корректная работа с матрицей

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

printf(" %d ", ptr[i]);

printf("\n\n");

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

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

printf(" %d ", ptr[i*3 +j]);

}