Основные теоретические сведения. В лабораторных работах 3 и 4 мы решали задачи со статическими массивами
В лабораторных работах 3 и 4 мы решали задачи со статическими массивами. Размер статического массива определяется еще на этапе компиляции.
Работа с фиксированным набором переменных в программе может серьезно стеснять разработчика. Часто в приложениях возникает необходимость в оперативном принятии решений относительно динамического выделения места для размещения переменных различных типов непосредственно во время выполнения в зависимости от входных данных, полученных программой.
Для одного набора данных может быть разумно применять большой массив целых чисел, в то время как другой набор входных данных может потребовать большого массива чисел с плавающей точкой.
Понятно, что поскольку динамически распределенные переменные не могут быть определены во время компиляции, они не имеют имен в исходном тексте программы. Когда они создаются, то идентифицируются адресами в памяти, которые сохраняются в указателях.
Обычно, когда выполняется ваша программа, у компьютера есть неиспользуемая память. Эта неиспользуемая память в С++ называется кучей или, иногда, свободным хранилищем. Вы можете выделить память внутри этого хранилища для новой переменной заданного типа с помощью специальной операции С++, которая возвращает адрес выделенного пространства. Этой операцией является new, и ее дополняет операция delete, которая освобождает память, ранее выделенную new.
Вы можете выделить память в свободной хранилище для некоторой переменной в одной части программы, а затем освободить выделенное пространство и вернуть его в свободное хранилище после того, как необходимость в этой переменной отпадет. Это позволяет позже в той же программе повторно задействовать эту память для других динамически распределяемых переменных.
Память из свободного хранилища используется всякий раз, когда возникает потребность в выделении памяти для элементов, которые могут быть определены лишь во время выполнения. Примером может служить выделение памяти для строк, вводимых пользователем вашего приложения. Неизвестно
насколько большими должны быть эти строки, поэтому имеет смысл выделять память для них во время выполнения, используя для этого операцию new. Это мощная техника, которая позволяет расходовать память очень эффективно, и во многих случаях разрабатывать программы, способные решать намного более масштабные проблемы, обрабатывая большие объемы данных, чем это возможно без ее применения.
Операции new и delete
Предположим, что вам необходимо пространство для переменной типа double. Вы можете определить указатель на тип double и затем запрашивать память во время выполнения. Вы можете делать это, используя операцию new в следующих операторах:
double* pvalue = NULL; // Указатель, инициализированный null
pvalue = new double; // Запрос памяти для переменной double
Пользуемся случаем, чтобы напомнить, что все указатели должны быть инициализированы. Динамическое использование памяти обычно предполагает появление множества "плавающих" указателей, поэтому важно, чтобы они не содержали неправильных значений. Следуйте правилу, что если указатель еще не содержит корректного значения адреса, то установите его в 0.
Операция new во второй строке приведенного выше кода должна вернуть адрес памяти из свободного хранилища, выделенный для размещения переменной типа double, и этот адрес сохраняется в pvalue. Затем вы можете применять этот указатель для ссылки на переменную, используя операцию разыменования, как уже было показано ранее.
*pvalue = 5555.0;
Вы можете сразу инициализировать переменную операцией new при ее создании. Если взять пример с переменной double, которая распределяется операцией new и чей адрес сохраняется в pvalue, то можно сразу установить ей значение 999.0 с помощью следующего оператора:
// Выделить память под double и инициализировать ее
pvalue = new double(555.0);
Когда отпадает необходимость в переменной, распределенной динамически, вы можете освободить память, которую она занимала в свободном хранилище, операцией delete:
delete pvalue; // Освободить память, на которую указывает pvalue
Эта операция обеспечивает возможность последующего использования этой памяти другими переменными. Если вы не применяете delete и позже присвоите указателю pvalue другое значение адреса, то станет невозможным освободить память или использовать переменную, которая в ней содержится, поскольку доступ к этому адресу будет утерян. В такой ситуации происходит то, что называется утечкой памяти (memory leak) - особенно если данная ситуация в программе повторяется многократно.
Динамическое распределение памяти для массивов
Динамически выделить память для массива очень просто. Если необходимо распределить массив типа char, то предполагая, что pString - указатель на char, можно написать следующий оператор:
pString = new char [20]; //распределение строки в 20 символов
Мы выделили память для символьного массива размером в 20 символов и сохраняет указатель на него в pString.
Чтобы освободить распределенный таким образом массив и вернуть память в свободное хранилище, вы должны применить операцию delete. Оператор должен выглядеть так:
delete []pString; // Удалить массив, на который указывает pstr
Обратите внимание на квадратные скобки, они говорят о том, что то, что вы удаляете - массив. Когда освобождается массив, распределенный в свободном хранилище, всегда нужно указывать квадратные скобки, иначе результат будет неопределенным. При этом не нужно указывать размер массива - достаточно просто скобок [ ].
Конечно, указатель pString после этого будет содержать адрес памяти, которая может быть уже распределена для каких-то других целей, поэтому, конечно же, он не должен никак использоваться. Поэтому когда вы применяете операцию delete для того, чтобы освободить некоторую память, которая была распределена ранее, то всегда должны сбрасывать значение указателя в 0, как показано ниже:
pString = 0; // Установить указатель в null
Рассмотрим, как выделить память под одномерный динамический массив.
Пусть размерность динамического массива вводится с клавиатуры. Необходимо выделить память под этот массив, а затем созданный динамический массив надо удалить. Соответствующий фрагмент программы имеет вид:
int n;
…..
cin>>n; // размерность массива
int *mas=new int[n]; // выделение памяти под массив
….
delete mas; //освобождение памяти
В данном примере mas является указателем на массив из n элементов.
Оператор int *mas=new int[n];
производит два действия: объявляется переменная типа указатель, а затем указателю присваивается адрес выделенной области памяти в соответствии с заданным типом объекта. Эти две операции можно разделить.
…
int n;
int* mas;
…
cin>>n; // n- размерность массива
mas=new int[n]; // выделение памяти под массив
…
delete mas;
Для примера решим задачу поиска суммы элементов одномерного массива, состоящего из n элементов , где размерность массива задается в процессе выполнения программы. И, соответственно, память в таком случае выделяется динамически.
//Листинг 24
//Поиск суммы элементов динамического массива вещественных чисел
#include <iostream.h>
void main ()
{
int i,n; // переменные для индекса и размера массива
float *a; // указателя на «float»
float s; //переменная для суммы
cout<<"n=";
cin>>n; //ввод размера массива
//выделение памяти для динамического массива
a=new float[n];
cout << "vvedite massiv A\n";
for (i=0;i<n; i++) //последовательный ввод элементов массива
//cin>>a[i]; //можно и так
cin>>*(a+i);
for(s=0, i=0; i<n; i++) //вычисление суммы
//s+=a[i];
s+=*(a+i);
cout << "S= "<<s<<'\n'; //вывод результата
//освобождение памяти
delete [] a;
}
В самом начале определим переменные, которые потребуются в дальнейшем- это индекс элемента массива, количество элементов в массиве, указатель, в котором сохранится адрес первого элемента массива при динамическом выделении памяти, и переменная для накопления суммы элементов.
Далее следует оператор ввода количества элементов в массиве.
Обратите внимание. что это количество элементов, размер массива , задается, когда программа уже работает. Далее в операторе a=new float[n];
происходит динамическое выделение памяти для n элементов массива.
Динамическим называется любое действие по распределению ресурса или связыванию, которое происходит не на этапе компиляции, а во время работы программы.
В следующем цикле происходит ввод элементов массива последовательно с клавиатуры. А потом выполняется суммирование. В листинге приводится два варианта операторов внутри цикла. Закомментированный вариант более привычен вашему глазу, но второй вариант аналогичен. Во втором варианте более наглядно видна идея индекса, как смещения от первого элемента. В данном случае - смещения адреса от адреса первого элемента массива.
После всего этого - выводим на экран результат наших трудов, снабдив предварительно заголовком.
и последнее усилие – освобождаем выделенную ранее память. Пусть и другие воспользуются.
Динамическое распределение многомерных массивов
Выделение памяти в свободном хранилище для многомерного массива предполагает использование операции new в несколько более сложной форме, чем для одномерного массива.
Рассмотрим, как динамически выделить память под двумерный массив.
Пусть требуется создать двумерный динамический массив целых чисел размерностью n на k:
...
int n, k, i;
int**mas;
…
cin>>n; //n- число строк массива
cin>>k; // k – число столбцов массива
mas = new int*[n]; //выделение памяти под n указателей на строку
// выделение памяти для каждой строки по числу столбцов k
for (i=0;i<n;i++)
mas[i] = new int[k];
…
for (i=0;i<n;i++) // освобождение памяти
delete mas[i];
delete [] mas;
Сначала необходимо с помощью операции new выделить память под n указателей. Выделенная память будет представлять собой вектор, элементом которого является указатель. При этом все указатели располагаются в памяти последовательно друг за другом. После этого необходимо в цикле каждому указателю присвоить адрес выделенной области размером, равным второй границе массива.
А теперь решим задачу матричной алгебры по поиску суммы элементов главной диагонали матрицы , с заданными в процессе работы программы размерами.
Надо отметить, что матрицу очень легко отождествить с двумерным массивом. Поэтому именно задачи матричной алгебры широко используются в учебных целях, для получения навыков работы с массивами. Далее в задачах этого мы типа будем применять термины матричной алгебры к двумерному массиву.
При этом следует помнить, что нумерация строк и столбцов массива начинается с 0.
// Листинг 25
//Определение суммы элементов главной диагонали динамического массива
#include < iostream.h >
void main()
{
int **array;
int n, m;
int i, j, sum;
//выделение памяти для динамического массива
cout<<"Enter number of rows and number of columns\n";
cin>> n>> m; //ввод размеров массива
array = new int*[n]; //выделение памяти для массива указателей
for (i = 0; i < n; i++) //выделение памяти для строк массива
{
array[i] = new int[m];
cout<<"Now enter all numbers\n";
for (j = 0; j < m; j++) //ввод элементов массива
cin>> array[i][j];
}
//Вывод массива на экран
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
cout<<array[i][j]<<'\t';
}
cout<<endl;
}
cout<<endl;
// Вычисление суммы элементов главной диагонали
sum = 0;
for (i = 0; (i < n) && (i < m); i++)
sum += array[i][i];
cout<<"Sum of diagonal:"<< sum <<"\n";
// Освобождение памяти
for (i = 0; i < n; i++)
delete[] array[i];
delete[] array;
}
В этом примере необходимо выделить память под двумерный массив.
Объявление указателя
int **array;
таким образом, указывает на то, что array - указатель на массив указателей.
Далее объявляем переменные для хранения размеров массива, которые введем в процессе работы программы, индексов и суммы. После следуют оператор для ввода размеров массива. Потом выделяем место в свободном хранилище для динамического двумерного массива. Обратите внимание на то,что размер массива мы задали в ходе выполнения программы, а не так, как задавали ее для статического массива, при его объявлении. Прежде всего выделяем память для массива указателей , по количеству строк в массиве, а потом, в цикле, выделяем память для каждой строки массива. Адреса строк располагаются в соответствующих элементах массива указателей.
А теперь в цикле инициализируем массив. Для удобства и наглядности имеет смысл вывести на экран введенный массив построчно, в виде матрицы. Мы будем иметь возможность оценить правильность полученного результата.
Суммируем элементы главной диагонали, и выводим результат.
После работы с данными, освобождаем память – сначала, в цикле, каждой строки, а уже после этого, массива указателей.
Решим еще одну задачу
// Листинг 26
//Дана действительная матрица m х n. Найти последовательность, //состоящую из наибольших значений строк исходной матрицы
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip.h>
int main()
{
//выделение места для динамического массива
//заполнение массива
srand(time(NULL));
int m, n, i, j;
int **matr;
int *b;
//cout << "Enter number of rows and number of columns\n";
//cin >> m >> n;
n = rand() % 10 + 1; //индексы - случайные числа
m = rand() % 10 + 1;
matr = new int*[m]; //выделение памяти под массив указателей
cout << "m: " << m << ", n: " << n << '\n';
cout << "matrix:\n";
for (i = 0; i < m; i++)
{
matr[i] = new int[n]; //выделение памяти для строк массива
//заполнение массива случайными числами и вывод массива на экран
for (j = 0; j < n; j++)
{
matr[i][j] = rand() % 100;
cout <<setw(5) << matr[i][j] ;
}
cout << endl;
}
cout << endl;
b = new int[m]; //массив наибольших значений строк
for (i = 0; i < m; i++) //определение наибольших значений строк
{
b[i] = matr[i][0];
for (j = 1; j < n; j++)
{
if (matr[i][j] > b[i])
{
b[i] = matr[i][j];
}
}
}
cout << "Maximums of rows:\n";
for (i = 0; i < m; i++) {
cout << b[i] << endl;
}
// Освобождение памяти
for (i = 0; i < m; i++)
delete[] matr[i];
delete[] matr;
delete[] b;
return 0;
}
В этом примере мы снова применили наши знания программирования для решения задачи матричной алгебры.
В отличие от предыдущих задач, мы не вводили значения элементов массива вручную , а воспользовались генератором случайных чисел. Это очень удобно, особенно если предположить, что массив может быть велик, и ввод с клавиатуры сильно утомителен.
Чтобы работать с генератором случайных чисел, нужно подключить соответствующую библиотеку
#include <stdlib.h>
а в самой программе воспользуемся функцией rand() для генерации случайного числа.
Но, чтобы функция заработала, нужно выполнить инициализацию генератора случайных чисел. Инициализацию генератора случайных чисел лучше выполнить таймером, тогда значения будут обновляться.
Для работы с таймером также необходима библиотека
#include <time.h>
и соответствующий оператор для инициализации генератора случайных чисел
srand(time(NULL));
Случайным образом мы задаем индексы элементов массива
m = rand() % 10 + 1;
Производимое генератором число случайно, и находится в определенном , достаточно большом диапазоне. Для заполнения массива мы можем захотеть, и обычно хотим, этот диапазон ограничить.
Когда мы получаем остаток от деления любого числа на десять, например, результат всегда будет находиться в диапазоне от 0 до 9. Но поскольку мы задаем индекс массива логично задать его в интервале от 1 до 10, что мы и сделали, добавив единицу. Смещение интервала может быть любым, каким захотим.
При заполнении массива случайными числами, мы воспользовались оператором
matr[i][j] = rand() % 100;
Значения элементов динамического массива будут меньше ста.
В программе также будет создан еще один одномерный динамический массив
b = new int[m];
для хранения наибольших значений строк.
Он также создается динамически, так как его размер неизвестен до выполнения программы.
Остальные действия , предпринятые нами, для создания динамического двумерного массива, уже знакомы. Перед завершением программы главное не забыть об освобождении всей выделенной памяти.
Варианты заданий
| Заполните массив К размерностью m×n случайными числами от -25 до 75. Выведете на экран. Посчитайте произведения всех отрицательных элементов массива. Выведите на экран. Найдите суммы каждого столбца и определить минимальную среди полученных сумм. Выведите на экран. Замените ею отрицательные элементы массива. Преобразованный массив выведите на экран. | |
| Присвойте элементам массива D размерностью m×m случайные числа от -10 до 15. Вывести на экран. Посчитать произведения всех положительных элементов массива. Вывести на экран. Отрицательные элементы четных строк массива замените их модулями. Преобразованный массив выведите на экран Найдите максимальный и минимальный элементы массива. Выведите на экран | |
| Присвойте элементам массива В размерностью m×n случайные числа от 0 до 90. Выведите на экран. Выберите четные элементы массива, среди них найдите максимальный элемент и выведите его на экран Найдите суммы всех строк массива. Выведите на экран. Замените элементы массива, кратные 5,средним арифметическим этих сумм. Преобразованный массив выведите на экран | |
| Присвойте элементам массива Q размерностью m×n случайные числа от -20 до 65. Выведите на экран. Определите минимальный элемент в каждом столбце матрицы . Выведите на экран Найти максимальный элемент массива. Выведите на экран. Замените им отрицательные элементы, расположенные в k-ой строке. Преобразованный массив выведите на экран | |
| Присвойте элементам массива Q размерностью m×m случайные числа от -30 до 65. Выведите на экран. Найдите индекс строки с минимальным элементом массива. Выведите на экран. Вычислите сумму элементов, расположенных в четных строках. Выведите на экран Замените им положительные элементы главной диагонали . Преобразованный массив выведите на экран | |
| Присвойте элементам массива В размерностью m×n случайные числа от -20 до 90. Выведите на экран. Найдите количество положительных элементов массива. Выведите на экран. Найдите максимальный элемент k-ой строки . Выведите на экран. Замените им отрицательные элементы, первой строки. Преобразованный массив выведите на экран. | |
| Дан целочисленный массив R размерностью n×n. Заполните его случайными числами от-50 до +50. Выведите на экран. Вычислите сумму элементов массива, расположенных выше главной диагонали. Выведите на экран. Определите количество положительных элементов на главной диагонали . Выведите на экран. Замените им все элементы, расположенные ниже главной диагонали. Преобразованный массив выведите на экран. | |
| Дан действительный массив P размерностью n×n. Заполните его случайными числами от-50 до +80. Выведите на экран Найдите сумму элементов каждого столбца массива . Выведите на экран. Определите минимальную из полученных сумм. Выведите на экран. Замените отрицательные элементы на главной диагонали полученной суммой. Преобразованный массив выведите на экран. | |
| Присвойте элементам массива Q размерностью m×n случайные числа от -20 до 80. Выведите на экран. Отрицательные элементы массива, расположенные в четных строках, заменить на квадраты их значений. Преобразованный массив выведите на экран. Найти максимальный элемент среди элементов, расположенных в четных столбцах. Выведите на экран. | |
| Присвойте элементам массива Q размерностью m×n случайные числа от -60 до 65. Выведите на экран. Отрицательные элементы массива, расположенные в нечетных строках, заменить на квадраты их значений. Преобразованный массив выведите на экран. Найдите максимальные элементы столбцов массива. Выведите на экран. | |
| Присвойте элементам массива А размерностью m×n случайные числа от 25 до 75. Выведите на экран. Выведите на экран отдельно элементы массива кратные 5. Элементам не кратным 5 присвойте значение 0 и выведите на экран преобразованный массив. Найдите наибольшее среди произведений элементов столбцов массива . Выведите на экран. | |
| Присвойте элементам массива В размерностью n ×n случайные числа от -20 до 25. Выведите на экран. Найдите наибольшее среди произведений элементов столбцов массива . Выведите на экран. Диагональные элементы массива заменить средними арифметическими соответствующих столбцов. Преобразованный массив выведите на экран | |
| Присвойте элементам массива В размерностью n ×n случайные числа от -50 до 50. Выведите на экран. Замените отрицательные элементы, расположенные на главной диагонали и выше нее на их квадраты и посчитать количество замен. Выведите преобразованный массив. Замените все элементы первой строки максимальным элементом массива. Выведите преобразованный массив. | |
| Присвойте элементам массива V размерностью m ×n случайные числа от -90 до 65. Выведите на экран. Найти наибольшее значение среди сумм элементов столбцов массива. Выведите на экран. Элементы k –ой строки массива заменить средними арифметическими соответствующих столбцов. Выведите на экран преобразованный массив. | |
| Присвойте элементам массива F размерностью m ×n случайные числа от -20 до 20. Выведите на экран. Найдите наибольшее среди произведений элементов столбцов массива . Выведите на экран. Замените отрицательные значения нечетных столбцов элементов массива этим значением. Выведите на экран преобразованный массив. | |
| Дан целочисленный массив R размерностью n×n. Заполните его случайными числами от-50 до +50. Выведите на экран. Вычислите сумму элементов массива, расположенных ниже главной диагонали. Выведите на экран. Определите количество положительных элементов на главной диагонали . Выведите на экран. Замените им все элементы, расположенные выше главной диагонали. Преобразованный массив выведите на экран. |
Контрольные вопросы
1) Что такое указатель? Как получить доступ к элементам массива через указатель?
2) Вы используете в программе динамический двумерный массив. Вам необходимо заполнить массив случайными числами и вывести на экран. Ваши действия?
3) Можно ли создать трехмерный динамический массив и , если да, то как?
4) Приведите решение любой из задач данной лабораторной работы кроме своего варианта.
Лабораторная работа №6
Цель: усовершенствовать навыки программирования на примере решения задач матричной алгебры с использованием динамических массивов и функций.
Задачи:
1) Повторить теоретические сведения о создании и использовании диннамических массивов в языке Си++.
2) Повторить теоретические сведения о создании и использовании функций в языке Си++.
3) Разработать программу решающую одну из задач матричной алгебры с использованием функций и динамическихмассивов.