ним оказался бы в состоянии, показанном на рис. 3.
Рис. 3.. Ошибка выхода за пределы массива.
Другими словами, значение "37" было бы размещено в ячейке памяти, доста-
точной для хранения целого числа, которая расположена сразу после массива "hours".
Это чрезвычайно нежелательная ситуация, потому что компилятор может зарезерви-
ровать эту ячейку памяти для другой переменной (например, для переменной
"count").
Массивы могут быть любого типа, не обязательно типа "int". Ниже приведена
программа 1.2, в которой символьный ("char") массив применяется для печати собст-
венного исходного файла на экране в обратном порядке.
#include <iostream.h>
#include <fstream.h>
const int MAX_LEN = 1000;
typedef char File_array[MAX_LEN];
int main()
{
char character;
File_array file;
int count;
ifstream in_stream;
in_stream.open("prg6_1_2.cpp");
in_stream.get(character);
for ( count = 0; !in_stream.eof() && count < MAX_LEN; count++ )
{
file[count] = character;
66
in_stream.get(character);
}
in_stream.close();
while (count > 0)
cout << file[--count];
return 0;
}
Программа 1.2.
В заголовке цикла "for" обратите внимание на условие "... && count < MAX ;
...", специально предусмотренное для предотвращения выхода за пределы массива.
2. Передача массивов в качестве параметров функций
Чтобы у программ была понятная человеку структура, допускающая модифи-
кацию и повторное использование исходного текста, отдельные алгоритмы следует
реализовывать в виде самостоятельных функций. Т.к. для хранения данных часто
применяются массивы, то бывают необходимы и функции для их обработки. Этим
функциям массивы можно передавать в качестве параметров. В показанном ниже
фрагменте программы 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[]").
Параметры-массивы всегда передаются по ссылке (а не по значению), хотя при
их описании в заголовке функции символ "&" не указывается. Правило "массивы все-
67
гда передаются по ссылке" введено для того, чтобы функции не делали собственных
внутренних копий переданных им массивов –для больших массивов это могло бы
привести к нерациональным затратам памяти. Следовательно, как и параметры по
ссылке, рассматривавшиеся в 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(...)", то он обратится только к заголовку функ-
68
ции "do_nothing(...)", и выдаст ошибку о невозможности передачи константного
массива в эту функцию.
3. Сортировка массивов
По отношению к массивам часто возникает задача сортировки по убыванию
или возрастанию. Разработано много различных алгоритмов сортировки, например,
пузырьковая сортировка и быстрая сортировка. В этом параграфе кратко рассматри-
вается один из простейших алгоритмов сортировки –сортировка методом выбора
наименьшего элемента.
Основные действия алгоритма для сортировки массива длиной L заключаются
в следующем:
Для каждого значения индекса i выполнить два действия:
1) Среди элементов с индексами от i до (L-1) найти
элемент с минимальным значением.
2) Обменять значения 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 )
69
{
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.
4. Двумерные массивы
Массивы в Си++ могут иметь более одной размерности. В данном параграфе
кратко описаны двумерные массивы. Они широко применяются для хранения дву-
мерных структур данных, например, растровых изображений и матриц.
При обработке изображений часто используются битовые маски –вспомога-
тельные двуцветные (черно-белые) изображения, состоящие только из 0 (белая точка)
и 1 (черная точка) (или, логических значений "false" и "true"). Предположим, что
требуется маска размером 64х32 пиксела. Для описания соответствующего массива
возможны операторы:
const int BITMAP_HEIGHT = 64;
const int BITMAP_WIDTH = 32;
bool bitmap[BITMAP_HEIGHT][BITMAP_WIDTH];
При обращении к элементам массива "bitmap" необходимо указывать два ин-