Динамічний масив

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Додавання нових елементів. У випадку, якщо розмір масиву замалий, створюється новий, вдвічі більший масив, елементам якого присвоюються значення елементів попереднього масиву

Динамічним називають такий масив, розмір якого можна змінювати під час виконання програми. Динамічні масиви надають змогу більш гнучко працювати з даними, оскільки дозволяють вводити довільний розмір.  Для зміни розміру динамічного масиву мова програмування, що підтримує такі масиви, повинна надавати вбудовану функцію чи оператор. В порівняні зі статичним масивом, динамічний не має фіксованого розміру та може задаватись під час виконання програми. Замість використання змінної типу string можна використовувати масив змінних типу char. У задачах пов'язаних з матрицями, матриці записують, як двовимірний масив. В старих комп'ютерах з малою кількістю оперативної пам'яті, а також при операціях з великою кількістю даних існує загроза повного засмічення пам'яті, тому в кінці програми прийнято видаляти масив.

Характеристика[ред.ред. код]

  • Розмірність — кількість індексів елемента (одновимірний, двовимірний, …, багатовимірний)
  • Розмір — загальна кількість елементів у масиві.
  • Логічний розмір — кількість елементів масиву, які містять якесь значення.

Багатовимірні масиви[ред.ред. код]

Багатовимірні масиви — це по-суті масив з масивів. Наприклад, двовимірний масив можна передати через одновимірний масив, кожний елемент якого є масивом. Часто двовимірні масиви використовують, як таблиці. Приклад створення двовимірного масиву мовою програмування C++:

 int N, M;
 cin >> N >> M;          //зчитування змінних(розмірів масиву)
 int **p = new int *[N]; //створення масиву вказівників на одновимірні підмасиви
 for(int i = 0; i < N; i++)
 {
     p[i] = new int[M];  // створення одновимірного підмасиву
 }
 
 //Операції над масивом
 // . . .
 
 for(int i = 0; i < N; i++)
 {
     delete [] p[i]; //Видалення підмасивів
 }
 delete [] p; //Видалення масиву вказівників

Зміна розміру масиву[ред.ред. код]

У випадку збільшення логічного розміру, може виникнути необхідність збільшення розміру масиву. При видаленні елементу, необхідно наступним до видаленого елементам присвоїти значення наступного, тобто зсунути елементи масиву вліво. При додаванні, щоб запобігти засміченню пам'яті при зміні розміру масиву багаторазово, його об'єм збільшують вдвічі з метою використання резервного простору для майбутніх операцій. Додавання пам'яті можна реалізувати наступним чином:

function insertEnd(dynarray a, element e)
   if (a.size = a.capacity)
       a.capacity ← a.capacity * 2  
   a[a.size] ← e
   a.size ← a.size + 1

Переваги та недоліки[ред.ред. код]

  • Можливість задавати розмір масиву під час виконання програми
  • Можливість додавати елементи
  • Засмічення пам'яті

Реалізація[ред.ред. код]

Pascal[ред.ред. код]

Підтримується в  DelphiFree Pascal, але не Turbo Pascal.

 byteArray : Array of Byte; // Одновимірний масив
 multiArray : Array of Array of string; // Двовимірний масив

C[ред.ред. код]

 //Одновимірний масив з a елементів
 int *mas = malloc (sizeof(int) * a); // Виділення пам’яті
 
 // Двовимірний масив з N рядків по M елементів
 // Виділення пам’яті для масиву вказівників на одновимірні підмасиви
 int **A = (int **)malloc(N*sizeof(int *));
 for(int i = 0; i < N; i++) 
 {
     // Виділення пам’яті для одновимірного підмасиву
     A[i] = (int *)malloc(M*sizeof(int));
 }
 
 // Звільнення пам'яті одновимірного масиву
 free(mas);
 
 // Звільнення пам'яті двовимірного масиву
 for(int i = 0; i < N; i++) 
 {
     // Звільнення пам’яті одновимірного підмасиву
     free(A[i]);
 }
 // Звільнення пам’яті масиву вказівників на одновимірні підмасиви
 free(A);

C++[ред.ред. код]

 // Створення одновимірного масиву
 int *mas = new int[a];
 
 // Створення двовимірного масиву з N рядків по M елементів
 // Створення масиву вказівників на одновимірні підмасиви
 int **M = new int *[N];
 for(int i=0; i < N; i++)
 {
     // Створення одновимірного підмасиву
     p[i] = new int[M];
 }
 
 // Вилучення одновимірного масиву 
 delete [] mas;
 
 // Вилучення двовимірного масиву 
 for(int i=0; i < N; i++)
 {
     // Вилучення одновимірного підмасиву
     delete [] p[i];
 }
 // Вилучення масиву вказівників на одновимірні підмасиви
 delete [] M;

Див. також[ред.ред. код]

Джерела[ред.ред. код]