Как добавить элемент в динамический массив c

C++ добавление элемента в конец динамического массива

Помогите не могу разобраться почему не работает: Необходимо в конец динамического массива добавить сумму его элементов. Мой код:

#include "stdafx.h" #include using namespace std; int* createArray(int*, int); void fillArray(int*, int); void printArray(int*, int); void deleteArray(int*); void addElemet(int*, int); int _tmain(int argc, _TCHAR* argv[]) < setlocale(LC_ALL, "rus"); int num = 0; cout > num; int sum = 0; int *pArray = NULL; pArray = createArray(pArray, num); fillArray(pArray, num); addElemet(pArray, num); printArray(pArray, num); deleteArray(pArray); return 0; > int* createArray(int *massiv, int number) //создание динамического массива < return massiv = new int[number]; >void fillArray(int* massiv, int number) //ввод данных в массив < for (int i = 0; i < number; i++) < cout > massiv[i]; > cout void printArray(int* massiv, int number) // вывод массива на печать < for (int i = 0; i < number; i++) < cout cout void deleteArray(int* massiv) //Очистка памяти < delete[] massiv; >void addElemet(int *massiv, int number) //добавление элемента в конец массива < int *temp = NULL; int numTemp = number + 1; int sum = 0; temp = createArray(temp, numTemp); // создаем временный массив for (int i = 0; i < number; i++) < temp[i] = i; //massiv[i]; // копируем данные со старого массива sum += massiv[i]; >temp[numTemp] = sum; // не добавляет элемент в конец массива, при выводе на экран скопированные элементы отображаются нормально, а последний отображает набор цифр deleteArray(massiv); // удаляем старый массив massiv = createArray(temp, numTemp); massiv = temp; //копируем временный массив в новый. deleteArray(temp); //удаляем временный массив > 

Динамический массив: взаимодействие и проблемы

О чем речь? Динамический массив – тип структуры данных, размер которого определяется в процессе реализации кода, а не на этапе написания. Таким образом программисту не нужно заранее определять объем необходимой памяти.

На что обратить внимание? Использовать динамические массивы можно не в каждом языке программирования, но наиболее популярные обладают такой функцией: Python, JavaScript, C++. Этот инструмент доступен и в Pascal, Ruby, Delphi.

В статье рассказывается:

1. Понятие динамического массива
2. Реализация динамических массивов в языках программирования
3. Взаимодействие с динамическим массивом
4. Динамический массив и производительность
5. Проблемы с динамическим массивом
6. Часто задаваемые вопросы о динамических массивах

Пройди тест и узнай, какая сфера тебе подходит:
айти, дизайн или маркетинг.
Бесплатно от Geekbrains

Понятие динамического массива

В мире программирования операционные системы компьютеров занимаются управлением памятью. Не важно, на каком языке программирования написана программа, взаимодействие с операционной системой идет через память.

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

Массив — это упорядоченная коллекция данных. Если элемент в массиве помечен как пятый, то он остается пятым независимо от того, что происходит вокруг. Упорядоченность гарантирует, что элементы всегда будут на своих местах, если только мы не изменим их порядок. Типы данных в элементах массива могут быть разнообразными: числа, строки, объекты, в зависимости от языка программирования.

Для наглядности представьте память компьютера как сетку ячеек, каждая из которых содержит фрагмент информации.

Для работы с массивами программисты используют переменные, которые представляют собой ссылки на определенные области памяти.

Узнай, какие ИТ — профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Павел Симонов
Исполнительный директор Geekbrains

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов
Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно
Уже скачали 25509

Динамический массив — это структура данных, позволяющая менять размер массива и автоматически освобождать ненужные ячейки. Примеры языков программирования, поддерживающих динамические массивы, включают JavaScript, Python, Java (через ArrayList), C++ (с использованием векторов).

Реализация динамических массивов в языках программирования

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

Реализация динамических массивов может быть организована через классы (в объектно-ориентированных языках) или обобщенные типы. В зависимости от языка, динамические массивы могут быть одномерными или многомерными.

Поддержка динамических массивов также предполагает наличие встроенных операций для определения размера массива и изменения его размера. Начальный размер динамического массива может быть равен нулю или задаваться при создании. Дальнейшие изменения размера выполняются через специальные встроенные операции. В некоторых языках (например, JavaScript, Lua) массив может автоматически расширяться при записи в несуществующую ячейку.

Для реализации динамических массивов с возможностью изменения размера приходится балансировать между противоречивыми требованиями.

Эффективное использование памяти: реализация не должна вызывать существенный перерасход памяти.

Эффективность в производительности, включая:

• минимальные накладные расходы при изменении размера массива;
• сохранение, насколько это возможно, постоянного времени доступа для чтения/записи элементов массива.

Совместимость с обычными статическими массивами на низком уровне. Например, для использования динамических массивов вместе с низкоуровневым кодом API операционной системы требуется размещение элементов массива в непрерывном блоке оперативной памяти в порядке, соответствующем индексации массива.

Выбор конкретного способа реализации зависит от приоритетов указанных требований.

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

Добавление и вставка элементов в массив

Представьте, что нам требуется добавить новое значение в конец динамического массива данных. Важно отметить, что элементы массивов всегда располагаются вплотную друг за другом, начиная с самого начала. Для добавления нового элемента мы помещаем его в ячейку с индексом текущей длины массива (currentLength):

Затем, увеличиваем значение currentLength на единицу:

Эта операция имеет постоянную сложность O(1) с точки зрения алгоритмической сложности.

Для вас подарок! В свободном доступе до 14.01 —>
Скачайте ТОП-10
бесплатных нейросетей
для программирования
Помогут писать код быстрее на 25%
Чтобы получить подарок, заполните информацию в открывшемся окне

Однако, в случае вставки нового элемента внутрь массива (например, после элемента со значением «5»), процедура схожа с тем, как это делается в обычных статических массивах. Нам необходимо сдвинуть значения «6», «7» и «8» на одну позицию вправо, чтобы освободить место для нового элемента. Затем, в освободившуюся позицию, записываем новое значение. Не забываем увеличить currentLength на единицу.

Вычислительная сложность этой операции составляет O(n), где n — физический размер динамического массива.

Изменение физического размера динамического массива

Работа с динамическими массивами понятна, пока есть свободное место. Но что делать, когда все ячейки массива заполнены, и нам необходимо добавить новый элемент?

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

Чтобы обойти эту проблему, используется более сложный, но надежный подход. Мы выделяем память под новый статический массив, размер которого в два или три раза больше исходного (обычно размер удваивается). В этот новый массив копируются значения из старого массива, после чего записывается новое значение, и currentLength увеличивается.

Сложность этой операции составляет O(n) по алгоритмической сложности, где n — физический размер динамического массива.

Если все новые элементы также заполняются, то процесс удвоения размера массива повторяется. Это принцип работы динамического массива элементов.

Возможно, возникнет вопрос, почему при выделении новой памяти под массив используется увеличение его размера в несколько раз, а не просто на один элемент (или на требуемое количество элементов).

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

Удаление элементов в динамическом массиве

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

Динамическое выделение памяти в Си

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

• выделение памяти под статический массив, содержащий максимально возможное число элементов, однако в этом случае память расходуется не рационально;
• динамическое выделение памяти для хранение массива данных.

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

int *p; // указатель на тип int

Начальный адрес статического массива определяется компилятором в момент его объявления и не может быть изменен.

Для динамического массива начальный адрес присваивается объявленному указателю на массив в процессе выполнения программы.

Стандартные функции динамического выделения памяти

Функции динамического выделения памяти находят в оперативной памяти непрерывный участок требуемой длины и возвращают начальный адрес этого участка.

Функции динамического распределения памяти:

void * malloc(РазмерМассиваВБайтах);
void * calloc(ЧислоЭлементов, РазмерЭлементаВБайтах);

Для использования функций динамического распределения памяти необходимо подключение библиотеки :

Поскольку обе представленные функции в качестве возвращаемого значения имеют указатель на пустой тип void , требуется явное приведение типа возвращаемого значения.

Для определения размера массива в байтах, используемого в качестве аргумента функции malloc() требуется количество элементов умножить на размер одного элемента. Поскольку элементами массива могут быть как данные простых типов, так и составных типов (например, структуры), для точного определения размера элемента в общем случае рекомендуется использование функции

int sizeof (тип);

которая определяет количество байт, занимаемое элементом указанного типа.

Память, динамически выделенная с использованием функций calloc(), malloc() , может быть освобождена с использованием функции

free(указатель);

«Правилом хорошего тона» в программировании является освобождение динамически выделенной памяти в случае отсутствия ее дальнейшего использования. Однако если динамически выделенная память не освобождается явным образом, она будет освобождена по завершении выполнения программы.

Динамическое выделение памяти для одномерных массивов

Форма обращения к элементам массива с помощью указателей имеет следующий вид:

int a[10], *p; // описываем статический массив и указатель
int b;
p = a; // присваиваем указателю начальный адрес массива
. // ввод элементов массива
b = *p; // b = a[0];
b = *(p+i) // b = a[i];

Пример на Си : Организация динамического одномерного массива и ввод его элементов.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
int main()
int *a; // указатель на массив
int i, n;
system( «chcp 1251» );
system( «cls» );
printf( «Введите размер массива: » );
scanf( «%d» , &n);
// Выделение памяти
a = ( int *)malloc(n * sizeof ( int ));
// Ввод элементов массива
for (i = 0; i printf( «a[%d] = » , i);
scanf( «%d» , &a[i]);
>
// Вывод элементов массива
for (i = 0; i printf( «%d » , a[i]);
free(a);
getchar(); getchar();
return 0;
>

Результат выполнения программы:

Динамическое выделение памяти для двумерных массивов

Пусть требуется разместить в динамической памяти матрицу, содержащую n строк и m столбцов. Двумерная матрица будет располагаться в оперативной памяти в форме ленты, состоящей из элементов строк. При этом индекс любого элемента двумерной матрицы можно получить по формуле

index = i*m+j;

где i — номер текущей строки; j — номер текущего столбца.

Рассмотрим матрицу 3×4 (см. рис.)

Индекс выделенного элемента определится как

index = 1*4+2=6

Объем памяти, требуемый для размещения двумерного массива, определится как

n·m·(размер элемента)

Однако поскольку при таком объявлении компилятору явно не указывается количество элементов в строке и столбце двумерного массива, традиционное обращение к элементу путем указания индекса строки и индекса столбца является некорректным:

a [j] — некорректно.

Правильное обращение к элементу с использованием указателя будет выглядеть как

• p — указатель на массив,
• m — количество столбцов,
• i — индекс строки,
• j — индекс столбца.

Пример на Си Ввод и вывод значений динамического двумерного массива

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
int main()
int *a; // указатель на массив
int i, j, n, m;
system( «chcp 1251» );
system( «cls» );
printf( «Введите количество строк: » );
scanf( «%d» , &n);
printf( «Введите количество столбцов: » );
scanf( «%d» , &m);
// Выделение памяти
a = ( int *)malloc(n*m * sizeof ( int ));
// Ввод элементов массива
for (i = 0; i for (j = 0; j printf( «a[%d][%d] = » , i, j);
scanf( «%d» , (a + i*m + j));
>
>
// Вывод элементов массива
for (i = 0; i for (j = 0; j printf( «%5d » , *(a + i*m + j)); // 5 знакомест под элемент массива
>
printf( «\n» );
>
free(a);
getchar(); getchar();
return 0;
>

Результат выполнения

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

• выделить блок оперативной памяти под массив указателей;
• выделить блоки оперативной памяти под одномерные массивы, представляющие собой строки искомой матрицы;
• записать адреса строк в массив указателей.

Графически такой способ выделения памяти можно представить следующим образом.

При таком способе выделения памяти компилятору явно указано количество строк и количество столбцов в массиве.
Пример на Си

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
int main()
int **a; // указатель на указатель на строку элементов
int i, j, n, m;
system( «chcp 1251» );
system( «cls» );
printf( «Введите количество строк: » );
scanf( «%d» , &n);
printf( «Введите количество столбцов: » );
scanf( «%d» , &m);
// Выделение памяти под указатели на строки
a = ( int **)malloc(n * sizeof ( int *));
// Ввод элементов массива
for (i = 0; i // Выделение памяти под хранение строк
a[i] = ( int *)malloc(m * sizeof ( int ));
for (j = 0; j printf( «a[%d][%d] = » , i, j);
scanf( «%d» , &a[i][j]);
>
>
// Вывод элементов массива
for (i = 0; i < n; i++) // цикл по строкам
for (j = 0; j < m; j++) // цикл по столбцам
printf( «%5d » , a[i][j]); // 5 знакомест под элемент массива
>
printf( «\n» );
>
// Очистка памяти
for (i = 0; i < n; i++) // цикл по строкам
free(a[i]); // освобождение памяти под строку
free(a);
getchar(); getchar();
return 0;
>

Результат выполнения программы аналогичен предыдущему случаю.

С помощью динамического выделения памяти под указатели строк можно размещать свободные массивы. Свободным называется двухмерный массив (матрица), размер строк которого может быть различным. Преимущество использования свободного массива заключается в том, что не требуется отводить память компьютера с запасом для размещения строки максимально возможной длины. Фактически свободный массив представляет собой одномерный массив указателей на одномерные массивы данных.

Для размещения в оперативной памяти матрицы со строками разной длины необходимо ввести дополнительный массив m , в котором будут храниться размеры строк.

Пример на Си : Свободный массив

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#define _CRT_SECURE_NO_WARNINGS
#include
#include
int main()
int **a;
int i, j, n, *m;
system( «chcp 1251» );
system( «cls» );
printf( «Введите количество строк: » );
scanf( «%d» , &n);
a = ( int **)malloc(n * sizeof ( int *));
m = ( int *)malloc(n * sizeof ( int )); // массив кол-ва элеменов в строках массива a
// Ввод элементов массива
for (i = 0; i printf( «Введите количество столбцов строки %d: » , i);
scanf( «%d» , &m[i]);
a[i] = ( int *)malloc(m[i] * sizeof ( int ));
for (j = 0; j

Результат выполнения

Перераспределение памяти

Если размер выделяемой памяти нельзя задать заранее, например при вводе последовательности значений до определенной команды, то для увеличения размера массива при вводе следующего значения необходимо выполнить следующие действия:

• Выделить блок памяти размерности n+1 (на 1 больше текущего размера массива)
• Скопировать все значения, хранящиеся в массиве во вновь выделенную область памяти
• Освободить память, выделенную ранее для хранения массива
• Переместить указатель начала массива на начало вновь выделенной области памяти
• Дополнить массив последним введенным значением

Все перечисленные выше действия (кроме последнего) выполняет функция

void * realloc ( void * ptr, size_t size);

• ptr — указатель на блок ранее выделенной памяти функциями malloc() , calloc() или realloc() для перемещения в новое место. Если этот параметр равен NULL , то выделяется новый блок, и функция возвращает на него указатель.
• size — новый размер, в байтах, выделяемого блока памяти. Если size = 0 , ранее выделенная память освобождается и функция возвращает нулевой указатель, ptr устанавливается в NULL .

Размер блока памяти, на который ссылается параметр ptr изменяется на size байтов. Блок памяти может уменьшаться или увеличиваться в размере. Содержимое блока памяти сохраняется даже если новый блок имеет меньший размер, чем старый. Но отбрасываются те данные, которые выходят за рамки нового блока. Если новый блок памяти больше старого, то содержимое вновь выделенной памяти будет неопределенным.

Пример на Си Выделить память для ввода массива целых чисел. После ввода каждого значения задавать вопрос о вводе следующего значения.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define _CRT_SECURE_NO_WARNINGS
#include
#include
int main()
int *a = NULL , i = 0, elem;
char c;
do printf( «a[%d]= » , i);
scanf( «%d» , &elem);
a = ( int *)realloc(a, (i + 1) * sizeof ( int ));
a[i] = elem;
i++;
getchar();
printf( «Next (y/n)? » );
c = getchar();
> while (c == ‘y’ );
for ( int j = 0; j < i; j++)
printf( «%d » , a[j]);
if (i>2) i -= 2;
printf( «\n» );
a = ( int *)realloc(a, i * sizeof ( int )); // уменьшение размера массива на 2
for ( int j = 0; j < i; j++)
printf( «%d » , a[j]);
getchar(); getchar();
return 0;
>

Результат выполнения

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

В [math]i[/math] -ую ячейку массива записывается элемент [math]x[/math] . Время выполнения — [math]O(1)[/math] .

add(x)

Добавление в массив элемента [math]x[/math] . Время выполнения — [math]O(1)[/math] ; в худшем случае, при котором необходимо перенести все элементы из текущего массива во вдвое больший массив — [math]O(n)[/math] ( [math]n[/math] — размер массива).

del()

Удаляет последний элемент массива. В случае, если количество элементов в массиве в [math]C[/math] раз меньше его длины, то происходит сжатие в [math]B[/math] раз. ( [math]C,B[/math] — константы, зависящие от реализации). Время выполнения операции в худшем случае — [math]O(n)[/math] .

size()

Возвращает количество элементов массива. Время выполнения — [math]O(1)[/math] .

Амортизационная стоимость каждой операции

Пусть наш массив расширяется в [math]2[/math] раза, и уменьшается в [math]2[/math] раза, когда длина массива в [math]4[/math] раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет [math]O(1)[/math] .

Метод предоплаты

Стоимость операции add(x)

Иллюстрация

Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили [math]i[/math] -ый элемент, мы будем класть по одной монетке к элементам с номерами [math]i[/math] и [math]i-\frac[/math] ). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — [math]3[/math] , и среднее время её работы — [math]O(1)[/math] .

Стоимость операции del()

При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции [math]i \bmod \dfrac[/math] . Тогда даже в самом худшем случае (только что расширились, а потом [math]\dfrac[/math] удалили) у каждого элемента из первых [math]\dfrac[/math] будет по монете и на удаление надо будет потратить только [math]1[/math] монету.

Метод потенциалов

За потенциал примем число: [math]\Phi(c, s) = \begin 2s-c, & \text s\geqslant\fracc \\ \fracc-s, & \text s\lt \fracc \end[/math] , где [math]c[/math] — размер массива, [math]s[/math] — число элементов массива.

Стоимость операции add(x)

• [math]\frac= 1[/math] , массив расширяется: [math] a_i = t_i + \Phi(2c, s + 1) — \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 [/math]

• [math]1\gt \frac\geqslant\frac[/math] , массив не расширяется: [math]a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3[/math]

• [math]\frac\lt \frac, \frac\geqslant\frac[/math] , массив не расширяется:

[math]a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\fracc — s)= 3+3s-\fracc= 3 + \frac3c-\fracc \lt 3+\fracc-\fracc=3[/math]

• [math]\frac\lt \frac, \frac\lt \frac[/math] , массив не расширяется: [math]a_i = t_i + \Phi(c, s + 1) — \Phi(c, s) = 1 + (\fracc — (s + 1)) — (\fracc — s) = 0[/math]

В итоге, средняя стоимость операции — [math]3[/math] , а среднее время работы — [math]O(1)[/math] .

Стоимость операции del()

• [math]\frac=\frac[/math] , массив сужается: [math]a_i = t_i + \Phi(\frac, s — 1) — \Phi(c, s) = s + (\frac\cdot\fracc-(s-1)) — (\fracc-s) = 1-\fracc+s=1[/math]
• [math]\frac\lt \frac\lt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s — 1) — \Phi(c, s) = 1 + (\fracc-(s-1))-(\fracc-s)= 2[/math]
• [math]\frac\geqslant\frac, \frac\lt \frac\Rightarrow s=\fracc[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s — 1) — \Phi(c, s) =1 +(\fracc-(s-1))-(2s-c)=2+\fracc-3s = 2[/math]
• [math]\frac\gt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s — 1) — \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0[/math]

Средняя стоимость операции — [math]2[/math] , а среднее время работы — [math]O(1)[/math] .

Динамические массивы в современных языках программирования

Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.

С++ — vector

В С++ динамический массив используется в структуре vector, она описана в STL(). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в [math]2[/math] раза при компиляции GNU C++ и в [math]1.5[/math] раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен [math]0[/math] .

Java — ArrayList

В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в [math]1.5[/math] раза. Причем начальный размер равен [math]10[/math] . Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

Источники информации

• Wikipedia — Dynamic array
• Wikipedia — Динамический массив

• Дискретная математика и алгоритмы
• Амортизационный анализ

Как добавить элемент в динамический массив c

Кроме отдельных динамических объектов в языке 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
Динамический массив
В [math]i[/math] -ую ячейку массива записывается элемент [math]x[/math] . Время выполнения — [math]O(1)[/math] .
add(x)
Добавление в массив элемента [math]x[/math] . Время выполнения — [math]O(1)[/math] ; в худшем случае, при котором необходимо перенести все элементы из текущего массива во вдвое больший массив — [math]O(n)[/math] ( [math]n[/math] — размер массива).
del()
Удаляет последний элемент массива. В случае, если количество элементов в массиве в [math]C[/math] раз меньше его длины, то происходит сжатие в [math]B[/math] раз. ( [math]C,B[/math] — константы, зависящие от реализации). Время выполнения операции в худшем случае — [math]O(n)[/math] .
size()
Возвращает количество элементов массива. Время выполнения — [math]O(1)[/math] .
Амортизационная стоимость каждой операции
Пусть наш массив расширяется в [math]2[/math] раза, и уменьшается в [math]2[/math] раза, когда длина массива в [math]4[/math] раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет [math]O(1)[/math] .
Метод предоплаты
Стоимость операции add(x)

Иллюстрация
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили [math]i[/math] -ый элемент, мы будем класть по одной монетке к элементам с номерами [math]i[/math] и [math]i-\frac[/math] ). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — [math]3[/math] , и среднее время её работы — [math]O(1)[/math] .
Стоимость операции del()
При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции [math]i \bmod \dfrac[/math] . Тогда даже в самом худшем случае (только что расширились, а потом [math]\dfrac[/math] удалили) у каждого элемента из первых [math]\dfrac[/math] будет по монете и на удаление надо будет потратить только [math]1[/math] монету.
Метод потенциалов
За потенциал примем число: [math]\Phi(c, s) = \begin 2s-c, & \text s\geqslant\fracc \\ \fracc-s, & \text s\lt \fracc \end[/math] , где [math]c[/math] — размер массива, [math]s[/math] — число элементов массива.
Стоимость операции add(x) 

[math]\frac= 1[/math] , массив расширяется: [math] a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 [/math]


[math]1\gt \frac\geqslant\frac[/math] , массив не расширяется: [math]a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3[/math]


[math]\frac\lt \frac, \frac\geqslant\frac[/math] , массив не расширяется:

[math]a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\fracc - s)= 3+3s-\fracc= 3 + \frac3c-\fracc \lt 3+\fracc-\fracc=3[/math]

[math]\frac\lt \frac, \frac\lt \frac[/math] , массив не расширяется: [math]a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\fracc - (s + 1)) - (\fracc - s) = 0[/math]

В итоге, средняя стоимость операции — [math]3[/math] , а среднее время работы — [math]O(1)[/math] .
Стоимость операции del()

[math]\frac=\frac[/math] , массив сужается: [math]a_i = t_i + \Phi(\frac, s - 1) - \Phi(c, s) = s + (\frac\cdot\fracc-(s-1)) - (\fracc-s) = 1-\fracc+s=1[/math]
[math]\frac\lt \frac\lt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\fracc-(s-1))-(\fracc-s)= 2[/math]
[math]\frac\geqslant\frac, \frac\lt \frac\Rightarrow s=\fracc[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\fracc-(s-1))-(2s-c)=2+\fracc-3s = 2[/math]
[math]\frac\gt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0[/math]

Средняя стоимость операции — [math]2[/math] , а среднее время работы — [math]O(1)[/math] .
Динамические массивы в современных языках программирования
Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.
С++ — vector
В С++ динамический массив используется в структуре vector, она описана в STL(). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в [math]2[/math] раза при компиляции GNU C++ и в [math]1.5[/math] раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен [math]0[/math] .
Java — ArrayList
В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в [math]1.5[/math] раза. Причем начальный размер равен [math]10[/math] . Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().
Источники информации

Wikipedia — Dynamic array
Wikipedia — Динамический массив


Дискретная математика и алгоритмы
Амортизационный анализ

Динамические массивы в C
Если вы используете относительно современный ЯП вроде JS, то массивы в С могут ввести вас в ступор.
Вступление
Массив в JavaScript:
let numbers = []; numbers.push(1); numbers.push(2); numbers.push(3); console.log(numbers); // [1, 2, 3]
Приведенный выше пример показывает, как бы мы создали массив в JS. Хорошо видно, что возможно добавить столько строк, сколько нам нужно.
int numbers[3];
numbers[0] = 1; numbers[1] = 2; numbers[2] = 3;
printf("%d\n", numbers[0]); // 1 printf("%d\n", numbers[1]); // 2 printf("%d\n", numbers[2]); // 3
Первое выражение numbers[3] говорит компилятору, что массив сохранит в памяти 3 числа. Далее сохраним 1,2 и 3 под соответствующими индексами и выведем на дисплей. 
Пока все прекрасно, но но нельзя добавить ещё элементы:
int numbers[3];
numbers[0] = 1; numbers[1] = 2; numbers[2] = 3; numbers[3] = 4;
printf("%d\n", numbers[0]); // 1 printf("%d\n", numbers[1]); // 2 printf("%d\n", numbers[2]); // 3 printf("%d\n", numbers[3]); // should be 4
И что на это скажет gcc ?:
array.c:8:5: warning: array index 3 is past the end of the array (which contains 3 elements) [-Warray-bounds]
Таким образом, мы получаем исключение за пределами границ памяти. Места в нашем массиве недостаточно, чтобы вместить ещё элементы. 
Что же, если мы нуждаемся в динамическом массиве, в который можно добавить n элементов?
На С мы можем создать собственную имплементацию массива с динамически растущим размером. 
Для этого используем блоки памяти.
malloc, realloc и указатели (pointers)
В С каждый тип данных имеет свой размер хранилища:


Тип
Размер хранилища
Диапазон значений



char
1 byte
-128 до 127 или 0 до 255


unsigned char
1 byte
0 до 255


signed char
1 byte
-128 до 127


int
2 или 4 bytes
-32,768 до 32,767 или -2,147,483,648 до 2,147,483,647


unsigned int
2 или 4 bytes
0 до 65,535 или 0 до 4,294,967,295


short
2 bytes
-32,768 to 32,767


unsigned short
2 bytes
0 до 65,535


long
8 bytes
-9223372036854775808 до 9223372036854775807


unsigned long
8 bytes
0 до 18446744073709551615


В моей системе это 4 байта для целых чисел (integers). Просто имея эти данные можно создавать динамические массивы любого размера. 
Размер типа данных можно получить при помощи функций sizeof(int), sizeof(double) или для тех типов данных, которые вам требуются. 
Используя функции malloc и realloc мы можем создавать динамические блоки памяти.
Допустим, мы хотим начать с возможности хранить 3 целых числа (integers),это можно сделать, выделив блок памяти из 12 байт:
Единственным аргументом malloc является размер блока памяти в байтах. 
Malloc возвращает указатель(pointer) на вновь созданный блок памяти. 
#define INITIAL_CAPACITY 3
int main(){ int* data = malloc(INITIAL_CAPACITY * sizeof(int)); }
Теперь у нас есть блок памяти, достаточно большой, чтобы вместить наши 3 целых числа - нам нужно сделать его динамическим. Сейчас мы все ещё не можем поместить больше 3-х элементов в наш блок памяти.
Если отслеживать размер и объемом используемой памяти, можно рассчитать, когда нужно изменить ее размер. Если блок памяти заполнен, удвоим размер этого блока памяти, при помощи вызвова realloc , который просто расширяет текущий блок памяти.
#define INITIAL_CAPACITY 3
void push(int *arr, int index, int value, int *size, int *capacity){ int* ptr; if(*size > *capacity){ ptr = realloc(arr, sizeof(arr) * 2); if(ptr == NULL) exit(0); else *capacity = sizeof(arr) * 2; } arr[index] = value; *size = *size + 1; }
int main(){ int size = 0; int capacity = INITIAL_CAPACITY; int* arr = malloc(INITIAL_CAPACITY * sizeof(int)); }
Теперь есть возможность добавлять элементы в блок памяти динамически. 
Собрав все это вместе, получим следующую программу:
#include #include #define INITIAL_CAPACITY 2 void push(int *arr, int index, int value, int *size, int *capacity){ int* ptr; if(*size > *capacity){ ptr = realloc(arr, sizeof(arr) * 2); if(ptr == NULL) exit(0); else *capacity = sizeof(arr) * 2; } arr[index] = value; *size = *size + 1; } int main(){ int size = 0; int capacity = INITIAL_CAPACITY; int* arr = malloc(INITIAL_CAPACITY * sizeof(int)); if(arr == NULL) { printf("Memory not allocated.\n"); exit(0); } else { push(arr, 0, 1, &size, &capacity); push(arr, 1, 2, &size, &capacity); push(arr, 2, 3, &size, &capacity); printf("Current capacity: %d\n", capacity); // Current capacity: 2 push(arr, 3, 4, &size, &capacity); push(arr, 4, 5, &size, &capacity); push(arr, 5, 6, &size, &capacity); printf("Current capacity: %d\n", capacity); // Current capacity: 16 } }
Только авторизованные участники могут оставлять комментарии.

blog/dynamic_arrays_in_c_lang.txt
Последние изменения: 2019/05/28

C++ добавление элемента в конец динамического массива
Помогите не могу разобраться почему не работает: Необходимо в конец динамического массива добавить сумму его элементов. Мой код:
#include "stdafx.h" #include using namespace std; int* createArray(int*, int); void fillArray(int*, int); void printArray(int*, int); void deleteArray(int*); void addElemet(int*, int); int _tmain(int argc, _TCHAR* argv[]) < setlocale(LC_ALL, "rus"); int num = 0; cout > num; int sum = 0; int *pArray = NULL; pArray = createArray(pArray, num); fillArray(pArray, num); addElemet(pArray, num); printArray(pArray, num); deleteArray(pArray); return 0; > int* createArray(int *massiv, int number) //создание динамического массива < return massiv = new int[number]; >void fillArray(int* massiv, int number) //ввод данных в массив < for (int i = 0; i < number; i++) < cout > massiv[i]; > cout void printArray(int* massiv, int number) // вывод массива на печать < for (int i = 0; i < number; i++) < cout cout void deleteArray(int* massiv) //Очистка памяти < delete[] massiv; >void addElemet(int *massiv, int number) //добавление элемента в конец массива < int *temp = NULL; int numTemp = number + 1; int sum = 0; temp = createArray(temp, numTemp); // создаем временный массив for (int i = 0; i < number; i++) < temp[i] = i; //massiv[i]; // копируем данные со старого массива sum += massiv[i]; >temp[numTemp] = sum; // не добавляет элемент в конец массива, при выводе на экран скопированные элементы отображаются нормально, а последний отображает набор цифр deleteArray(massiv); // удаляем старый массив massiv = createArray(temp, numTemp); massiv = temp; //копируем временный массив в новый. deleteArray(temp); //удаляем временный массив > 


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

Dbeaver как открыть базу данных
Open hardware monitor как настроить скорость вентиляторов
Как отнять процент от числа в excel
Как сделать круговую диаграмму в powerpoint