Динамические массивы. Динамическая память на С++

1.

Динамические массивы
Динамическая память на
С++
1

2.

Когда необходимы
динамические массивы
• Если до начала работы программы неизвестно,
сколько в массиве элементов, или необходимо
освободить память, удалив массив, или размер
массива слишком велик и статический стек не
поддерживает такие объёмы, то в программе
следует использовать динамические массивы.
• Память под них выделяется с помощью операции
new или функции malloc (Си) в динамической
области во время выполнения программы.
• Адрес начала массива хранится в переменной,
называемой указателем.
2

3.

Способы описания одномерных
динамических массивов
int n = 10;
int *a = new int[n];
Во второй строке описан указатель на целую величину,
которому присваивается адрес начала непрерывной области
динамической памяти, выделенной с помощью функции new.
Выделяется столько памяти, сколько необходимо для
хранения n величин типа int.
Величина n может быть переменной.
Обнуление памяти при её выделении не происходит:
содержание выделенного блока памяти не инициализируется,
оно остается с неопределенными значениями.
Инициализировать динамический массив с помощью
списка констант нельзя.
Еще один способ описания динамического массива:
3
double *b = (double *)malloc(n* sizeof (double));

4.

Способы обращения к элементам
динамического массива
Обращение к элементу динамического массива
осуществляется так же, как и к элементу обычного:
a[3].
Но можно и так: *(a+3).
В переменной-указателе хранится адрес начла
массива. Для получения адреса третьего элемента,
к этому адресу добавляется 3.
Если динамический массив в какой-то момент работы
программы становится не нужен, и мы собираемся в
дальнейшем эту память использовать повторно,
необходимо освободить её сл. образом:
4
delete [ ] a;

5.

1. Инициализация одномерного массива
#include <iostream>
using namespace std;
void f(int *tf, int nf) // функция инициализации массива индексами
{
for(int i = 0 ; i < nf; i ++) // цикл по индексу эл-та массива
tf [ i ] = i;
// эл-ту массива присваивается его индекс
return;
}
// Главная функция
int main( )
{
int n = 6; // размер массива
int *t = new int [n]; // присваивание указателю адреса массива и
// выделение памяти под эл-ты массива
f(t, n); // обращение к функции инициализации массива
for(int i=0; i<n; i++) // цикл по индексу эл-та массива
cout << t[i] << " " ;
// вывод: значения эл-та массива и двух
пробелов
cout << endl;
// переход на другую строку
5
return 0;}

6.

Выделение памяти под двумерный массив
int n, m;
cout << “Input number of rows and columns: “;
cin>> n>>m;
int **a=new int *[n]; // выделяется память под массив
указателей на строки массива (n).
for (int i = 0; I < n; i++) //цикл для выделения
памяти под каждую строку массива.
a[ i ] = new int [m]; //каждому элементу
массива указателей на строки присваивается адрес
начала участка памяти, выделенного под строку
двумерного массива.
Каждая строка состоит из m элементов типа int.
6

7.

2. Размещение массива в оперативной
памяти
При размещении элементов двумерных массивов они располагаются в
памяти подряд по строкам, т.е. быстрее всего изменяется последний
индекс, а медленнее – первый.
Такой порядок дает возможность обращаться к любому элементу
двумерного массива, используя адрес его начального элемента и
только одно индексное выражение.
int arr[m][n]:
Адрес (arr[i][j])= Адрес(arr[0][0]) + (i*n+j)*k,
где k – количество байтов, выделяемое для элемента массива (в
зависимости от типа).
7

8.

Двумерный массив – это «массив строк,
каждая из которых - тоже массив»
int **a
int *a [n]
int a [n] [m]
m
8

9.

Принцип выделения памяти под
двумерный массив
Указатели на двумерные массивы в языке С++ – это
массивы массивов, т.е. такие массивы, элементами которых
являются массивы.
При объявлении таких массивов в памяти компьютера
создается несколько различных объектов. Например, при
выполнении объявления двумерного массива:
int arr [4][3];
1. В памяти выделяется участок для хранения значения
переменной arr, которая является указателем на массив из
четырех указателей.
2. Для этого массива из четырех указателей тоже выделяется
память. Каждый из этих четырех указателей содержит адрес
одномерного массива из трех элементов типа int.
3. Следовательно, в памяти компьютера выделяется четыре
участка для хранения четырех массивов чисел типа int,
каждый из которых состоит из трех элементов.

10.

Схематично распределение
памяти для данного двумерного
массива выглядит так:
Таким образом, объявление arr[4][3] порождает в программе три разных
объекта:
указатель с идентификатором arr,
безымянный массив из четырех указателей: arr[0], arr[1], arr[2], arr[3]
безымянный массив из двенадцати чисел типа int.

11.

Способы доступа к объектам массива
Для доступа к безымянным массивам используются адресные выражения с
указателем arr.
Доступ к элементам одномерного массива указателей осуществляется с
указанием одного индексного выражения в форме arr[2] или *(arr+2).
Для доступа к элементам двумерного массива чисел типа int arr[i][j] должны быть
использованы следующие выражения:
Например, пусть i=1, j=2, тогда обращение к элементу arr[1][2], который может
быть определён так:
arr[i][j] arr[1][2]=10
*(*(arr+i)+j) *(*(arr+1)+2)=10
(*(arr+i))[j] (*(arr+1))[2]=10
Можно сделать, например, с помощью указателя ptr:
ptr[1*3 + 2] или ptr[5]
/*здесь 1 и 2 - это индексы используемого элемента, а 3 это число
элементов в строке*/
Причем внешне похожее обращение arr[5] выполнить невозможно, так как
указателя с индексом 5 не существует.

12.

Использование индексных и адресных выражений
при обработке двумерных массивов (пример).
int main(){
int i, j;
int t[2][3]; // при вводе обращение с помощью индексов
// можно использовать адресные выражения
for(i=0;i<2;i++)
for(j=0;j<3;j++)
t[i][j]=i+j;
for(i=0;i<2;i++)
for(j=0;j<3;j++)
//при печати рассматриваем имя массива как указатель
на начало
printf(" %d ", *(*(t + i) +j) );
//или printf(" %d ", (*(t + i))[j]);
system("pause");
return 0;
}

13.

Демонстрация связи между матрицей и
указателем на нее.
int main(){
int i,j;
int t[2][3],*ptr;
ptr=&t[0][0];
for(i=0;i<2;i++)
for(j=0;j<3;j++)
t[i][j]=i+j;
for(i=0;i<2;i++)
for(j=0;j<3;j++)
printf(" %d ", *(ptr+i*3+j));
printf("\n\n");
//С матрицей так делать нельзя
/* for(i=0;i<2;i++)
for(j=0;j<3;j++)
printf(" %d ", *(t + i*3 +j) ); */
//Корректная работа с матрицей
for(i=0;i<6;i++)
printf(" %d ", ptr[i] );
printf("\n\n");
for(i=0;i<2;i++)
for(j=0;j<3;j++)
printf(" %d ", ptr[i*3 +j] );
system("pause");
return 0;
}

14.

Некоторые выводы
• В Си нет массивов. Для их эмуляции используется постоянный адрес и
область памяти, выделяемая специальными функциями. int
A={1,2,…,10};
• Если А – это имя массива, то это и одновременно адрес первого
элемента этого массива: int х=*(А+1); или х=*А;
• Допустимо: если int*p; A[i]=*A[A+i]; &A[i]=A+i; то p= &A[i];
если p=A+5; то p[0] = A[5] =6 (смещение от начала выделенной памяти
= 0), то p[-1]=5
• Размер выделяемой памяти под массив ограничен разрядностью
адресации ОС и физической памятью, выделяемой и ОС.
• Для работы с большими объёмами массивов желательно проверять,
выделена память или нет:
if (NULL==A)
{cout<<“OS didn’t give memory. Exit…\n”;
exit(1);
}
NULL – адрес в НИКУДА
14

15.

3. Задача (двумерный массив)
Дан двумерный массив, содержащий З строки и
4 столбца.
Элементами массива являются целые числа.
Элементы каждого из столбцов увеличить на
найденное
максимальное значение этого столбца.
Результат получить в другом массиве.
15

16.

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;
Запуск генератора случайных чисел
лучше делать ВНЕ функции
инициализации
// инициализация массива случайными числами
void f_rand(int **tf, int nf, int mf, int r_min, int r_max)
{
srand( (unsigned int) time(NULL)); // рандомизация генератора
for(int i=0; i<nf; i++) // цикл по строкам
for(int j=0; j<mf; j++) // цикл по столбцам
tf[i][j]=rand( ) % (r_max - r_min+1) + r_min; // инициализация
эл-та массива
return; // возврат в место вызова функции
}
16

17.

// вывод массива на экран
void f_print(int **tf, int nf, int mf)
{
cout << endl;
// переход на новую строку
for(int i=0; i<nf; i++) // цикл по строкам
{
for(int j=0; j<mf; j++)
// цикл по столбцам
cout << setw(6) << tf[i][j] ; // вывод эл-та массива
cout << endl; // переход на новую строку
}
return;
}
17

18.

Элементы каждого из столбцов
увеличить на найденное
максимальное значение этого столбца.
// функция решения задачи
void f_task(int **t1f, int **t2f, int nf, int mf) Результат получить в другом массиве.
{
for(int j=0; j<mf; j++) // цикл по СТОЛБЦАМ
{
int im = 0;
// номер максимального эл-та в столбце
for(int i=1; i<nf; i++) // цикл по строке
{
if(t1f[i][j] > t1f[im][j]) // если найден больший эл-т
im = i; // запоминаем этот номер
}
for(int i=0; i<nf; i++) // цикл по строке
t2f[i][j] = t1f[i][j] + t1f[im][j]; // задание значений другого
массива
}
return; // возврат обратно в место вызова
}
18

19.

int main( )
// главная функция
{
setlocale(0,""); // поддержка кириллицы
int n = 6; // кол-во строк в массиве
int m = 7; // кол-во столбцов в массиве
int **t1 = new int *[n]; // указатель на массив указателей на int
for(int i = 0; i < n; i++)
// цикл по строкам
t1[i] = new int [m]; // каждому эл-ту массива указателей на
строки
// присваивается адрес начала участка памяти,
// выделенного под строку двумерного массива
//и выделяется память под каждую строку массива
int **t2 = new int *[n]; // указатель на массив указателей на int
for(int i = 0; i < n; i++)
// цикл по строкам
t2[i] = new int [m]; // присваивание адреса и выделение
памяти
19

20.

// обращение к функции инициализации массива
f_rand(t1, n, m, -5, 5);
cout << "Исходный массив"<< endl;
// обращение к функции вывода массива
f_print(t1, n, m);
// обращение к функции решения поставленной задачи
f_task(t1, t2, n, m);
cout << endl << "Сформированный массив"<< endl;
// обращение к функции вывода массива
f_print(t2, n, m);
return 0; // выход из главной функции
}
20

21.

21

22.

В рамках структурного
подхода главная программа
должна иметь ЛИНЕЙНУЮ
структуру
Циклы и ветвления в main() допустимы
только, если они ответственны за
пользовательский интерфейс.
Но и для организации пользовательского
интерфейса желательно создавать
отдельные модули.
22