СОРТИРОВКА массива - ПРИМЕР в файле list6_4cpp.

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

- ПОИСК в массиве

означает нахождение в массиве элемента, совпадающего с заданным значением. Методы поиска делятся на две группы: для упорядоченных и неупорядоченных массивов. Метод линейного поиска применяется для неупорядоченных массивов, а метод двоичного поиска - для сортированных массивов. (Пример - list6_5.cpp)

Рассмотрим понятия ПАРАМЕТРОВ-ФУНКЦИЙ и УКАЗАТЕЛИ НА ФУНКЦИИ:

(Листинг 6.5. исходный текст программы SEARCH.CPP)

БИБЛИОТЕЧНЫЕ ФУНКЦИИ ПОИСКА и СОРТИРОВКИ в непрерывных массивах:

*/

void *bsearch(const void *key, const void *base, size_t nelem,

size_t width, int (*fcmp)(const void*, const void*));

// key - указатель на искомый элемент,

// возвращаемое значение - указатель на элемент (0 - не найден)

// base - базовый адрес массива

// num - число элементов в массиве

// width - размер элемента

// fcmp - указатель на функцию сравнения элементов массива

// Функция возвращает указатель на элемент, а не значение индекса элемента

// Если элемент не обнаружен, возвращается 0.

// Для вычисления индекса можно использовать следующую формулу:

index = (searchRslt - arrayBase) / sizeof(arrayBase[0]);

 

void *lfind(const void *key, const void *base, size_t *num,

size_t width, int (*fcmp)(const void *, const void*));

void *lsearch(const void *key, void *base, size_t *num,

size_t width, int (*fcmp)(const void *, const void *));

// - если нет элемента, то он вставляется, поэтому возвращаемое значение

// всегда не ноль.

void qsort(void *base, size_t nelem,

size_t width, int (*fcmp)(const void *, const void *));

/*

- При объявлении многомерных массивов вам нужно указать тип массива, его имя и размер (заключенный в свою пару скобок) по каждому измерению. Нижнее значение индекса для любого измерения равно 0. Верхнее значение индекса по любому измерению равно количеству элементов поэтому измерению минус единица.

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

Пример работы с двумерным массивом:

(Листинг 6.6. Исходный текст программы MATRIX1.CPP)

- При объявлении многомерных массивов им можно присвоить начальные значения. Список ИНИЦИАЛИЗАЦИИ должен быть заключен в фигурные скобки, а элементы в нем должны быть разделены запятыми. Можно при инициализации задать данных меньше, чем размер массива, В этом случае компилятор автоматически присвоит нулевые значения тем элементам, для которых вы не указали начальные значения:

(Листинг 6.7. Исходный текст программы MATRIX2.CPP.)

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

(Листинг 6.8. Исходный текст программы MATRIX3.CPP)

Строки и управление вводом/выводом

Здесь подробнее рассматриваются операции консольного ввода/вы­вода. C++, как и его предок — язык С — не определяет операции ввода/вывода как часть языка, а выносит операции консольного ввода/вывода в библиотеки ввода/вывода. Такие библиотеки в основном предназначены для работы в MS-DOS. Рассмотрим небольшую выборку функций ввода/вывода, объявляемых в заголовочных файлах STDIO.H и IOSTREAM.H.

Сегодня мы рассмотрим следующие темы:

· Форматированный потоковый вывод

· Потоковый ввод

· Функция printf

· Строки в C++

· Ввод строк

· Использование стандартной библиотеки функций для работы со строками

· Присвоение значений строкам

· Определение длины строки

· Конкатенация строк

· Сравнение строк

· Преобразование строк

· Перестановка символов в строке в обратном порядке

· Поиск символа

· Поиск подстроки