учебное пособие. Часть1. Информатика

int b[N][M]; float a[3][4];

В описании N и M – количество строк и количество столбцов матрицы. Традиционно в качестве

идентификатора номера строки используют символ i, а столбца – j. При изменении второго индекса j на единицу перемещение идет вдоль строки, а при изменении первого индекса i на единицу – вертикально вдоль столбца. Элемент одномерного массива а[i] является указателем на начало i –ой строки матрицы. К элементу двумерного массива, описанному выше, можно обратиться с помощью идентификатора

а[i][j].

Ниже приведены примеры обращения к элементам двумерных массивов:

a[i][j] = 13.13; a[0][1] = 8; b[5][6] = 7; b[i][8] = 0;

211

int a [N1][M1], // Mатрица

printf ( "Введите число стpок и столбцов массива:" ); scanf ( "%d%d", &n, &m );

randomize ();

int s = 0; //Сумма элементов матрицы for ( i = 0; i<n; i++ )

for ( j = 0; j<m; j++ )

{

a[i][j] = random (10); s = s+a[i][j];

}

printf ( "Полученный массив\n" ); for ( i = 0; i<n; i++ )

{

for ( j = 0; j<m; j++ ) printf ( "%5d", a[i][j] ); printf ( "\n" );

}

printf ( "s = %d \n", s ); return 0;

}

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

диагонали, для этого задаем номер строки и номер столбца с помощью одного идентификатора i. Програм-

ма приведена в примере pr19, графическая схема алгоритма – на рис. 22.

//Пример pr19

#include <cstdio> using namespace std;

int main ()

{

213

Начало

const int N1 = 10; //максимальнoе число стpок и столбцов матрицы int a[N1][ N1], //матрица

s; //Сумма элементов главной диагонали

printf ( "Введите число стpок и столбцов матрицы:" ); scanf ( "%d", &n );

printf ( "Введите элементы матрицы \n" ); for ( i = 0; i<n; i++ )

for ( j = 0; j<n; j++ ) scanf ( "%d", &a[i][j] );

printf ( "Исходный массив \n" ); for ( i =0; i<n; i++ )

{

for ( j = 0; j<n; j++ ) printf ( "%5d", a[i][j] ); printf ( "\n" );

214

}

s = 0;

for ( i = 0; i<n; i++ ) s = s+a[i][i];

printf ( "%5d \n", s );

}

return 0;

}

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

Все глобальные переменные и константы, объявленные в программе на языке С++, размещаются в одной непрерывной области оперативной памяти, которая называется сегментом данных [7]. Длина сегмента данных определя- ется архитектурой процессора 8086 и составляет 64 Кбайта, что может вы- звать определенные затруднения при обработке больших массивов данных. С другой стороны, объем памяти ПЭВМ достаточен для успешного решения задач с большой размерностью данных. Выходом из положения может слу- жить использование так называемой динамической памяти.

Динамическая память – это оперативная память ПЭВМ, представляе- мая программе при её работе, за вычетом сегмента данных, стека, и собст- венно тела программы. Размер динамической памяти может варьировать в широких пределах. Динамическая память – это фактически единственная возможность обработки массивов данных большого размера. Существуют и другие задачи, которые трудно или невозможно решить без использования динамической памяти. В частности, такие проблемы возникают при разра- ботке систем автоматизированного проектирования: размерность математи- ческих моделей может значительно отличаться в различных проектах, стати- ческое распределение памяти в этом случае практически невозможно. Кроме того, динамическая память используется для временного запоминания дан- ных при работе с графическими и звуковыми средствами ПЭВМ.

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

Для управления динамической памятью используются уже знакомые нам указатели. Вся динамическая память рассматривается как подобная стеку структура, называемая кучей.

215

Для выделения памяти под любую переменную используется операция new [2]:

указатель = new имя_типа инициализатор

Эта операция позволяет выделить и сделать доступным свободный участок в основной памяти, размеры которого соответствуют типу данных, определяемому именем типа. В выделенный участок памяти заносится зна- чение, определяемое инициализатором, который не является обязательным элементом. В случае успешного выполнения операция new возвращает ад- рес начала выделенного участка памяти. Если участок нужных размеров не может быть выделен (нет памяти), то операция new возвращает нулевое значение указателя (NULL). Необязательный параметр инициализатор – это выражение в круглых скобках. Указатель должен ссылаться на тот же тип, что имя_типа в операции new. Можно написать такой фpагмент пpогpаммы:

int *ptr; float *ptr1; ptr = new int; *ptr = 10;

ptr1 = new float(13.15);

В пеpвом случае опеpация new позволяет выделить 2 байта памяти и адрес начала выделенного участка присваивается указателю ptr. Следующий оператор присваивания инициализирует этот участок памяти числом 10. Во втоpом случае опеpация new позволяет выделить 4 байта памяти, адрес нача- ла выделенного участка присваивается указателю ptr1 и этот участок памяти инициализируется числом 13.15. В дальнейшем доступ к выделенному участ- ку памяти осуществляется с помощью операции косвенной адресации (или разыменовывание). Продолжительность существования выделенного участка - от точки создания до конца программы или до явного освобождения. С по-

мощью операции

delete указатель

осуществляется явное освобождение памяти. Например: delete ptr;

delete ptr1;

Если указатель, на который действует операция delete, не содержит ад- рес блока, зарезервированного ранее операцией new, то последствия будут не предсказуемыми.

Для выделения динамической памяти под массив операция new исполь- зуется следующим образом:

int *mas1; //одномерный массив mas1=new int[n];

216

float *mas2; // двумерный массив mas2 = new float [n*n];

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

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

//Пример pr20 #include <cstdio> #include <cstdlib> using namespace std;

int main ()

{

int n, m;

рrintf ( "\nВведите количество cтpок и столбцов" ); scanf ( "%d%d", &n, &m );

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

//одномеpный массив

int j, i;

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

// указателей randomize ();

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

{

mas2[i] = new int[m];//выделение памяти

//под стpоку матpицы for ( j=0; j<m; j++ )

mas2[i][j] = random (25);

}

puts ( "\n Вывод элементов двумеpного массива" ); for ( i = 0; i<n; i++ )

{

printf ( "\n" );

217

for ( j = 0; j<m; j++ )

printf ( "%d \t", mas2[i][j] );

}

//Фоpмиpование одномеpного массива for ( i = 0; i<n; i++ )

{

mas[i] = 0;

for ( j = 0; j<m; j++ ) mas[i] = mas[i]+mas2[i][j];

}

puts ( "\n Вывод элементов одномеpного массива" ); for ( i = 0; i<n; i++ )

printf ( "%d \t", mas[i] ); // Освобождение памяти for ( i = 0; i<n; i++ ) delete mas2[i];

delete [] mas2; delete [] mas; return 0;

}

Контрольные вопросы

1.Чем матрица отличается от одномерного массива?

2.Как изменяются индексы элементов матрицы, лежащих выше главной диагонали?

3.Как изменяются индексы элементов матрицы, лежащих ниже главной диагонали?

4.Как изменяются индексы элементов матрицы, лежащих выше побочной диагонали?

5.Как изменяются индексы элементов матрицы, лежащих ниже побочной диагонали?

6.Зачем нужны динамические массивы?

7.Как описываются динамические массивы?

8.Что значит выделить динамическую память?

9.Как определяется размер выделенного участка памятм при использовании операции new?

218

5. функции

Программа в языке С++ состоит из функций. Функции – относительно самостоятельные фрагменты программы, спроектированные для решения конкретных задач и снабженные именем [2]. С одной из них, главной, мы уже знакомы. Функции аналогичны программам в миниатюре и имеют общее на- звание подпрограммы. Главное отличие простой функции от главной в том, что с главной функции начинается выполнение программы, а все остальные функции вызываются либо главной, либо из других функций. Применение функций (подпрограмм) дает возможность сэкономить память за счет разме- щения многократно повторяющихся частей программ в функции, а также возможность конструировать программу как набор отдельных подпрограмм, что, в свою очередь, позволяет работать группе программистов над сложной задачей. Даже в том случае, если некоторая задача решается в одной про- грамме и одним программистом, лучше оформить ее решение в виде подпро- грамм, поскольку функции повышают уровень модульности, облегчают чте- ние, внесение изменений и коррекцию ошибок в программе. Пусть необхо- димо написать программу, которая выполняет следующие действия:

вводит массив чисел; определяет среднее арифметическое чисел;

определяет местоположение максимального элемента; заменяет максимальный элемент массива средним арифметическим; выводит обработанный массив.

Операторную часть такой программы можно записать следующим образом:

{..............

vvodmas(mas);

sr=sredmas(mas);

max=maxmas(mas);

zamena(mas);

vivod(mas);

……………

}

Как видно из приведенного фрагмента, программа разделена по смыслу на пять подпрограмм, которые еще следует написать. В программе на языке С++ описание функций может располагаться либо до функции main, либо после функции main. Никакая функция не может быть описана внутри дру- гой функции. Кроме того, функции могут быть описаны в отдельном файле и

подключены к программе с помощью директивы препроцессора include. Каждая функция описывается один раз, а вызываться на выполнение может многократно. В языке C++ описание должно обязательно предшествовать

219

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

Структура подпрограммы почти полностью повторяет структуру глав- ной функции, что как раз подчеркивает структурированность языка. В функ- циях могут быть описаны собственные константы, типы, переменные. В этом случае они называются локальными. Их область действия распространяется только на те функции, в которых они описаны. Переменные, описанные вне функций, в том числе и вне главной функции, называются глобальными. Их область действия распространяется на все функции, расположенные в том же файле после описания. Имена локализованных переменных могут совпадать с ранее объявленными глобальными именами. В этом случае считается, что локальное имя "закрывает" глобальное и делает его недоступным, т. е. одно- именные локальные и глобальные переменные − это разные переменные. Память под глобальные переменные отводится до начала выполнения про- граммы и освобождается в момент завершения программы. Доступ к ним возможен из любой функции. Память под локальные переменные выделяется в момент вызова подпрограммы и освобождается после завершения её вы- полнения. Доступ к ним возможен только из той подпрограммы, в которой они описаны.

В общем случае структуру подпрограммы можно представить сле- дующим образом:

заголовок функции тело функции

Общая форма записи заголовка функции:

<тип> <имя> ([<список формальных параметров>])

Здесь <имя> − правильный идентификатор, который используется для обращения к функции; <тип> − тип возвращаемого функцией результата;

<список формальных параметров> − включает в себя параметры, ко-

торые используются для передачи данных в подпрограмму и из подпрограм- мы. Список формальных параметров необязателен и может отсутствовать (круглые скобки опускать нельзя). Если он есть, то может включать в себя параметры, передаваемые по значению, указателю и ссылке. Например:

void sum(float a, float b, float *s) void sk (int *a, int c , float d) float f (float x, float &y)

int ab (int a) void par (void)

Таким образом, в списке формальных параметров перечисляются име- на формальных параметров и их тип. Список формальных параметров рас-

220