Динамические массивы в C++ — урок 8
В пятом уроке мы разобрали понятие массива. При объявлении, мы задавали массиву определенный постоянный размер. Возможно, кто-то из читателей пробовал делать так:
Но, как уже было сказано — при объявлении статического массива, его размером должна являться числовая константа, а не переменная. В большинстве случаев, целесообразно выделять определенное количество памяти для массива, значение которого изначально неизвестно.
Например, необходимо создать динамический массив из N элементов, где значение N задается пользователем. В предыдущем уроке мы учились выделять память для переменных, используя указатели. Выделение памяти для динамического массива имеет аналогичный принцип.
Создание динамического массива
using namespace std; int main() < int num; // размер массива cout > num; // получение от пользователя размера массива int *p_darr = new int[num]; // Выделение памяти для массива for (int i = 0; i < num; i++) < // Заполнение массива и вывод значений его элементов p_darr[i] = i; cout delete [] p_darr; // очистка памяти return 0; >
Синтаксис выделения памяти для массива имеет вид указатель = new тип[размер] . В качестве размера массива может выступать любое целое положительное значение.
Си, динамические массивы
писал я тут большую программу с разными сортировками, все сделал, все работает. Кроме того, что компилятор выдает предупреждение, мол в стеке слишком много байт(не удивительно, так-то, 3 статических массива по 5000 элементов задаю). Мне как-то объяснили, что нужно использовать динамические массивы. Я, вроде, понял, что это такое, но как использовать на практике -не очень. Я написал программу с одной сортировкой, буду рад, если покажете, как заменить массив на динамический.
#include #include "locale.h" #include "stdbool.h" void printArray(int A[], int* n) < int i; for (i = 0; i < *n; i++) printf("%d ", A[i]); printf("\n"); >void writeArray(int A[], int B[], int* n) < int i; printf("-----------Обьявление массива-----------\n"); printf("Введите размер массива:\n"); scanf_s("%d", &*n); printf("Наберите массив:\n"); for (i = 0; i < *n; i++) scanf_s("%d", &A[i]); printf("Массив: "); printArray(A, n); printf("-----------Массив объявлен -------------\n"); for (i = 0; i < *n; i++) B[i] = A[i]; >void BubbleSort(int A[], int* n) < int i, j; int tmp, bsw = 0, bco = 0, NO = 0; printf("-----------Сортировка массива пузырьком-----------\n"); printf("Массив на входе: "); printArray(A, n); bool this; for (i = 0; i < *n; i++) < this = true; for (j = 0; j < *n - i - 1; j++) < if (A[j] >A[j + 1]) < tmp = A[j]; A[j] = A[j + 1]; A[j + 1] = tmp; this = false; >> if (this == true) break; > printf("Готовый массив: "); printArray(A, n); > int main()
Отслеживать
задан 23 ноя 2020 в 13:08
13 1 1 серебряный знак 4 4 бронзовых знака
В вашем варианте достаточно заменить int A[3000]; int B[3000]; на int \*A = malloc(3000\*sizeof(int)); int \*B = malloc(3000\*sizeof(int)); . Конечно, если вы компилируете код как С. По окончании работы можно освободить память — free(A); free(B);
Как создать динамический массив в си
Кроме отдельных динамических объектов в языке 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Динамические массивы в 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