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

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.

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

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

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

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

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

Тельные двуцветные (черно-белые) изображения, состоящие только из 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++)

70

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

bitmap[row][column] = false;

}

Символьные строки

Во многих уже рассматривавшихся программах для вывода на экран часто ис-

пользовались символьные строки, например, ""Введите возраст:"". В Си++ строки

Хранятся и обрабатываются в виде символьных массивов, на которые накладывается

Дополнительное ограничение (см. п.5.1).

5.1 Завершающий нуль-символ '\0'

Символьный массив для хранения строки должен иметь длину на 1 символ

Больше, чем длина строки. В последнем элементе массива хранится специальный

нуль-символ (символ с кодом 0, часто обозначается '\0'). Этот служебный символ

Обозначает конец строки, и это общепринятое правило представления строк, которое

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

На рис. 6 показаны два массива, в которых хранятся символы строки ""Введите

возраст:"", но из них только массив "phrase" является правильным представлением

строки. Хотя и "phrase", и "list" являются символьными массивами, но только

"phrase" имеет достаточную длину для хранения символьной строки ""Введите воз-

раст:"" вместе с завершающим символом "'\0'".

Рис. 6.. Правильное ("phrase") и неправильное ("list") представление сим-

Вольной строки.

Объявление и инициализация символьных строк

Символьные строки описываются как обычные массивы:

char phrase[17];

Массивы можно полностью или частично проинициализировать непосредст-

Венно в операторе описания. Список значений элементов массива заключается в фи-

гурные скобки "{}" (это правило верно для любых массивов, а не только для сим-

Вольных). Например, оператор

char phrase[17] = { 'В','в','е','д','и','т','е',' ',

'в','о','з','р','а','с','т',

':', '\0' };

71

одновременно и объявляет массив "phrase", и присваивает его элементам значения

согласно рис. 6. То же самое делает оператор:

char phrase[17] = "Введите возраст:";

Если не указывать размер "17", то размер массива будет выбран в соответствии

С количеством инициализирующих значений (с учетом завершающего нуль-символа).

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

char phrase[] = { 'В','в','е','д','и','т','е',' ',

'в','о','з','р','а','с','т',

':', '\0' };

char phrase[] = "Введите возраст:";

Очень важно запомнить, что символьные строки хранятся в виде массивов. По-

этому их нельзя приравнивать и сравнивать с помощью операций "=" и "==". Напри-

мер, нельзя записать оператор присваивания:

phrase = "Вы напечатали строку:";

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

Течные функции.

Библиотечные функции для работы с символьными строками

В стандартном библиотечном файле "string.h" хранятся прототипы большо-

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