© 2006 Бублик В.В. Процедурне програмування. 6. Масиви1 (37) Вшануємо память Dennis MacAlistair Ritchie (September 9, 1941 – October 12, 2011)

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви2 (37) Бублик Володимир Васильович Процедурне програмування C/C++ Лекція 6. Базові поняття програмування. Масиви Лекції для студентів 2 курсу Консультації: вівторок,середа, четвер год., кімн. 204/1, к афедра мультимедійних систем You are welcome! Hamburg, Eppendorf

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви3 (37) Масив Математична точка зору Функція з області індексів у множину значень, наприклад, з множини цілих чисел {1, 2, …, n} до множини дійсних чисел R х: {1, 2, …, n} R Значення масиву для індексу і позначають як х(і) (Фортран, ПЛ/1) або х[i] (Алгол, Паскаль, С) і називають і-м елементом масиву

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви4 (37) Масив Комп'ютерна точка зору Можливість звертатися до цілої ділянки пам'яті за допомогою одного імені х, модифікуючи адресу вмістом індексного регістру IR Звертання до x[і] полягатиме в занесенні на індекс регістр значення і і модифікації ним виконавчої адреси команди move IR, I IR load x

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви5 (37) Модифікація адреси Виходячи із зручності обчислення адреси елемента масиву розмірності n, його перший елемент одержує індекс 0, а останній n-1 Вміст регістру індексуВиконавча адреса 0х 1х n-1x+n-1

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви6 (37) Робота з пам'яттю Пам'ять під масив виділяється один раз при його створенні і повністю звільняється при його видаленні Перерозподілу пам'яті упродовж часу існування масиву не передбачено Вихід індексу за межі масиву не контролюється: залежно від розмірності x[-1000], x[10], x[100], x[10000] … можуть показувати в нікуди

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви7 (37) Різновидності масивів Статичний масив: розмірність визначається сталим виразом і в такий спосіб стає відомою вже на етапі компіляції Динамічний масив: розмірність визначається на етапі виконання програми у момент його створення

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви8 (37) Статичний масив Визначення double x[3]; вводить три елементи пам'яті, розміщені послідовно та пронумеровані, починаючи з 0 x[0], x[1], x[2] Масив заповнений сміттям

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви9 (37) Ініціалізація масивів double x[3]= {0.1, 0.2, 0.3};

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви10 (37) Ініціалізація масивів double x[3]= {0.1, 0.2, 0.3}; cout<<x[0]<<' '<<x[1]<<' '<<x[2]<<endl; cout<<x[3]<<' '<<x[-1]<<' '<<x[100]<<endl; double y[3]= {0.1, 0.2}; // не дуже добре, y[2]? //список ініціалізації коротший, ніж розмірність //(довший не пропустить компілятор) double z[]= {0.1, 0.2, 0.3, 0.4, 0.5}; //розмірність масиву визначається //списком ініціалізації

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви11 (37) Проблеми Хто відповідає за розмірність масиву? cont unsigned int size = 100; Хто слідкує за відповідністю розмірності списку ініціалізації? double x[size] = {1,2,3,4,5}; Хто підраховуватиме кількість елементів у визначенні double z[]= {0.1, 0.2, 0.3, 0.4, 0.5};

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви12 (37) Приклад програми // Скалярний добуток const int n=10; double x[n], y[n]; …// тут масиви ініціалізуються double s = 0; for (int i=0; i<n; ++i) s+=x[i]*y[i];

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви13 (37) Тип елемента масиву Масиви стандартних типів int a[n]; char c[m]; Масиви указників (головним чином для багатомірних масивів) int i=1, j=1, k=1; int *ip[] = {&i, &j, &k}; Але не псевдонімів int &ir[] = {i, j, k};// Error: Чому?

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви14 (37) До речі Чим масив char c[m]; відрізняється від рядка char * pc;

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви15 (37) Двомірні масиви. Розміщення в пам'яті const int m=2, n=3; // особливість позначень double a[m][n]; Двомірні масиви розміщуються рядками 1.a[0][0] 2.a[0][1] 3.a[0][2] 4.a[1][0] 5.a[1][1] 6.a[1][2]

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви16 (37) Змінна з індексом Одномірний масив x[i] Двомірний масив c[i][j] Що б це значило? a[i,j]

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви17 (37) Змінна з індексом Одномірний масив x[i] Двомірний масив c[i][j] Що б це значило? Типова помилка a[i,j] value(a[I,j]) == value (a[(i,j)]) == value(a[j])

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви18 (37) Приклад // Множення матриць const int n=10; double a[n][n], b[n][n], c[n][n]; …// тут масиви ініціалізуються for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) { c[i][j] = 0; for (int k=0; k<n; k++) c[i][j]+=a[i][k]*b[k][j]; }

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви19 (37) Звичайний цикл обробки масиву for (int i=0; i<n; ++i) //do something with x[i] { ………………………………..; //наприклад, cout<<x[i]<<endl; } Далі будуть інші способи організації циклів

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви20 (37) Динамічний масив Визначення масиву за допомогою указника double *px = new double[n]; Тепер n довільний вираз, в тому числі змінний cin>>n; double *px = new double[n]; Розмірність стає відомою лише на етапі виконання

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви21 (37) Спільна поведінка double *px = new double[n]; double x[3]= {0.1, 0.2, 0.3}; Поведінка масиву: px[i]; x[i]; Поведінка указника *(px+i); *(x+i);

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви22 (37) Вихідний код a=b; 0043CDB3 fld qword ptr [b] 0043CDB9 fstp qword ptr [a] a=x[1]; 0043CDBC fld qword ptr [ebp-20h] 0043CDBF fstp qword ptr [a] a=x[i]; 0043CDC2 mov eax,dword ptr [i] 0043CDC5 fld qword ptr x[eax*8] 0043CDC9 fstp qword ptr [a] a=*(x+i); 0043CDCC mov eax,dword ptr [i] 0043CDCF fld qword ptr x[eax*8] 0043CDD3 fstp qword ptr [a]

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви23 (37) Вихідний код a= p[i]; 0043CDFE mov eax,dword ptr [i] 0043CE01 mov ecx,dword ptr [p] 0043CE04 fld qword ptr [ecx+eax*8] 0043CE07 fstp qword ptr [a] a=*(p+i); 0043CE0D mov eax,dword ptr [i] 0043CE10 mov ecx,dword ptr [p] 0043CE13 fld qword ptr [ecx+eax*8] 0043CE16 fstp qword ptr [a]

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви24 (37) Адресна арифметика Для довільного указника або масиву x мають місце тотожності x[i] == *(x+i) &x[i] == x+i

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви25 (37) Ітератори double x[10]; Доступ за індексом: x[i]; x[0], x[1], x[2], …, x[9] double * p = &x; Доступ за указником: *(p+i); *p, *(p+1), *(p+2), …, *(p+9)

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви26 (37) Ітератори double x[10]; Доступ за індексом: x[i]; x[0], x[1], x[2], …, x[9] double * p = &x; Доступ за указником: *(p+i); *p, *(p+1), *(p+2), …, *(p+9) double * itor = p; Доступ за ітератором: *itor ; *itor++, *itor++, *itor++, …, *itor++

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви27 (37) Цикл за ітератором const int n=4; int ia[n]; int *pcurrent = ia; int *const pend = ia +n; while (pcurrent!=pend) cout<< *(pcurrent++) <<endl;

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви28 (37) На замітку Для чого потрібен цикл за ітератором? Для того, щоб звертатися до кожного елементу масиву за указником елементу, а не модифікувати адресу бази індексом Коли його застосовувати? Кожного разу, коли елементи масиву, а в майбутньому також інших структур даних, переглядаються послідовно один за одним NB: Як часто, читаючи книгу, ви зауважуєте номер сторінки, на якій ви знаходитеся?

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви29 (37) Два сценарії обробки динамічного масиву void etude1(size_t n) { // Визначення указника і створення масиву double *array = new double [n]; // Сценарій 1: Цикл з лічильником for (size_t i=0; i<n; i++) cout<<array[i]<< ; cout<<endl; // Видалення масиву delete [] array ; return; }

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви30 (37) Два сценарії обробки динамічного масиву void etude2(size_t n) { double *array = new double [n]; // Сценарій 2: Цикл за ітератором size_t i(0); double * pcurrent = array; double *pend = array+n; while (pcurrent != pend) cout<< (*(pcurrent ++)= i++)<< ; cout<<endl; delete [] array ; return; }

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви31 (37) Правило гарного тону Створенням і знищенням динамічних масивів керує сама програма. Кожному new [] відповідає свій delete [] Операція new int (n) створює один елемент памяті, який ініціалізовано значенням n. Операція delete видаляє один елемент памяті, а саме той, на який показує указник. Якщо цю память було виділено операцією new int [n], то n-1 елементів памяті залишаться «сміттям». Операція delete [] dynar видаляє весь масив.

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви32 (37) Двомірні динамічні масиви int m=sizex, n=sizey; double **ppi; ppi = new double* [m]; for (int i=0; i<m; ++i) ppi[i]= new double[n];

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви33 (37)33 (32) Масиви указників Масив указників цілих int *ppi[] читається як int *(ppi[]) або int **ppi

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви34 (37) Двомірні динамічні масиви (масив масивів) int m=sizex, n=sizey; int **ppi; ppi = new int* [m]; for (int i=0; i<m; ++i) ppi[i]=new int [n];

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви35 (37) Використання масивів 1.Масив, а тим більше масив масивів, завжди служить джерелом помилок в програмі (бо указники!) 2.Краще всього користуватися надійнішими контейнерами для даних, залишивши для масиву роль нижнього поверху, на якому будується реалізація контейнерів

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви36 (37)36 (32) Масиви символів Два способи ініціалізації: Списком: стандартний для всіх масивів char hello[] = {Д, о, б, р, и, д, е, н, ь, !, \0}; за нульовий код відповідає програма Рядком: спеціальний для масиву символів char hello[] = Добридень!; нульовий код вбудує система

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви37 (37) Масиви символів чистий С Обчислення довжини рядка, порівняння двох рядків, копіювання рядків і інші корисні функції size_t strlen (const char *); char * strcpy(char *, const char *); char * strncpy(char *, const char *, size_t); int strcmp (const char *, const char *); char * strcat (char *, const char *); char * strchr (const char *, int ch);// search for char ch char * strstr (const char *, const char * s); //search for s and many other …

© 2006 Бублик В.В. Процедурне програмування. 6. Масиви38 (37) Куди йтимемо далі? 1.Замість масивів символів char * використовуватимемо class string 2.Замість простих масивів С контейнерні класи, наприклад, class vector 3.Указники ховатимемо від користувача в маніпуляторах (інтелектуальних указниках smart pointers)