Лекція 5 (Масиви)
.docxМАСИВИ
Основні поняття
Між покажчиками і масивами існує тісний взаємозв'язок. Будь-яка дія над елементами масивів, що досягається індексуванням, може бути виконана за допомогою покажчиків (посилань) і операцій над ними. Варіант програми з покажчиками буде виконаний швидше, але для розуміння він складніший. Як показує практика роботи на Сі, покажчики рідко використовуються зі скалярними змінними, а частіше - з масивами. Покажчики дають можливість застосовувати адреси приблизно так, як це робить ЕОМ на машинному рівні. Це дозволяє ефективно організувати роботу з масивами. Будь-яку серйозну програму, що використовує масиви, можна написати за допомогою покажчиків.
У повсякденному житті постійно доводиться стикатися з однотипними об'єктами. Як і багато інших мов високого рівня, С++ надає програмісту можливість роботи з наборами однотипних даних - масивами. Окрема одиниця таких даних, що входять в масив, називається елементом масиву. В якості елементів масиву можуть виступати дані будь-якого типу, а також покажчики на однотипні дані. Оскільки всі елементи масиву мають один тип, вони мають однаковий розмір.
Для роботи з масивом необхідно:
-
визначити параметри масиву: ім'я масиву, його розмірність (кількість вимірів) і розмір - кількість елементів масиву;
-
виділити ОП для його розміщення. З точки зору виділення пам’яті у мові Сі визначають масиви даних:
-
статичні: з виділенням ОП до початку виконання функції; ОП виділяється в стеку або в ОП для статичних даних;
-
динамічні: ОП виділяється з купи в процесі виконання програми, за допомогою функцій malloc() і calloc(). Динамічні масиви використовують, якщо розмір масиву невідомий до початку роботи програми і визначається в процесі її виконання, наприклад за допомогою обчислення або введення.
Розмір масиву визначається так:
1. Для статичних масивів при його оголошенні; ОП виділяється до початку виконання програми: ім'я масиву - покажчик-константа, а кількість елементів масиву визначається:
-
явно; наприклад:
int а[5]; або float Array [20];
-
неявно, при ініціалізації елементів масиву; наприклад:
int а[] = {1,2,3};
2. Для динамічних масивів у процесі виконання програми; ОП для них запитується і виділяється динамічно, з купи: ім'я покажчика на масив - це змінна.
Розмір масиву можна не вказувати. В цьому разі необхідно вказати порожні квадратні дужки:
-
якщо при оголошенні ініціалізується значення його елементів; наприклад:
static int а[] = {1, 2, 3};
char b[] = "Відповідь:";
-
для масивів - формальних параметрів функцій; наприклад:
int fun1(int a[], int n);
int fun2(int b[k][m][n]);
-
при посиланні на раніше оголошений зовнішній масив; наприклад:
int а[5]; /* оголошення зовнішнього масиву */
main ()
{
extern int а[]; /*посилання на зовнішній масив */
}
Масиви бувають одновимірними та багатовимірними.
Одновимірні масиви
Для одновимірного масиву при оголошенні
short massiv [20];
в пам'яті буде зарезервовано місце для розміщення двадцяти цілочисельних елементів. Елементи масиву в пам'яті розташовуються безпосередньо один за одним. На рис. 1 показано розташування одновимірного масиву двобайтових елементів (типу short) в пам'яті.
… |
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
Зайнята область пам’яті |
0-й ел-т масиву |
1-й ел-т масиву |
2-й ел-т масиву |
3-й ел-т масиву |
|
|
|
(N-2) -й ел-т масиву |
(N-1) -й ел-т масиву |
|||||||||||||||
|
||||||||||||||||||||||||
Молодші адреси |
|
|
|
|
|
|
Старші адреси |
|||||||||||||||||
|
||||||||||||||||||||||||
Напрям збільшення адрес пам’яті |
||||||||||||||||||||||||
Рисунок 1 – Одновимірний масив в пам’яті |
Звернення до елементів масиву може здійснюватися одним із двох способів:
-
за номером елементу в масиві (через його індекс);
-
за покажчиком.
При ініціалізації масивів дотримуються таких правил.
-
Значення, що ініціалізують, заключають у фігурні дужки:
int Temp[12]={2,4,7,11,12,12,13,12,10,8,5,1};
-
Якщо в списку ініціалізації значень зазначено менше, ніж оголошено в розмірі масиву, має місце часткова ініціалізація. У цьому випадку іноді після останнього значення в виразі для ініціалізації для наочності ставлять кому. Наприклад:
int m1[5] = {0,1,2,3,}, m2[10] = {0};
-
При оголошенні одновимірного масиву з одночасною його ініціалізацією дозволяється опускати значення розміру, зазвичай вказане вище в квадратних дужках. При цьому компілятор самостійно підрахує кількість елементів у списку ініціалізації і виділить під них необхідну область пам'яті:
// Виділення в пам'яті місця для шести об'єктів типу int 64 байта
int Even [] = {0, 2, 4, 6, 8, 10};
-
Якщо далі в програмі буде потрібно визначити, скільки елементів є у масиві, можна скористатися наступним виразом:
int Size = sizeof(Even)/sizeof(Even [0]);
Тут вираз sizeof(Even) визначає загальний розмір, займаний масивом Even в пам'яті (в байтах), а вираз sizeof (Even [0]) повертає розмір (теж в байтах) одного елемента масиву.
-
Масив типу char (рядок) може бути ініціалізований двома способами:
char str1[] = {'a', 'b', 'c', '\0'};
char str2[] = "abc";
Під рядки str1 і str2 буде відведено по 4 байти. Рядок str2 буде автоматично доповнена нульовим байтом.
-
У багатомодульному проекті ініціалізація масиву при оголошенні здійснюється лише в одному з модулів. В інших модулях отримати доступ до елементів масиву можна за допомогою ключового слова extern:
// Модуль first.cpp
char Hello[] = {'H','e','l','l','o'};
// Модуль second.cpp
extern Hello[];
// Модуль n.cpp
extern Hello[5];
Спроба повторної ініціалізації викличе повідомлення компілятора про помилку.
При зверненні через індекс за ім'ям масиву в квадратних дужках вказується номер елемента, до якого потрібно виконати доступ. Слід пам'ятати, що в С++ елементи масиву нумеруються, починаючи з 0. Перший елемент масиву має індекс 0, другий - індекс 1 і т.д. Таким чином, запис типу:
x = Array [13];
у = Array [19];
виконає привласнення змінній x значення 14-го елемента, а змінної у - значення 20-го елемента масиву.
Доступ до елементів масиву через покажчики полягає в наступному. Ім'я оголошеного масиву асоціюється компілятором з адресою його самого першого елементу (з індексом 0). Таким чином, можна привласнити покажчику адресу нульового елемента, використовуючи ім'я масиву:
charArrayOfChar [] = {'W', 'O', 'R', 'L', 'D'};
char * pArr = ArrayOfChar; // PArr вказує на ArrayOfChar[0] ('W')
Розіменовуючи покажчик pArr, можна отримати доступ до вмісту ArrayOfChar[0]: char Letter = * pArr;
Оскільки в С++ покажчики і масиви тісно взаємопов'язані, збільшуючи або зменшуючи значення покажчика на масив, програміст отримує можливість доступу до всіх елементів масиву шляхом відповідної модифікації покажчика:
pArr+=3; // PArr вказує на ArrayOfChar[3] {'L *)
pArr++; // PArr вказує на ArrayOfChar[4] ('D')
char Letter=*pArr; // Letter = 'D';
Таким чином, після проведених арифметичних операцій покажчик pArr буде посилатися на елемент масиву з індексом 4. До цього ж елементу можна звернутися іншим способом:
Letter = *(ArrayOfChar+4); // Еквівалент Letter = ArrayOfChar [4];
Присвоєння значень одного масиву значень іншого масиву виду
Array[] = Another[]
або
Array = Another
неприпустимо, тому що компілятор не може самостійно скопіювати всі значення одного масиву в значення іншого. Для цього програмісту необхідно робити певні дії (при доступі до елементів з індексом найчастіше використовується циклічне присвоєння). Оголошення виду
char (* Array)[10];
визначає покажчик Array на масив з 10 символів (char). Якщо ж опустити дужки, компілятор зрозуміє запис як оголошення масиву з 10 покажчиків на тип char. Розглянемо приклад використання масиву.
# іnclude <iostream.h>
int main ()
{ // Оголошення цілочисельного масиву з 5 елементів:
short Number [5];
char endl = '\n';
// Заповнення всіх елементів масиву У циклі
for (int i=0; i<5; i++)
Number [i]= ;
// Виведення вмісту з 3-го пo 5-й елемент
for (int i-2; i<5; i++)
cout << Number[i]<< endl;
return 0;
}
Приклад оголошення масиву:
int а[10];
іnt *p = а; /* - р одержує значення а */
При цьому компілятор виділяє масив в стеку ОП розміром
(sizeof(Type)* розмір-масиву ) байтів.
У вищенаведеному прикладі це 2 * 10 = 20 байтів. Причому а - покажчик-константа, адреса початку масиву, тобто його нульового елемента, р - змінна; змінній р можна присвоїти значення одним із способів:
р = а;
р = &а[0];
р = &a[i];
де &а[i] = (а + i) - адреса і-елемента масиву.
Відповідно до правил перетворення типів значення адреси i-елемента масиву на машинному рівні формується таким чином:
&а[i]=а+i*sizeof(int);
Справедливі також наступні співвідношення:
&a=a+0=&a[0] - адреса а[0] - нульового елемента масиву;
а+2 = &а[2] - адреса а[2] - другого елементи масиву;
а+i = &a[i] - адреса a[i] - i-гo елемента масиву;
*а=*(а+0)=*(&а[0])=a[0] - значення 0-ого елемента масиву;
*(а+2) = а[2] - значення а[2] - другого елементи масиву;
*(а+i) = а[i] - значення a[i] - i-гo елемента масиву;
*а+2 = а[0]+2 - сума значень а[0] і 2.
Якщо р - покажчик на елементи такого ж типу, які і елементи масиву a та p=а, то а та р взаємозамінні; при цьому:
p = &a[0] = a+0;
p+2 = &a[2] = a+2;
*(p+2) = (&a[2]) = a[2] = p[2];
*(p+i) = (&a[i]) = a[i] = p[i];
Для a та p еквівалентні всі звертання до елементів a у вигляді:
a[i], *(a+i), *(i+a), i[a], та
p[i], *(p+i), *(i+p), i[p]
Багатовимірні масиви
Двовимірний масив (матриця) можна представити як одновимірний масив, кожний елемент якого – масив. Тривимірний масив - це масив, кожний елемент якого являє двовимірну матрицю.
Приклади оголошення багатовимірних масивів:
char Matrix2D[6][9]; // Двовимірний масив 6x9 елементів
unsigned long Arr3D[4][2][8]; // Тривимірний
// Масив 7-й ступеня мірності
int Massiv[22][16][7][47][345][91][3];
Розміщення в пам’яті двовимірного масиву Mas[n][m]:
Напрям збільшення індексу n
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|||
1 |
|
|
|
|
|
|
|
|
|
||||||
2 |
|
|
|
|
|
|
|
|
|
||||||
3 |
|
|
|
|
|
|
|
|
|
||||||
4 |
|
|
|
|
|
|
|
|
|
||||||
5 |
|
|
|
|
|
|
|
|
|
||||||
6 |
|
|
|
|
|
|
|
|
|
||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
||||
|
Напрям збільшення індексу m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
Багатовимірні масиви ініціалізуються в порядку якнайшвидшого зміни самого правого індексу (задом наперед): спочатку відбувається присвоєння початкових значень всіх елементів останнього індексу, потім попереднього і т.д. до самого початку:
int Mass[3][2][4] = {1,2,3,4,5,6,7,8,9,10,11,12,
13,14,15,16,17,18,19,20,21,22,23,24};
Щоб не заплутатися, для наочності можна групувати дані за допомогою проміжних фігурних дужок:
int Mass[3][2][4] = {{{l,2,3,4}, {5,6,7,8}},
{{9,10,ll,12},{13,14,15,16}},
{{17,18,19,20},{21,22,23,24}};
Для багатовимірних масивів при ініціалізації дозволяється опускати лише величину першої розмірності:
int main()
{
char x[][3]={{9,8,7},{6,5,4},{3,2,1}};
for(int i=0; i<3; i++)
{ for(int j=0; j<3; j++)
printf("%d ", (int)x[i][j]);
printf("\n");
}
return 0;
}
На початку роботи програми в пам'яті резервується місце для дев'яти однобайтних елементів (тип char) із заповненням масиву в порядку проходження байт ініціалізації:
Далі за допомогою вкладеного циклу здійснюється виведення значень масиву: зовнішній цикл for перебирає рядки вихідної матриці, в той час як внутрішній цикл виводить значення масиву по стовпцях. В результаті на екрані буде відображено:
9 8 7
6 5 4
3 2 1
Доступ до елементів багатовимірного масиву через покажчики здійснюється дещо складніше. Оскільки, наприклад, двовимірний масив Matrix[x][у] може бути представлений як одновимірний (Matrix[x]), кожен елемент якого також є одновимірним масивом (Matrix[y]), покажчик на двовимірний масив pMtrx, посилаючись на елемент масиву Matrix[x][у], по суті, вказує на масив Matrix[y] у масиві Matrix[x].
Таким чином, для доступу до вмісту комірки покажчик pMtrx доведеться розіменовувати двічі.
int main()
{
char ArrayOfChar[3][2]={'W','O','R','L','D','!'};
char *pArr=(char *)ArrayOfChar;
pArr+=3;
char Letter=*pArr;
cout << Letter;
return 0;
}
У наведеному прикладі оголошується масив символів розмірністю 3 x 2 і покажчик pArr на нього (фактично - покажчик на ArrayOfChar[0][0]). У рядку
char *pArr = (char *)ArrayOfChar;
ідентифікатор ArrayOfChar вже є покажчиком на елемент з індексом 0, однак, оскільки масив двовимірний, потрібно його повторне розіменування. Збільшення pArr на 3 призводить до того, що він вказує на елемент масиву, значення якого - символ 'L' (елемент ArrayOfChar[1][1]). Далі здійснюється виведення вмісту комірки масиву, на яку вказує pArr.
Поняття покажчика на масив розглянемо на прикладі двовимірного цілочисельного масиву m.
int * p1;
int (* p2) [4];
p1 - це покажчик на об'єкт цілого типу, йому може бути присвоєно адресу будь-якого елементу матриці m. Наприклад, адреса 0-го елемента 1-го рядка можна привласнити трьома еквівалентними способами:
p1 = &m[1][0]; p1 = m[1]; p1=*(m+1);
p2 - це покажчик на масив з чотирьох цілочисельних елементів і йому може бути присвоєно адресу будь-якого рядка матриці, наприклад:
p2 = m+1;
Відповідно, оператор
p1++;
викликає перехід до наступного елемента 1-го рядка, а оператор
p2++;
викликає перехід до наступного рядка матриці. Тоді *p1=6, а **p2=9.
Інтерпретація складних декларацій.
У деклараціях зазвичай використовується ім'я (ідентифікатор) і один з модифікаторів *, [] і (), причому дозволяється використовувати більше одного модифікатора в одній декларації. Для розкриття цих декларацій застосовуються наступні правила:
-
Чим ближче модифікатор стоїть до ідентифікатора, тим вище його пріоритет.
-
Пріоритет () і [] вище, ніж пріоритет *.
-
Пріоритет підвищується взяттям у дужки ().
Приклади:
int matrix[10][10]; |
matrix – масив масивів типу int |
char **argv; |
argv – покажчик на покажчик на char |
int (*ip)[10]; |
ip – покажчик на масив з 10 елементів типу int |
int *ip[10]; |
ip - 10-елементний масив покажчиків на int |
int *ipp[3][4]; |
ipp - 3-елементный масив покажчиків на 4-елементний масив типу int |
int (*ipp)[3][4]; |
ipp – покажчик на 3-елементний масив, кожний елемент якого - 4-елементний масив типу int |