Введите следующее слово (или '.' для завершения списка): сообщение
Введите следующее слово (или '.' для завершения списка): .
ПЕЧАТЬ СОДЕРЖИМОГО СПИСКА В ПРЯМОМ ПОРЯДКЕ:
это короткое тестовое сообщение
ПЕЧАТЬ СОДЕРЖИМОГО СПИСКА В ОБРАТНОМ ПОРЯДКЕ:
сообщение тестовое короткое это
Подсказка: при разработке функции "print_list_backwards()" еще раз посмотрите
на программу 2.1.
б) Напишите и протестируйте итерационный (т.е. нерекурсивный) вариант функ-
ции "print_list_backwards(...)". (Какой вариант функции вам показался про-
ще в разработке?)
Упражнение 3
Даны два положительных целых числа m и n таких, что m<n. Известно, что
наибольший общий делитель чисел m и n совпадает с наибольшим общим делителем
чисел m и (n-m). С учетом этого свойства напишите рекурсивный вариант функции
"greatest_common_divisor(...)", которая принимает два положительных целых пара-
метра и возвращает их наибольший общий делитель. Проверьте свою функцию с по-
мощью подходящей тестовой программы.
Упражнение 4
Бинарный поиск –это рекурсивно определенный алгоритм поиска заданного
значения в отсортированном массиве. Он особенно эффективен при обработке боль-
ших массивов, т.к. не требует последовательного просмотра всех элементов массива.
Основные действия алгоритма заключаются в следующем. Предположим, тре-
буется определить в массиве a[] индекс элемента со значением v. Массив a[] предва-
рительно отсортирован по возрастанию. Сначала проверим значение среднего эле-
мента массива a[]. Если это значение равно v, то работа алгоритма завершается, и
функция возвращает в качестве результата индекс среднего элемента. Если же оказы-
вается, что средний элемент меньше, чем v, то требуется выполнить поиск только во
второй половине массива. При этом повторяется процедура деления массива пополам.
Аналогично, если среднее значение оказывается больше, чем v, то требуется продол-
жить поиск только в первой половине массива.
Работу этого алгоритма легко понять, если мысленно применить его к поиску
заданного слова в словаре. Применяя бинарный поиск, вы должны начать с середины
словаря и затем ограничить поиск половиной словаря или до, или после средней
страницы. Затем деление просматриваемых страниц словаря повторяется и т.д..
Для выполнения бинарного поиска напишите функцию с прототипом:
99
int binary_search( int value, int list[], int first, int last );
Эта функция должна искать значение "value" в массиве "list[]" в интер-
вале индексов от "list[first]" до "list[last]". Если значение "value" обнаружено в
заданном диапазоне, то функция должна возвратить индекс соответствующего эле-
мента массива "list[]". В противном случае функция должна вернуть -1. Например,
для массива
list = { 2, 2, 3, 5, 8, 14, 16, 22, 22, 24, 30 }
функция
binary_search( 24, list, 0, 10 );
должна вернуть значение 9, функция
binary_search( 24, list, 2, 6 );
должна вернуть -1, а функция
binary_search( 22, list, 0, 10 );
должна вернуть значение 7 или 8.
Проверьте свою функцию с помощью подходящей тестовой программы. (Для
этого вы можете модифицировать программу 7.1).
100
ЛЕКЦИЯ 9. Составные типы данных
1. Назначение составных типов данных
В программах часто приходится обрабатывать информацию, описывающую
более сложные объекты, чем числа и символы. Например, в библиотечной базе дан-
ных требуется обрабатывать данные об объектах "Книги", в системе кадрового учета
– "Сотрудники", "Отделы" и т.п. В зависимости от решаемой задачи, программист оп-
ределяет, какие характеристики (свойства) объектов нужно учитывать. Для хранения
этих свойств в программе выделяются переменные подходящих типов, например,
символьный массив для имени сотрудника и вещественное число для его зарплаты.
Оказывается, если свойства объектов хранить в отдельных переменных, то при боль-
шом количестве различных свойств и при наличии большого количества экземпляров
однотипных объектов программисту становится довольно сложно следить за кор-
ректным использованием переменных.
В Си++ для построения новых типов данных используются классы, объеди-
няющие в себе и свойства объектов, и действия (алгоритмы), которые эти объекты
способны выполнять. Но, поскольку проблема обработки сложных типов данных ста-
ла актуальной еще до распространения объектно-ориентированного программирова-
ния, уже в язык Си было введено понятие структуры. Структура – это составной
тип данных, который получается путем объединения компонент, принадлежащих к
другим типам данных (возможно, тоже составным). Впоследствии в Си++ понятие
структуры было расширено до класса.
Пример структур в математике –комплексные числа, состоящие из двух веще-
ственных чисел, и координаты точек, состоящие из двух или более вещественных чи-
сел в зависимости от размерности координатного пространства. Пример из обработки
данных –это описание людей с помощью нескольких существенных характеристик,
таких, как имя и фамилия, дата рождения, пол и семейное положение.
Понятие структуры встречается во многих языках программирования и в об-
ласти баз данных, только вместо термина "структура", специфичного для Си++, в
других языках обычно применяется термин "запись" (подразумевается, что перемен-
ные составных типов предназначены для записи существенных характеристик объек-
тов, обрабатываемых в программе, например, людей или материальных предметов).
2. Описание и инициализация структур
Структура предназначена для объединения нескольких переменных в один тип
данных. Сначала тип структуры надо описать, а затем можно создавать переменные
этого нового типа. Описание типа структуры "T" имеет следующий синтаксис:
struct T {
T1 var1;
T2 var2;
...
T3 var3;
};
где "T1", "T2", "T3" –имена встроенных типов данных ("int", "char" и др.) или дру-
гих составных типов. "var1", "var2", "var3" –это имена внутренних переменных
структуры (они также называются компонентами, полями или членами структуры).
101
Далее приведены три примера описания структур для представления ком-
плексных чисел, дат и сведений о людях:
struct Complex {
double re;
double im;
};
struct Date {
int day;
int month;
int year;
};
struct Person {
char name[50];
Date birthdate;
double salary;
};
Обратите внимание на точку с запятой в конце описания типа структуры. Это
одно из очень немногих мест в Си++, где необходимо ставить точку с запятой после
фигурной скобки. На примере типа "Person" видно, что компоненты структуры мо-
гут, в свою очередь, тоже быть составными. Переменные типа структуры описывают-
ся аналогично переменным встроенных типов:
Complex z;
Date d;
Person p;
В операторе описания переменные можно инициализировать путем перечисле-
ния значений компонент в фигурных скобках (аналогично инициализации массивов):
Complex z = { 1.6, 0.5 };
Date d = { 1, 4, 2001 };
Person p = { "Сидоров", {10, 3, 1978}, 1500.48 };
Для обращения к отдельным компонентам структуры применяется опера-
ция "." (точка). Сначала указывается имя переменной-структуры, а затем –имя ком-
поненты. Например:
z.im = 3.2;
d.month = 7;
p.birthdate.year = 1980;
p.salary = 2000.00;
Важно отметить, что не все возможные комбинации значений компонент
структуры могут иметь смысл применительно к конкретной задаче. Например, тип
"Date", определенный выше, включает значения {50, 5, 1973} и {100, 22, 1815}, хотя
дней с такими датами не существует. Т.о., определение этого типа не отражает реаль-