Лекция 21 Динамические массивы

Динамические массивы

Динамическим называется массив, размерность которого становится известной в процессе выполнения программы.

В C++ для работы с динамическими массивами применяются специальные операции newи delete. С помощью операции newвыделяется память под динамический массив, а с помощью операции deleteсозданный массив удаляется из памяти.

Пример 1. Выделение памяти под динамический массив.

Пусть размерность динамического массива вводится с клавиатуры.

Необходимо выделить память под этот массив, а затем созданный динамический массив надо удалить. Соответствующий фрагмент программы имеет вид:

int n, *mas; // объявление переменных целого типа и типа указатель

cin >>n; // n — размерность массива вводится с клавиатуры

mas=new int[n]; // выделение памяти под массив

...

delete mas; // освобождение памяти

...

В данном примере mas– переменная типа указатель указывает на массив из nэлементов целого типа.

Можно объединить в одном операторе две операции:

- объявление переменной mas типа указатель и

- присвоение указателю начального адреса выделенной области памяти в соответствии с заданным типом int и количетсвом элеметов массива n.

int n;

cin >>n; // n - размерность массива вводится с клавиатуры

int *mas=new int[n]; // объявление переменной mas типа указатель и выделение памяти под массив

...

delete mas; // освобождение памяти

...

Если с помощью операции newневозможно выделить требуемый объем памяти, то результатом операции newявляется значение 0.

Cоздание многомерных динамических массивов.

Пример 2. Выделение памяти под двумерные массивы.

Пусть требуется создать двумерный динамический массив целых чисел размерностью nxk:

...

int n, k, i,**mas;// Объявление указателя на двумерный массив

...

cout << ” Задайте число строк массива — n “; cin >> n;

cout << ” Задайте число столбцов массива — n “; cin >> k;

mas=new int*[n]; // выделение памяти под n адресов строк

for(i=0;i<n;i++)

mas[i]=new int[k]; // выделение памяти для каждой строки по числу столбцов к

...

for(i=0;i<n;i++)

delete[] mas[i]; // освобождение памяти

delete[] mas;

...

Сначала необходимо с помощью операции newвыделить память под nуказателей. Выделенная память будет представлять непрерывную область ячеек, в которых все указатели располагаются последовательно друг за другом. После этого необходимо в цикле каждому указателю присвоить начальный адрес области памяти, выделенной под строку массива.

Рис. 3. Размещение динамического двумерного массива в памяти.

Созданный таким образом двумерный динамический массив существенно отличается от обычного двумерного массива. Под обычный двумерный массив при объявлении выделяется сплошной участок памяти размером, равным произведению его границ. Для двумерного динамического массива выделенная память не представляет собой сплошной участок, поскольку она выделяется с помощью нескольких операций new.

Использования указателей и массивов

Пусть необходимо упорядочить массив целых чисел по возрастанию. Размер массива задается пользователем.

В данном случае возникает задача сортировки. Для ее решения рассмотрим алгоритм сортировки массива из 4-х целых чисел.

Пусть заданы начальные значения элементов массива (рис. 4а). Возьмем самый плохой вариант, когда числа упорядочены по убыванию.

Исходный массив
1- сравнение					1 проход (3 сравнения)
2- сравнение
3- сравнение
1- сравнение					2 проход (2 сравнения)
2- сравнение
1- сравнение					3 проход (1 сравнение)

Рис. 4. Этапы сортировки массива из 4-х чисел

Проведем сравнение смежных элементов массива, начиная с первого и до последнего, и в случае неупорядоченности поменяем их местами.

Очевидно, что для массива из 4-х чисел необходимо в первом проходе провести три сравнения (рис. 4). Ясно, что после 1-го прохода максимальный элемент переместится на последнее место в массиве.

Так как массив еще не упорядочен, необходимы дальнейшие проходы сравнений смежных элементов с перестановками.

Но во втором проходе число сравнений на 1 меньше, чем в первом, так как максимальный элемент находится на последнем месте в массиве, и привлекать его для дальнейших сравнений не имеет смысла.

Следовательно, для полного упорядочивания массива нужно повторять проходы сравнений смежных элементов, начиная с 1-го элемента массива и до предпоследнего в предыдущем проходе.

Из примера видно, что для полного упорядочивания массива из 4-х элементов необходимо провести три прохода смежных сравнений, причем в каждом проходе число сравнений на 1 меньше, чем в предыдущем.

Если задан массив из nэлементов, то для его сортировки по возрастанию необходимо провести
n-1 проходов сравнений смежных элементов:

для 1-го прохода должно быть произведено n-1сравнений элементов, начиная с 1-го элемента,

для 2-го прохода должно быть произведено n-2сравнений элементов, начиная с 1-го элемента,

и т.д.,

для i-го прохода должно быть произведено n-iсравнений элементов, начиная с 1-го элемента

и т.д.,

для (n-1)-го последнего прохода должно быть проведено одно сравнение.

Используем данный алгоритм сортировки для нашего примера. Программа имеет следующий вид:

#include <iostream.h>

main()

{

int n, i, j, *mas, buf;

соut <<" Введите размерность массива:";

cin >> n;

mas=new int[n];

соut << “ Вводите элементы массива. ";

for(i=0; i<n; i++)

{

cout<<"mas ["<<i<<”]=”;

cin>>mas[i];

}

for(i=l; i<n; i++)

for(j=l; j<=n-i; j++)

if (mas[j-l]>mas[j])

{

buf=mas[j-l]; mas[j-l]=mas[j]; mas[j]=buf;

}

cout <<"Peзyльтиpyющий массив: ";

for(i=0; i<n; i++) cout<<mas[i]<<" ";

delete mas;}

В данной программе с помощью директивы препроцессора #includeподключается стандартная библиотека потокового ввода-вывода.

В разделе переменных объявлены следующие переменные:

n— количество элементов массива,

i и j — переменные счетчики циклов,

mas— указатель на динамический массив,

buf— переменная для временного хранения элементов массива.

В начале программы вводится число элементов массива n. Далее с помощью операции newпод массив выделяется требуемый участок памяти. Затем пользователем в цикле вводятся элементы массива. Далее с помощью 2-х вложенных циклов производится упорядочивание массива по возрастанию в соответствии с описанным алгоритмом. Во внутреннем цикле организовано сравнение смежных элементов массива, и в случае необходимости элементы массива меняются местами. Внешний цикл обеспечивает n-1 проходов сравнений смежных элементов массива.

Затем в цикле организован вывод результирующего массива. Далее с помощью операции deleteиз памяти удаляется созданный динамический массив. На этом работа программы заканчивается.

Функции.

Общие сведения о функциях

Функциииспользуются в случаях, когда аналогичные преобразования над различными данными необходимо выполнять в нескольких местах программы.

Каждая программа в своем составе должна иметь главную функцию main().

Кроме функции main(), в программу может входить произвольное число функций.

Каждая функция может вызывать другие функции и саму себя, но не функцию main(). Функцияmain(). может вызывать все функции, но не саму себя.

С понятием функции в языке C++ связано три следующих компонента:

вызов функции;

описание функции;

прототип функции.

Вызов функции представляет собой выражение вида:

имя_функции(список_аргументов); и выполняется двумя способами.

Если у функции отсутствует возвращаемое значение, то вызов выполняется в виде отдельного оператора, например, circle(x,y,r).

Если у функции существует возвращаемое значение, то вызов функции является частью оператора, например, x=y+sin(z);

Возвращаемое значение функции передается в место вызова функции, присваивается имени функции и является значением выражения в составе оператора.

Описание функции состоит из двух частей:

заголовка и тела функции и имеет следующую форму записи:

[тип_результата]<имя>([список_параметров через запятую]) /* заголовок функции*/

{

/* операторы - тело_функции */

}

В заголовке функции тип результата — тип возвращаемого значения. Если спецификатора типа отсутствует, считается, что функция возвращает целое значение (int).Если функция не возвращает никакого значения, то на месте типа записывается спецификатор void.

В списке параметров для каждого параметра должен быть указан тип. При отсутствии параметров список может быть пустым или иметь спецификатор void.

Тело функции представляет собой последовательность объявлений и операторов, описывающих определенный алгоритм. Важным оператором тела функции является оператор возврата в точку вызова: return [выражение];.

Оператор returnимеет двойное назначение. Во-первых, он обеспечивает немедленный возврат в вызывающую функцию и, во-вторых может использоваться для передачи вычисленного значения функции. В теле функции может не быть оператора return. В последнем случае возврат в вызывающую программу происходит после выполнения последнего оператора тела функции.

При вызове функции аргументы подставляются вместо параметров.

Число и типы аргументов должны совпадать с числом и типом параметров функции.

Язык C++ не предусматривает автоматического преобразования типов вслучаях, когда аргументы не совпадают по типам с соответствующими им параметрами, поэтому до вызова функции указывается ее Прототип для того, чтобы компилятор мог проверить соответствие типов аргументов и параметров при вызове функции.

Прототип по форме такой же, как и заголовок функции, но в конце его ставится «;». В прототипе можно не указывать имена параметров функции, а только их типы, например
function(int, float,char);

При наличии прототипа вызываемые функции не обязаны размещаться в одном файле с вызывающей функцией.

Пример 1. Пример функции с возвращаемым значением.

Составить программу, содержащую обращение к функции вычисления максимума из двух чисел:

#include<iostream.h>

int max(int, int); /* прототип функции */

void main()

{

int x,y,z;

cout << " поочередно введите х и у ";

cin>> x; cin>> y;

z=max(x,y); // вызов функции max, x и y – аргументы функции

cout <<"Maximum = " << z;

}

#include "d:max.cpp" // включение файла max.cpp с функцией max.

Описание функции maxнаходится в файле mах.срр,находящемся в корневом каталоге диска d:, и имеет следующий вид:

int max(int a, int b) // a и b – параметры функции

{

int с; /*рабочая переменная */

if (a>=b) c=a; Вместо операторов if else

else c=b; можно записать: c=(a>=b)?a:c;

return c;

}

Во второй строке программы записан прототип функции mах().

Так как есть возвращаемое значение, то вызов функции является выражением в правой части оператора присваивания z=max(x,y);,при выполнении которого значения аргументов х и у подставляются вместо параметров а и b соответственно.

После выполнения тела функции возвращаемое значение передается в место вызова функции и присваивается переменной z.

Описание функции находится в отдельном файле max.cpp, поэтому для включения файла в программу необходимо в тексте программы указать директиву препроцессора

#include "d:max.cpp".

Описание функции может находиться в одном файле с главной программой. При этом директива #include "mах.срр " не указывается, а вместо нее помещается описание функции.

Пример 2. Использование функции без возвращаемого значения.

Составить программу, включающую функцию, при обращении к которой на экран выдается символ, набранный на клавиатуре. Выполнение программы завершается набором символа С.

#include <iostream.h>

void echo(char); // прототип функции

void main()

{

char x;

do

{

cout << " Введите символ, для выхода введите С "; cin >> x;

echo(x);

}

while (x!= ‘C’);

}

void echo(char a)

{

cout << “ Введенный символ: "<< a;

}

В функции echo() отсутствует возвращаемое значение, поэтому обращение к функции осуществляется оператором вызова функции echo(x);.

В результате обращения к функции на экран будет выведен символ, введенный с клавиатуры.

Описание функции может находиться как до, так и после функции main(). Если описание функции предшествует ее вызову, то прототип может отсутствовать.

Библиотечные функции

Типичным является следующий набор функций:

• манипулирование строками;

• сравнение и преобразование символов;

• преобразование строк в числа и обратно;

• дата и время дня;

• математические функции;

• функции ввода-вывода;

• сортировка;

• графические.

Наиболее часто используются математические функции. Прототипы математических функций входят в файл math.h.

Таблица 1 Математические функции

Имя	Результат выполнения функции
int abs(int)	абсолютное значение аргумента типа int
double cos(double)	косинус угла, заданного в радианах
double exp(double)	экспонента в степени с аргументом типа double
double fabs(double)	абсолютное значение аргумента типа double
double log(double)	натуральный логарифм аргумента типа double
double log10(double)	десятичный логарифм аргумента типа double
max(x,y)	максимальный из двух аргументов типа int
min(x,y)	минимальный из двух аргументов типа int
double pow(double,double)	значение аргумента 1 в степени аргумента 2
double sin(double)	синус угла, заданного в радианах
double sqrt(double)	квадратный корень положительного аргумента типа double
double (tan double)	тангенс угла, заданного в радианах

Пример 3. Использование математических функций.

Пусть требуется составить программу для вычисления у = х² — cos z.

#include <iostream.h>

#include <math.h>

void main()

{

float x;

double z, y;

cout << " Введите х ";

cin >> x;

cout << " Введите z ";

cin >> z;

y=pow(x,2)-cos(z);

}

Дата добавления: 2014-01-20