Что такое динамический массив

Динамический массив

Динамическим называется массив, размер которого может меняться во время исполнения программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. В отличие от динамических массивов существуют статические массивы и массивы переменной длинны. Размер статического массива определяется на момент компиляции программы. Размер массива переменной длинны определяется во время выполнения программы. Отличием динамического массива от массива переменной длинны является автоматическое изменение размеров, что не трудно реализуется в случаях его отсутствия, поэтому часто не различают массивы переменной длины с динамическими массивами.

Пример динамического массива на языке «Pascal»

byteArray : Array of Byte; // Одномерный массив multiArray : Array of Array of string; // Многомерный массив 

Динамические массивы (или массивы переменной длины) поддерживаются Delphi, FreePascal, но не Turbo Pascal.

Пример объявления динамического массива на языках C/C++

Одномерный динамический массив:

Создаем массив с 10-ю элементами типа int:

int *mas = malloc (sizeof(int) * 10); 

int *mas = new int[10]; 

Получить доступ к значению каждого элемента можно по индексу (порядковый номер):

mas[0] = 2; // присвоили значение 2 нулевому элементу массива mas mas[1] = 7; // присвоили значение 7 первому элементу массива mas //. и т.д. 

Следовательно, если брать такой подход, то вам понадобится около десяти строк кода, чтобы проинициализировать весь массив. Для того, чтобы этого избежать напишем тоже самое в цикле:

for(int i = 0; i  10; i++) cin>>mas[i]; // пользователь вводит значение каждого i-того элемента массива > 

После чего работаем с массивом. Также его можно вывести на экран:

for(int i = 0; i  10; i++) cout  [i]  ; > 

Для освобождения из памяти одномерного динамического массива используем:

free(mas); 

С++: оператор delete:

delete []mas; 

Строго говоря вышеописанная реализация массива не является динамической, т.к. нет изменения размера массива во время работы, а всего лишь массивом переменной длины. Возможным решением является realloc, но можно применить только при использовании malloc, но не new. Для того чтобы изменить размер такого массива необходимо объявить еще один массив нужного размера, скопировать в него все данные и освободить память занимаемую старым массивом. В С++ библиотечным решением является std::vector. В С89 нет массивов переменной длины, они есть только в С99 (который поддерживают не все компиляторы). Некоторые (довольно старые) компиляторы С++ также не поддерживают массивов переменной длинны.

Ссылки

• Структуры данных

Wikimedia Foundation . 2010 .

• Динамический диапазон (техника)
• Динамо-3 (футбольный клуб, Киев)

Полезное

Смотреть что такое «Динамический массив» в других словарях:

• Массив — У этого термина существуют и другие значения, см. Массив (значения). Эту страницу предлагается переименовать в Массив (информатика). Пояснение причин и обсуждение на странице Википедия:К переименованию/4 ноября 2012. Возможно, её … Википедия
• массив электропитания — [Интент] Для индивидуальных пользователей единственным устройством, реально нуждающимся в такой защите, является компьютер. В корпоративной среде, кроме ПК, в обеспечении качественного электропитания нуждаются серверы, коммуникационное… … Справочник технического переводчика
• Vector (C++) — Стандартная библиотека языка программирования C++ fstream iomanip ios iostream sstream Стандартная библиотека шаблонов algorithm … Википедия
• Ruby — Класс языка: мультипарадигмальный: динамический, объектно ориентиров … Википедия
• Object Pascal — Семантика: императивная Класс языка: мультипарадигмальный: императивный, структурный, объектно ориентированный, обобщённый[1], процедурный Тип исполнения: компилируемый … Википедия
• Руби IDE — Ruby Семантика: мультипарадигмальный Тип исполнения: интерпретатор Появился в: 1995 г. Автор(ы): Юкихиро Мацумото Последняя версия: 1.9.1 … Википедия
• Рубин (язык программирования) — Ruby Семантика: мультипарадигмальный Тип исполнения: интерпретатор Появился в: 1995 г. Автор(ы): Юкихиро Мацумото Последняя версия: 1.9.1 … Википедия
• Язык программирования Рубин — Ruby Семантика: мультипарадигмальный Тип исполнения: интерпретатор Появился в: 1995 г. Автор(ы): Юкихиро Мацумото Последняя версия: 1.9.1 … Википедия
• Стандартная библиотека языка C++ — Стандартная библиотека языка программирования C++ fstream iomanip ios iostream sstream Стандартная библиотека шаблонов … Википедия
• Вектор — Вектор многозначный термин; величина, характеризующаяся размером и направлением. В Викисловаре есть статья «вектор» … Википедия

• Обратная связь: Техподдержка, Реклама на сайте

• �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

• Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
• Искать во всех словарях
• Искать в переводах
• Искать в ИнтернетеИскать в этой же категории

Что такое динамический массив

Кроме отдельных динамических объектов в языке C++ мы можем использовать динамические массивы. Для выделения памяти под динамический массив также используется оператор new , после которого в квадратных скобках указывается, сколько массив будет содержать объектов:

int *numbers ; // динамический массив из 4 чисел // или так // int *numbers = new int[4];

Причем в этом случае оператор new также возвращает указатель на объект типа int — первый элемент в созданном массиве.

В данном случае определяется массив из четырех элементов типа int, но каждый из них имеет неопределенное значение. Однако мы также можем инициализировать массив значениями:

int *numbers1 >; // массив состоит из чисел 0, 0, 0, 0 int *numbers2 >; // массив состоит из чисел 1, 2, 3, 4 int *numbers3 >; // массив состоит из чисел 1, 2, 0, 0 // аналогичные определения массивов // int *numbers1 = new int[4]<>; // массив состоит из чисел 0, 0, 0, 0 // int *numbers1 = new int[4](); // массив состоит из чисел 0, 0, 0, 0 // int *numbers2 = new int[4]< 1, 2, 3, 4 >; // массив состоит из чисел 1, 2, 3, 4 // int *numbers3 = new int[4]< 1, 2 >; // массив состоит из чисел 1, 2, 0, 0

При инициализации массива конкретными значениями следует учитывать, что если значений в фигурных скобках больше чем длина массива, то оператор new потерпит неудачу и не сможет создать массив. Если переданных значений, наоборот, меньше, то элементы, для которых не предоставлены значения, инициализируются значением по умолчанию.

Стоит отметить, что в стандарт С++20 добавлена возможность выведения размера массива, поэтому, если применяется стандарт С++20, то можно не указывать длину массива:

int *numbers >; // массив состоит из чисел 1, 2, 3, 4

После создания динамического массива мы сможем с ним работать по полученному указателю, получать и изменять его элементы:

int *numbers >; // получение элементов через синтаксис массивов std::cout 
Причем для доступа к элементам динамического массива можно использовать как синтаксис массивов ( numbers[0] ), так и операцию разыменования ( *numbers )
Соответственно для перебора такого массива можно использовать различные способы:
unsigned n< 5 >; // размер массива int* p < new int[n] < 1, 2, 3, 4, 5 >>; // используем индексы for (unsigned i<>; i < n; i++) < std::cout std::cout ; i < n; i++) < std::cout std::cout ; q != p + n; q++) < std::cout std::cout 
Обратите внимание, что для задания размера динамического массива мы можем применять обычную переменную, а не константу, как в случае со стандартными массивами.
Для удаления динамического массива и освобождения его памяти применяется специальная форма оператора delete :
delete [] указатель_на_динамический_массив;
#include int main() < unsigned n< 5 >; // размер массива int* p < new int[n] < 1, 2, 3, 4, 5 >>; // используем индексы for (unsigned i<>; i < n; i++) < std::cout std::cout


Чтобы после освобождения памяти указатель не хранил старый адрес, также рекомендуется обнулить его:
delete [] p; p = nullptr; // обнуляем указатель
Многомерные массивы
Также мы можем создавать многомерные динамические массивы. Рассмотрим на примере двухмерных массивов. Что такое по сути двухмерный массив? Это набор массив массивов. Соответственно, чтобы создать динамический двухмерный массив, нам надо создать общий динамический массив указателей, а затем его элементы - вложенные динамические массивы. В общем случае это выглядит так:
#include int main() < unsigned rows = 3; // количество строк unsigned columns = 2; // количество столбцов int** numbers>; // выделяем память под двухмерный массив // выделяем память для вложенных массивов for (unsigned i<>; i < rows; i++) < numbers[i] = new int[columns]<>; > // удаление массивов for (unsigned i<>; i < rows; i++) < delete[] numbers[i]; >delete[] numbers; >
Вначале выделяем память для массива указателей (условно таблицы):
int** numbers>;
Затем в цикле выделяем память для каждого отдельного массива (условно строки таблицы):
numbers[i] = new int[columns]<>;
Освобождение памяти идет в обратном порядке - сначала освобождаем память для каждого отдельного вложенного массива, а затем для всего массива указателей.
Пример с вводом и выводом данных двухмерного динамического массива:
#include int main() < unsigned rows = 3; // количество строк unsigned columns = 2; // количество столбцов int** numbers>; // выделяем память под двухмерный массив for (unsigned i<>; i < rows; i++) < numbers[i] = new int[columns]<>; > // вводим данные для таблицы rows x columns for (unsigned i<>; i < rows; i++) < std::cout ; j < columns; j++) < std::cout > numbers[i][j]; > > // вывод данных for (unsigned i<>; i < rows; i++) < // выводим данные столбцов i-й строки for (unsigned j<>; j < columns; j++) < std::cout std::cout for (unsigned i<>; i < rows; i++) < delete[] numbers[i]; >delete[] numbers; >
Пример работы программы:
Enter data for 1 row 1 column: 2 2 column: 3 Enter data for 2 row 1 column: 4 2 column: 5 Enter data for 3 row 1 column: 6 2 column: 7 2 3 4 5 6 7
Указатель на массив
От типа int** , который представляет указатель на указатель (pointer-to-pointer) следует отличать ситуацию "указатель на массив" (pointer to array). Например:
#include int main() < unsigned n; // количество строк int (*a)[2] = new int[n][2]; int k<>; // устанавливаем значения for (unsigned i<>; i < n; i++) < // устанавливаем данные для столбцов i-й строки for (unsigned j<>; j < 2; j++) < a[i][j] = ++k; >> // вывод данных for (unsigned i<>; i < n; i++) < // выводим данные столбцов i-й строки for (unsigned j<>; j < 2; j++) < std::cout std::cout // удаляем данные delete[] a; a = nullptr; >
Здесь запись int (*a)[2] представляет указатель на массив из двух элементов типа int. Фактически мы можем работать с этим объектом как с двухмерным массивом (таблицей), только количество столбцов в данном случае фиксировано - 2. И память для такого массива выделяется один раз:
int (*a)[2] = new int[n][2];
То есть в данном случае мы имеем дело с таблице из n строк и 2 столцов. Используя два индекса (для строки и столца), можно обращаться к определенному элементу, установить или получить его значение. Консольный вывод данной программы:
1 2 3 4 5 6
Динамический массив. Принцип работы
Мы продолжаем курс по структурам данных. На этом занятии речь пойдет о динамических массивах. Что это такое? На данный момент мы с вами уже хорошо знаем, что из себя представляет и как работает статический массив. Но у него есть один существенный недостаток – неизменяемое число элементов. Поэтому, когда создается статический массив, программист должен как то решить, сколько элементов он должен иметь. Далеко не всегда можно указать разумное значение. Чтобы как то выйти из этой ситуации в мире программирования появилась более гибкая структура данных тоже в виде массива, но с изменяемым (увеличивающимся) числом элементов. Такие массивы получили название динамические.
Приведу один простой пример их использования. Предположим, мы просматриваем файловую систему и сохраняем имена файлов в каждом каталоге. Очевидно, число файлов может варьироваться от нескольких десятков до нескольких тысяч. Если воспользоваться статическим массивом, то придется задавать число элементов, скажем, в 10 000. И это приведет к неоправданному расходу памяти. Гораздо лучше взять динамические массивы с начальным размером в 100 элементов. А, затем, по мере необходимости, увеличивать этот размер. Тогда память будет расходоваться куда экономнее.
 
Структура динамического массива
Давайте теперь посмотрим, как можно организовать массив с изменяемым числом элементов. Для этого воспользуемся обычным массивом с некоторым начальным размером, допустим, в 10 элементов:
 
Реальный размер массива называют физическим, а число записанных в него данных – логическим. Чтобы программно оперировать этими величинами вводят две вспомогательные переменные, например:
currentLength = 7 maxCapacity = 10
Переменная currentLength содержит индекс следующего добавляемого в массив значения, а также определяет число уже записанных данных. Переменная maxCapacity равна максимальному числу элементов, который имеет массив dar.
Добавление и вставка элементов в массив
Теперь предположим, что мы хотим добавить новое значение в конец этого массива. Так как все элементы в массивах должны следовать строго друг за другом с самого начала без каких-либо пропусков, то новое значение нам следует записать в ячейку с индексом currentLength:
dar[currentLength] = 8
и увеличить значение currentLength на единицу:
currentLength += 1
 
С точки зрения О большого скорость этой операции составляет O(1).
Но это добавление в конец. А что если нам нужно вставить новое значение, скажем, после пятерки. Как в этом случае будет выглядеть алгоритм? В действительности, так же, как и в обычном статическом массиве. Необходимо сдвинуть значения 6, 7, 8 вправо на один элемент и на прежнее место шестерки записать вставляемое значение. Переменная currentLength увеличивается на единицу:
 
Вычислительная сложность этой операции с точки зрения О большого составляет O(n), где n – физический размер динамического массива.
Изменение физического размера динамического массива
Я думаю эти простые операции добавления и вставки новых значений в массив, пока есть свободное место, вы себе хорошо представляете. Но что делать, когда все элементы заняты, а мы хотим добавить еще один?
 
Было бы неплохо выделить следующие несколько байт под новый элемент массива и записать туда требуемое значение.
 
При этом вся выделенная под массив область памяти должна быть непрерывной. К сожалению, в общем случае, такую операцию выполнить не получится, т.к. следующие ячейки памяти могут быть заняты другими процессами. Поэтому приходится идти несколько более сложным, но более надежным путем. Выделяется память под новый статический массив длиной в два, три раза больший первоначального (чаще всего удваивают физический размер). В этот новый массив копируют все значения из прежнего массива, записывают новое значение и увеличивают переменную currentLength:
 
Вычислительная сложность этой операции с позиции О большого составляет O(n), где n – физический размер динамического массива.
Далее, если все новые элементы также будут заполнены, то операция удвоения физического размера массива повторяется. Это принцип работы динамического массива.
Здесь у вас может возникнуть вопрос, зачем под новый массив выделять в несколько раз больше элементов, чем в прежнем? Почему бы не увеличить его просто на один элемент (или требуемое число элементов)? Зачем удваивать? Ответ прост. Если нам не хватило физического размера прошлого массива, то скорее всего не хватит и для нового массива с одним дополнительным элементов. А, значит, операцию выделения памяти и копирования всех прежних значений в новый массив снова придется повторять. Это приводит к неоправданному расходу процессорного времени. Логичнее сделать размер массива сразу в два раза больше и минимизировать вероятность создания новых массивов с большими размерами.
Удаление элементов в динамическом массиве
Итак, с добавлением новых значений и изменением физического размера динамического массива мы с вами разобрались. Осталось сказать пару слов про удаление значений. Здесь все намного проще, т.к. физический размер массива при этом не меняется. Поэтому здесь все абсолютно так же, как и в случае со статическими массивами.
Предположим, нам нужно исключить последнее значение. Нет ничего проще. Достаточно уменьшить значение currentLength на единицу и все. Последнего значения теперь как бы нет. Вычислительная сложность этой операции составляет O(1).
 
Немного сложнее выполняется удаление остальных значений (не последнего). В этом случае нам нужно сдвинуть все элементы правее удаляемого влево на одну позицию и не забыть уменьшить значение currentLength на единицу:
 
Сложность этой операции составляет O(n). Еще раз отмечу, что при удалении значений физический размер массива не меняется, даже если ранее он увеличивался.
Заключение
Давайте подведем итог этого занятия.
Динамический массив – это массив, который может менять число своих элементов в процессе работы программы.
Динамические массивы реализуются на основе обычных статических массивов и хранят данные в непрерывной области памяти. Благодаря этому доступ к произвольному элементу выполняется за фиксированное время с вычислительной сложностью O(1).
Если начального физического размера динамического массива недостаточно, то создается новый массив размером в несколько раз больше предыдущего с копированием всех прежних значений. Часто делают удвоение размеров.
Операции добавления и удаления значений элементов в динамическом массиве выполняются почти так же, как и в статических массивах. Разница только в том, что при добавлении новых значений может дополнительно происходить увеличение физического размера массива. При этом вычислительная сложность операций вставки/удаления составляет O(n), где n – общий размер динамического массива.
На следующем занятии мы продолжим эту тему и увидим, как реализуются динамические массивы на языках Python и С++. 
Видео по теме

#1. О большое (Big O) - верхняя оценка сложности алгоритмов

#2. О большое (Big O). Случаи логарифмической и факториальной сложности

#3. Статический массив. Структура, его преимущества и недостатки

#4. Примеры реализации статических массивов на C++

#5. Динамический массив. Принцип работы

#6. Реализация динамического массива на Python

#7. Реализация динамического массива на С++ с помощью std::vector

#8. Односвязный список. Структура и основные операции

#9. Делаем односвязный список на С++

#10. Двусвязный список. Структура и основные операции

#11. Делаем двусвязный список на С++

#12. Двусвязный список (list) в STL на С++

#13. Очереди типов FIFO и LIFO

#14. Очередь collections.deque на Python

#15. Очередь deque библиотеки STL языка C++

#16. Стек. Структура и принцип работы

#17. Реализация стека на Python и C++

#18. Бинарные деревья. Начало

#19. Бинарное дерево. Способы обхода и удаления вершин

#20. Реализация бинарного дерева на Python

#21. Множества (set). Операции над множествами

#22. Множества set и multiset в C++

#23. Контейнер map библиотеки STL в C++

#24. Префиксное (нагруженное, Trie) дерево. Ассоциативные массивы

#25. Хэш-таблицы. Что это такое и как работают

#26. Хэш-функции. Универсальное хэширование

#27. Метод открытой адресации. Двойное хэширование

#28. Использование хэш-таблиц в Python и С++
© 2023 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта
Что такое динамический массив
Часто стал видеть в интернете и здесь, на РУСО, как авторы, говоря о динамических массивах, понимают под этим словом массив, который создан во время работы программы, то есть на Си вот такой массив:
int * array = malloc(array_size * sizeof(int)); 
Но когда я изучал программирование, нас учили что динамический массив это что-то более сложное. Это массив размер котрого можно менять в процессе работы программы. Термин поменял свое содержание, расширился или люди ошибаются?
Отслеживать

задан 9 ноя 2017 в 10:27

6,853 2 2 золотых знака 23 23 серебряных знака 43 43 бронзовых знака
Вы написали - размер которого можно менять в процессе работы программы. Я в ответе привел возможность realloc, другой вариант тривиален - Вы вводите число array_size и создаете массив такого размера. Вполне себе изменение (0 -> array_size) во время работы программы.
9 ноя 2017 в 11:06
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Динамическим называется массив, размер которого, при необходимости, может меняться во время исполнения программы. Это верное определение.
int * array = malloc(array_size * sizeof(int)); 
Это и есть пример динамического массива. Ты можешь ниже в программе выделить ему новую память, расширить или сузить его.
Отличие статических от динамических массивов в том, что размер первого определяется на момент компиляции, а размер второго, может меняться в программе
Отслеживать

ответ дан 9 ноя 2017 в 10:32

Иван Гладуш Иван Гладуш

1,192 1 1 золотой знак 10 10 серебряных знаков 26 26 бронзовых знаков

Динамическим называется массив, размер которого, при необходимости, может меняться во время исполнения программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. В отличие от динамических массивов существуют статические массивы и массивы переменной длины. Размер статического массива определяется на момент компиляции программы. Размер массива переменной длины определяется во время выполнения программы. Отличием динамического массива от массива переменной длины является автоматическое изменение размеров, что не трудно реализуется в случаях его отсутствия, поэтому часто не различают массивы переменной длины с динамическими массивами

Материал взят из статьи с Википедии.
Массив, который создается таким образом - динамический:
int * array = malloc(array_size * sizeof(int)) 
И Вы можете поменять его размер на этапе выполнения, например, через realloc :
#include #include #include int main() < long *buffer, *oldbuffer; size_t size; if((buffer = (long*)malloc(1000 * sizeof(long ))) == NULL) exit(EXIT_FAILURE); size = _msize(buffer); printf_s("Size of block after malloc of 1000 longs: %u\n", size); oldbuffer = buffer; if((buffer = realloc(buffer, size + (1000 * sizeof(long)))) == NULL) < free(oldbuffer); exit(EXIT_FAILURE); >size = _msize( buffer ); printf_s("Size of block after realloc of 1000 more longs: %u\n", size); free(buffer); exit(EXIT_SUCCESS); > 
Пример взят с сайта справки MSDN.
Альтернатива - это статический массив, его размер не меняется во время исполнения программы и определяется в момент компиляции программы. Можно сказать, что динамический массив - это массив, размер которого задается как константой, так и переменной, поэтому употребление термина массив переменной длины будет уместным.


Похожие публикации:

Javarush откуда
Rsca что это такое
Shape 0 python что это
Как закрыть группу в телеграмме на время