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

 

 

# include < iostream >

using namespace std;

int main () {

int **Array; // Указатель на массив указателей

int n, m, j, i;

cout << ”Enter number of rows \n ”;

cin >> n;

cout << ”Enter number of columns \n ”;

cin >> n;

Array = new int * [ n ]; //Выделяется память под одномерный массив,

//каждый элемент которого, является указателем

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

Array[ i ] = new int [ m ]; // Каждому указателю присваивается адрес

//первой ячейки памяти, выделяемой под “m”

// элементов массива

for (i = 0; i < n; i ++) // Ввод 2-мерного массива

for (j = 0; j < m; j ++) // Ввод 2-мерного массива

cin >> Array [ i ] [ j ]; // Ввод 2-мерного массива

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

delete Array [ i ]; // Удаление строк массива

delete [ ] Array; // Удаление массива указателей

return 0;

}

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

// Передача одномерного динамического массива в функцию

void funct (double *A, int n);

int main () {

double * B;

int n;

cin >> n;

B = new double [ n ];

funct (B, n);

…

// Передача двумерного динамического массива в функцию

void funct (double **A, int m, int n);

int main () {

double **B;

int m, n;

cin >> n >> m;

B = new double * [ n ];

for (int j = 0; j < n; j ++)

B [ j ] = new double [ m ];

funct (B, n, m);

…

Задания к самостоятельной работе

1. Дан одномерный массив. Написать функцию, определяющую минимальный, максимальный элементы массива и среднее арифметическое минимального и максимального элементов. Кроме того, программа должна иметь функцию ввода одномерного массива и функцию вывода.

2. Написать функцию перемножения матриц А размером nхm и В размером mхl. Элементы результирующей матрицы получить с помощью следующей формулы. Массивы должны быть динамическими.

3. Написать функции вычисления суммы элементов каждой строки матрицы А размером 6х6, определения наибольшего значения этих сумм.

4. Дана действительная матрица размера 6х9. Найти среднее арифметическое наибольшего и наименьшего значений ее элементов. Программа должна быть составлена с использованием функций.

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

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

7. В одномерном массиве, состоящем из n вещественных чисел, вычислить:

а) количество элементов массива, меньших С;

б) сумму положительных элементов, расположенных после первого положительного элемента.

Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых лежит в интервале [a, b], а потом – все остальные.

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

Лабораторная работа 4

Перегрузка функций

Перегрузка функции - это определение двух или более функций с одним и тем же именем, но разным набором параметров. Работа перегруженных функций основана на различии списков параметров (на различии их типов и/или количестве), принимаемых функцией. При обращении к функции компилятор использует то определение функции, тип и количество параметров которой совпадают с типом и количеством параметров, передаваемых в функцию при обращении к ней.

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

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

# include < iostream >

using namespace std;

double avg (int a, int b);

double avg (int a, int b, int c);

double avg (double a, double b);

double avg (double a, double b, double c);

int main()

{

int x, y, z;

cout << ” Enter 3 integers \n ”;

cin >> x >> y >> z;

cout << ” average value of 2 numbers = ” << avg (x, y);

cout << ” average value of 3 numbers = ” << avg (x, y, z);

double n, m, k;

cout << ” Enter 3 real numbers \n ”;

cin >> n >> m >> k;

cout << ” average value of 2 real numbers = ” << avg (n, m);

cout << ” average value of 3 real numbers = ” << avg (n, m, k);

return 0;

}

double avg (int a, int b) { return (a + b) / 2.0;}

double avg (int a, int b, int c) { return (a + b + c) / 3.0; }

double avg (double a, double b) { return (a + b) / 2; }

double avg (double a, double b, double c) {return (a + b + c) /3;}

Шаблоны функции

Шаблоны функции позволяют создавать функции, которые могут использовать аргументы различных типов. Большинство функций используют алгоритмы, которые могут работать с различными типами данных. Например, функция сортировки может сортировать символьные, вещественные и целочисленные массивы.

Использовать несколько определений идентичных функций, работающих с данными разного типа, не эффективно. В этом случае следует использовать шаблоны функции. При этом определение и прототип функции начинаются со строки template < class T >. Эта строка является префиксом шаблона и указывает компилятору, что следующее за ним определение функции является шаблоном, а Т - параметром типа. Слово class в этом случае обозначает тип. В качестве Т может быть указан любой тип.

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

Пример: универсальная функция сортировки.

 

# include < iostream.h >

template < class T >

void sort (T a[ ], int size);

main () {

char c [ 8 ] = {‘ p ’, ’ r ’, ’ o ’, ’ g ’, ’ r ’, ’ a ’, ’ m ’, ’ \0 ’ };

sort (c, 8);

int A [ 5 ] = { 5, 10, 1, 4, 9 };

sort (A, 5);

double B [ 4 ] = { 3.2, 1.5, 9.8, 2.8 };

sort (B, 4);

return 0;

}

template < class T >

void sort (T a [ ], int size) {

int i, P;

T D;

for (p = 1; p <= size - 1; p ++)

for (i = 0; i < size - 1; i ++)

if (a [ i ] > a [ i + 1 ]) {

D = a [ i ];

a [ i ] = a [ i + 1 ];

a [ i +1] = D;

}

Рекурсивные функции

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

Рекурсивная задача в общем случае разбивается на два этапа. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи — так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто воз­вращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой — это называется рекурсивным вызовом, или шагом рекурсии. Шаг рекурсии вклю­чает ключевое слово return, так как в дальнейшем его результат будет объ­единен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова, возможно, в main.

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

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

Как пример рассмотрим рекурсивную программу для расчета факториала.

Факториал неотрицательного целого числа n, записываемый как n!, равен n*(n-1)*(n-2)*…*1, причем считается, что 1! = 1 и 0! = 1. Например, 5! вычисляется как 5 x 4 x 3 x 2 x 1 и равен 120.

Факториал целого числа, number, большего или равного 0, может быть вычислен итеративно(нерекурсивно) с помощью оператора for следующим образом:

factorial = 1;

for (int counter = number; counter >=1; counter--)

factorial *= counter;

Теперь используем рекурсию для вычисления и печати факториалов целых чисел от 0 до 10. Рекурсивная функция factorial сначала проверяет, истинно ли условие завершения рекурсии, т.е. меньше или равно 1 значение number. Если действительно number меньше или равно 1, factorial возвра­щает 1, никаких дальнейших рекурсий не нужно и программа завершает свою работу. Если number больше 1, оператор

return number * factorial (number - 1);

представляет задачу как произведение number и рекурсивного вызова factorial, вычисляющего факториал величины number-1. Отметим, что factorial (number - 1) является упрощенной задачей по сравнению с исходным вычислением factorial (number).

В объявлении функции factorial указано, что она получает параметр типа unsigned long и возвращает результат типа unsigned long. Это является крат­кой записью типа unsigned long int. Описание языка C++ требует, чтобы переменная типа unsigned long int хранилась по крайней мере в 4 байтах (32 битах), и таким образом могла бы содержать значения в диапазоне по крайней мере от 0 до 4294967295. (Тип данных long int также хранится по крайней мере в 4 байтах и может содержать значения по крайней мере в диапазоне от 2147483647). Функ­ция factorial начинает вырабатывать большие значения так быстро, что даже unsigned long не позволяет нам напечатать много значений факториала до того, как будет превышен допустимый предел переменной unsigned long.

// Рекурсивная функция факториала

# include < iostream >

unsigned long factorial (unsigned long);

main ()

{ for (int i = 0; i <= 10; i++)

cout << i << “! = “ << factorial (i) << endl;

return 0;

}

// рекурсивное описание функции вычисления факториала

unsigned long factorial (unsigned long number)

{ if (number <= 1) return 1;

else return (number * factorial (number – 1);

}

Задания к самостоятельной работе

 

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

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

3. Определите, содержат ли следующие фрагменты программы ошибки. Для каждой ошибки укажите, как она может быть исправлена.

За­мечание: в некоторых фрагментах ошибки могут отсутствовать.

a) template < class A >

int sum (int numl, int num2, int num3)

{ return numl + num2 + num3;)

b) void printResults (int x, int y)
{ cout «"Сумма равна " «x + у «' \n';

return x + y; }

c) template < class A>

A product (A numl, A num2, A num3)

{ return numl * num2 * num3; }

double cube (int);
int cube (int);

4. Ряд Фибонначи состоит из чисел, каждое из которых является суммой двух предыдущих(1, 1, 2, 3, 5, 8, 13, …). Найти n-ный элемент ряда, используя рекурсию.

5. Наибольший общий делитель (НОД) двух целых чисел х и у — это наибольшее целое, на которое без остатка делится каждое из двух чисел. Напишите рекурсивную функцию nod, которая возвращает наибольший общий делитель чисел х и у. НОД для х и у опреде­ляется рекурсивно следующим образом: если у равно 0, то nod(x, у) возвращает х; в противном случае nod(x, у) равняется nod(y, х % у), где % — это операция вычисления остатка.

Лабораторная работа 5

Структуры

Структура – одна или несколько переменных, которые для удобства работы с ними сгруппированы под одним именем.

В отличие от массивов переменные структуры могут иметь различный тип.

Структура – абстрактный тип данных, т.е. тип данных, определяемый пользователем.

Синтаксис определения структуры:

struct имя

{ список переменных;

};

Ключевое слово struct указывает на то, что далее приведено имя структуры как нового типа данных. Имя структуры иначе называют телом структуры.

Идентификаторы, объявленные внутри фигурных скобок, называются элементами структуры. Элементы одной и той же структуры должны иметь уникальные имена. Структуры, как и глобальные переменные, должны быть объявлены вне каких-либо функций.

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

Примеры структур: точка, описываемая двумя координатами х и у; структура «платежная ведомость», содержащая сведения о служащем: имя, адрес, зарплата, номер карточки и так далее.

Программа, объявляющая точку с координатами х и у, используя структуру:

# include < iostream >

# include < math>

struct Point {

int x;

int y;

}

main () {

Point A, B; // объявление двух точек A и B с координатами x и y.

cout << ” Enter coordinates of point A \n ”;

cin >> A.x >> A.y;

cout << ” Enter coordinates of point B \n ”;

cin >> B.x >> B.y;

double d;

d = sqrt (pow ((A.x - B.x), 2) + pow ((A.y - B.y), 2));

cout << d;

return 0;

}

Доступ к отдельным элементам структуры производится с помощью операции “точка” (”.”), которая называется оператором прямого доступа к элементам структуры.

Point A;

A.x=1;

A.y=2;

Существует вторая операция доступа к элементам структуры, которая называется “операция указателя структуры” и обозначается через знак ->. Эта операция используется, если переменная была объявлена как указатель структурного типа.

Point * A;

A->x=-5;

A->y=0;

или

(*A).x=-5;

(*A).y=0;

Скобки необходимы в этой записи, потому что операция “.” имеет более высокий приоритет, чем операция косвенной адресации “*”.

Так же, как и любую другую переменную, переменную структурного типа можно одновременно объявлять и инициализировать:

Point A={-1,0};

Point B={-2,-6};

Значения переменных структуры присваиваются в порядке их объявления при определении структуры.

Структуры внутри структур

Допускается объявление вложенных структур. Это означает, что структура может содержать 1 или несколько элементов структурного типа.

Пример:

struct MD {

int headers;

int cylinders;

int speed;

car name[10];

double size;

};

struct Computer {

char model[20];

int memory;

int diagonal;

MD disk;

};

Для доступа к элементу структуры MD используется следующая запись:

Computer A;

A.disk.size=20;