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

Динамічним називають такий масив, розмір якого можна змінювати під час виконання програми. Динамічні масиви надають змогу більш гнучко працювати з даними, оскільки дозволяють вводити довільний розмір.  Для зміни розміру динамічного масиву мова програмування, що підтримує такі масиви, повинна надавати вбудовану функцію чи оператор. В порівняні зі статичним масивом, динамічний не має фіксованого розміру та може задаватись під час виконання програми. Замість використання змінної типу 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

Підтримується в  Delphi, Free 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); 

 // Створення одновимірного масиву  int *mas = new int[a];  // Створення двовимірного масиву з N рядків по M елементів  // Створення масиву вказівників на одновимірні підмасиви  int **p = 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 [] p; 

Fortran

program dynamic_arrays  implicit none  integer :: nx, n,m,i  integer, allocatable, dimension(:) :: x,temp  integer, allocatable, dimension(:,:) :: y  nx=5  n=10  m=20  ! створення одновимірного масиву  allocate(x(nx))  ! ініціалізація всього масиву  x = 1  ! показуємо масив  print*,'x = ', x  print*, ' allocated(x)=',allocated(x)  ! створення нового масиву вдвічі довшого за попередній  allocate(temp(2*size(x)))  ! ініціалізація всього масиву  temp = -1  ! x видаляється і створюється вдвічі довший без копіювання даних, temp видаляється  call move_alloc(temp,x)  print*, ' allocated(temp)=',allocated(temp)  ! показуємо масив  print*,'x = ', x  print*, ' allocated(x)=',allocated(x)  ! вилучення одновимірного масиву  deallocate(x)  ! створення двовимірного масиву з m рядків по n елементів (в фортрані - спочатку по стовпцях!)  allocate(y(n,m))  ! ініціалізація всього масиву  do i =1,m  y(:,i)=i  end do  ! показуємо масив  print*,'y = '  do i=1,m  print*, y(:,i)  enddo  ! вилучення двовимірного масиву  deallocate(y) end program dynamic_arrays 

Див. також

• Масив (структура даних)

Джерела

• Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
• VPOOL [ 1 жовтня 2014 у Wayback Machine.] - C language implementation of dynamic array.
• — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
• Open Data Structures - Chapter 2 - Array-Based Lists [ 27 грудня 2013 у Wayback Machine.]
• Прата С. Мова програмування С++, - 6-те видання.-М. "Вильям", - Москва, 2012. - 374 с.