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

Масив, базовият тип на който е едномерен масив, се нарича двумерен. Масив, базовият тип на който е двумерен масив, се нарича тримерен и т.н. На практика се използват масиви с размерност най-много 3.

Задаване на многомерни масиви

Нека Т e име или дефиниция на произволен тип, различен от псевдоним, void и функционален, size1, size2, …, sizen (n>1 е дадено цяло число) са константни изрази от интегрален или изброен тип с положителни стойности. T[size1][size2] … [sizen] е тип n-мерен масив от тип T. T се нарича базов тип за типа масив.
Примери:
int [5][3] е двумерен масив от тип int;
double [4][5][3] е тримерен масив от тип double;

Множество от стойности

Множеството от стойности на типа T[size1][size2] … [sizen] се състои от всички редици от по size1 елемента, които са произволни константи от тип T[size2] … [sizen]. Достъпът до елементите на редиците е пряк и се осъществява с помощта на индекс, като достъпът до първия елемент се осъществява с индекс със стойност 0, до последния – с индекс със стойност size1-1, а до всеки от останалите елементи – с индекс със стойност с 1 по-голяма от тази на индекса на предишния елемент. Елементите от множеството от стойности на даден тип многомерен масив са константите на този тип масив.
Примери:
1. Множеството от стойности на типа int[5][3] се състои от всички редици от по 5 елемента, които са едномерни масиви от тип int[3]. Достъпът до елементите на редиците се осъществява с индекс със стойности 0, 1, 2, 3 и 4.

0 1 2 0 1 2 0 1 2

int[5][3]




0 1 4

2. Множеството от стойности на типа double[4][5][3] се състои от всички редици от по 4 константи от тип double[5][3]. Достъпът до елементите на редиците се осъществява с индекс със стойности 0, 1, 2 и 3.

double[4][5][3]




0 1 2 3
където с констi (i = 0, 1, 2, 3) е означена произволна константа от тип double[5][3].
Променлива величина, множеството от допустимите стойности на която съвпада с множеството от стойности на даден тип масив, се нарича променлива от дадения тип масив или само масив. Фиг. 3 дава обобщение на синтаксиса на дефиницията на променлива от тип масив.


<дефиниция_на_променлива_от _тип_многомерен_масив> ::=
T <променлива>[size1][size2] … [sizen]; |
T <променлива>[size1][size2]…[sizen]
= {<редица_от_константи_от_ти T1>};|
T <променлива>[size1][size2]…[sizen]
= {<редица_от_константи_от_ти T>};

където
Т e име или дефиниция на произволен тип, различен от псевдоним, void и функционален;
Т1 е име на типа T[size2]…[sizen];
size1, size2, …sizen са константни изрази от интегрален или изброен тип със положителни стойности;
<променлива> ::= <идентификатор>
<редица_от_константи_от_ти T1> ::= <константa_от_тип Т1>|
<константа_от_тип Т1>, <редица_от_константи_от_ти Т1>
а <редица_от_константи_от_ти Т> се определя по аналогичен начин.


Фиг. 3.

Примери:
int x[10][20];
double y[20][10][5];
int z[3][2] = {{1, 3},
{5, 7},
{2, 9}};
int t[2][3][2] = {{{1, 3}, {5, 7}, {6, 9}},
{{7, 8}, {1, 8}, {-1, -4}};

Фрагментите
<променлива>[size1][size2] … [sizen],
<променлива>[size1][size2]…[sizen] ={<редица_от_константи_от_ти T1>}
<променлива>[size1][size2]…[sizen] ={<редица_от_константи_от_ти T>};
от дефиницията от Фиг. 3, могат да се повтарят. За разделител се използва символът запетая.
Примери:
int a[3][4], b[2][3][2] = {{{1, 2}, {3, 4}, {5, 6}},
{{7, 8}, {9, 0}, {1, 2}}};
double c[2][3] = {1, 2, 3, 4, 5, 6}, d[3][4][5][6];

При дефиницията с инициализация, от Фиг. 3., е възможно size1 да се пропусне. Тогава за стойност на size1 се подразбира броят на редиците от константи на най-външно ниво, изброени при инициализацията.
Пример: Дефиницията
int s[][2][3] = {{{1,2,3}, {4, 5, 6}},
{{7, 8, 9}, {10, 11, 12}},
{{13, 14, 15}, {16, 17, 18}}};
е еквивалентна на
int s[3][2][3] = {{{1,2,3}, {4, 5, 6}},
{{7, 8, 9}, {10, 11, 12}},
{{13, 14, 15}, {16, 17, 18}}};
Ако изброените константни изрази в инициализацията на ниво i са по-малко от sizei, останалите се инициализират с нулеви стойности.
Примери: Дефиницията
int fi[5][6] = {{1, 2}, {5}, {3, 4, 5},
{2, 3, 4, 5}, {2, 0, 4}};
е еквивалентна на
int fi[5][6] = { {1, 2, 0, 0, 0, 0},
{5, 0, 0, 0, 0, 0},
{3, 4, 5, 0, 0, 0},
{2, 3, 4, 5, 0, 0},
{2, 0, 4, 0, 0, 0}};
Вложените фигурни скобки не са задължителни. Следното инициализиране
int ma[4][3] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
е еквивалентно на
int ma[4][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}};
но е по-неясно.
Следващата дефиниция
int ma[4][3] = {{0}, {1}, {2}, {3}};
е еквивалентна на
int ma[4][3] = {{0, 0, 0 }, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}};
и е различна от
int ma[4][3] = {0, 1, 2, 3};
която пък е еквивалентна на
int ma[4][3] = {{0, 1, 2}, {3, 0, 0}, {0, 0, 0}, {0, 0, 0}};

Инициализацията е един начин за свързване на променлива от тип масив с конкретна константа от множеството от стойности на този тип масив. Друг начин предоставят т.нар. индексирани променливи. С всяка променлива от тип масив е свързан набор от индексирани променливи. Фиг. 4. обобщава техния синтаксис.


<индексирана_променлива> ::=
<променлива_от_тип_масив>[<индекс1>][<индекс2>][<индексn>]
където
<индексi> e израз от интегрален или изброен тип.
Всяка индексирана променлива е от базовия тип.


Фиг. 4.

Примери:
1. С променливата x, дефинирана по-горе, са свързани индексираните променливи
x[0][0], x[0][1], …, x[0][19],
x[1][0], x[1][1], …, x[1][19],
…
x[9][0], x[9][1], …, x[9][19],
които са от тип int.
2. С променливата y са свързани следните реални индексирани променливи:
y[i][0][0], y[i][0][1], …, y[i][0][4],
y[i][1][0], y[i][1][1], …, y[i][1][4],
…
y[i][9][0], y[i][9][1], …, y[i][9][4],
за i = 0, 1, …, 19.
Дефиницията на променлива от тип многомерен масив не само свързва променливата с множеството от стойности на указания тип, но и отделя 4B памет, в която записва адреса на първата индексирана променлива на масива. Останалите индексирани променливи се разполагат последователно след първата по по-бързото нарастване на по-далечните си индекси. За всяка индексирана променлива се отделя толкова памет, колкото базовият тип изисква. Следващият пример илюстрира по-подробно представянето.
Пример:
ОП
x


x[0] x[0][0] x[0][1] … x[0][19]
- - -

x[1] x[1][0] x[1][1] … x[1][19] …
- - -

x[9] x[9][0] x[9][1] … x[9][19]
- - -
като за всяка индексирана променлива са отделени 4B ОП, които са с неопределено съдържание, тъй като x не е дефинирана с инициализация. Освен това, чрез индексираните променливи x[0], x[1], ..., x[9] могат да се намерят адресите на x[0][0], x[1][0], ..., x[9][0] съответно, т.е.
cout << x[0] << x[1] << ... << x[9];
ще изведе адресите на x[0][0], x[1][0], ... и x[9][0].

Забележка: Двумерните масиви разполагат в ОП индексираните си променливи по по-бързото нарастване на втория индекс. Това физическо представяне се нарича представяне по редове. Тези масиви могат да бъдат използвани за реализация и работа с матрици и др. правоъгълни таблици.
Важно допълнение: При работа с масиви трябва да се има предвид, че повечето реализации не проверяват дали стойностите на индексите са в рамките на границите, зададени при техните дефиниции. Тази особеност крие опасност от допускане на труднооткриваеми грешки.

Често допускана грешка: В Паскал, Ада и др. процедурни езици, индексите на индексираните променливи се ограждат само в една двойка квадратни скобки и се отделят със запетаи. По навик, при програмиране на C++, често се използва същото означение. Това е неправилно, но за съжаление не винаги е съпроводено със съобщение за грешка, тъй като в езика C++ съществуват т.нар. comma-изрази. Използвахме ги вече в заглавните части на оператора за цикъл for. Comma-изразите са изрази, отделени със запетаи. Стойността на най-десния израз е стойността на comma-израза. Операцията за последователно изпълнение запетая е лявоасоциативна. Така 1+3, 8, 21-15 е comma-израз със стойност 6, а [1, 2] е comma-израз със стойност [2]. В C++ ma[1,2] означава адреса на индексираната променлива ma[2][0] (индексът [0] се добавя автоматично).

Задачи върху многомерни масиви

Задача 55. Да се напише програма, която въвежда елементите на правоъгълна матрица a[nxм] и намира и извежда матрицата, получена от дадената като всеки от нейните елементи е увеличен с 1.

Програма Zad55.cpp решава задачата.
Program Zad55.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[10][20];
// въвеждане на броя на редовете на матрицата
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 10)
{cout << "Incorrect input! \n";
return 1;
}
// въвеждане на броя на стълбовете на матрицата
cout << "m= ";
int m;
cin >> m;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (m < 1 || m > 20)
{cout << "Incorrect input! \n";
return 1;
}
// въвеждане на матрицата по редове
int i, j;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= m-1; j++)
{cout << "a[" << i << ", " << j << "]= ";
cin >> a[i][j];
if (!cin)
{cout << "Error, Bad Input! \n";
return 1;
}
}
// конструиране на нова матрица b
int b[10][20];
for (i = 0; i <= n-1; i++)
for (j = 0; j <= m-1; j++)
b[i][j] = a[i][j] + 1;
// извеждане на матрицата b по редове
for (i = 0; i <= n-1; i++)
{for (j = 0; j <= m-1; j++)
cout << setw(6) << b[i][j];
cout << '\n';
}
return 0;
}

Забележка: За реализиране на операциите извеждане и конструиране се извърши обхождане на елементите на двумерен масив по редове.

Задача 56. Да се напише програма, която намира и извежда сумата от елементите на всеки стълб на квадратната матрица a[nxn].

Програма Zad56.cpp решава задачата. В нея въвеждането на матрицата и нейната размерност са пропуснати, тъй като са аналогични на тези от Zad55.cpp.
Program Zad56.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[10][10];
int n;
…
int i, j;
for (j = 0; j <= n-1; j++)
{int s = 0;
for (i = 0; i <= n-1; i++)
s += a[i][j]; // s = s + a[I][j]
cout << setw(10) << j << setw(10) << s << "\n";
}
return 0;
}
Реализирано е обхождане на масива по стълбове (първият индекс се изменя по-бързо).

Задача 57. Да се напише програмен фрагмент, който намира номерата на редовете на целочислената квадратна матрица a[nxn], в които има елемент, равен на цялото число x.
…
for (i = 0; i <= n-1; i++)
{j = -1;
do
j++;
while (a[i][j] != x && j < n-1);
if (a[i][j] == x) cout << setw(5) << i << '\n';
}
…
Фрагментът реализира последователно обхождане на всички редове на матрицата и за всеки ред проверява дали съществува елемент, равен на дадения елемент x.

Задача 58. Да се напише програмен фрагмент, който обхожда кватратната матрица a[nxn] по диагонали, започвайки от елемента a00, както е показано по-долу:
a00 a01 a02 … a0,n-1
a10 a11 a12 … a1,n-1
…
an-1,0 an-1,1 an-1,2 … an-1,n-1

…
int k;
for (k = 0; k <= n-1; k++)
{for (i = k; i >= 0; i--)
cout << "(" << i << ", "<< k-i << ") ";
cout << '\n';
}
for (k = n; k <= 2*n-2; k++)
{for (i = n-1; i >= k-n+1; i--)
cout << "(" << i << ", "<< k-i << ") ";
cout << '\n';
}
…

Задача 59. Да се напише програмен фрагмент, който обхожда кватратната матрица a[nxn] по диагонали, започвайки от елемента an-1,0, както е показано по-долу:

a00 a01 a02 … a0,n-1
a10 a11 a12 … a1,n-1
…
an-2,0 an-2,1 an-2,2 … an-2,n-1
an-1,0 an-1,1 an-1,2 … an-1,n-1

…
int k;
for (k = n-1; k >= 0; k--)
{for (i = k; i <= n-1; i++)
cout << "(" << i << ", "<< i-k << ") ";
cout << '\n';
}

for (k = -1; k >= 1-n; k--)
{for (i = 0; i <= n+k-1; i++)
cout << "(" << i << ", "<< i-k << ") ";
cout << '\n';
}
…

Задача 60. Да се напише програма, която:
а) въвежда по редове елементите на квадратната реална матрица A с размерност n x n;
б) от матрицата A конструира редицата B: b0, b2,..., bm-1, където m = n.n, при което първите n елемента на B съвпадат с елементите на първия стълб на A, вторите n елемента на B съвпадат с елементите на втория стълб на A и т.н., последните n елемента на B съвпадат с елементите на последния стълб на A;
в) сортира във възходящ ред елементите на редицата B;
г) образува нова квадратна матрица A с размерност n x n, като елементите от първия ред на A съвпадат с първите n елемента на B, елементите от втория ред на A съвпадат с вторите n елемента на B и т.н. елементите от n - тия ред на A съвпадат с последните n елемента на B;
д) извежда по редове новата матрица A.

Програма Zad60.cpp решава задачата.

Program Zad60.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[10][10];
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 10)
{cout << "Incorrect input! \n";
return 1;
}
// въвеждане на масива a
int i, j;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= n-1; j++)
{cout << "a[" << i<< "][" << j << "]= ";
cin >> a[i][j];
}
// извеждане на елементите на a по редове
for (i = 0; i <= n-1; i++)
{for (j = 0; j <= n-1; j++)
cout << setw(5) << a[i][j];
cout << "\n";
}
// развиване на матрицата a по стълбове
int b[100];
int m = -1;
for (j = 0; j <= n-1; j++)
for (i = 0; i <= n-1; i++)
{m++;
b[m] = a[i][j];
}
m++; // m е броя на елементите на редицата b
// извеждане на редицата b
for (i = 0; i <= m-1; i++)
cout << setw(5) << b[i];
cout << '\n';
// сортиране на b по метода на пряката селекция
for (i = 0; i <= m-2; i++)
{int k = i;
int min = b[i];
for (j = i+1; j <= m-1; j++)
if (b[j] < min)
{min = b[j];
k = j;
}
int x = b[i]; b[i] = b[k]; b[k] = x;
}
// извеждане на сортираната b
for (i = 0; i <= m-1; i++)
cout << setw(5) << b[i];
cout << '\n';
// конструиране на новата матрица a
m = -1;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= n-1; j++)
{m++;
a[i][j] = b[m];
}
// извеждане на матрицата a
for (i = 0; i <= n-1; i++)
{for (j = 0; j <= n-1; j++)
cout << setw(10) << a[i][j];
cout << '\n';
}
return 0;
}