Передача массивов в качестве параметров функций

Чтобы у программ была понятная человеку структура, допускающая модифи-

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

реализовывать в виде самостоятельных функций. Т.к. для хранения данных часто

применяются массивы, то бывают необходимы и функции для их обработки. Этим

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

фрагменте программы 2.1 содержится определение функции, которая принимает мас-

сив типа "Hours_array" (см. программу 1.1) и возвращает среднее количество часов,

отработанных сотрудниками группы.

 

float average(Hours_array hrs)

{

float total = 0;

int count;

for (count = 0; count < NO_OF_EMPLOYEES; count++)

total += float(hrs[count]);

return (total/NO_OF_EMPLOYEES);

}

Фрагмент программы 2.1.

 

Эту функцию можно сделать более универсальной, если размер массива не

фиксировать в ее определении, а передать в качестве второго параметра:

 

float average(int list[], int length)

{

float total = 0;

int count;

for (count = 0; count < length; count++)

total += float(list[count]);

return (total/length);

}

 

В этом примере показан очень распространенный способ оформления функций,

работающих с массивами: в одном параметре передается длина массива, а в другом –

сам массив, причем в описании параметра-массива не указывается длина массива (на-

пример, "int list[]").

Параметры-массивы всегда передаются по ссылке (а не по значению), хотя при

их описании в заголовке функции символ "&" не указывается. Правило "массивы все-

}

;

 

гда передаются по ссылке" введено для того, чтобы функции не делали собственных

внутренних копий переданных им массивов – для больших массивов это могло бы

привести к нерациональным затратам памяти. Следовательно, как и параметры по

ссылке, рассматривавшиеся в 3-ей лекции, все изменения элементов параметров-

массивов внутри функций будут видны и в вызывающей функции.

Далее показана функция (фрагмент программы 2.2), принимающая в качестве

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

вен сумме двух соответствующих элементов первого и второго массивов.

 

void add_lists(int first[], int second[], int total[],

int length)

 

int count;

for (count = 0; count < length; count++)

total[count] = first[count] + second[count];

 

Фрагмент программы 2.2.

 

 

В целях безопасности, для защиты от случайного изменения элементов масси-

ва, в описание первых двух параметров функции добавим модификатор типа "const":

 

void add_lists(const int fst[], const int snd[], int tot[],

int len)

 

int count;

for (count = 0; count < len; count++)

tot[count] = fst[count] + snd[count];

 

 

Теперь компилятор не будет обрабатывать ни один оператор в определении

функции, который пытается модифицировать элементы константных массивов "fst"

или "snd". Фактически, ограничение, накладываемое модификатором "const" в дан-

ном контексте, в некоторых ситуациях оказывается слишком строгим. Например,

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

 

void no_effect(const int list[])

{

do_nothing(list);

}

 

void do_nothing(int list[])

{

 

;

}

Фрагмент программы 2.3.

 

 

Ошибка компиляции программы 2.3 объясняется тем, что, хотя фактически

функция "do_nothing(...)" не выполняет никаких действий, но в ее заголовке отсут-

ствует модификатор "const". Когда компилятор в теле функции "no_effect(...)"

встретит вызов функции "do_nothing(...)", то он обратится только к заголовку функ-

 

 

{

}

{

}

 

ции "do_nothing(...)", и выдаст ошибку о невозможности передачи константного

массива в эту функцию.

 

 

Сортировка массивов

По отношению к массивам часто возникает задача сортировки по убыванию

или возрастанию. Разработано много различных алгоритмов сортировки, например,

пузырьковая сортировка и быстрая сортировка. В этом параграфе кратко рассматри-

вается один из простейших алгоритмов сортировки – сортировка методом выбора

наименьшего элемента.

Основные действия алгоритма для сортировки массива длиной L заключаются

в следующем:

Для каждого значения индекса i выполнить два действия:

Среди элементов с индексами от i до (L-1) найти

элемент с минимальным значением.

Обменять значения i-го и минимального элемен-

тов.

Работу этого алгоритма рассмотрим на примере сортировки массива из 5 целых

чисел:

int a[5];

Значения элементов неотсортированного массива показаны на рис. 4.

 

Рис. 4.. Начальное состояние массива.

 

В процессе сортировки методом выбора наименьшего элемента массив будет

последовательно переходить в состояния, показанные на рис. 5 (слева направо). Каж-

дое состояние получается из предыдущего путем перестановки двух элементов, поме-

ченных на рис. 5 кружками.

 

Рис. 5.. Последовательные шаги сортировки массива методом выбора наи-

меньшего элемента.

 

На Си++ алгоритм сортировки можно реализовать в виде трех функций. Функ-

ция высокого уровня будет называться "selection_sort(...)" (у нее два параметра –

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

функцию "minimum_from(array,position,length)", котораявозвращаетиндексмини-

мального элемента массива "array", расположенного в диапазоне между индексом

"position" и концом массива. Затем для обмена двух элементов массива вызывается

функция "swap(...)".

 

void selection_sort(int a[], int length)

 

1)

2)

 

{

for (int count = 0; count < length - 1; count++)

swap(a[count], a[minimum_from(a,count,length)]);

}

 

int minimum_from(int a[], int position, int length)

{

int min_index = position;

 

for (int count = position + 1; count < length; count++)

if (a[count] < a[min_index])

min_index = count;

 

return min_index;

}

 

void swap(int& first, int& second)

 

int temp = first;

first = second;

second = temp;

 

Фрагмент программы 3.1.

 

Двумерные массивы

Массивы в Си++ могут иметь более одной размерности. В данном параграфе

кратко описаны двумерные массивы. Они широко применяются для хранения дву-

мерных структур данных, например, растровых изображений и матриц.

При обработке изображений часто используются битовые маски – вспомога-

тельные двуцветные (черно-белые) изображения, состоящие только из 0 (белая точка)

и 1 (черная точка) (или, логических значений "false" и "true"). Предположим, что

требуется маска размером 64х32 пиксела. Для описания соответствующего массива

возможны операторы:

const int BITMAP_HEIGHT = 64;

const int BITMAP_WIDTH = 32;

bool bitmap[BITMAP_HEIGHT][BITMAP_WIDTH];

При обращении к элементам массива "bitmap" необходимо указывать два ин-

декса. Например, чтобы изменить значение 2-го пиксела слева в 4-й строке надо запи-

сать оператор:

bitmap[3][1] = true;

Все сказанное во 2-м параграфе относительно одномерных массивов как пара-

метров функций верно и для двумерных массивов, но у них есть еще одна особен-

ность. В прототипах и заголовках функций можно опускать первую размерность мно-

гомерного массива-параметра (т.е. записывать пустые квадратные скобки "[]"), но все

остальные размерности надо обязательно указывать. Далее в качестве примера приве-

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

 

void clear_bitmap(bool bitmap[][BITMAP_WIDTH],

int bitmap_height)

{

for (int row = 0; row < bitmap_height; row++)

 

{

}

 

for (int column = 0; column < BITMAP_WIDTH; column++)

bitmap[row][column] = false;

 

 

}

Указатели

 

Назначение указателей

Язык Си++ унаследовал от языка Си мощные средства для работы с оператив-

ной памятью: динамическое выделение и освобождение блоков памяти, доступ к от-

дельным ячейкам памяти по их адресам. Эти возможности делают язык Си++, как и

Си, удобным для разработки системного программного обеспечения и прикладных

программ, в которых применяются динамические структуры данных (т.е. такие, раз-

мер которых не известен на этапе компиляции и может меняться во время выполне-

ния программы).

Во всех программах из предыдущих лекций переменные объявлялись так, что

компилятор резервировал для каждой из них некоторое количество памяти (в соот-

ветствии с типом данных) еще на этапе компиляции. В начале выполнения блока опе-

раторов, внутри которого объявлена переменная, автоматически выполняется выде-

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

В данной лекции подробно рассматривается понятие указателя, – средства, ко-

торое дает программисту наиболее гибкий способ контроля операций выделе-

ния/освобождения памяти во время выполнения программ.

 

 

1.1 Объявление указателей

Указателем называется адрес переменной в оперативной памяти. Переменная

указательного типа (часто она называется переменная-указатель или просто указа-

тель) – это переменная, размер которой достаточен для хранения адреса оперативной

памяти. Переменные-указатели объявляются с помощью символа "*", который добав-

ляется после названия обычного типа данных. Например, оператор описания (его

можно прочитать как "указатель на целочисленную переменную"):

int* number_ptr;

объявляет переменную-указатель "number_ptr", которая может хранить адреса пере-

менных типа "int".

Если в программе используется много однотипных указателей, то дляих объ-

явления можно ввести новый тип. Это делается с помощью оператора описания ново-

го типа "typedef". Например, если записать оператор:

typedef int* IntPtrType;

то в программе можно будет объявлять сразу несколько переменных-указателей, не

применяя для каждой из них символ "*":

IntPtrType number_ptr1, number_ptr2, number_ptr3;

 

 

1.2 Применение символов "*" и "&" в операторах присваивания значений указателям

В операторах присваивания допускается совместное использование обычных и

указательных переменных одного типа (например, "int"). Для получения значения

переменной по ее указателю предназначена операция разыменования указателя "*". У

нее есть обратная операция – операция взятия адреса "&". Упрощенно, операция "*"

означает "получить значение переменной, расположенной по этому адресу", а опера-

ция "&" – "получить адрес этой переменной". Для пояснения смысла этих операций

далее приводится программа 1.1.

 

#include <iostream.h>

 

typedef int* IntPtrType;

 

int main()

 

IntPtrType ptr_a, ptr_b;

int num_c = 4, num_d = 7;

 

ptr_a = &num_c;

ptr_b = ptr_a;

 

/* СТРОКА 10 */

/* СТРОКА 11 */

cout<< *ptr_a << " " << *ptr_b << "\n";

ptr_b = &num_d; /* СТРОКА 13 */

cout<< *ptr_a << " " << *ptr_b << "\n";

*ptr_a = *ptr_b; /* СТРОКА 15 */

cout<< *ptr_a << " " << *ptr_b << "\n";

cout<< num_c << " " << *&*&*&num_c << "\n";

return 0;

 

Программа 1.1.

 

Программа 1.1 выдает на экран следующие сообщения:

Графически состояние программы 1.1 после выполнения операторов присваи-

вания в 10-11-й строках, 15-й и 19-й показано, соответственно, на рис. 1, 2 и 3.

 

Рис. 1.. Состояние про-

граммы 1.1 после выпол-

нения 10-й и 11-й строк.

 

Рис. 2.. Состояние про-

граммы 1.1 после выпол-

нения 13-й строки.

 

Рис. 3.. Состояние про-

граммы 1.1 после выпол-

нения 15-й строки.

 

Операции "*" и "&", в некотором смысле, являются взаимно обратными, так что

выражение "*&*&*&num_c" означает то же самое, что и "num_c".

 

 

1.3 Операторы "new" и "delete". Константа "NULL"

Рассмотрим оператор присваивания в 10-й строке программы 1.1:

ptr_a = &num_c;

Можно считать, что после выполнения этого оператора у переменной "num_c"

появляется еще одно имя – "*ptr_a". Часто в программах бывает удобно пользоваться

переменными, у которых есть только такие имена – динамическими переменными. Не-

зависимых имен у них нет. К динамическим переменным можно обращаться только

через указатели с помощью операции разыменования (например, "*ptr_a" и "*ptr_b").

Динамические переменные "создаются" с помощью оператора распределения

динамической памяти "new", а "уничтожаются" (т.е. занимаемая ими память освобож-

 

{

}

 

дается для дальнейшего использования) с помощью оператора "delete". Действие

этих операторов показано в программе 1.2 (она очень похожа на программу 1.1).

 

#include <iostream.h>

 

typedef int* IntPtrType;

 

int main()

{

IntPtrType ptr_a, ptr_b;

 

ptr_a = new int;

*ptr_a = 4;

ptr_b = ptr_a;

/* СТРОКА 7 */

 

/* СТРОКА 9 */

/* СТРОКА 10 */

/* СТРОКА 11 */

 

cout << *ptr_a << " " << *ptr_b << "\n";

 

ptr_b = new int;

*ptr_b = 7;

 

/* СТРОКА 15 */

/* СТРОКА 16 */

 

cout << *ptr_a << " " << *ptr_b << "\n";

 

delete ptr_a;

ptr_a = ptr_b;

 

 

/* СТРОКА 21 */

 

cout << *ptr_a << " " << *ptr_b << "\n";

 

delete ptr_a;

 

/* СТРОКА 25 */

 

return 0;

}

Программа 1.2.

 

Программа 1.2 печатает на экране следующие сообщения:

4 4

4 7

7 7

На рисунках 4-8 показаны состояния программы 1.2 после выполнения 7-й, 9-

11-й, 15-16-й, 21-й и 25-й строк.

 

Рис. 4.. Состояние про-

граммы 1.2 после выпол-

нения 7-й строки с описа-

ниями переменных.

 

Рис. 5.. Программа 1.2

после выполнения опера-

торов присваивания в 9-й,

10-й и 11-й строках.

 

 

Рис. 6.. Программа 1.2

после выполнения опера-

торов присваивания в 15-

й и 16-й строках.

 

 

Рис. 7.. Программа 1.2 после

выполнения оператора присваи-

вания в 21-й строке.

 

 

Рис. 8.. Программа 1.2 после вы-

полнения оператора "delete" в

25-й строке.

 

Состояния на рис. 4 и рис. 8 похожи тем, что значения указателей "ptr_a" и

"ptr_b" не определены, т.е. они указывают на несуществующие объекты. Обратите

внимание, что указатель "ptr_b" в конце программы оказывается в неопределенном

состоянии, хотя при вызове оператора "delete" этот указатель явно не передавался.

Если указатель "ptr" указывает на несуществующий объект, то использование

в выражениях значения "*ptr" может привести в непредсказуемым (и часто катастро-

фическим) результатам. К сожалению, в Си++ нет встроенного механизма проверки

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

безопасными, если всегда будет стараться присваивать несуществующим указателям

нулевой адрес (символическое имя нулевого адреса – "NULL"). Для хранения перемен-

ных в Си++ нулевой адрес не используется.

Константа "NULL" (целое число 0) описана в библиотечном заголовочном файле

"stddef.h". Значение "NULL" можно присвоить любому указателю. Например, в про-

грамме 1.3, являющемся усовершенствованным вариантом программы 1.2, для защи-

ты от использования неопределенных указателей "*ptr_a" и "*ptr_b" были добавлены

следующие строки:

 

#include <iostream.h>

#include <stddef.h>

...

...

delete ptr_a;

ptr_a = NULL;

delete ptr_b;

ptr_b = NULL;

...

...

if (ptr_a!= NULL)

{

*ptr_a =...

...

...

Фрагмент программы 1.3.

 

В случае, если для создания динамической переменной не хватает свободной

оперативной памяти, то после вызова "new" Си++ автоматически присвоит соответст-

вующему указателю значение "NULL". В показанном ниже фрагменте программы 1.4

этот факт используется для организации типичной проверки успешного создания ди-

намической переменной.

 

#include <iostream.h>

#include <stdlib.h>

/* "exit()" описана в файле stdlib.h */

#include <stddef.h>

...

...

 

 

ptr_a = new int;

if (ptr_a == NULL)

{

cout << "Извините, недостаточно оперативной памяти";

exit(1);

}

...

...

Фрагмент программы 1.4.

 

Указатели можно передавать в качестве параметров функций. В программе 1.5

проверка на корректность указателя выполняется в отдельной функции, выполняю-

щей создание динамической целочисленной переменной:

 

void assign_new_int(IntPtrType& ptr)

 

ptr = new int;

if (ptr == NULL)

{

cout << "Извините, недостаточно оперативной памяти";

exit(1);

 

}

}

Фрагмент программы 1.5.

 

 

2. Переменные типа "массив". Арифметические операции с указателями

В 6-й лекции были рассмотрены массивы – наборы однотипных переменных. В

Си++ понятия массива и указателя тесно связаны. Рассмотрим оператор описания:

int hours[6];

Этот массив состоит из 6-ти элементов:

hours[0]

hours[1]

hours[2]

hours[3]

hours[4]

hours[5]

Массивы в Си++ реализованы так, как будто имя массива (например, "hours")

является указателем. Поэтому, если добавить в программу объявление целочисленно-

го указателя:

int* ptr;

то ему можно присвоить адрес массива (т.е. адрес первого элемента массива):

ptr = hours;

После выполнения этого оператора обе переменные – "ptr" и "hours" – будут

указывать на целочисленную переменную, доступную в программе как "hours[0]".

Фактически, имена "hours[0]", "*hours" и "*ptr" являются тремя различными

именами одной и той же переменной. У переменных "hours[1]", "hours[2]" и т.д.

также появляются новые имена:

 

или

*(hours + 1)

*(hours + 2)

*(ptr + 1)

*(ptr + 2)

...

В данном случае "+2" означает "добавить к адресу указателя смещение, соот-

ветствующее 2-м целым значениям". Из арифметических операций к указателям часто

применяется сложение и вычитание (в том числе операции инкремента и декремента

 

 

{

...

 

"++" и "--"), а умножение и деление не используются. Значения однотипных указате-

лей можно вычитать друг из друга.

Главное, что нужно запомнить относительно сложения и вычитания значений

из указателя – в выражениях Си++ указывается не число, которое нужно вычесть (или

добавить) из адреса, а количество переменных заданного типа, на которые нужно

"сместить" адрес.

Арифметические выражения с указателями иногда позволяют более кратко за-

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

английской строки в верхний регистр (фрагмент программы 2.1).

 

void ChangeToUpperCase(char phrase[])

{

int index = 0;

while (phrase[index]!= '\0')

{

if (LowerCase(phrase[index]))

ChangeToUpperCase(phrase[index]);

index++;

}

}

 

bool LowerCase(char character)

{

return (character >= 'a' && character <= 'z');

 

 

void ChangeToUpperCase(char& character)

{

character += 'A' - 'a';

}

Фрагмент программы 2.1.

 

Обратите внимание на полиморфизм функции "ChangeToUpperCase(...)" – при

обработке вызова компилятор различает две перегруженных функции, т.к. у них раз-

ные параметры (у одной – параметр типа "char", а у другой – параметр типа "сим-

вольный массив"). Имя массива "phrase" является переменной-указателем, поэтому

функцию с параметром-массивом можно переписать короче, если использовать

арифметические выражения с указателями:

 

void ChangeToUpperCase(char* phrase)

{

while (*phrase!= '\0')

{

if (LowerCase(*phrase))

ChangeToUpperCase(*phrase);

phrase++;

 

}

}

Фрагментпрограммы 2.2.

 

Эта модификация функции не влияет на остальные части программы – вызовы

вариантов функций с параметром-указателем или параметром-массивом записывают-

сяодинаково, например:

 

}

 

char a_string[] = "Hello World";

...

...

ChangeToUpperCase(a_string);

 

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

Правила создания и уничтожения динамических переменных типов "int",

"char", "double" и т.п. (см. п.1.3) распространяются и на динамические массивы. По

отношению к массивам динамическое распределение памяти особенно полезно, по-

скольку иногда бывают массивы больших размеров.

Динамический массив из 10-ти целых чисел можно создать следующим обра-

зом:

int* number_ptr;

number_ptr = new int[10];

Переменные-массивы в Си++ являются указателям, поэтому к 10-ти элементам

динамического массива допускается обращение:

number_ptr[0]

number_ptr[1]

...

number_ptr[9]

или:

number_ptr

*(number_ptr + 1)

*(number_ptr + 9)

Для уничтожения динамического массива применяется оператор "delete" c

квадратными скобками "[]":

delete[] number_ptr;

Скобки "[]" играют важную роль. Они сообщают оператору, что требуется

уничтожить все элементы массива, а не только первый.

Работа с динамическими массивами показана в программе 3.1. В приведенном

фрагменте программы у пользователя запрашивается список целых чисел, затем вы-

числяется и выводится на экран их среднее значение.

 

...

...

int no_of_integers, *number_ptr;

 

cout << "Введите количество целых чисел в списке: ";

cin >> no_of_integers;

 

number_ptr = new int[no_of_integers];

if (number_ptr == NULL)

{

cout<< "Извините, недостаточно памяти.\n";

exit(1);

}

 

cout<< "Наберите " << no_of_integers;

cout << " целых чисел, разделяя их пробелами:\n";

for (int count = 0; count < no_of_integers; count++)

cin >> number_ptr[count];

cout<< "Среднеезначение: ";

cout << average(number_ptr, no_of_integers);

 

delete[] number_ptr;

...

...

 

...

Фрагментпрограммы 3.1.

 

Динамические массивы, как и обычные, можно передавать в качестве парамет-

ров функций. Поэтому в программе 3.1 без изменений будет работать функция

"average()" из предыдущей лекции (лекция 6, п. 2).