Передача массивов в качестве параметров функций
Чтобы у программ была понятная человеку структура, допускающая модифи-
кацию и повторное использование исходного текста, отдельные алгоритмы следует
реализовывать в виде самостоятельных функций. Т.к. для хранения данных часто
применяются массивы, то бывают необходимы и функции для их обработки. Этим
функциям массивы можно передавать в качестве параметров. В показанном ниже
фрагменте программы 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 )
|
|
|
|
{
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).