Динамические массивы
Для того чтобы создать в динамической области некоторый объект необходима одна обычная (не динамическая переменная) переменная-указатель. Сколько таких объектов нам понадобится для одновременной обработки – столько необходимо иметь обычных переменных-указателей. Таким образом, проблема “задач неопределенной размерности” созданием одиночных динамических объектов решена быть не может.
Решить эту проблему поможет возможность создавать в динамической области памяти массивы объектов с таким количеством элементов, которое необходимо в данный момент работы программы – то есть создание динамических массивов. Действительно, для представления массива требуется всего одна переменная-указатель, а в самом массиве, на который ссылается этот указатель, может быть столько элементов, сколько требуется в данный момент времени.
Сначала рассмотрим одномерные динамические массивы.
Для создания одномерного динамического массива, элементами которого являются, например, действительные числа, используется следующий синтаксис инструкции new:
double *Arr = new double [1000];
Здесь в динамической области памяти будет выделено пространство на 1000 значений типа double, и адрес этой области будет присвоен переменной-указателю Arr. Таким образом, переменная-указатель Arr, как и переменная для обычного массива, будет содержать адрес первого элемента массива.
Освободить динамическую область от этого массива можно так:
delete [ ] Arr;
После этого участок памяти объемом 1000 * sizeof ( double ) байт будет возвращен в список свободной памяти и может быть повторно использован для размещения других динамических объектов.
С помощью функций malloc и calloc тот же самый одномерный динамический массив создается так:
double *Arr = (double *) malloc(1000 * sizeof (double ) );
или
double *Arr = (double *) сalloc(1000, sizeof (double ) );
Освобождение памяти в этих случаях осуществляется с помощью функции free:
Free ( Arr );
Работа с одномерным динамическим массивом осуществляется так же, как и с обычным. Рассмотрим пример, в котором создадим динамический массив целых с количеством элементов, введенном с клавиатуры; заполним его случайными значениями в диапазоне от 1 до 100; подсчитаем и выведем на экран среднее значение всех элементов этого массива:
int n;// Количество элементов массива
cin >> n;// Вводим количество элементов массива с клавиатуры
int *Arr = new int [ n ];// Создаем массив Arrцелых чисел на n элементов
for ( int i = 0; i < n; ++ i)// Заполняем массив случайными значениями
Arr [ i ] = rand ( ) % 100 + 1;
int Sum = 0;// Сумма элементов массива
for ( int i = 0; i < n; ++ i )// Подсчитываем сумму элементов массива
Sum += Arr [ i ];
cout << (double) Sum / n << endl;// Выводим на экран среднее значение
delete [ ] Arr;// Освобождаем память
Очень часто в процессе работы программы требуется изменять размеры уже созданных и заполненных данными массивов. Общий алгоритм решения этой задачи таков:
1. создать исходный массив размерности N1 и заполнить его данными;
2. создать промежуточный массив размерности N2 (пусть N2 > N1);
3. скопировать данные из исходного массива в промежуточный массив;
4. освободить память от исходного массива;
5. переменной-указателю исходного массива присвоить значение переменной-указателя промежуточного массива;
6. заполнить новые элементы массива данными.
Вот как можно решить эту задачу в стиле C++:
int N1 = 10,// Начальный размер массива
N2 = 20;// Новый размер массива
int *Arr = new int [N1];// Создаем исходный массива из N1 элемента
for (int i = 0; i < N1; ++ i)// Заполняем исходный массив числами от 0 до 9
Arr[i] = i;
for (int i = 0; i < N1; ++ i)// Выводим исходный массив на экран
cout << Arr[i] << " ";
cout << endl;
int *Rez = new int [N2];// Создаем промежуточный массив из N2 элементов
for (int i = 0; i < N1; ++ i)// Копируем данные из исходного массива
Rez[i] = Arr[i];// в промежуточный
delete [ ] Arr;// Освобождаем память от исходного массива. Если этого не
// сделать, произойдет утечка памяти
Arr = Rez;// Изменяем переменную исходного массива
for (int i = N1; i < N2; ++ i)// Дополняем исходный массив числами от 10 до 19
Arr[i] = i;
for (int i = 0; i < N2; ++ i)// Снова выводим исходный массив на экран
cout << Arr[i] << " ";
cout << endl;
delete [ ] Arr;// Окончательно освобождаем память от исходного массива.
В результате работы этого фрагмента программы на экран будут выведены значения массива до его расширения и после расширения:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Если удалить из этого фрагмента строки, не имеющие непосредственного отношения к решаемой задаче (это ввод данных в массивы, вывод данных на экран), то “скелет” алгоритма будет таким:
int N1 = 10,// Начальный размер массива
N2 = 20;// Новый размер массива
int *Arr = new int [N1];// Создаем исходный массива из N1 элемента
……. // Работаем с массивом старой длины
int *Rez = new int [N2];// Создаем промежуточный массив из N2 элементов
for (int i = 0; i < N1; ++ i)// Копируем данные из исходного массива
Rez[i] = Arr[i];// в промежуточный
delete [ ] Arr;// Освобождаем память от исходного массива. Если этого не
// сделать, произойдет утечка памяти
Arr = Rez;// Изменяем переменную исходного массива
……. // Работаем с массивом новой длины
delete [ ] Arr;// Окончательно освобождаем память от исходного массива.
А вот как решается эта же задача при использовании стиля языка C:
int N1 = 10,// Начальный размер массива
N2 = 20;// Новый размер массива
int *Arr = (int *) malloc( N1 * sizeof ( int ) );// Создаем массив из N1 элемента
for (int i = 0; i < N1; ++ i)// Заполняем массив числами от 0 до 9
Arr[i] = i;
for (int i = 0; i < N1; ++ i)// Выводим массив на экран
cout << Arr[i] << " ";
cout << endl;
Arr = (int *) realloc( Arr, N2 * sizeof ( int ) );// Изменяем размер массива
for (int i = N1; i < N2; ++ i)// Дополняем массив числами от 10 до 19
Arr[i] = i;
for (int i = 0; i < N2; ++ i)// Снова выводим массив на экран
cout << Arr[i] << " ";
cout << endl;
delete [ ] Arr;// Окончательно освобождаем память от исходного массива.
А вот, что представляет “скелет” алгоритма, в этом случае:
int N1 = 10,// Начальный размер массива
N2 = 20;// Новый размер массива
int *Arr = (int *) malloc( N1 * sizeof ( int ) );// Создаем массив из N1 элемента
……. // Работаем с массивом старой длины
Arr = (int *) realloc( Arr, N2 * sizeof ( int ) );// Изменяем размер массива
……. // Работаем с массивом новой длины
delete [ ] Arr;// Окончательно освобождаем память от исходного массива.
Не правда ли, существенно короче и понятнее.
Перейдем к рассмотрению двумерных массивов. С ними дело обстоит несколько сложнее, чем с одномерными динамическими массивами.
В стиле C++ двумерный массив целых чисел можно создать и удалить следующим образом:
int ( * Arr ) [ 10 ] = new int [ dim ] [ 10 ];
delete [ ] Arr;
В этом примере создается двумерный массив из dimстрок и 10 столбцов. Элементами массива являются целые числа типа int. При таком способе создания двумерных массивов изменять в процессе выполнения программы можно только самую левую размерность массива (dim). Вторая размерность должна задаваться константным значением (в нашем случае 10). Таким образом, динамически изменяемым в таких массивах является только количество строк, а количество столбцов остается постоянным. Пример использования этого метода:
cin >> dim;// Вводим с клавиатуры количество строк массива
int ( * Arr ) [ 10 ] = new int [ dim ] [ 10 ];// Выделяем память в динамической области
// Заполняем массив Arr значениями равными сумме индексов элементов массива
for ( int i = 0; i < dim; ++ i )
for ( int j = 0; j < 10; ++ j )
Arr [ i ] [ j ] = i + j;
// Выводим на экран элементы массива Arrв виде таблицы, содержащей dimстрок и
// 10 столбцов
for (int i = 0; i < dim; ++ i)
{
for (int j = 0; j < 10; ++ j)
cout << setw(4) << Arr[i][j];
cout << endl;
}
delete [ ] Arr;// Освобождаем память от массива Arr
Недостаток этого метода очевиден – мы можем управлять только одной размерностью такого массива.
Для того чтобы избавиться от этого недостатка представим двумерный массив как одномерный массив, элементами которого являются одномерные массивы элементов базового типа массива.
Пусть базовым типом элементов нашего двумерного массива, как и в предыдущем примере, будут целые числа типа int. Этот двумерный массив можно представить как набор из RowCount строк, то есть как одномерный массив строк. Этому массиву на приведенном ниже рисунке соответствует вертикальный массив, элементами которого являются указатели на тип int (каждый элемент этого массива будет содержать адрес первого элемента соответствующей строки int*). Каждая строка представляет собой одномерный массив из ColCount элементов типа int. Элементы массивов-строк служат для хранения данных, для которых и предназначен двумерный массив.
| int**Arr |
  ColCount
| |||
 
RowCount
| int* | int* | ||
 
| int | int | …. | int |
| int* | ||||
| int | int | ….. | int |
| …. | …….. | |||
| int* | ||||
| int | int | ….. | int |
Таким образом, для того чтобы получить двумерный массив, нам необходимо:
1. создать одномерный динамический массив из RowCount указателей на базовый тип элементов массива (в нашем случае указателей на тип int);
2. в цикле создать RowCountодномерных динамических массивов, каждый из которых содержит ColCount элементов базового типа (в нашем случае указателей на тип int) и адреса их первых элементов записать в соответствующие элементы “вертикального” массива.
Остается неясным вопрос: как определить массив указателей (“вертикальный” массив)? Обычный одномерный массив определяется как указатель на базовый тип данных элементов этого массива. Базовым типом элементов этого массива являются указатели int*. Для того чтобы определить указатель на указатель достаточно использовать следующую конструкцию: (int*)* или проще int**.
Таким образом, для того чтобы создать динамический массив Arrизуказателей, можно поступить так:
int ** Arr = new int * [ RowCount ]
Создание массива-строки p еще проще:
int * p = new int [ ColCount ]
Тогда для создания всего двумерного динамического массива необходимо выполнить следующие действия:
int ** Arr = new int * [ RowCount ];// Создаем “вертикальный” массив
for ( int i = 0; i < RowCount; ++ i )
Arr [ i ] = new int [ ColCount ];// Создаем i-ый массив-строку
Для освобождения памяти необходимо:
1. сначала в цикле удалить RowCount массивов-строк;
2. затем удалить “вертикальный” массив.
for ( int i = 0; i < RowCount; ++ i )
delete [ ] Arr [ i ];// Удаляем i-ый массив-строку
delete [ ] Arr;// Удаляем “вертикальный” массив
Следующий рабочий фрагмент программы обеспечивает: создание такого двумерного массива размерности n на m (вводятся с клавиатуры), заполнение его некоторыми данными; вывод значений элементов массива на экран в виде таблицы; освобождение памяти:
int **CreateArr ( unsigned RowCount, unsigned ColCount )
// Создает двумерный динамический массив целых чисел из RowCount строк
// и ColCountстолбцов. Возвращает адрес массива.
{
int **Arr = new int* [RowCount];
for ( unsigned i = 0; i < RowCount; ++i )
Arr[i] = new int[ColCount];
Return Arr;
}
void FreeArr( int **Arr, unsigned RowCount )
// Удаляет двумерный динамический массив целых чисел Arr из RowCount строк
{
for ( unsigned i = 0; i < RowCount; ++i)
delete [ ] Arr [ i ];
delete [ ] Arr;
}
int _tmain(int argc, _TCHAR* argv[])
{
int N1 = 10,
N2 = 20;
cin >> N1 >> N2;// Вводим размерности массива
int ** Arr = CreateArr ( N1, N2 );// Создаем массив
// Начинаем работу с массивом
for ( int i = 0; i < N1; ++ i )// Заполняем массив данными
for ( int j = 0; j < N2; ++ j )
Arr [ i ][ j ] = i + j;
for ( int i = 0; i < N1; ++ i )// Выводим массив на экран
{
for ( int j = 0; j < N2; ++ j )
cout << setw(4) << Arr [ i ][ j ];
cout << endl;
}
// Заканчиваем работу с массивом
FreeArr ( Arr, N1 );// Освобождаем память
system ( "pause" );
Return 0;
}
В этом примере действия, связанные с созданием динамического двумерного массива и его удалением, оформлены в виде функций, чтобы не отвлекать внимание от содержания основного алгоритма. Операции с созданным таким образом двумерным динамическим массивом осуществляются точно так же, как и с обычными двумерными массивами.
Для создания динамических двумерных массивов с другими базовыми типами элементов достаточно в предыдущих примерах заменить тип данных int, на необходимый тип данных. Ну, и конечно, изменить работу с элементами массива в соответствии с их типом данных. Обязательные места исправлений выделены красным цветом.
По аналогии с двумерными динамическими массивами можно создавать и массивы большей мерности.
Дата добавления: 2019-02-07; просмотров: 718;