Лабораторная работа №5
Изучение одномерных динамических массивов и строк в языке программирования С++
Цель лабораторной работы
Целью лабораторной работы является получение опыта работы с динамическим выделением и освобождением памяти, а также с динамическими массивами в языке программирования С++.
Вопросы для предварительного изучения
1. Ознакомится с лекционным материалом темой 14.
2. Изучить по основной и дополнительной литературе, следующие разделы:
2.1. По рекомендованной литературе изучить: [Л2]: главы 2,3.
2.2. По рекомендованной литературе изучить: [Д2]: пп. 2.1; 2.2.
3. Изучить краткие теоретические сведения и порядок оформления лабораторной работы.
Краткие теоретические сведения
Выделение памяти под массив можно осуществлять как средствами языка Си, так и новыми средствами С++. Будем изучать только средства С++, так как они эффективно переносятся на пользовательские, объектно-ориентированные типы данных. Конструктором массива С++ является new — оператор, обеспечивающий выделение динамической памяти в ОЗУ. Оператор new пытается выделить достаточно памяти для размещения новых данных и, в случае успеха, возвращает адрес первого элемента выделенной памяти.
Пусть type – произвольный тип данных, это может быть int, double, char или даже некоторый пользовательский тип. Существует три выражения, позволяющие выделить память с помощью оператора new.
type *pt;
type eque;
…
pt = new type; /* Выделяет ячейку памяти типа type (sizeof(type) байт) и возвращает её адрес (адрес её первого байта), который помещается в pt. */
pt = new type(eque); /* Выделяет ячейку памяти типа type (sizeof(type) байт), присваивает ей значение переменной eque и возвращает её адрес (адрес её первого байта), который помещается в pt. Вместо переменной eque может быть константа типа type. */
pt = new type[n]; /* Выделяет n (n – переменная целочисленного типа данных) идущих подряд в оперативной памяти ячеек памяти типа type (n*sizeof(type) байт) и возвращает адрес (адрес её первого байта), который помещается в pt. Вместо переменной n может быть любая целочисленная константа. Легко заметить, что выражения: pt = new type[1] и pt = new type эквивалентны.*/
Для того чтобы освободить выделенную оператором new память необходимо использовать оператор delete. В языке программирования C++ оператор delete возвращает память, выделенную оператором new, обратно в кучу. Вызов delete должен происходить для каждого вызова new, чтобы избежать утечки памяти. После вызова delete объект, указывающий на этот участок памяти, становится некорректным и не должен больше использоваться. Многие программисты присваивают 0 (нуль-указатель) указателям после использования delete, чтобы минимизировать количество ошибок программирования. Однако нужно отметить, что удаление нуль-указателя фактически не имеет эффекта, так что нет необходимости проверять нуль-указатель перед вызовом delete.
Если память выделена выражениями: pt = new type(eque) и pt = new type, то освобождение памяти производится операцией delete pt. Если же память была выделена выражением pt = new type[n], то её освобождение лучше всего производить с помощью следующего синтаксиса delete: delete [] pt.
Будем нумеровать элементы массива длины n от 0 до n-1. Тогда очевидно, что адрес некоторого i-ого элемента массива (i от 0 до n-1) вычисляется как a+i (см. арифметику указателей). Тогда обращение к элементу массива будет иметь вид: *(a+i) или есть специальный синтаксис a[i], что тоже самое.
Заметим что о том, что лежит в указателе – адрес первого элемента массива или просто адрес какой-то ячейки памяти знает только программист. Отметим также, что в языке С++ есть более высокоуровневая обёртка – тип данных стандартной библиотеки шаблонов vector, который мы будем изучать в следующей нашей дисциплине ООП.
Таким образом, чтобы далее работать с массивом, надо знать число его элементов. Есть три пути хранения и использования массивов.
1. Хранить число переменных отдельно (можно так же объединить указатель на массив и переменную с количеством его элементов в структуру);
2. Использовать первый элемент массива для хранения числа его элементов;
3. Использовать особое значение для обозначения последнего элемента массива. По этому пути пошли строковые переменныt char*. Этот способ удобен в том случае, когда у Вас есть значения элемента, которые не могут встречаться в массиве и их удобно использовать в качестве флага на конечном элементе.
Может показаться, что операция delete всё-таки «знает» размер массива, раз удаляет его не принимая в качестве аргумента число элементов массива. Это и так и не так. Выделение памяти происходит блоками - непрерывными фрагментами оперативной памяти (таким образом, каждый блок — это несколько идущих подряд байтов). Размер блока может зависеть от компилятора, ОС и т.п. В памяти создаётся таблица адресов и количество блоков (их длина вычисляется автоматически). Операция new выделяет не точно, а лишь приблизительно n элементов, а именно число блоков, которых достаточно, чтобы вместить n элементов. А для работы с массивом необходимо точно знать количество его элементов. Выделение сводится к занесению в таблицу адреса первого байта выделенной памяти и информации свидетельствующей о количестве блоков или адресе последнего (следующего за) из них(ими). Оператор delete просто ищет в таблице переданный ему адрес и удаляет его. После чего содержимое ячеек не меняется, но освобождённая память может быть вновь использована программой в своих целях.
Задание №1
Осуществить ввод массива. Тип элементов массива задаётся вариантом.
Форма ввода задаётся вариантом. Если ввод массива осуществляется пользователем, то необходимо запросить сначала число элементов массива, а потом запрашивать у пользователя (в вежливой форме) каждый элемент массива. Если ввод осуществляется из файла, то в первой строчке файла должно быть натуральное число – количество элементов массива, а во второй перечислены элементы массива. Если ввод осуществляется случайно, то программа должна в вежливой форме запросить у пользователя количество элементов массива n и интервал генерации случайных чисел [ a, b ] или считать их из файла, где они находятся в первой и единственной строке файла в формате: n a b.
Выполнить задание, представленное в столбцах а) и б) таблицы вариантов.
Осуществить вывод в файл или пользователю (в соответствии с вариантом) в вежливой форме массив и результаты вычислений.
Варианты заданий
| вариант | ввод | вывод | тип | а) вычислить: | б) вычислить: |
| файл | пользователь | целые | сумму отрицательных элементов массива | произведение элементов массива, расположенных между максимальным и минимальным элементами | |
| пользователь | файл | вещественные | сумму положительных элементов массива | произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами | |
| случайно | файл | целые | произведение элементов массива с четными номерами | сумму элементов массива, расположенных между первым и последним нулевыми элементами | |
| файл | пользователь | вещественные | сумму элементов массива с нечетными номерами | сумму элементов массива, расположенных между первым и последним отрицательными элементами | |
| случайно | файл | целые | максимальный элемент массива | сумму элементов массива, расположенных до последнего положительного элемента | |
| файл | пользователь | вещественные | минимальный элемент массива | сумму элементов массива, расположенных между первым и последним положительными элементами | |
| пользователь | файл | целые | номер максимального элемента массива | произведение элементов массива, расположенных между первым и вторым ну левыми элементами | |
| случайно | файл | вещественные | номер минимального элемента массива | сумму элементов массива, расположенных между первым и вторым отрицательными элементами | |
| файл | пользователь | целые | максимальный по модулю элемент массива | сумму элементов массива, расположенных между первым и вторым положи тельными элементами | |
| случайно | файл | вещественные | минимальный по модулю элемент массива | сумму модулей элементов массива, расположенных после первого элемента, равного нулю | |
| файл | пользователь | целые | номер минимального по модулю элемента массива | сумму модулей элементов массива, расположенных после первого отрицательного элемента | |
| пользователь | файл | вещественные | номер максимального по модулю элемента массива | сумму элементов массива, расположенных после первого положительного элемента | |
| случайно | файл | целые | количество элементов массива, лежащих в диапазоне [ c,d ] – диапазон вводится от пользователя | сумму элементов массива, расположенных после максимального элемента | |
| файл | пользователь | вещественные | количество элементов массива, равных 0 | сумму элементов массива, расположенных после минимального элемента | |
| случайно | файл | целые | количество элементов массива, больших С, С вводится от пользователя | произведение элементов массива, расположенных после максимального по модулю элемента | |
| файл | пользователь | вещественные | количество отрицательных элементов массива | сумму модулей элементов массива, расположенных после минимального по модулю элемента | |
| пользователь | файл | целые | количество положительных элементов массива | сумму элементов массива, расположенных после последнего элемента, равного нулю | |
| случайно | файл | вещественные | количество элементов массива, меньших С, С вводится от пользователя | сумму целых частей элементов массива, расположенных после последнего отрицательного элемента | |
| файл | пользователь | целые | произведение отрицательных элементов массива | сумму положительных элементов массива, расположенных до максимального элемента | |
| случайно | файл | вещественные | произведение положительных элементов массива | сумму элементов массива, расположенных до минимального элемента | |
| файл | пользователь | целые | среднее арифметическое элементов массива | сумму элементов массива, выходящих за пределы дисперсии | |
| пользователь | файл | вещественные | дисперсию элементов массива | сумму элементов массива, меньших среднего арифметического | |
| случайно | файл | целые | исправленное среднеквадратическое отклонение элементов массива | сумму элементов массива, вдвое больших среднего арифметического |
Задание №2
Осуществить ввод массива. Тип элементов массива задаётся вариантом.
Форма ввода задаётся вариантом. Если ввод массива осуществляется пользователем, то необходимо запросить сначала число элементов массива, а потом запрашивать у пользователя (в вежливой форме) каждый элемент массива. Если ввод осуществляется из файла, то в первой строчке файла должно быть натуральное число – количество элементов массива, а во второй перечислены элементы массива. Если ввод осуществляется случайно, то программа должна в вежливой форме запросить у пользователя количество элементов массива n и интервал генерации случайных чисел [ a, b ] или считать их из файла, где они находятся в первой и единственной строке файла в формате: n a b.
Выполнить задание, представленное в правом крайнем столбце.
Осуществить вывод в файл или пользователю (в соответствии с вариантом) в две строки – в первой строке массив до изменения, во второй – после.
Варианты заданий
| вариант | ввод | вывод | тип | суть задания |
| пользователь | файл | вещественные | Преобразовать массив таким образом, чтобы сначала располагались все положительные элементы, а потом — все отрицательные (элементы, равные 0, считать положительными) | |
| случайно | файл | целые | Сжать массив, удалив из него все элементы, модуль которых не превышает 1, а освободившиеся в конце массива элементы заполнить нулями | |
| файл | пользователь | вещественные | Сжать массив, удалив из него все элементы, модуль которых находится в интервале [ с,d ] – интервал вводится от пользователя. Освободившиеся в конце массива элементы заполнить нулями | |
| случайно | файл | целые | Преобразовать массив таким образом, чтобы сначала располагались все элементы, равные нулю, а потом — все остальные. | |
| файл | пользователь | вещественные | Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в нечетных позициях, а во второй половине — элементы, стоявшие в четных позициях. | |
| пользователь | файл | вещественные | Преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает 1, а потом — все остальные. | |
| случайно | файл | вещественные | Преобразовать массив таким образом, чтобы элементы, равные нулю, располагались после всех остальных | |
| файл | пользователь | целые | Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в четных позициях, а во второй половине — элементы, стоявшие в нечетных позициях. | |
| случайно | файл | вещественные | Сжать массив, удалив из него все элементы, величина которых находится в интервале [ c,d ]. Интервал вводится от пользователя. Освободившиеся в конце массива элементы заполнить нулями | |
| файл | пользователь | вещественные | Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых лежит в интервале [ c,d ], а потом — все остальные. Интервал вводится от пользователя | |
| пользователь | файл | вещественные | Преобразовать массив таким образом, чтобы сначала располагались все отрицательные элементы, а потом — все положительные (элементы, равные 0, считать положительными). | |
| случайно | файл | целые | Заменить все отрицательные элементы массива их квадратами, а положительные квадратными корнями | |
| файл | пользователь | вещественные | Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых не превышает 1, а потом — все остальные | |
| случайно | файл | целые | Преобразовать массив таким образом, чтобы сначала располагались все элементы, отличающиеся от максимального не более чем на 30%, а потом остальные. | |
| файл | пользователь | вещественные | Изменить порядок следования элементов в массиве на обратный | |
| пользователь | файл | целые | Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых не превышает С, а потом — все остальные. С вводится от пользователя. | |
| случайно | файл | вещественные | Преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает С, а потом — все остальные. С вводится от пользователя. | |
| файл | пользователь | целые | Отсортировать массив простым выбором с помощью итераторов по убыванию | |
| случайно | файл | вещественные | Отсортировать массив простым выбором с помощью итераторов по возрастанию | |
| файл | пользователь | целые | Преобразовать массив так, чтобы элементы, стоявшие на нечётных местах, были отсортированы по возрастанию, а на чётных по убыванию. Сортировка простым выбором. | |
| пользователь | файл | вещественные | Преобразовать массив так, чтобы элементы, стоявшие на нечётных местах, были отсортированы по убыванию, а на чётных по возрастанию. Сортировка расчёской. | |
| случайно | файл | целые | Отсортировать массив расчёской с помощью итераторов по убыванию | |
| файл | пользователь | целые | Отсортировать массив расчёской выбором с помощью итераторов по возрастанию |