Алгоритмы и алгоритмические языки

Министерство образования и науки Российской Федерации Набережночелнинский институт (филиал) федерального государственного автономного образовательного учреждения высшего образования «Казанский (Приволжский) федеральный университет» Отделение информационных технологий и энергетических систем Кафедра системного анализа и информатики СБОРНИК ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ «АЛГОРИТМЫ И АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ» Составитель: И.З. Ахметзянов доцент кафедры САиИ 2016 СОДЕРЖАНИЕ ЛЕКЦИЯ 1. ИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ ОСНОВЫ РАБОТЫ ЭВМ ..................4 1.1. Системы счисления и формы представления чисел............................................................4 1.2. Варианты представления информации в ПК.......................................................................6 Представление дробных чисел в ЭВМ ................................................................................................ 7 Представление символьной информации в ЭВМ................................................................................ 8 ЛЕКЦИЯ 2. АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ ................................................................9 2.1. Этапы подготовки и решения задач на компьютере...........................................................9 Комментарии к этапам решения задач на ЭВМ ............................................................................... 9 2.2. Алгоритм и его свойства ....................................................................................................10 Разбор алгоритма Евклида................................................................................................................11 2.3. Способы отображения алгоритмов....................................................................................12 Графы .................................................................................................................................................13 Блок-схемы .........................................................................................................................................13 Псевдокод ...........................................................................................................................................13 ЛЕКЦИЯ 3. ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ И ПРОГРАММ ........................................................ 15 3.1. Методы проектирования. Идеологии проектирования алгоритмов.................................15 3.2. Базовые управляющие структуры......................................................................................16 Структура следования ......................................................................................................................16 Структура выбора (развилка)...........................................................................................................17 Структура повторения (цикла) ........................................................................................................18 3.3. Средства для создания приложений ..................................................................................20 Классификация языков программирования .......................................................................................20 Процесс создания приложения ..........................................................................................................21 Состав сред программирования........................................................................................................21 ЛЕКЦИЯ 4. ЛЕКСИКА ЯЗЫКА C++. ТИПЫ ДАННЫХ. СТРУКТУРА ПРОГРАММЫ........................... 23 4.1. Краткая история языка .......................................................................................................23 4.2. Лексика языка C++ .............................................................................................................24 Идентификаторы..............................................................................................................................24 Литералы ...........................................................................................................................................25 Операторы .........................................................................................................................................25 Комментарии .....................................................................................................................................25 Директивы препроцессора.................................................................................................................25 4.3. Типы данных. Переменные и константы...........................................................................26 Обзор типов данных ..........................................................................................................................26 Фундаментальные типы и литералы................................................................................................27 4.4. Объявление переменных и констант .................................................................................30 Чистые объявления, определения и инициализация объектов..........................................................30 4.5. Инструкции консольного ввода и вывода .........................................................................31 Консольный ввод в стиле языка C .....................................................................................................32 Консольный вывод в стиле языка C...................................................................................................33 4.6. Инструкция присваивания...................................................................................34 4.7. Структура программы и процесс создания программы....................................................34 ЛЕКЦИЯ 5. ВЫРАЖЕНИЯ. РЕАЛИЗАЦИЯ БАЗОВЫХ УПРАВЛЯЮЩИХ СТРУКТУР В C++............... 40 5.1. Выражения..........................................................................................................................40 Операторы .........................................................................................................................................41 Правила применения операторов ......................................................................................................43 Обзор некоторых операторов...........................................................................................................44 Часто используемые стандартные арифметические функции.......................................................46 5.2. Базовые управляющие структуры в C++...........................................................................46 Реализация структуры следования ...................................................................................................46 Реализация структур выбора............................................................................................................47 Развилка с множественным выбором...............................................................................................48 Реализация структур повторения ....................................................................................................49 Инструкция цикла с постусловием....................................................................................................52 ЛЕКЦИЯ 6. МАССИВЫ В C++. МАССИВЫ И УКАЗАТЕЛИ ............................................................. 54 6.1. Понятие о массивах............................................................................................................54 Причины использования массивов .....................................................................................................54 Определение массива .........................................................................................................................54 Особенности массивов.......................................................................................................................55 6.2. Объявление и использование массивов в C++ ..................................................................56 Объявление массивов..........................................................................................................................56 Обращение к данным массивов..........................................................................................................57 Пример программы ............................................................................................................................59 6.3. Понятие об указателях .......................................................................................................59 Адресация данных в оперативной памяти........................................................................................60 Доступ к данным через указатели ....................................................................................................60 Области использования указателей ..................................................................................................61 Объявление указателей ......................................................................................................................61 Элементарные действия с указателями...........................................................................................61 6.4. Связь указателей и массивов..............................................................................................62 6.5. Динамические массивы......................................................................................................63 ЛЕКЦИЯ 7. ФУНКЦИИ В С++........................................................................................................ 65 7.1. Понятие о подпрограммах..................................................................................................65 7.2. Локальные и глобальные переменные. Область видимости.............................................66 7.3. Создание функций в С++ ...................................................................................................68 7.4. Аргументы функций...........................................................................................................71 7.5. Возврат результата из функции .........................................................................................72 7.6. Функции и массивы............................................................................................................75 ЛЕКЦИЯ 8. РАБОТА СО СТРОКОВЫМИ ДАННЫМИ. C-СТРОКИ (ДОПОЛНИТЕЛЬНАЯ ТЕМА) ... 79 ЛЕКЦИЯ 9. ФАЙЛОВЫЙ ВВОД-ВЫВОД (ДОПОЛНИТЕЛЬНАЯ ТЕМА)............................................ 87 9.1. Общие сведения о файлах ..................................................................................................87 9.2. Общая процедура работы с файлами. Типы файлов в языке C/С++ ................................88 9.3. Файловый ввод/вывод в стиле языка C .............................................................................90 Открытие файла ...............................................................................................................................90 Закрытие файла.................................................................................................................................91 Ввод и вывод в бинарных файлах.......................................................................................................91 Ввод и вывод в текстовых файлах ....................................................................................................93 Пример................................................................................................................................................95 9.4. Файловый ввод/вывод в стиле языка C++ .........................................................................98 ЛЕКЦИЯ 10. СТРУКТУРЫ (ДОПОЛНИТЕЛЬНАЯ ТЕМА).................................................................100 10.1. Объявление типа структуры...........................................................................................100 ЛЕКЦИЯ 11. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ (ДОПОЛНИТЕЛЬНАЯ ТЕМА) ....................105 11.1. Общие сведения о динамических структурах данных, их виды...................................105 Классификация динамических структур данных ...........................................................................106 11.2. Связные списки...............................................................................................................106 СПИСОК ЛИТЕРАТУРЫ .................................................................................................................112 Основная литература...............................................................................................................112 Дополнительная литература ...................................................................................................112 Интернет-ресурсы: ..................................................................................................................112 ЛЕКЦИЯ 1. ИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ ОСНОВЫ РАБОТЫ ЭВМ Для того, чтобы решить задачу на ЭВМ необходимо:  Представить алгоритм решения задачи в виде совокупности команд для ЭВМ (т.е. составить программу вычислений на языке, понятном ЭВМ),  Выполнить заданную последовательность команд (т.е. выполнить программу),  Представить полученные результаты работы ЭВМ в виде понятном человеку. 1.1. Системы счисления и формы представления чисел Информация в ЭВМ кодируется, как правило, в двоичной или в двоично-десятичной системе счисления. Система счисления - это способ наименования и изображения чисел с помощью символов, имеющих определенные количественные значения. В зависимости от способа изображения чисел системы счисления делятся на позиционные и непозиционные. В позиционной системе счисления количественное значение каждой цифры зависит от ее места (позиции) в числе. В непозиционной системе счисления цифры могут не менять своего количественного значения при изменении их расположения в числе. Практически при любых математических вычислениях, а также для представления информации в вычислительных системах используются только позиционные системы счисления. Количество (Р) различных символов (цифр), используемых для изображения числа в позиционной системе счисления, называется основанием системы счисления. Пример 1.1 Позиционная система счисления - арабская десятичная система, в которой основание Р=10, для изображения чисел используются 10 цифр (от 0 до 9) Непозиционная система счисления римская, в которой для каждого числа используется специфическое сочетание символов (XIV, CXXVII и т.п.) Значения цифр лежат в пределах от 0 до (Р1). В общем случае запись любого смешанного числа в системе счисления с основанием Р будет представлять собой ряд вида: (1) X  am 1 P m 1  am  2 P m  2    a1P1  a0 P 0  a1P 1  a 2 P 2    a s P  s , где нижние индексы определяют местоположение цифры в числе (разряд):  положительные значения индексов - для целой части числа (т разрядов);  отрицательные значения - для дробной (s разрядов). Максимальное целое число, которое может быть представлено в т разрядах: N max  P m  1 Минимальное значащее (не равное 0) число, которое можно записать в s разрядах дробной части: N min  P  s Имея в целой части числа т, а в дробной s разрядов, можно записать всего P ms разных чисел. Двоичная система счисления имеет основание Р=2 и использует для представления информации всего две цифры; 0 и 1. Легкость аппаратной реализации (на различного рода ключах, транзисторах, реле и т.п.) представления двоичного разряда обусловила тот факт, что данная система счисления является базовой для представления информации в любых электронно-вычислительных системах. Также двоичная система является базовой в алгебре логики, где значениям 0 и 1 сопоставлены понятия «ложь» и «истина». Восьмеричная система счисления с основанием Р=8 имеет 8 цифр, от 0 до 7, для представления чисел. Для отображения больших чисел в восьмеричной системе необходимо использовать в три раза меньше разрядов, чем в двоичной системе. Поэтому восьмеричная система в основном использовалась для более компактной записи чисел, изначально представленных в двоичной форме, для расчетов на ЭВМ (например, в текстах программ). В настоящее время используется достаточно редко, так как для современных ЭВМ и программистов более удобной оказалась шестнадцатеричная система счисления. В шестнадцатеричной системе счисления основание равно 16, а для отображения чисел используются десять цифр от 0 до 9 и шесть первых букв латинского алфавита от A до F. Основное назначение данной системы то же, что и для восьмеричной; система очень широко используется для представления числовой информации при разработке вычислительных алгоритмов и программ для ЭВМ. Существуют правила перевода чисел из одной системы счисления в другую, основанные в том числе и на соотношении (1). Арифметические действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими многочленами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые соответствуют данному основанию P системы счисления. Можно выделить три способа перевода чисел из одной системы счисления в другую, каждый из которых удобен в конкретной ситуации. Рассмотрим их на примере преобразования чисел с дробной частью; для целых чисел, очевидно, преобразование выполняется аналогично, дробная часть равна нулю. 1) Преобразование из системы счисления с основанием P в десятичную систему счисления – X(P)  X(10). Используется соотношение (1). Необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер 1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления. Пример 1.2. Перевод дробного числа из двоичной системы счисления в десятичную систему. 101110, 101( 2 )  1  25  0  24  1 23  1  2 2  1  21  0  20  1 2 1  0  2 2  1  2 3  46.625(10) , т.е. двоичное число 101110.101, равное десятичному числу 46,625. 2) Преобразование числа из двоичной системы счисления в систему счисления, основанием которой является степень двойки  X ( 2)  X ( 2m ) , где m>1. Для этого достаточно объединить цифры двоичного числа в группы по m цифр. В целой части группировка производится справа налево, в дробной — слева направо. Если в последней группе недостает цифр, дописываются нули: в целой части — слева, в дробной — справа. Затем каждая группа заменяется соответствующей цифрой новой системы в соответствии с табл. 1.1. Табл. 1.1. Таблица соответствий чисел в различных системах счисления 2 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Р 16 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 4 1 2 3 8 9 A B C D E F Пример 1.3. Переведем из двоичной системы в шестнадцатеричную число 1111010101,11(2). 0011 1101 0101 , 1100(2) = 3D5,C(16). 3) Преобразование числа из десятичной системы счисления в систему с основанием P>1. Целая часть числа делится на P, после чего запоминается остаток от деления. Полученное частное вновь делится на P, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P выписываются в порядке, обратном их получению. Дробная часть умножается на P, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на P и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Если дробь является периодической, умножение обрывается на каком-либо шаге, и исходное числе записывается приближенно в системе с основанием P. Рассмотрим два примера перевода числа из десятичной системы счисления в двоичную. Пример 1.4. Возьмём десятичное число 12410 и поделим его на основание двоичной системы, то есть число 2. Деление будем производить по схеме на рис. 1.1. Рис. 1.1. Перевод числа 12410 в двоичную систему. В результате первого деления получим разряд единиц (самый младший разряд). В результате второго деления получим разряд двоек. Деление продолжаем, пока результат деления больше двух. В конце операции преобразования мы получили двоичное число 11111002. Пример 1.5. Перевести число 380,1875(10) из десятичной системы счисления в двоичную. Рис. 1.2. Перевод числа 380,1875(10) в двоичную систему. В результате получается двоичное число 101111100,0011(2). 1.2. Варианты представления информации в ПК Вся информация (данные) представлена в виде двоичных кодов. Для удобства работы введены следующие термины, обозначающие совокупности двоичных разрядов (табл. 1.2). Эти термины обычно используются в качестве единиц измерения объемов информации, хранимой или обрабатываемой в ЭВМ. Табл. 1.2. Двоичные совокупности Количество двоичных разрядов в группе 1 8 16 81024 810242 810243 810244 Наименование единицы измерения Бит Байт Параграф Килобайт (Кбайт) Мегабайт (Мбайт) Гигабайт (Гбайт) Терабайт (Тбайт) Представление дробных чисел в ЭВМ В вычислительных машинах применяются различные формы представления двоичных чисел: форма с фиксированной запятой; форма с плавающей запятой. Представление чисел в двоичном коде с фиксированной запятой Кроме целых чисел часто требуется работать с дробными числами. В данном варианте представления чисел используется определенное число двоичных разрядов. При этом распределение разрядов между целой и дробной частями остается неизменным для любых чисел, т.е. положение дробной запятой фиксируется. Например, можно принять, что дробная точка находится точно посередине переменной, и тогда мы сможем записывать смешанные числа: В современных ЭВМ режим работы с преимущественно для представления целых чисел. фиксированной точкой используется Представление чисел в двоичном коде с плавающей запятой Часто приходится обрабатывать очень большие числа (например, расстояние между звёздами) или наоборот очень маленькие числа (например, размеры атомов или электронов). При таких вычислениях пришлось бы использовать числа с очень большой разрядностью. В то же время нам не нужно знать расстояние между звёздами с точностью до миллиметра. Для вычислений с такими величинами числа с фиксированной запятой неэффективны. В десятичной арифметике для записи таких чисел используется алгебраическая форма. При этом число записывается в виде мантиссы, умноженной на 10 в степени, отображающей порядок числа (показатель). Например: 0,2105; 0,1610-38. Для записи двоичных чисел тоже используется такая форма записи. Эта форма записи называется запись числа с плавающей точкой. Напомним, что мантисса не может быть больше единицы и после запятой в мантиссе не может записываться ноль. Разработаны промышленные стандарты, используемые для представления чисел в компьютерах. Существует стандарт IEEE 754 для представления чисел с одинарной точностью (float) и с двойной точностью (double). Для записи числа в формате с плавающей запятой одинарной точности требуется тридцатидвухбитовое слово. Для записи чисел с двойной точностью требуется шестидесятичетырёхбитовое слово. Чаще всего числа хранятся в нескольких соседних ячейках памяти процессора. Форматы числа в формате с плавающей запятой одинарной точности и числа в формате с плавающей запятой удвоенной точности приведены на рисунке: Рис. 1.3.Форматы чисел с плавающей точкой одинарной и двойной точности. На рисунке буквой S обозначен знак числа, 0 - это положительное число, 1 - отрицательное число. e обозначает смещённый порядок числа. Смещение требуется, чтобы не вводить в число еще один знак. Смещённый порядок всегда положительное число. Для одинарной точности для порядка выделено восемь бит. Для смещённого порядка двойной точности отводится 11 бит. Для одинарной точности смещение принято 127, а для двойной точности - 1023. В десятичной мантиссе после запятой могут присутствовать цифры 1:9, а в двоичной - только 1. Поэтому для хранения единицы после двоичной запятой не выделяется отдельный бит в числе с плавающей запятой. Единица подразумевается, как и двоичная запятая. Кроме того, в формате чисел с плавающей запятой принято, что мантисса всегда больше 1. То есть диапазон значений мантиссы лежит в диапазоне от 1 до 2 Представление символьной информации в ЭВМ Значением символьной переменной является один символ из фиксированного набора. Такой набор обычно включает буквы, цифры, знаки препинания, знаки математических операций и различные специальные символы (процент, амперсанд, звездочка, косая черта и др.). Подчеркнем, что, в отличие от строковой переменной, символьная всегда содержит ровно один символ. (Строковая содержит строку из нескольких символов.) Очевидно, в памяти компьютера никаких символов не содержится. Символы представляются их целочисленными кодами в некоторой фиксированной кодировке. Рассмотрим две основные из них. Код ASCII (American Standard Code for Information Interchange  Американский стандартный код для обмена информацией) имеет основной стандарт и его расширение. Изначально в системе ASCII для кодирования каждого символа использовалось 7 бит, а её таблица символов содержала 128 позиций (из которых 32 были отведены под управляющие последовательности, а собственно под символы было отведено, соответственно, 96). Среди этих 96 позиций 52 были уже забронированы за заглавными и строчными буквами английского алфавита, 10 - за арабскими цифрами, прочие - за различными знаками препинания и специальными символами. Позже систему кодирования ASCII пересмотрели, и для кодирования каждого символа стали использовать не 7, а 8 бит (этот 8-й бит существовал и ранее, но использовался не для представления данных, а для осуществления контроля чётности). Объём таблицы символов возрос до 256 позиций, что позволило дополнить таблицу символами национальных языков (например, кириллицы), а также символами псевдографики. /Посмотреть таблицу ASCII кодов/ Недостаток «мест» в таблице символов вынуждал создавать наборы таблиц символов для различных языков, между которыми следовало переключаться при переходе с одного языка на другой. Для восточных языков, использующих иероглифы, использование кодировки ASCII являлось практически неприемлемым. Поэтому американские корпорации IBM и Xerox ещё в первой половине 1980-х начали работу над созданием новой "многоязычной" системы кодирования. Был создан межнациональный консорциум под названием Unicod, в результате работы которого был разработан одноименный вариант кодировки. Unicode. Способ кодирования символов, в котором для представления символов используются двоичные последовательности длиною в 16 бит (2 байта), а также единая большая таблица символов объёмом в 65536 позиций. Кодировка Unicode включает символы алфавитов всех европейских стран и кириллицу. К сожалению, большинство существующих компьютерных программ приспособлено к представлению одного символа в виде одного байта. Поэтому в настоящее время часто используется промежуточное решение: компьютерные программы работают с внутренним представлением символов в кодировке Unicode (такое решение принято в языках Java и C#). При записи в файл символы Unicode приводятся к однобайтовой кодировке в соответствии с текущей языковой установкой. При этом, конечно, часть символов теряется - например, в кодировке Windows невозможно одновременно записать русские буквы и немецкие умлауты, поскольку умлауты в западно-европейской кодировке имеют те же коды, что и русские буквы в русской кодировке. Даже во время разработки стандарта Unicode было ясно, что предоставляемого количества позиций не хватает для более менее полного представления символов всех широко используемых национальных языков, т.к., например, только японский язык насчитывает около 65000 иероглифов. ЛЕКЦИЯ 2. АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ 2.1. Этапы подготовки и решения задач на компьютере Решение задач на компьютере включает в себя следующие основные этапы, часть из которых осуществляется без участия компьютера. 1. Постановка задачи:  сбор информации о задаче;  формулировка условия задачи;  определение конечных целей решения задачи;  определение входных и выходных данных, их типов. 2. Математическое описание задачи:  анализ существующих аналогов задачи;  анализ технических и программных средств;  разработка математической модели;  разработка структур данных. 3. Разработка алгоритма:  выбор метода проектирования алгоритма;  выбор формы записи алгоритма (блок-схемы, псевдокод и др.);  проектирование алгоритма. 4. Программирование:  выбор языка программирования;  уточнение способов организации данных;  запись алгоритма на выбранном языке программирования. 5. Тестирование и отладка:  синтаксическая отладка;  отладка логической структуры программы; 6. Тестовое решение задачи и анализ результатов решения  выбор тестовых примеров;  многократное решение задачи на ЭВМ для различных наборов исходных данных (на разных тестовых примерах).  анализ полученных результатов специалистом или пользователем, поставившим задачу. 7. Сопровождение программы:  составление документации к решенной задаче, к математической модели, к алгоритму, к программе; составление инструкции пользователя. Комментарии к этапам решения задач на ЭВМ Этап 1. Постановка задачи осуществляется заказчиком или потребителем результатов решения задачи совместно с исполнителем (вычислителем). Для постановки задачи, как правило, требуется знание той предметной области, к которой относится решаемая задача. Поэтому участие специалиста в данной области (им чаще всего бывает сам заказчик) в постановке задачи обязательно. Этап 2. Важнейшей частью данного этапа является разработка математической модели исследуемого явления, объекта или процесса. Математическая модель (ММ) – совокупность математических формул, уравнений, неравенств и т. д., описывающих соотношения между величинами, определяющими результат. Формирование ММ выполняется специалистом в данной предметной области. ММ должна удовлетворять по крайней мере двум требованиям: реалистичности и реализуемости. Под реалистичностью понимается правильное отражение моделью наиболее существенных черт исследуемого явления. Реализуемость достигается разумным упрощением ММ за счет исключения из рассмотрения второстепенных факторов, использования приближенных соотношений. Условием реализуемости является возможность выполнения необходимых вычислений за отведенное время при доступных затратах требуемых ресурсов. Пояснение. Объекты, процессы, особенно реальные, весьма сложны и связаны многими связями с окружающей средой и другими объектами и процессами. Учесть все в одной модели практически невозможно. Поэтому в целях ускорения и облегчения работ используются упрощенные модели, где исключены из рассмотрения не первостепенные факторы, упрощены взаимодействия и т.д., но так, чтобы сохранились исследуемые свойства и характеристики объекта. Вычислительные задачи, особенно сложные, требуют выбора подходящих методов их решения. При обосновании выбора метода необходимо учитывать различные факторы и условия, в том числе точность вычислений, время решения задачи на ЭВМ, требуемый объем памяти и другие. Решение любой более или менее сложной задачи предполагает и требует деления на этапы. Поэтапное решение задачи, в свою очередь, требует выполнения этапов в определенной последовательности. Процесс составления (определения) последовательности этапов решения задачи называется алгоритмизацией, а сам план действий по решению задачи  алгоритмом. Степень детализации алгоритма на разных этапах его реализации может быть различной. Если задача должна выполняться на ЭВМ, то необходимо точное, формальное описание соответствующих алгоритмов. Тогда применяются, как правило, специальные алгоритмические языки или графические формы изображения для представления алгоритмов. В общем случае алгоритм описывает последовательность действий для решения некоторого класса прикладных задач. 2.2. Алгоритм и его свойства Алгоритм  некоторая конечная совокупность предписаний (указаний, инструкций), задающая последовательность выполнения операций при решении той или иной задачи. Алгоритмы имеют шесть важных особенностей (свойств): 1. Конечность. Алгоритм всегда должен завершаться после конечного числа шагов. При этом число шагов может оказаться сколь угодно большим. 2. Определенность (детерминированность). Каждый шаг алгоритма должен быть точно определен. Действия, которые необходимо произвести, должны быть строго и недвусмысленно определены в каждом возможном случае. Если на каком-то шаге результат не может быть получен, необходимо указать, что считать результатом (промежуточным) в этом случае. 3. Наличие входных данных. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т. е. величин, заданных ему до начала работы. 4. Наличие выходных данных. Алгоритм имеет некоторое количество выходных величин, т. е. величин, имеющих вполне определенные отношения к входным данным. 5. Эффективность. От алгоритма обычно требуется также, чтобы он был эффективным. Это означает, что все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми – закон получения величин на каждом шаге должен быть простым и локальным. Если речь идет об алгоритмах, ориентированных на ЭВМ, то говорят о двух составляющих эффективности: память (или пространство) и время. Пространственная эффективность измеряется количеством памяти, требуемой для выполнения программы. Компьютеры обладают ограниченным объемом памяти. Если две программы реализуют идентичные функции, то та, которая использует меньший объем памяти, характеризуется большей пространственной эффективностью. Иногда память становится доминирующим фактором в оценке эффективности программ. Однако в последний годы в связи с быстрым ее удешевлением эта составляющая эффективности постепенно теряет свое значение. Временная эффективность программы определяется временем, необходимым для ее выполнения. Свойство эффективности является относительной характеристикой алгоритма. 6. Массовость. Алгоритм решения задачи разрабатывается в таком виде, чтобы он мог быть применим для некоторого класса задач, различающихся лишь исходными данными. Разбор алгоритма Евклида Алгоритм Евклида  это алгоритм для нахождения наибольшего общего делителя двух целых чисел. Пусть даны два целых положительных числа m и n, причем n0. Требуется найти их наибольший общий делитель, т. е. наибольшее положительное целое число, которое нацело делит как m, так и n. Алгоритм Е. Начало. Е1. [нахождение остатка] Разделим m на n. Пусть остаток равен r. (Имеем 0  r  n.) Е2. [это нуль?] Если r = 0, алгоритм кончается; n  искомое число. Конец. ЕЗ. [замена] Положим m := n; n := r и возвратимся к шагу Е1. Каждый шаг алгоритма начинается с фразы, взятой в квадратные скобки, которая как можно короче резюмирует суть этого шага. Эта фраза обычно пишется также в сопровождающей алгоритм блок-схеме (см. рис. 2.1), так чтобы без особого труда представить себе алгоритм, о котором идет речь. Начало E1. Нахождение остатка Е2. Это нуль? нет E2. Замена да Конец Рис. 2.1. Блок-схема алгоритма Евклида После фразы в [] следует описание словами и символами тех действий, которые должны быть выполнены, или тех решений, которые должны быть приняты. Иногда встречаются заключенные в круглые скобки комментарии (например, второе предложение в шаге Е1), которые являются дополнительной информацией об этом шаге. 1) Обозначение := на шаге ЕЗ — это очень важная операция присваивания. Выражение «m:= n» означает, что значение переменной т должно быть заменено текущим значением переменной n. Специальное обозначение (:=) используется для того, чтобы отличать операцию присваивания от операции сравнения на равенство (=). При описании алгоритмов мы не скажем: "Положим m = n", но, возможно, спросим: "m = n?" Знак "=" означает условие, которое можно проверить, знак ":=" означает действие, которое можно произвести. Операция увеличения n на 1 обозначается так: "n := n + 1" (читается "n заменить на n+1"). В общем случае запись "переменная := Формула" означает, что по данной Формуле должны быть произведены вычисления при текущих значениях входящих в нее переменных, и полученным результатом надо заменить предыдущее значение переменной, стоящей слева от символа ":=". Следует обратить внимание на порядок действий в шаге ЕЗ. Операция "Положим m := n, n := r" совершенно отлична от операции "положите n := r, m := n": в последнем случае предыдущее значение величины n было бы утрачено прежде, чем его можно использовать для замещения m. Таким образом, фактически последняя операция эквивалентна такой: "положим n := r, m := r". Рассмотрим алгоритм Е на численном примере. Предположим, что m = 119, n =544. Шаг Е1. Деление нацело m на n дает нуль, остаток от деления 119, т.о. r := 119. Шаг Е2. Поскольку r  0, выполняется переход к шагу Е3. Шаг ЕЗ. Полагаем m := 544, n := 119. Переходим к шагу Е1. 544 68 Шаг Е1. Так как 4 , то полагаем r := 68. 119 119 Шаг Е2. Т.к. r  0, выполняется переход к шагу Е3. Шаг ЕЗ. Полагаем m := 119, n := 68. Переходим к шагу Е1. Последующие итерации (однократные выполнения) цикла дают нам: r := 51, m := 68, n := 51; r := 17, m := 51, n := 17. И наконец, когда 51 разделено на 17, r := 0. Таким образом, данный алгоритм завершается на шаге Е2. Наибольший общий делитель чисел 119 и 544 равен 17. Проверим, обладает ли данный алгоритм всеми свойствами алгоритма. Конечность. Алгоритм Е. удовлетворяет этому условию, т.к. после шага Е1 значение r меньше, чем n. Поэтому, если r  0, то значение n уменьшится к следующему выполнению шага Е1. Убывающая последовательность положительных целых чисел должна в конце концов завершиться, поэтому шаг Е1 выполняется только конечное число раз для любого заданного первоначального значения n. Определенность. Каждый шаг алгоритма точно определен. Действия, которые необходимо произвести, строго и недвусмысленно определены в каждом возможном случае. Поэтому требование определенности означает, что, когда бы ни выполнялся шаг Е1, мы должны быть уверены, что m и n всегда будут положительными целыми числами. По предположению это верно в начальный момент, и после шага E1 r будет неотрицательным целым числом, которое не должно быть равным нулю, когда мы достигаем шага ЕЗ, таким образом, как и требуется, m и n — действительно положительные целые числа. Ввод. Алгоритм имеет две входные величины, заданные ему до начала работы. В алгоритме Е. входные величины, а именно m и n, выбираются из множества натуральных чисел. Вывод. Алгоритм Е. имеет одну выходную величину, а именно то значение n в шаге Е2, которое является наибольшим общим делителем двух входных величин. Эффективность. Все операции, которые необходимо произвести в алгоритме, являются достаточно простыми, чтобы их в принципе можно выполнить точно и за конечный отрезок времени с помощью карандаша и бумаги. Таким образом, приведенный выше алгоритм Евклида обладает всеми характерными свойствами алгоритмов. 2.3. Способы отображения алгоритмов Для отображения алгоритмов используется текстовое представление в форме псевдокода либо алгоритмических языков или графическое представление в виде блок-схем или графов. Достоинством графических способов представления А. является бóльшая наглядность, нежели у текстовых способов, а недостатками – меньшая компактность при равной степени детализации А. и относительная сложность перехода к языкам программирования на ЭВМ. Графы Граф – совокупность вершин (узлов) и связывающих их ребер (ветвей). Ими широко пользуются для получения структурных математических моделей на различных уровнях проектирования. Пример 2.1. Вычисление результата по формуле. Необходимо составить алгоритм вычисления результата по формуле Z = (xy)(x+y). + Ввод Х Начало * Ввод Y  Вывод Z Конец + Рис. 2.2. Граф алгоритма вычисления Блок-схемы Блок-схема представляет собой графическое представление А. с помощью совокупности условных графических обозначений. Элементы блок-схемы соединяются между собой линиями потока (линиями связи). Каждая линия потока соединяет два блока и направлена в одну сторону. Обозначения элементов блок-схем: Начало, конец А (1 вход или 1 выход). Инструкция вычисления, элемент структуры следования (1 вх. и 1 вых.) Инструкция ввода данных (1 вх. и 1 вых.) Проверка условия в инструкциях выбора, цикла (1 вх. и 2 вых.) Проверка значения выражения (переменной) (1 вх. и несколько вых.) Инструкция вывода данных (1 вх. и 1 вых.) Разрыв линии связи, соединитель между страницами блок-схемы (1 вх. или 1 вых.) Линия связи Соединение линий связи имеет вид Псевдокод Псевдокод – это специальный неформальный язык для записи алгоритмов. Он занимает промежуточное положение между языками программирования на ЭВМ и естественными («человеческими») языками. Хотя псевдокод определен как неформальный язык, тем не менее в нем используются некоторые правила, а также имеются некоторые конструкции, присущие формальным языкам. Так, например, выражения (формулы) в алгоритмах записываются по правилам, принятым в языках программирования. Записи алгоритмов на псевдокоде позволяют легко перейти на любой язык программирования. Элементы псевдокода (ключевые слова): Начало – начало алгоритма (А.), вход в А. Конец – конец работы А. (выход из А.) Описания переменных: Вещ – объявление переменной вещественного типа; Цел - объявление переменной целого типа; Симв – объявление переменной символьного типа Лог - объявление переменной логического типа; Синтаксис: Тип Имя переменной 1<, Имя переменной 2, …> То, что указано в < >, необязательно Присваивание результата выражения переменной. Синтаксис: Имя переменной := Математическое выражение. Ввод – ввод переменных (исходных данных) Вывод – вывод переменных (результатов вычислений) Инструкция выбора (единственный выбор): Если условие То Список инструкций Все-если Инструкция выбора (двойной выбор): Если условие То Список инструкций 1 Иначе Список инструкций 2 Все-если Инструкция повторения (с предусловием) Цикл пока условие Список инструкций Все-цикл Инструкция повторения (управляемая счетчиком) Цикл для имя переменной от нач. значение до кон. значение <шаг вел. шага> Список инструкций Все-цикл ЛЕКЦИЯ 3. ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ И ПРОГРАММ 3.1. Методы проектирования. Идеологии проектирования алгоритмов Существует два основных метода проектирования алгоритмов:  метод нисходящего проектирования (пошаговая детализация);  метод восходящего проектирования. Под нисходящим проектированием алгоритмов ("сверху вниз") понимается такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций. Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так далее до уровня команд исполнителя А. Восходящий метод, наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи (метод "снизу вверх"). На практике «чистую» нисходящую разработку осуществить практически невозможно, так как выбор более конкретизированных элементов на каждой стадии должен производиться на основе представления и понимания возможностей языка реализации. Восходящая разработка в чистом виде также практически неприменима; построение каждого нового элемента должно сопровождаться «просмотром вперед» с целью проверки, выполняются ли все требования, предъявляемые к разрабатываемой программе. Но даже при таком подходе на более позднем этапе часто обнаруживается, что использованная ранее последовательность построения была выбрана неправильно и требует корректировки. В чистом виде каждый из методов используется достаточно редко. На практике при разработке алгоритмов обычно используется сочетание методов нисходящего и восходящего проектирования. Развитие технологий проектирования алгоритмов и программирования стимулировалось необходимостью создавать все более сложные программы, сохраняя при этом приемлемые сроки проектирования и надежность создаваемых программ. Можно выделить несколько существующих в настоящее время идеологий проектирования алгоритмов и программирования:  структурное проектирование;  процедурное проектирование;  модульное проектирование;  объектно-ориентированное проектирование;  компонентно-ориентированное проектирование. Порядок перечисления неслучаен: он отражает последовательность развитие идеологий и связан с тем, что каждая концепция является базой и неотъемлемой частью последующей концепции. Структурное проектирование подразумевает, что алгоритм формируется из базовых структурных алгоритмических единиц, или управляющих структур (следование, ветвление, повторение), используя их последовательное соединение и/или вложение друг в друга по определённым правилам, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно. Структурированный алгоритм – это алгоритм, представленный как следования и вложения базовых алгоритмических структур. У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз ("как читается, так и исполняется"). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения. Структурный подход к программированию предусматривает  декомпозицию сложной задачи на взаимодействующие простые части;  составление программ последовательно уточняющими шагами (метод нисходящего проектирования);  логика взаимодействий в программе должна опираться на минимальное число простых базовых управляющих структур; для проявления логики программы и выделения её структур следует использовать отступы в тексте программы (2-4 пробела); имена всех объектов программы должны быть мнемоническими, т.е. иметь смысловую нагрузку; оформление наиболее сложных мест в программе комментариями. Процедурное проектирование подразумевает использование подпрограмм, каждая из которых выполняет некоторую локальную, четко формулируемую подзадачу. Проектирование алгоритмов (программ) упрощается, т.к. становится возможным повторное использование подпрограмм, улучшается структурированность сложных программ. Модульный подход базируется на использовании модулей, позволяющих группировать в них данные и методы их обработки (подпрограммы), а также скрывать «ненужные» особенности хранения данных в модулях. Использование модулей обосновано необходимостью создания все более сложных программ. Дальнейшее усложнение алгоритмов привело к разработке объектно-ориентированного подхода. В отличие от структурного и процедурного проектирования, где алгоритм детализировался на структурные элементы – подалгоритмы (подпрограммы), выполняющие какие-то подзадачи, ООП строится на объектной декомпозиции предметной области – основными элементами программы становятся виды абстракций (классы) и представители этих классов (объекты). В соответствии с алгоритмической декомпозицией предметной области мы при анализе задачи пытаемся понять, какие алгоритмы необходимо разработать для ее решения, каковы спецификации этих алгоритмов (вход, выход), и как эти алгоритмы связаны друг с другом. В языках программирования данный подход в полной мере поддерживается средствами модульного программирования (библиотеки, модули, подпрограммы). Объектно-ориентированная технология разработки программных продуктов объединяет данные и процессы в логические сущности  объекты, которые имеют способность наследовать характеристики (методы и данные) одного или более объектов, обеспечивая тем самым повторное использование программного кода. Это приводит к значительному уменьшению затрат на создание программных продуктов, повышает эффективность жизненного цикла программных продуктов (сокращается длительность фазы разработки). При выполнении программы объекту, посылается сообщение, которое инициирует обработку данных объекта. На сегодняшний день объектный подход и его основы - объектная модель и объектная декомпозиция поддерживаются современными объектно-ориентированными языками программирования (Object Pascal, C++, Java, C#…). 3.2. Базовые управляющие структуры Управляющие структуры составляют тот базис структурного программирования, с помощью которого может быть описано управление в любом вычислительном процессе. В теории алгоритмов известна теорема о структурировании, которая утверждает, что любая программа может быть написана с использованием всего трёх типов управляющих структур: следование, выбор (развилка), повторение (цикл). Характерным для всех управляющих конструкций в структурном программировании является то, что они имеют один вход и один выход. Структура следования Структура следования – это управляющая структура по умолчанию. Она встроена во все языки программирования и подразумевает выполнение инструкций последовательно, одной за другой. Псевдокод: Блок-схема: Инструкция 1 Инструкция 2 … Инструкция n Инструкция 1 Инструкция 2 . . . Инструкция n Структура выбора (развилка) Все управляющие структуры выбора позволяют выбирать один из нескольких альтернативных вариантов действий в зависимости от выполнения (или невыполнения) некоторого условия либо в зависимости от значения, которое принимает некоторая переменная (выражение). Структура с единственным выбором В данной управляющей структуре выполняется проверка некоторого условия, и, если это условие истинно, то выполняется список инструкций. В случае, если условие ложно, то список инструкций игнорируется, и выполняется следующая после структуры выбора инструкция (строка псевдокода). Псевдокод: Блок-схема: … Если условие То Список инструкций Все-если … Условие  + Инструкция 1 Инструкция 2 Список инструкций … Инструкция n Структура с двойным выбором Данная структура применяется, когда нужно выбрать один из двух альтернативных вариантов действий в зависимости от выполнения (невыполнения) некоторого условия. Псевдокод: Блок-схема: Если условие То Список инструкций 1 Иначе Список инструкций 2 Все-если  Список инструкций 2 Условие + Список инструкций 1 Структура с множественным выбором Структура с множественным выбором используется, когда необходимо выбрать один из нескольких (как правило, более двух) альтернативных вариантов действий в зависимости от значения, которое принимает некоторая переменная (результат некоторого выражения). / подробнее пока можно не рассказывать / Структура повторения (цикла) В общем случае структура цикла используется, когда некоторая последовательность инструкций должна выполняться несколько (более одного) раз до тех пор, пока остается истинным некоторое условие. Однократное выполнение инструкций, включенных в структуру цикла, называется итерацией цикла. Число итераций цикла может быть известно заранее, а может определяться инструкциями внутри самого цикла. Цикл с предусловием Список инструкций выполняется до тех пор, пока остается истинным условие, проверяемое в начале каждой итерации цикла. Так как любой алгоритм, а следовательно, любая его часть должны обладать свойством конечности, то внутри цикла должны обязательно (!) быть предусмотрены инструкции (входящие в Список инструкций), в определенный момент изменяющие условие с истинного на ложное. Количество итераций цикла обычно неизвестно перед началом цикла. Псевдокод: Блок-схема: Цикл пока условие Список инструкций Все-цикл + Условие  Список инструкций Цикл с постусловием Особенностью цикла с постусловием является то, что, в отличие от цикла с предусловием, количество итераций не может быть равным нулю, т.к. проверка условия завершения (продолжения) цикла выполняется в конце каждой итерации. Блок-схема Список инструкций Условие +  Цикл, управляемый параметром (счетчиком) Если количество итераций цикла известно заранее (например, сохранено в какой-либо переменной), то целесообразно применять данную управляющую структуру. В структуре используется специальная переменная целого типа, называемая счетчиком. Лучше стремиться (хотя это не является обязательным), чтобы переменная, выполняющая роль счетчика, была создана только для этой цели и для хранения других значений не использовалась. Значение счетчика в цикле автоматически изменяется от начального значения до конечного значения с заданным шагом (значение шага по умолчанию равно 1). В тело цикла не рекомендуется включать инструкции, изменяющие значение счетчика. В начале каждой итерации цикла выполняется проверка условия счетчик > конечное значение. Если условие ложно, то цикл прекращается, и начинает выполняться следующая после цикла инструкция. Псевдокод: Блок-схема: Цикл для счетчик от нач. значение до кон. значение <шаг вел. шага> Список инструкций Все-цикл счетчик := нач. значение счетчик  кон. значение   + Список инструкций счетчик := счетчик + шаг Во всех приведенных блок-схемах обозначение список инструкций может включать любое число произвольных инструкций, в числе которых могут быть и структуры выбора и повторения. В таком случае последние называются вложенными структурами. Для всех рассмотренных управляющих структур необходимо рассмотреть примеры. 3.3. Средства для создания приложений Классификация языков программирования Язык программирования  формализованный язык для описания алгоритма решения задачи на компьютере. Средства для создания приложений — совокупность языков и систем программирования, а также различные программные комплексы для отладки и поддержки создаваемых программ. Языки программирования можно условно классифицировать по принципам образования конструкций языка:  языки низкого уровня – языки программирования, привязанные к конкретной  архитектуре вычислительной системы, включают в себя: o машинные языки (computer languages) – языки программирования, воспринимаемые аппаратной частью компьютера (машинные коды); o машинно-ориентированные языки (computer-oriented languages) – языки программирования, которые отражают структуру конкретного типа компьютера (ассемблеры, языки низкого уровня); алгоритмические языки (языки высокого уровня) – не зависящие от архитектуры компьютера языки программирования для отражения структуры алгоритма: o процедурно-ориентированные языки (procedure-oriented languages) – языки программирования, в которых имеется возможность описания программы как совокупности процедур (подпрограмм) (Pascal, C, Basic, Fortran и др.); o проблемно-ориентированные языки (universal programming languages) – языки программирования, предназначенные для решения задач определенного класса (Lisp, РПГ, Simula, Prolog и др.); o объектно-ориентированные языки (object-oriented languages) – языки программирования, в которых используется отображение объектов реального мира, их свойств и связей между ними при помощи специальных типов и структур данных – классов, объектов классов (Object Pascal, C++, C#, Java). Процесс создания приложения Любая программа, подготовленная на языке программирования, проходит этап трансляции, когда происходит преобразование исходного кода программы (source code) в объектный код (object code), который далее пригоден к обработке редактором связей. Редактор связей — специальная программа, обеспечивающая построение загрузочного модуля (load module), пригодного к выполнению (рис. 3.1). Исходный код программы на языке высокого Транслятор (компилятор) Объектный код программы на машинном языке Редактор связей (компоновщик) Исполняемый модуль программы Рис. 3.1. Схема процесса создания исполняемого модуля программы Трансляция может выполняться с использованием средств компиляторов (compiler) или интерпретаторов (interpreter). Компиляторы транслируют всю программу, но без ее выполнения. Интерпретаторы, в отличие от компиляторов, выполняют пооператорную обработку и выполнение программы. Существуют специальные программы, предназначенные для трассировки и анализа выполнения других программ, так называемые отладчики (debugger). Как правило, отладчики позволяют осуществить трассировку (отслеживание выполнения программы в пооператорном варианте), идентификацию места и вида ошибок в программе, контроль изменения значений переменных, результатов выражений и т.п. Состав сред программирования Современная система программирования как правило представляет собой интегрированную среду. Интегрированная среда объединяет в себе возможности текстовых редакторов исходных текстов программ и командный язык компиляции. Среды разработки приложений включают в себя следующие основные компоненты:  текстовый редактор;  транслятор (компилятор/интерпретатор);  отладчик;  средства оптимизации программного кода;      редактор связей (компоновщик); набор стандартных библиотек (возможно, с исходными кодами); сервисные средства (утилиты) для работы с библиотеками, текстовыми и двоичными файлами; средства поддержки и управления проектом программного комплекса. справочная система; Создание интегрированных сред разработки стало возможным благодаря бурному развитию персональных компьютеров и появлению развитых средств интерфейса пользователя (сначала текстовых, а потом и графических). Их появление на рынке определило дальнейшие развитие такого рода технических средств. Пожалуй, первой удачной средой такого рода можно признать интегрированную среду программирования Turbo Pascal на основе языка Pascal производства фирмы Borland. Ее широкая популярность определила тот факт, что со временем все разработчики компиляторов обратились к созданию интегрированных средств разработки для своих продуктов. Развитие интегрированных сред несколько снизило требования к профессиональным навыкам разработчиков исходных программ. Теперь в простейшем случае от разработчика требовалось только знание исходного языка (его синтаксиса и семантики). При создании прикладной программы ее разработчик мог в простейшем случае даже не разбираться в архитектуре целевой вычислительной системы. ЛЕКЦИЯ 4. ЛЕКСИКА ЯЗЫКА C++. ТИПЫ ДАННЫХ. СТРУКТУРА ПРОГРАММЫ Содержание лекции: Краткая история языка Лексика языка C++ Типы данных. Переменные и константы Объявление переменных и констант Инструкции консольного ввода и вывода Инструкция присваивания Структура программы и процесс создания программы 4.1. Краткая история языка Алгоритмический язык объектно-ориентированного программирования C++ – это надмножество алгоритмического языка процедурного и модульного программирования C (правда, с некоторыми незначительными исключениями). Предшественником языку C был алгоритмический язык B, первоначально предназначенный для написания операционной системы UNIX (автор – Кен Томпсон (Ken Tompson), Bell Labs, 1970 г.). Основная цель создания языка B – придумать предельно компактный алгоритмический язык высокого уровня. Как следствие, язык оказался пригодным для решения лишь узкого круга задач (т. к. был привязан к архитектуре ЭВМ). На его основе был разработан алгоритмический язык C (автор – Деннис Ритчи (Dennis Ritchie), Bell Labs, 1972 г.). Главная цель создания языка C – восстановить обобщенность, потерянную в языке B, но при этом по возможности сохранить компактность. В результате получился язык, который позволяет учитывать каждую деталь алгоритма для достижения максимальной производительности ЭВМ и одновременно считается языком высокого уровня, т. к. не является привязанным к особенностям архитектуры конкретной ЭВМ (в отличие от языков низкого уровня). Поскольку язык C первоначально создавался для написания операционных систем, то его часто называют языком системного программирования. Также его иногда называют ассемблерным языком высокого уровня. Язык C++ разработан на основе языка C (автор – Бьерн Страуструп (Bjarne Stroustrup), AT&T, Bell Labs, 1980 г.). Основная цель создания языка C++ – обеспечить поддержку парадигм объектно-ориентированного и обобщенного программирования, сохранив при этом достоинства языка C: компактность и независимость от архитектуры ЭВМ. При этом тексты программ на C могут почти без изменений использоваться внутри текстов программ на C++. Первое официальное описание языка C++ появилось в 1987 г. С этого момента он получает самое широкое распространение в мире при разработке системного и прикладного программного обеспечения. Язык непрерывно развивается. Последний на текущий момент международный стандарт языка C++ принят в августе 1998 г.: ISO/IEC 14882, Standard for the C++ Programming Language. На основе языка C++ разработан язык программирования Java (автор – Патрик Нотон (Patrick Naughton), Sun Microsystems, 1995 г.). Основная цель создания языка Java – обеспечить возможность написания объектно-ориентированных программ, способных выполняться на любой платформе без перекомпиляции. По существу Java – это урезанный вариант C++ с некоторыми важными дополнениями. При этом исходный код программы на Java всегда преобразуется в специальный код – байт-код, который впоследствии на любой платформе интерпретируется при помощи специальной программной прослойки в ОС, называемой виртуальной машиной Java (JVM). Язык начинают повсеместно применять при создании приложений, распространяемых по сети и интенсивно использующих сетевые ресурсы. Если программист знает C++, то программирование на Java не вызовет у него каких-либо значительных затруднений. Программы на языке Java не совместимы с программами на C и C++ ни снизу вверх, ни сверху вниз. На основе языка C++ в качестве альтернативы языку Java позже был также разработан язык C# (авторы – Андерс Хейлсберг (Anders Hejlsberg) и Скотт Вилтамут (Scott Wiltamuth), Microsoft, 2000 г.). Основная цель создания языка C# – обеспечить возможность написания объектно-ориентированных программ, способных выполняться без перекомпиляции на любой платформе, поддерживающей технологию .NET (произносится: «дот-нэт»). В C#, в отличие от Java, достигнута полная интеграция языка с ОС Windows, поддерживающими данную технологию (.NET). Кроме того, в C# обеспечена межъязыковая возможность взаимодействия аппаратных и программных средств разных поставщиков, именуемая в литературе многоязыковым программированием. Также C# содержит встроенные средства для создания программных компонентов. Поэтому его часто называют языком компонентноориентированного программирования. Как и в случае с языком Java, если программист знает C++, то ему будет несложно обучиться программированию на языке C#. Также подобно языку Java программы на языке C# не совместимы с программами на языках C и C++. 4.2. Лексика языка C++ Идентификаторы Идентификатор (или просто имя) – это имя переменной, константы, функции, типа, синоним типа, имя метки или имя константы типа перечисления (enum). Применение идентификатора начинается с разъяснения компилятору его назначения. Это разъяснение называется определением. В соответствии с этим определением идентификатор может применяться только в некоторой части программы. Эта часть называется областью видимости идентификатора. Некоторые правила именования идентификаторов: 1. Идентификатор начинается с буквы и может содержать буквы и цифры (знак подчеркивания считается буквой). 2. Ограничения на длину имени не накладываются, но конкретная реализация может различать лишь конечное число его начальных символов (в Visual C++ компилятор различает только первые 31 символ). 3. Имена, начинающиеся со знака подчеркивания, зарезервированы для нужд реализации (использовать их в программах не следует). 4. Идентификаторы с малой областью видимости должны быть короткими, а с большой – по возможности подробными. Для разделения слов в имени удобно пользоваться знаком подчеркивания. Можно каждое слово в имени начинать с прописной буквы. (Например: MyFirstName, SetNewValue, my_first_name, set_new_value) 5. Стилистическое соглашение между программистами: в начале имени добавляется сокращенное обозначение типа данных (i – int, d – double, p – указатель, sz – C-строка и т. д.). 6. В именах макросов (о них позже) лучше использовать только заглавные буквы. Примеры допустимых идентификаторов: hello DEFINED var0 long_name bAr BAR _class MyVariable foO __ Примеры недопустимых идентификаторов: 012 $sys if .name pay.due n+m A1&A2 Not_Done! Некоторые идентификаторы являются стандартными, например, имя главной функции программы (main). Литералы Литерал – это изображение конкретного значения одного из арифметических типов, либо типа C-строки. Различают литералы: логические, символьные, целые, с плавающей точкой и строковые. Примеры литералов: true 'a' 12345 543.21 "Простая строка на C++!" Операторы Оператор в C++ – это один или несколько подряд идущих специальных символов либо ключевое слово. Он предназначен для выполнения некоторых действий (операций) над данными (операндами), а также для составления выражений. Операторы бывают унарные и бинарные. Унарные операторы бывают префиксные и постфиксные (суффиксные). Важные особенности C++, позволяющие строить гибкие и эффективные выражения: 1. Поддерживается очень много различных операторов. 2. Действие присваивания реализовано в виде оператора =. 3. Для пользовательских типов данных возможно определение своих операций. Примеры выражений на C++: a += 5 + (b = c % 2) a = ((b < c) ? (d = e) : (f = g)) p = &(x++) Комментарии Комментарий – это произвольный текст, поясняющий работу участков программы и не влияющий на ее выполнение. В C++ комментарий включается в программу двумя способами. При первом способе его началом является пара символов «//», а окончанием последний символ строки: // Это комментарий! При втором способе его началом является пара символов «/*», а окончанием – пара символов «*/»: /* Еще один пример комментария! */ Директивы препроцессора Препроцессор – это обработчик макросов1, всегда обрабатывающий тексты файлов программы перед началом компиляции. Все директивы начинаются с символа «шарп» (#), который должен быть первым символом в данной строке. За ним идет зарезервированное слово. Стандартные директивы пре процессора используют следующие зарезервированные слова: if ifdef ifndef elif else endif include define undef line error pragma 1 Макросы - лексемы, созданные с помощью директивы #define, которые могут принимают параметры подобно функциям. Областью применения макросов является замена некоторых небольших (как правило, повторяющихся) конструкций в тексте программы на более наглядное и короткое имя (макрос). При препроцессировании программы выполняется подстановка вместо имени макроса его значения. Примеры простых директив препроцессора: #include #include "myhead.h" #define NAME rest of line Согласно стандарту директивы препроцессора записываются с начала строки. Кроме стандартных реализация может поддерживать дополнительные директивы препроцессора. 4.3. Типы данных. Переменные и константы Важнейшим элементом любой программы являются данные, с которыми работает программа. С некоторой долей условности данные можно разделить на  входные – данные, которые программа получает «извне» (их вводит пользователь, используя различные устройства ввода (клавиатуру, мышь, сканер и др.), они вводятся посредством сетевых интерфейсов (Ethernet, Wi-Fi, Bluetooth и др.), их считывает программа с жесткого диска или flashкарты и т.д.)  промежуточные – данные, получаемые программой во время ее выполнения, которые, в свою очередь, используются самой программой в ее дальнейшей работе;  выходные – данные, которые являются результатом работы программы, формируются в виде, удобном для их непосредственного восприятия пользователем (через устройства вывода: монитор, принтер), либо хранения их в постоянной памяти (на жестком диске и т.д.), либо их обработки в других программах (как правило, обмен данными между разными программами осуществляется через промежуточнное их сохранение все в той же постоянной (дисковой) памяти. Для всех данных, используемых в программе, должен быть задан свой тип. Тип данных определяет множество допустимых значений, набор операций, которые можно применять к таким значениям, и объем памяти, требуемый для одного значения данного типа. Во время выполнения программы те данные, с которыми работает программа, размещаются (хранятся) в оперативной памяти компьютера. В тексте программы данные могут быть представлены в виде переменных, констант и литералов (значений). Переменная – область оперативной памяти, выделенная программе, в которой хранится значение некоторого типа. Значение переменной может изменяться программой во время ее выполнения. У каждой переменной есть собственное имя, по которому выполняется доступ (чтение значения переменной либо запись в нее нового значения) к переменной. Константа – область оперативной памяти, выделенная программе, в которой хранится значение некоторого типа. Значение константы, заданное ей изначально, запрещено изменять. У константы, как и у переменной, есть имя. Литерал – значение некоторого типа, заданное непосредственно в тексте программы. Литерал не имеет имени. Литералы также называют просто значениями или неименованными константами. Переменные и константы часто называют общим термином «объекты». То есть объект – некоторая именованная область памяти, хранящая значение (совокупность значений) некоторого типа. Обзор типов данных Пусть имеется некоторое выражение на C++: x = i + f(2); Выражение будет иметь смысл, если имена (идентификаторы) x, y и f будут подходящим образом объявлены. Каждое имя в программе имеет связанный с ним тип. Тип определяет действия, которые могут быть применены к этому имени. Например, следующие объявления сделают выражение осмысленным: double x; // x – переменная типа с плавающей точкой двойной точности. int i = 7; // i – целочисленная переменная с начальным значением 7. // f – функция с аргументом целого типа, возвращающая значение типа с // плавающей точкой (кроме ее объявления должно быть ее определение). float f(int); В C++ различают три группы типов данных: фундаментальные типы, встроенные типы и типы, определяемые пользователем. Фундаментальные типы делятся на: 1. Логический тип (bool). 2. Символьные типы (char, wchar_t). 3. Целочисленные (целые) типы (например, тип int). 4. Типы с плавающей точкой (например, double). 5. Тип void – используется для указания на отсутствие информации. Логический, символьные и целые типы вместе называются интегральными, и к ним можно применять все арифметические и все логические операции. Интегральные типы вместе с вещественными типами с плавающей точкой называются арифметическими, и к ним применимы все арифметические операции и обычные (непобитовые) логические операции (операции сравнения, операции: «И», «ИЛИ», «НЕ»). Встроенные типы делятся на: 1. Типы указателей (например, int*). 2. Типы ссылок (например, double&). 3. Типы массивов (используются квадратные скобки: []). 4. Типы функций (используются круглые скобки: ()). Типы, определяемые пользователем (пользовательские), делятся на: 1. Типы перечислений (enum) – используются для представления значений из конкретного множества. 2. Типы структур и классы (struct, union, class). Пользовательские типы позволяют формировать на базе фундаментальных и встроенных типов структуры данных (объекты) произвольной сложности. Фундаментальные типы и литералы Краткие сведения о фундаментальных типах сведены в Таблица 4.1. Ниже подробно рассматриваются логический, символьные, целочисленные и вещественные с плавающей точкой типы и их литералы, а также тип void. Таблица 4.1 Наименование типа Логический тип bool Символьные типы char wchar_t Диапазон (множество) значений Описание Объем памяти для хранения значения Примеры литералов Логический тип true, false 1 байт true false Символьный тип в кодировке ANSI (ASCII) Символьный тип в кодировке Unicode 256 символов ANSI 1 байт 65536 Unicode 2 байт 'a' '2' '/n' L'a' L'2' L'/n' Целочисленный (целый) тип int Знаковый целочисленный тип Типы с плавающей точкой (вещественные) float Вещественный тип одинарной символов –2147483648 … 2147483647 4 байт 4 –10729655 0x5FA4 по модулю: 4 байт 3.0 точности double Вещественный тип двойной точности от 1.18e-38 до 3.40e+38 по модулю: от 2.23e-308 до 1.79e+308 Пустой тип void Пустой тип - 8 байт 0.45E–05 –4. 3.0 0.45E–0005 –4. - - Логический тип и его литералы Объекты логического типа (bool) могут принимать одно из двух значений: истина (true) и ложь (false); используются для хранения результатов выполнения логических операций и занимают, как правило, 1 байт. Например: double x = 1.2, y = 2.1; bool b = x == y; // b истинно, если x = y, иначе b ложно. По определению, true имеет значение 1, а false – значение 0 при неявном преобразовании к целому типу. И наоборот, целое число можно неявно преобразовать в логическое значение. При этом ненулевое целое преобразуется в true, а нулевое – в false. Например: bool b = 7; int i = true; // b принимает // i принимает В арифметических и побитовых логических преобразуются в целые типа int. Например: значение true. значение 1. операциях логические операнды bool a = true, b = true; bool c = a + b; // a + b равно 2, поэтому c = true. bool d = a | b; // a | b равно 1 (побитовое ИЛИ), поэтому d = true. Указатель можно неявно преобразовать к типу bool подобно целому числу. Символьные типы и их литералы В объекте типа char может храниться один из символов, имеющихся в наборе символов стандарта ANSI. Например: char sym = 'a'; Практически на любой платформе на объект типа char отводится 1 байт, так что существует 256 различных значений этого типа. Каждому символьному значению соответствует свое целочисленное значение, называемое его кодом. Обычно под кодом понимают беззнаковое целое, но в C++ код символа типа char, как правило, является знаковым целым (меняется в диапазоне от -128 до 127). Можно явно указать диапазон кода, используя при объявлении объектов символьного типа модификаторы знака signed и unsigned: signed char sym1;// Символы со знаковым кодом в диап. от –128 до 127. unsigned char sym2;// Символы с беззнаковым кодом в диап. от 0 до 255. В объекте типа wchar_t может храниться один из символов, имеющихся в наборе символов стандарта Unicode. Практически на любой платформе на объект типа wchar_t отводится 2 байта, так что существует 65536 различных значений этого типа. В остальном он подобен типу char. Символьный литерал для типа char – это символ, заключенный в апострофы. Примеры: 'd', 'Ю' и т. д. Каждому такому литералу соответствует свой уникальный код. Некоторые символы имеют специальное назначение и могут не иметь какого-либо изображения. Они записываются с помощью обратного слеша «\»: '\n' – переход на новую строку; '\r' – возврат на начало строки; '\t' – горизонтальная табуляция; '\a' – звуковой сигнал; '\v' – вертикальная табуляция; '\f' – переход на новую страницу; '\\' – обратный слеш; '\'' – апостроф; '\"' – двойная кавычка; '\0' – ноль, т. е. символ с кодом 0; '\ЦЦЦ' – 8-ричный код любого символа (Ц – 8-ричная цифра); '\xЦЦ' ('\XЦЦ') – 16-ричный код любого символа (Ц – 16-ричная цифра). Символьный литерал для типа wchar_t – это символ, заключенный в апострофы, перед которыми ставится буква L. Примеры: L'd', L'Ю' и т. д. Каждому такому литералу также соответствует свой уникальный код. Целочисленные типы и их литералы Тип char можно считать полноценным целочисленным типом минимального размера (1 байт). Однако настоящим целочисленным типом принято считать тип int (в Visual C++ имеет размер 4 байта). Он является знаковым типом. Как и для типа char, для него применимы модификаторы знака: int i1; // Знаковое целое примерно от –2.15e9 до 2.15e9. signed int i2; // То же, что i1. unsigned int i3; // Беззнаковое целое от 0 до примерно 4.3e9. Также для него применимы модификаторы размера short (в Visual C++ имеет размер 2 байта) и long (в Visual C++ имеет размер также 4 байта): int i1; short int i2; long int i3; // Знаковое целое // То же, что i1. от –32768 до 32767. Вместо short int можно писать просто short, вместо long int – просто long, вместо signed int – просто signed, а вместо unsigned int – просто unsigned. Модификаторы знака и размера могут применяться совместно. Например, в Visual C++ стандартный тип wchar_t объявлен как синоним типа unsigned short (правда, по стандарту wchar_t – это ключевое слово спецификатора типа). Целочисленные литералы бывают трех видов: десятичные, восьмеричные и шестнадцатеричные. Наиболее употребимы десятичные: 0 1234 976 645372810. Литерал, начинающийся с нуля, за которым идут цифры от 0 до 7, является восьмеричным: 00 05 077 0321. Литерал, начинающийся с 0x (0X), за которым идут цифры от 0 до 9 и буквы от a (A) до f (F), является шестнадцатеричным: 0x0 0x20 0x3f 0xD2E. Для явной записи литералов типа longint можно использовать суффикс l (L): 35L. Для явной записи литералов типа unsigned int можно использовать суффикс u (U): 35U. Эти суффиксы можно использовать совместно. Если они отсутствуют, компилятор сам выбирает подходящий тип литерала. Типы с плавающей точкой и их литералы Числа в формате с плавающей точкой могут храниться в объектах одного из трех типов: float (одинарной точности; в Visual C++ имеет размер 4 байта, диапазон по модулю: от 1.18e-38 до 3.40e+38), double (двойной точности; в Visual C++ имеет размер 8 байт, диапазон по модулю: от 2.23e-308 до 1.79e+308) и long double (расширенной точности; в Visual C++ имеет размер также 8 байт и тот же диапазон по модулю). Для всех этих типов зарезервированы конкретные значения нуля (0), бесконечности (Inf, от англ. слова Infinity – бесконечность) и неопределенности (NaN, от англ. словосочетания Not a Number – не число). Объявления стандартных математических функций над целочисленными и вещественными данными содержатся в библиотеке . По умолчанию литералы вещественных чисел с плавающей точкой являются константами типа double. Примеры: 1.23 .23 0.23 1. 1.0 1.2е10 1.23е-15. В записи литерала с плавающей точкой не должно быть пробелов. Если требуется литерал типа float, можно явно определить его с помощью суффикса f (F): 2.0f 2.9е-3f. Если требуется литерал типа long double, можно явно определить его с помощью суффикса l (L): 2.997L 2.0L 2.9е-3L 3.14159265L. Тип void Тип void (другое название – пустой тип) является фундаментальным типом, но объектов типа void не существует. Поэтому его можно использовать только как часть более сложного типа. Тип void используется в двух случаях: либо для указания на то, что функция не возвращает значения, либо в качестве базового типа для указателей на объекты неизвестного типа. Например: void x; void f(); void *pv, // Ошибка(!): не // Функция f, не // Указатель на существует объектов типа void. возвращающая значение. объект неизвестного типа (неопределенного). Ключевое слово void используется и в некоторых других ситуациях, но в любом случае оно всегда указывает на отсутствие некоторой информации. 4.4. Объявление переменных и констант Прежде чем объект (переменная или константа) может быть использован в программе, он обязательно должен быть определен. Определение объектов преследует следующие цели:  имя объекта связывается с типом данных, которые могут храниться в объекте;  при компиляции программы в её теле для объявляемого объекта резервируется память, размер которой определяется типом объекта;  для переменной может быть указано начальное значение, которое она получит сразу при создании (инициализация). Для констант инициализация обязательна. В программах на C++ определения переменных и констант могут располагаться в практически в любом месте, но до их первого использования. Чистые объявления, определения и инициализация объектов В C++ существуют различающиеся понятия «определение» и «объявление». Объявление – более общее понятие. Объявление объекта (также и функции) может являться либо определением, либо чистым объявлением. Разница в том, что чистое объявление объекта не подразумевает выделения памяти для объекта. Назначение чистого объявления в программе – указать компилятору, что где-то в другом месте программы данное имя определено, и таким образом сделать это имя доступным в данном месте программы. Объект нельзя использовать после чистого объявления, если он где-либо в данной программе не определен. Определение объекта должно быть одно, и только одно, в то время как чистых объявлений того же объекта может быть несколько (правило одного определения). Объявление состоит из четырех частей: необязательных спецификаторов, базового типа, объявляющей части и необязательного инициализатора. Объявление заканчивается точкой с запятой2. Например: const double pi(3.1416); // определение вещественной константы char sym1('A'); // определение символьной переменной с инициализацией 2 За исключением определений функций и пространств имен char sym2; // определение символьной переменной без инициализации unsigned int x(2); // определение целочисленной //беззнаковой переменной с инициализацией В первом примере: необязательный спецификатор – const, базовый тип – double, объявитель (объявляющая часть) – pi, инициализатор – (3.1416). В качестве необязательных спецификаторов выступают различные ключевые слова, описывающие характеристики, не связанные с самим типом. Например, extern, virtual, const, unsigned и т. д. Объявляющая часть (объявитель) состоит из имени и, возможно, операторов объявления. В основном встречаются следующие операторы объявления: * – указатель (префикс); *const – константный указатель (префикс); & – ссылка (префикс); [] – массив (суффикс); () – функция (суффикс). Суффиксные операторы объявления «крепче связаны» с именем, чем префиксные: int *vpi[100]; // Массив из 100 указателей на элементы int (*pvi)[100]; // Указатель на массив из 100 элементов типа int. типа int. Необязательный инициализатор выполняет инициализацию определяемого в объявлении объекта. Инициализация – это заполнение объекта некоторым содержанием на этапе его создания. Не следует путать инициализацию с присваиванием. Присваивание – это заполнение ранее созданного объекта новым содержанием. Разрешается объявлять несколько имен в одном объявлении. Тогда объявление содержит список объявителей, разделенных запятыми. Например: int х1, у1, y2(0); // Равносильно «int х1; int у1; int y2(0)». Примеры определений и чистых объявлений объектов: // Объявления, являющиеся определениями. char sym; // символьная переменная const double pi = 3.1415926535897932385; // вещественная константа const char *season[] = { "весна", "лето", "осень", "зима" }; // массив строк struct Date { int d, m, y; ); // структура из трех целочисленных элементов // Чистые объявления – не являются определениями. extern int error_number; // чистое объявление целочисл. переменной extern const double x; // чистое объявление вещественной константы 4.5. Инструкции консольного ввода и вывода В вычислительном алгоритме, который предполагает реализацию в виде программы для ЭВМ, исходные данные, необходимые для выполнения алгоритма (программы), должны быть введены в оперативную память ЭВМ до начала их использования. Ввод данных означает их получение от источника данных и сохранение в оперативной памяти компьютера в виде переменных. Источником данных обычно является какое-то устройство ввода. В качестве таких устройств могут выступать клавиатура, мышь, графический планшет, сканер, тачпад, цифровой фотоаппарат (видеокамера), сетевая карта (стандарта Ethernet или Wi-Fi), адаптер Bluetooth и др. Ввод данных осуществляется в результате выполнения соответствующей команды алгоритма, которая называется инструкцией ввода. По умолчанию в инструкции ввода подразумевается ввод данных, которые пользователь программы вводит с клавиатуры. После получения результата (окончательного, или промежуточного) выполнения алгоритма этот результат должен быть предоставлен пользователю. Для этого используется вывод данных посредством того или иного устройства вывода. Примеры устройств вывода: монитор, принтер, сетевая карта, Bluetooth-адаптер, устройство внешней памяти (жесткий диск, оптический DVD-привод, flash-накопитель и др.). Вывод данных осуществляется при выполнении соответствующей команды алгоритма, которая называется инструкцией вывода. По умолчанию под выводом подразумевается вывод данных в текстовом виде на монитор. Под консольным вводом/выводом понимается реализация инструкций ввода и вывода, осуществляемых через пользовательский интерфейс программы в виде консольного окна. Консольным окном (консолью) называется окно стандартного вида, создаваемое операционной системой для так называемых консольных приложений. Консольными называют приложения, не имеющие собственного специально разработанного графического интерфейса; в качестве интерфейса пользователя как раз и используется консольное окно. Консольное окно поддерживает отображение данных только в символьном (текстовом) виде. Консольные приложения часто создаются тогда, когда для работы им не требуется ввода большого объема данных пользователем и не требуется подробный вывод на экран результатов. Большое количество служебных приложений, входящих в состав Windows, являются консольными. Язык поддерживает реализацию инструкций консольного ввода/вывода в стиле языка C и в стиле языка C++. В последнем случае ввод/вывод реализован на основе специальных классов. Пока ограничимся только кратким рассмотрением организации консольного ввода/вывода в стиле языка C. Консольный ввод в стиле языка C Для организации ввода данных пользователем с клавиатуры используется функция scanf. Ее выполнение означает, что программа будет ожидать ввода пользователем с клавиатуры одного или более значений определенного типа. Полученные в результате ввода значения функция сохраняет в указанных переменных в памяти ЭВМ. Синтаксис функции: int scanf(const char *format [, argument] ...); Такая запись в общем виде означает, что функция имеет как минимум один аргумент, задаваемый в виде строки, которая называется строкой ввода. Кроме этого, функция может иметь и другие (необязательные – поэтому указываются в [квадратных скобках]) аргументы в произвольном количестве, произвольных типов, перечисляемые через запятую. В качестве аргументов, начиная со второго, должны использоваться адреса переменных, объявленных ранее в программе. Переменные могут быть любого фундаментального типа, кроме пустого. Строка ввода содержит спецификации преобразования – наборы символов, начинающиеся с символа «%». Спецификация определяет, к какому типу данных должна быть преобразована строка символов, вводимых пользователем с клавиатуры. После их ввода пользователем в виде набора символов, соответствующим нажатым при вводе клавишам, функция в соответствии со спецификациями ввода преобразует строки символов в значения требуемого типа и записывает эти значения в переменные по указанным адресам. Под адресом переменной понимается номер ячейки памяти, в которой располагается значение переменной. Адрес переменной вычисляется с помощью операции &. Например, адрес переменной x можно определить в виде &x. Примеры: double a; scanf("%lf", &a); // пользователь должен ввести одно вещественное число В результате выполнения функции введенное действительное число сохранится в переменной a. пользователем с клавиатуры double x; int y; scanf("%lf%d", &x, &y); // пользователь должен ввести одно вещественное и одно //целое число В результате выполнения функция будет ожидать от пользователя ввода с клавиатуры одного действительного и одного целого числа. После каждого введенного значения пользователь должен нажимать Enter. После ввода всех значений функция сохранит их, соответственно, в переменных x и y. Подробные справочные сведения по использованию функции scanf c примерами можно найти в пособии по стандартному консольному вводу/выводу. Консольный вывод в стиле языка C Для вывода данных с клавиатуры используется функция printf. Синтаксис функции: int printf(const char *format [, argument] ...); Такая запись в общем виде означает, что функция имеет как минимум один аргумент, задаваемый в виде строки, которая называется строкой вывода. Кроме этого, функция может иметь и другие (необязательные – поэтому указываются в [квадратных скобках]) аргументы в произвольном количестве, произвольных типов, перечисляемые через запятую. Принцип работы функции printf заключается в следующем. Строка вывода представляет собой набор символов, включающих обычные символы (выводятся в консольное окно как есть) и спецификации преобразования (начинаются с символа «%»). Спецификации преобразования вставляются в строку вывода в тех местах, куда при выводе строки требуется подставить какое-либо значение. Для каждой спецификации указывается тип выводимого значения. Само значение указывается в виде дополнительного аргумента функции printf, в качестве которого может быть значение переменной, константы, результат выражения или просто значение некоторого типа. Спецификаций преобразования в одной строке вывода может быть несколько, но каждой из них должен соответствовать «свой» аргумент функции printf. Типы выводимых значений и типы спецификаций должны соответствовать. Примеры: printf("Пример простого вывода строки"); В результате в консольное окно выведется следующее: Пример простого вывода строки printf("Выводится значение дважды два: %d. ", 2*2); В результате в консольное окно выведется следующее: Выводится значение дважды два: 4. double a(1.456), f; f = sin(a); printf("Значение синуса угла %0.3f градусов равно %0.5f. ", 180*a/3.1416, f); В результате в консольное окно выведется следующее: Значение синуса угла 83.422 градусов равно 0,02541. printf("Начинаем вывод... "); printf(" Продолжаем выводить в той же строке...\n"); printf("Начинаем выводить с новой строки. "); В результате в консольное окно выведется следующее: Начинаем вывод... Продолжаем выводить в той же строке... Начинаем выводить с новой строки. Обычно, для того, чтобы сделать диалог программы с пользователем с программой более понятным, программа информирует пользователя о действиях, ожидаемых от него, путем вывода соответствующих текстовых сообщений. Например, ввод данных в программе можно организовать следующим образом: int a1, a2; printf("Введите два целых числа: \n"); scanf("%d%d", &a1, &a2); Необходимый набор справочных сведений, необходимых для вывода данных с помощью функции printf, а также многочисленные примеры, приведены в пособии по стандартному консольному вводу/выводу. Там же приводятся сведения по консольному вводу/выводу в стиле C++. 4.6. Инструкция присваивания Инструкция присваивания является важнейшей инструкцией, без которой невозможна работа с данными в программе. Она предписывает вычислить выражение, стоящее справа от знака присваивания, и присвоить результат переменной, имя которой стоит слева от оператора присваивания. Переменная и выражение должны иметь совместимые типы, например, вещественный и целочисленный (но не наоборот). Общий вид инструкции присваивания: Имя_переменной = Выражение; Простейшими вариантами выражений могут являться просто имена объектов или значения. Примеры операций присваивания: int y = z = x = x(2), y, z; // объявление трех целочисленных переменных x; // значение переменной x присваивается переменной y 156; // значение 156 присваивается переменной z z-x*x+5*x*z+1; //значение результата выражения присваивается переменной x Полезно знать, что в языке C++, в отличие, например, от языка Pascal, присваивание является оператором. Это означает, что помимо собственно задания нового значения переменной, в результате присваивания возвращается результат, который может использоваться в других операциях в составе выражения. Так, например, допустимыми являются следующие выражения (попробуйте сами сообразить, как будут вычисляться такие выражения, и какие значения примут в результате переменные): double x,y,z(3); x = y = 2*z; double a,b(6),c; a = 3*x + (c = b/3)/c; 4.7. Структура программы и процесс создания программы По большому счету любая программа на C++ состоит из подпрограмм и данных. Все подпрограммы в C++ называются функциями. Любая программа на C++ в общем случае состоит из совокупности текстовых файлов, которые делятся на две группы. Первая группа представляет собой исходные файлы (другое название – модули реализации). В них обычно находятся определения функций и данных программы. Тип расширения исходных файлов определяется реализацией (общепринятые расширения: .cpp, .cxx, .c, .cc, .C). Вторая группа представляет собой заголовочные файлы (другое название – интерфейсные модули). Они подключаются к исходным файлам при помощи директив препроцессора и обычно содержат объявления функций и данных программы. Заголовочные файлы имеют расширение .h или .hpp (от слова header – заголовок). Заголовочные файлы также используются для подключения библиотечных функций и данных. Заголовочные файлы стандартной библиотеки не имеют расширения. Принято в начале любого модуля приводить комментарий, содержащий сведения об имени модуля, о его назначении, о разработчике и о дате разработки. Функциональная схема процесса создания программы на C++ изображена на Рис. 4.1. Важной особенностью этого процесса является наличие в нем препроцессора. Перед началом трансляции (компиляции) он выполняет макроподстановки в текстах исходных и заголовочных файлов, использующихся в данной программе. В результате препроцессирования получаются единицы трансляции, по одной на каждый исходный файл. По окончании успешной трансляции получаются объектные модули программы, по одному на каждую единицу трансляции. Они содержат машинные коды функций и данных программы и обычно имеют расширение .obj. Редактор связей собирает из объектных модулей исполняемый модуль (имеет расширение .exe) и подключает к нему машинные коды библиотечных функций и данных, используемых в программе. В ОС класса Win32 библиотеки бывают статически подключаемые (имеют расширение .lib от слова library – библиотека) и динамически подключаемые (имеют расширение .dll от словосочетания dynamic link library – динамически подключаемая библиотека). Редактор связей подключает к исполняемому модулю только функции и данные из статических библиотек. Машинный код из них входит в состав исполняемого модуля. Динамические библиотеки подключаются к исполняемому модулю в процессе выполнения программы, т. е. после ее загрузки в оперативную память. Машинный код из них не входит в состав исполняемого модуля. Каждый из основных этапов создания программы, изображенных на Рис. 4.1, считается завершенным, если выявлены и устранены все (или абсолютное большинство) ошибки, относящиеся к одной из трех групп. Выделяют следующие группы ошибок:  синтаксические;  ошибки компоновки;  ошибки времени выполнения (в том числе логические ошибки) Синтаксические ошибки возникают при несоблюдении программистом правил синтаксиса языка программирования. Эти правила различаются для разных языков программирования, и являются строгими (обязательными для выполнения). Поиск синтаксических ошибок в исходном тексте программы осуществляется компилятором либо препроцессором. При обнаружении ошибки компилятор (препроцессор) выводит соответствующее сообщение с указанием места ошибки и краткого ее описания. Успешная трансляция (компиляция) исходного текста программы возможна только после устранения всех (!) синтаксических ошибок. Исправлением найденных компилятором синтаксических ошибок (как, впрочем, и всех прочих ошибок) должен заниматься программист. В Рис. 4.1 Функциональная схема процесса создания программы на C++. Таблица 4.2 приведены примеры некоторых типичных синтаксических ошибок, которые могут встретиться в программе на языке C++. Рис. 4.1 Функциональная схема процесса создания программы на C++. Таблица 4.2 Примеры синтаксических ошибок на C++ Фрагмент кода с ошибкой Исправленный вариант кода void main(){} x = 3y+1; y-1 = 5+6/y if x>5 { x = 5; y = 0; else x = 0; } void main(){} x = 3*y+1; возможно: y-1 == 5+6/y возможно: if (x>5) { x = 5; y = 0; } else x = 0; Ошибки компоновки возникают вследствие различных причин, препятствующих успешной сборке исполняемого файла (.exe) из объектных модулей компоновщиком. Такими причинами, например, являются отсутствие в подключенной внешней библиотеке функции, вызываемой из некоторого модуля программы; коллизия, вызванная наличием в разных библиотеках, подключенных к программе, двух подпрограмм с одинаковыми заголовками, соответствующими одному и тому же вызову в тексте программы. При наличии ошибок компоновки успешная сборка исполняемого файла невозможна. Как правило, при обнаружении ошибки компоновки точное место в программе не указывается, поэтому устранение таких ошибок требует больших усилий/опыта программиста. Ошибки времени выполнения возникают, как следует из их названия, во время выполнения готовой программы. Можно выделить следующие разновидности таких ошибок: – ошибки, способные нарушить работу программы; – ошибки, вызывающие некорректный результат работы программы. Первая разновидность ошибок является следствием некорректного выполнения инструкций. Типичными являются ошибки, связанные с выделением памяти, работой с файлами, некорректным выполнением математических операций и т.д. Любая консольная программа на C++ должна в одном из своих исходных файлов содержать определение одной и только одной функции с именем main. Эта функция называется главной функцией программы. Программа начинается с выполнения этой функции и заканчивается по ее завершении. В простейшем случае программа состоит из одного-единственного исходного файла с определенной в нем функцией main(…). Минимальная программа на языке C++ (которая ничего не делает) имеет вид: void main() { } Ниже приведен листинг исходного файла простой программы (имя проекта – fmioc) с вводом-выводом в стиле языка C (такой ввод-вывод по сравнению с вводом-выводом в стиле языка C++ является более компактным). Листинг 4.1. Простая программа с вводом-выводом в стиле языка C. //fmioc.cpp // Программа преобразования значений длины в футах в метры // и сантиметры; определяет точку входа для консольного приложения. // Пояснения: // Используется ввод-вывод в стиле языка C. //————————————————————————————————————————————————————————————————————————— // Разработчик: Романовский Э.А. //————————————————————————————————————————————————————————————————————————— #include // Подключение заголовочного файла стандартной int main() // Главная функция программы. { // Объявление переменных. double feet, meters, centimeters; // Вывод данных. printf("Введите длину в футах: "); // Ввод данных. scanf("%lf", &feet); while (feet > 0) // Цикл с предусловием. { // Выражения. centimeters = feet * 12 * 2.54; meters = centimeters / 100; // Форматированный вывод данных. printf("Введенная длина равна:\n"); printf("%8.2f футов.\n", feet); библиотеки. printf("%8.2f метров.\n", meters); printf("%8.2f сантиметров.\n", centimeters); printf("\nВвдите следующее значение (0 - конец // Ввод данных. scanf("%lf", &feet); } // Возвращение return 0; результата работы программы в программы): "); операционную систему. } Здесь для вывода данных применяется функция printf(…), а для ввода данных – функция scanf(…). Чтобы их использовать в исходном файле программы, следует подключить к нему при помощи директивы #include заголовочный файл стандартной библиотеки с именем cstdio. Он содержит объявления этих функций (и многих других). По окончании своего выполнения программа возвращает в ОС число. Нулевое значение числа означает успешное завершение программы, а ненулевое значение означает аварийное завершение программы. Проблема. Выводимые в консольное окно ОС Windows символы и строки, содержащие, в частности, символы национального алфавита, выглядят на экране совсем по-другому. То же самое происходит при вводе символьных данных. Причина. При консольном вводе-выводе символы и строки обычно кодируются в соответствии со стандартом ANSI (на 1 символ отводится 1 байт), использующим DOS-кодировку (другое название – кодировка OEM). В среде программирования для Windows символы кодируются в соответствии со стандартом ANSI, использующим Windows-кодировку, или в соответствии со стандартом Unicode (на 1 символ отводится 2 байта). Решение. В программе требуется выполнять преобразование символов и строк из Windowsкодировки в кодировку OEM перед их выводом и из кодировки OEM в Windows-кодировку сразу после их ввода. Преобразующие функции будут рассмотрены позже, при изучении консольного ввода-вывода. Другим вариантом решения проблемы, менее корректным, но более простым, является сохранение исходного файла программы в DOS-кодировке (кодовая страница 866), что возможно сделать, например, в Visual Studio. Тогда русские символы будут корректно отображаться и в тексте программы (для этого открывать файл каждый раз нужно с обязательным явным указанием требуемой кодировки!!!), и при выводе строк в консольное окно. ЛЕКЦИЯ 5. ВЫРАЖЕНИЯ. РЕАЛИЗАЦИЯ БАЗОВЫХ УПРАВЛЯЮЩИХ СТРУКТУР В C++ Изучаемые разделы: Выражения БУС: следование БУС: ветвление (развилки) БУС: циклы 5.1. Выражения Выражение – это синтаксическая единица языка, определяющая способ вычисления некоторого значения. Выражение состоит из:  знаков операций;  операндов;  круглых скобок. В простейшем случае выражение может состоять из одной переменной, константы или литерала. Операнды – это данные, над которыми выполняются действия. Операндом может быть константа (литерал), переменная, элемент массива, поле записи (объекта), вызов функции. Операции определяют действия, которые производятся над операндами. Операции могут быть унарными и бинарными. Унарная операция относится к одному операнду, и ее знак (оператор) записывается перед операндом (напр., Х). Бинарная операция определяет действие над двумя операндами, и ее знак записывается между операндами (напр., X+Y). Операции в выражении выполняются с учетом их приоритета. В первую очередь выполняются операции с более высоким приоритетом. Если последовательно встречаются операции с одинаковым приоритетом, то они выполняются слева направо. Круглые скобки используются для изменения порядка выполнения операций в выражении. Подвыражение внутри скобок вычисляется в первую очередь. Скобки могут быть вложенными. Тогда вычисляется в первую очередь подвыражение в скобках с максимальным уровнем вложенности. Тип значения выражения определяется типом операндов и составом выполняемых операций. В зависимости от типов операций и операндов выражения могут быть арифметическими, логическими. Результатом арифметического выражения является число (значение одного из арифметических типов), тип которого зависит от типов операндов, составляющих это выражение. В арифметическом выражении можно использовать арифметические типы (интегральные и вещественные), арифметические, логические операции и функции, возвращающие число. Результатом логического выражения является логическое значение true или false. Логические выражения чаще всего используются в инструкциях выбора и цикла и состоят из:  логических литералов true и false;  логических переменных или констант типа bool;  операций сравнения (отношения);  логических операций;  круглых скобок;  арифметических или символьных выражений, являющихся операндами операций сравнения. Кроме этого, в логических выражениях могут присутствовать арифметических типов, неявно преобразуемых к логическому типу. значения или объекты В языке C++ существует разделение выражений на неименующие выражения и именующие выражения. Результатом неименующего («обычного») выражения является значение некоторого типа. Именующим выражением называют такое выражение, результатом которого является ссылка (значение ссылочного типа) на объект некоторого типа. Ссылкой на объект является значение либо объект специального ссылочного типа. Ссылка на объект в программе (например, в выражении) интерпретируется (воспринимается) как сам объект. Любые действия, выполняемые над ссылкой на некоторый объект, означают применение этих действий к самому объекту. Ссылка (ссылочный тип) является понятием, родственным с понятием указателя (типом указателя), хотя имеет ряд существенных отличий. Среди операторов языка C++ есть операторы, результатом которых является ссылка на объект; остальные операторы в результате своего выполнения возвращают некоторое значение (не ссылку). Простейшим вариантом именующего выражения является просто имя переменной. В общем случае именующим является такое выражение, в котором последним выполняется оператор, возвращающий ссылку на объект. Операторы Последовательность вычисления операторов в выражении определяется следующими факторами:  приоритетом операций;  ассоциативностью операций;  наличием круглых скобок. Приоритет операций определяет последовательность выполнения операторов в выражении при отсутствии круглых скобок. Операции, имеющие более высокий приоритет, выполняются раньше операций с более низким приоритетом. Если в выражении встречаются операции, имеющие равный приоритет, то они выполняются в последовательности, определяемой их ассоциативностью. Операции могут быть правоассоциативными (выполняются справа налево) или левоассоциативными (выполняются слева направо). К первым относятся все унарные операции и операция присваивания. Все остальные являются левоассоциативными. Если часть выражения заключена в круглые скобки, то эта часть вычисляется раньше части выражения вне скобок. Скобки могут быть вложенными, тогда в первую очередь вычисляется часть выражения в скобках с наибольшим уровнем вложенности (в «самых внутренних» скобках), затем – в скобках с меньшим уровнем вложенности и т.д. Рассмотрим список основных операторов, используемых в языке C++. Список представлен в виде таблицы ниже, в которой используются следующие общие обозначения: name – некоторое имя; class-name – имя структуры, класса или объединения; member – имя элемента или метода объекта класса (либо имя объекта-члена или функции-члена класса); type – тип, его имя или синоним (тип следует заключать в круглые скобки); expr / expr-list – некоторое выражение / список некоторых выражений (в т. ч. именующих); lvalue – именующее выражение; lobject – выражение, именующее объект некоторого класса; pointer – выражение, определяющее адрес некоторого объекта в памяти (указатель); pointer-to-member – выражение, определяющее адрес элемента или метода объекта класса. Таблица некоторых основных операторов C++ Название/назначение Доступ к глобальному имени Разрешение области видимости (получение квалифицированного имени) Выбор элемента или метода объекта класса или структуры Выбор элемента или метода через указатель на объект класса Доступ к элементу массива по индексу Вызов функции Конструирование значения Постфиксный инкремент Постфиксный декремент Идентификация типа Идентификация типа во время выполнения Явное преобразование родственных типов с проверкой во время компиляции Явное преобразование несвязанных типов с проверкой во время компиляции Явное константное преобразование Явное преобразование типов с проверкой во время выполнения Размер объекта Размер типа Префиксный инкремент Префиксный декремент Дополнение (побитовая инверсия) Отрицание (логическая операция «НЕ», инверсия) Унарный плюс Унарный минус Разадресация (получение адреса объекта) Разыменование (получение ссылки на объект) Создание (выделение памяти) Создание (выделение памяти и инициализация) Создание (размещение) Создание (размещение и инициализация) Уничтожение (освобождение памяти) Уничтожение массива Явное преобразование типа Выбор элемента или метода объекта по указателю на элемент или метод Выбор элемента или метода объекта по указателю на элемент или метод через указатель на объект Место применения ::name namespace-name::name class-name::member lobject.member pointer->member pointer[expr] expr(expr-list) type(expr-list) lvalue++ lvalue-typeid(type) typeid(expr) static_cast(expr) reinterpret_cast(expr) const_cast(expr) dynamic_cast(expr) sizeof expr sizeof(type) ++lvalue --lvalue ~expr !expr +expr -expr &lvalue *pointer new type new type(expr-list) new(expr-list) type new(expr-list) type(expr-list) delete pointer delete[] pointer (type)expr lobject.*pointer-to-member pointer->*pointer-to-member Умножение Деление {дш целых - деление нацело) Остаток от деления нацело Сложение (бинарный плюс) Вычитание (бинарный минус) Побитовый логический сдвиг влево Побитовый логический сдвиг вправо Меньше Меньше или равно Больше Больше или равно Сравнение на равенство (равно) Сравнение на неравенство (не равно) Побитовое «И» (пересечение) Побитовое» «ИЛИ» (объединение) Побитовое «Исключающее ИЛИ Логическая операция «И» (конъюнкция) Логическая операция «ИЛИ» (дизъюнкция) Условное выражение ?: Присваивание Умножение и присваивание Деление и присваивание Остаток от деления нацело и присваивание Сложение и присваивание Вычитание и присваивание Побитовый сдвиг влево и присваивание Побитовый сдвиг вправо и присваивание Побитовое «И» и присваивание Побитовое «Исключающее ИЛИ» и присваивание Побитовое «ИЛИ» и присваивание Генерация исключения Операция «запятая» (последовательность) expr*expr expr/expr expr%expr expr+expr expr-expr expr<>expr exprexpr expr>=expr expr==expr expr!=expr expr&expr ехрr|ехрr expr^expr expr&&expr expr||expr expr?expr:expr lvalue=expr lvalue*=expr lvalue/=expr lvalue%=expr lvalue+=expr lvalue-=expr lvalue<<=expr lvalue>>=expr lvalue&=expr Lvalue^=expr lvalue|=expr throw expr expr, expr Подряд идущие строки таблицы, выделенные одним цветом, имеют одинаковый приоритет. В целом, операторы расположены в порядке убывания приоритета. Правила применения операторов Для изменения последовательности выполнения операторов используются круглые скобки «()»: (a+b)*c. Унарные операторы и операторы присваивания правоассоциативны. Остальные операторы являются левоассоциативными. Например, a=b=c означает a=(b=c), а a+b+c означает (a+b)+c. Для определения типа результата арифметических и побитовых логических операций используются правила стандартных арифметических преобразований. В упрощенном варианте эти правила можно сформулировать так. Если хотя бы один из операндов операции имеет вещественный тип (double), то результат операции будет иметь тип double. Если все операнды операции имеют какой-либо интегральный тип, то результат операции будет интегрального типа, чаще всего типа int. Полная версия правил стандартных арифметических преобразований формулируется так. Результат выполнения некоторой операции имеет тип операнда «наибольшего размера». Однако если такой операнд имеет размер, меньший размера типа int (bool, short и т. д.), вычисления производятся с применением арифметики целых чисел типа int, и результат всегда имеет тип int. Таким образом, если операнд «наибольшего размера» относится к типу double, вычисления производятся с использованием арифметики чисел типа double, и результат имеет тип double. Если он относится к типу long, вычисления производятся с использованием арифметики длинных целых чисел типа long, и результат имеет тип long. При этом имеются два замечания: 1. Операнды побитовых логических операций не могут принадлежать типам с плавающей точкой. 2. При выполнении арифметической операции не выполняются никакие проверки на переполнение разрядной сетки результата вычисления. int i(1); while (i > 0) ++i; // Рано cout << "Переменная i стала или поздно значение отрицательной!\n"; в i будет отрицательным. Согласно стандарту результат применения обычных (непобитовых) логических операций должен иметь тип bool3. Обзор некоторых операторов ++ -Операция инкремент (++) выполняет увеличение своего операнда на единицу. Операция декремент (--) уменьшает свой операнд на единицу. В основном в операциях ++ или  операндом является некоторая целочисленная переменная. Операции ++ и -- могут быть либо в префиксной, либо в постфиксной формах. В 1-м случае знак «++» стоит перед операндом, а во 2-м – после операнда. Различие этих форм поясним на примере операции инкремента (для декремента аналогично). Рассмотрим пример: int x(2), y(2), z; // объявлены три целочисленных переменных z = ++x; // переменной z присвоено значение 3 z = y++; // перем-й z присвоено значение 2 Поясним пример. В первой из операций присваивания переменная z получила значение 3, т.к. результатом операции префиксного инкремента явилось значение переменной x после его увеличения на единицу. Во второй операции присваивания в переменную z сохранится 2, т.к. постфиксный инкремент возвращает значение переменной x до его увеличения на единицу. Префиксные варианты инкремента и декремента возвращают ссылку на свой операнд. Постфиксные варианты возвращают значение. ! Операцию отрицания можно применять, помимо логических выражений, также и к целочисленным (и даже к вещественным) выражениям. При применении операции «НЕ» к некоторому числовому выражению действует правило: если результат выражения – нуль, то результат отрицания – true. В противном случае результат отрицания – false. Например, результатом выражения !(30-2*15) будет true, а результатом выражения !(2*30.5) будет false. Поэтому операция отрицания используется в тех случаях, когда нужно подтвердить гипотезу, что выражение равно нулю (проверка на равенство нулю). / 3 В Visual C++ в некоторых случаях он может иметь тип int Операция деления имеет по сравнению с делением в Pascal следующее крайне важное отличие. Если хотя бы один из операндов операции деления имеет вещественный тип, то результат деления будет вещественным. Если же оба операнда будут целочисленными, то деление будет выполняться нацело с целочисленным результатом (!). Если этого не учитывать при составлении выражений, то велика вероятность появления неочевидных (труднообнаружимых) ошибок при вычислении. Так, например, рассмотрим случай, когда нужно извлечь корень 3-й степени из некоторого выражения: double x(3.2), y; y = pow((x*x+8.5)/sin(x), 1/3); // в y будет записано значение 1 Указанный результат объясним, если принять во внимание вышесказанное и посмотреть на показатель при возведении в степень (1/3). При делении оба операнда записаны, как целочисленные литералы, что даст результат деления, равный 0. Любое выражение в нулевой степени равно 1, что не совсем то, что требовалось. Исправить ошибку в выражении можно, записав его в виде y = pow((x*x+8.5)/sin(x), 1.0/3); // выражение записано правильно ?: Условный оператор используется для замены развилок в случаях, когда нужно присвоить переменной либо одно значение (либо результат выражения), либо другое в зависимости от некоторого условия. Так, развилку с двойным выбором вида if (x>0) y = x; else y = -x/2.0; можно заменить на простую строку y = x>0 ? x : -x/2.0 Результат оператора может быть или ссылкой, или значением в зависимости от типов второго и третьего операндов. = Присваивание в C/C++ отличается от присваивания в Pascal тем, что является полноценной операцией, которая возвращает результат и может быть частью выражения. Результат является ссылкой на левый операнд оператора. Так, предположим, что нужно трем переменным x, y, z присвоить одно и то же значение. Это может выглядеть так: x = y = z = 1; Операция присваивания является правоассоциативной операцией, поэтому в примере вначале 1 присвоится переменной z, затем присвоенное z значение будет присвоено y, и, наконец, значение, присвоенное y, будет присвоено переменной x. Таким образом, операции присваивания, следующие подряд в выражении, выполняются справа налево. Возможно с применением операции присваивания формировать и более сложные выражения, однако это полезно не во всех случаях, т.к. может ухудшить читаемость программы. =* =/ =+ =- =% и др. Данные операторы являются составными и выполняют два действия. Первым действием является какая-либо арифметическая операция, операндами которой являются операнды составной операции. Второе действие – присваивание результата первого действия левому операнду. Данные операторы предпочтительно использовать в случаях, подобных такому: x = x + 3; В этом случае лучше написать так: x += 3; Результатом выполнения операторов является ссылка на их левый операнд. Часто используемые стандартные арифметические функции Таблица. Некоторые математические функции в языке C/C++ Действие / мат. функция Функция в С/C++ abs(x), fabs(x) |x| 2 x*x x sqrt(x) x pow(x, n) xn pow(x, 1.0/n) n x exp(x) ex log(x) ln x log10(x) lg x log(a, b) log a b cos(x) cos x sin(x) sin x tan(x) tg x Cotan(x) ctg x acos(x) arccos x asin(x) arcsin x atan(x) arctg x arcctg x Примечание: для доступа к некоторым приведенным функциям необходимо подключить библиотеку Cmath, добавив в начало текста программы строку #include 5.2. Базовые управляющие структуры в C++ Язык С++ поддерживает реализацию базовых управляющих структур следования, выбора и повторения. Все виды структур могут быть вложенными друг в друга. Уровень вложенности практически не ограничен, но программист должен, по возможности, не допускать избыточной вложенности структур друг в друга. Реализация структуры следования Совокупность последовательно выполняемых инструкций, заключенных в операторные скобки {} называется блоком. Реализация автоматического выполнения инструкций блока в последовательности их следования в тексте программы встроена в язык программирования и поддерживается на аппаратном уровне (на уровне микропроцессора4). Блоки обычно являются частью других управляющих структур, хотя могут быть и самостоятельными структурами5. В частном случае блок может состоять из одной инструкции, тогда операторные скобки можно опустить. Формат блока: { Инструкция1; 4 В настоящее время активно развиваются технологии параллельных вычислений, предполагающих одновременное выполнение нескольких инструкций программы на отдельных микропроцессорах (микропроцессорных ядрах). Тем не менее понятие структуры следования и в таких программах сохраняет свой смысл. 5 Одним из применений блоков является ограничение области видимости локальных переменных в программе. Локальная переменная, объявленная внутри блока, видна только до конца этого блока, включая вложенные блоки. Инструкция2; … ИнструкцияN; } Независимо от числа входящих в блок инструкций последний воспринимается как единое целое и может располагаться в любом месте программы, где допускается наличие инструкции. Блоки могут вкладываться друг в друга. Далее, везде, где в других управляющих структурах или иных частях программы будет указано обозначение Блок или БлокИнструкций, подразумевается наличие какого-либо блока, оформленного в соответствии с изложенным. Реализация структур выбора В общем случае инструкции выбора используются для организации ветвления в программе. Развилка с единственным выбором Развилка с единственным выбором имеет синтаксис: // единственный выбор if (Условие) БлокИнструкций; Условие представляет собой выражение логического типа. Если условие истинно, то выполняются инструкции, входящие БлокИнструкций. В противном случае управление передается инструкции, следующей после развилки. Допускается (и очень часто используется) применять в качестве Условия арифметические выражения, в этом случае их результат неявно преобразуется к логическому типу по правилу: нулевое значение – соответствует логическому false, ненулевое – true. Примеры: if (a < b) { a += b; b = 0; } if (!a) // если значение переменной a равно 0 { printf("Значение равно нулю!\n"); exit(-2); // аварийное завершение программы } Развилка с двойным выбором Синтаксис развилки с двойным выбором: if (Условие) БлокИнструкций1; else БлокИнструкций2; Если Условие истинно (или имеет ненулевое значение), то выполняется блок БлокИнструкций1, в противном случае управление передается блоку БлокИнструкций2. Пример программы, использующей развилку с двойным выбором: //решение квадратного уравнения #include #include #include void main() { // --- ввод исходных данных --- double a, b, c; printf("Введите коэффициенты a, b, c: "); scanf("%lf%lf%lf", &a, &b, &c); double D(b*b – 4*a*c); double X1, X2; // --- вычисление корней уравнения --// начало развилки с двойным выбором if (D < 0) printf("Ошибка! Корни мнимые.\n"); else { // начало вложенной развилки с двойн. выб. if (!D) //эквивалентно условию D == 0 { X1 = -b / (2*a); X2 = X1; } else { X1 = (-b + sqrt(D) / (2*a)); X2 = (-b - sqrt(D) / (2*a)); } // --- вывод результата, если он получен --printf("x1 = %0.2f, x2 = %0.2f.\n", X1, X2); } } Для организации ветвления на три и более направлений можно использовать несколько вложенных друг в друга развилок с двойным выбором. Однако для этих целей по возможности лучше использовать развилки с множественным выбором. Развилка с множественным выбором Данная разновидность структуры выбора позволяет сделать выбор из произвольного числа имеющихся вариантов, т.е. выполнить ветвление на произвольное число вариантов. Инструкция состоит выражения (селектора), списка вариантов и необязательной ветви else. Синтаксис: switch (Селектор) { case Вариант1: БлокИнструкций1; break; // ... case ВариантN: БлокИнструкцийN; break; default: БлокИнструкцийПоУмолчанию;] } Селектор представляет собой выражение интегрального типа. Каждый из вариантов выбора (Вариант1 … ВариантN) представляет собой константное выражение типа, соответствующего типу выражения Селектор. БлокИнструкций1, …, БлокИнструкцийN – блоки, содержащие инструкции, выполняемые при совпадении значения Селектора с соответствующим значением Варианта. Развилка с множественным выбором выполняется следующим образом. Сначала вычисляется значение Селектора. Затем производится последовательный просмотр вариантов на предмет совпадения их значений с значением Селектора. Если для очередного варианта совпадение обнаружено, то выполняются инструкции, включенные в соответствующий БлокИнструкций. Наличие инструкции break после каждого блока не допускает выполнения инструкций из следующего блока (иначе они бы выполнялись, в отличие от аналогичной ситуации в языке Pascal). Если значение Селектора не совпало ни с одним из вариантов, то выполняется блок БлокИнструкцийПоУмолчанию (при его наличии, т.к. наличие варианта default необязательно). Пример программы, выводящей наименование дня недели по его номеру: // программа для определения названия // дня недели по его номеру #include void main() { const int WeekEndDay1(6); int WeekEndDay2(7), DayNumber; printf("Введите номер дня недели: "); scanf("%d", &DayNumber); switch (DayNumber) { case 1 : printf("Понедельник\n"); break; case 2 : printf("Вторник\n"); break; case 3 : printf("Среда\n"); break; case 4 : printf("Четверг\n"); break; case 5 : printf("Пятница\n"); break; case WeekEndDay1 : // Правильно! Константное выражение printf("Суббота\n"); break; case WeekEndDay2 : // Ошибка!! Неконстантное выражение! printf("Воскресенье\n"); break; } default : printf("Ошибка: неверно задан день недели!\n"); } Реализация структур повторения Инструкции повторения (циклы) используются, когда возникает необходимость выполнения некоторой инструкции (блока) более одного раза. Блок инструкций, выполняемых в цикле, называют телом цикла. Циклы, в частности, необходимы для эффективной работы с массивами. Очевидно, что в теле цикла на каждой его итерации исполняется один и тот же набор инструкций, составляющих тело цикла. Но при этом вовсе необязательно, чтобы результат выполнения таких инструкций был одинаковым на каждой итерации. Это объясняется тем, что, как правило, данные, с которыми оперируют инструкции в теле цикла, изменяются от итерации к итерации, и, соответственно, меняется результат этих инструкций. В C++ существует три разновидности структур (инструкций) повторения:  цикл с параметром (for);  цикл с предусловием (while);  цикл с постусловием (do-while). Цикл с параметром является частным случаем цикла с предусловием и применяется обычно в случае, когда число повторений (итераций) цикла известно заранее. В противном случае используются циклы с пост- и предусловием. Это разделение циклов по предназначению достаточно условно, так как практически всегда в программе цикл одного вида может быть эквивалентно заменен на иную разновидность цикла. Другое дело, что для определенных задач часто удобно применять определенный цикл. Например, для работы с массивами данных наиболее удобным является цикл с параметром (for). Выполнение любого цикла может быть прервано с помощью инструкции break, которая передает управление следующей за инструкцией цикла инструкции. Инструкция цикла с параметром Особенность данной разновидности цикла в том, что в нем используется специальная переменная, обычно интегрального типа, называемая параметром. Перед началом выполнения цикла этой переменной задается некоторое начальное значение. Затем, при выполнении цикла, в начале каждой итерации значение переменной-параметра изменяется некоторым образом (чаще всего увеличивается или уменьшается на какую-то постоянную величину). Сразу после очередного изменения параметра выполняется проверка условия: не превысило ли его новое значение заданную предельную величину. Если нет, то выполняется очередная итерация цикла. В противном случае цикл завершается, и управление передается следующей после цикла инструкции. Синтаксис: for(Инструкция_инициализации_параметра; Условие; Инструкция_изменения_параметра) БлокИнструкций Заголовок цикла состоит из слова for, за которым следуют круглые скобки, в которых содержатся три секции, разделяемые точкой с запятой. Первая секция Инструкция_инициализации_параметра однократно выполняется перед началом выполнения цикла и предназначена для задания начального значения параметра. Вторая секция содержит логическое выражение, которое проверяется перед началом каждой итерации цикла. Если результат этого выражения равен true, текущая итерация выполняется, если false – цикл завершается. Третья секция цикла содержит некоторую инструкцию, которая выполняется перед проверкой Условия перед каждой итерацией, в результате которой значение параметра изменяется на некоторую величину. Чаще всего в цикле значение параметра изменяется с шагом 1, для чего удобно использовать операцию инкремента/декремента. Очевидно, параметр в цикле должен изменять свое значение таким образом, чтобы после определенного количества итераций Условие стало ложным. Пример программы, использующей цикл с параметром для вычисления факториала n! целого числа n: // программа для вычисления факториала целого числа #include #include void main() { unsigned int n; // переменная беззнакового целого типа // может хранить только неотрицательные целые значения // ввод целого значения printf("Введите неотрицательное целое число: "); scanf("%d", &n); // вычисление факториала в цикле с параметром i unsigned int f(1), i; for (i = 1; i <= n; ++i) f *= i; // вывод результата printf("Факториал числа %d равен %d.\n\n", n, f); // завершение программы printf("Нажмите любую клавишу для завершения программы..."); getch(); } В программе цикл многократно выполняет одну и ту же инструкцию, которая текущее значение переменной f умножает на значение переменной-параметра i, а полученное значение присваивает переменной f, заменяя ее прежнее значение. В каждой итерации цикла значение переменной i увеличивается на 1 в результате операции инкремента. Последняя итерация цикла выполняется, когда значение переменной i равно значению n. Если при вводе исходного числа пользователь задал значение 0, то условие в цикле сразу окажется ложным, и ни одной итерации не выполнится. При этом переменная f сохранит свое начальное значение 1, что и будет значением факториала 0!. Инструкция цикла с предусловием Данная инструкция используется, как правило, в случаях, когда число итераций цикла заранее неизвестно и, в частном случае, может быть равно нулю. Такой цикл всегда можно использовать вместо цикла for, но не всегда это удобно. В общем случае, такие циклы используют тогда, когда не удается выделить и использовать специальный параметр, от значения которого будет зависеть, в какой момент цикл завершится. Синтаксис: while (Условие) БлокИнструкций; Блок БлокИнструкций выполняется до тех пор, пока результат проверки Условия остается равным true. Как только Условие стало ложным, цикл прекращается. Пример программы, использующей цикл с предусловием: // программа для вычисления значения функции f(x) = sin(x)*cos(x), // начиная с некоторого значения аргумента x // до тех пор, пока функция неотрицательна. #include #include void main() { double x, dx, f; // ввод данных printf("Введите начальное значение аргумента x: "); scanf("%lf", &x); printf("Введите положительное значение шага приращения аргумента: "); scanf ("%lf", &dx); // проверка правильности введенного значения if (dx <= 0) { printf("Вы ввели неверное значение шага приращения аргумента.\n" "Программа будет завершена после нажатия любой клавиши..."); getch(); exit(-1); // аварийное завершение программы } f = sin(x)*cos(x); // вычисляем значение функции для нач. значения x // "шапка" таблицы printf("%10s %8s\n", "X ", "F(X) "); // цикл вычислений и вывода результата в виде таблицы while (f >= 0) { // выводится очередная строка таблицы printf("%8.2f %8.2f\n", x, f); x += dx; // увеличивается значение аргумента на шаг dx f = sin(x); // вычисляем новое значение функции } printf("Значение функции стало меньше 0. Вычисления завершены.\n\n"); } // завершение программы printf("Нажмите любую клавишу для завершения программы..."); getch(); В программе цикл с предусловием использован для многократного вычисления значения функции, где аргумент каждый раз увеличивается на постоянную величину. Также в теле цикла выполняется вывод текущих значений аргумента и функции в виде строки таблицы. Условие, проверяемое в начале каждой итерации, становится ложным, если очередное значение функции (переменной f) стало отрицательным, что приводит к завершению цикла. Инструкция цикла с постусловием Цикл с постусловием используется в случаях, когда тело цикла должно выполниться не менее одного раза, и количество итераций заранее неизвестно. Инструкция цикла с постусловием аналогична циклу с предусловием за исключением того, что условие проверяется после выполнения тела цикла. Синтаксис: do БлокИнструкций; while (Условие) Тело цикла выполняется, пока Условие остается равным true. Перед первой проверкой Условия тело цикла обязательно однократно выполняется. Пример программы, в которой используется цикл с постусловием: // программа для сложения вводимых пользователем неотрицательных // целых чисел с ограничением максимального значения суммы #include #include void main() { // значение суммы чисел не должно превышать значения этой константы const size_t maxSum(100); // тип size_t эквивалентен типу unsigned int // объявляются переменные беззнакового целого типа // могут хранить только неотрицательные целые значения size_t value, Sum(0); // ввод данных и их суммирование printf("Вводите неотрицательные целые числа," " нажимая после ввода каждого Enter.\n"); printf("Для завершения ввода введите 0.\n"); do { scanf("%d", &value); if (Sum + value > maxSum) { printf ("\nНевозможно прибавить значение %d: " " сумма превысит %d.\n", value, maxSum); break; // инструкция прерывания цикла } Sum += value; } while (value); // пока value не станет равно 0 // вывод результата printf("\nСумма введенных чисел равна %d.\n\n", Sum); // завершение программы printf("Нажмите любую клавишу для завершения программы..."); getch(); } При использовании циклов с пост- и предусловием программист должен включить в тело цикла инструкции, изменяющие значение условия на противоположное, в противном случае может произойти зацикливание. ЛЕКЦИЯ 6. МАССИВЫ В C++. МАССИВЫ И УКАЗАТЕЛИ Изучаемые разделы: Понятие о массивах Использование массивов в C++ Понятие об указателях Связь массивов и указателей Динамические массивы 6.1. Понятие о массивах Причины использования массивов Если бы при создании программ разработчики могли обойтись для хранения необходимых данных только переменными простых (фундаментальных) типов, каждая из которых способна сохранять только одно значение, то тогда, наверное, не было бы необходимости в больших объемах оперативной памяти, свойственных современным компьютерам. Это потому, что программы не имели бы возможности оперировать большими объемами данных, т. к. для этого понадобилось бы либо создавать огромное количество «обычных» переменных для одновременного хранения в памяти этих данных, либо выполнять их ввод «по чуть-чуть», используя только небольшое число переменных, с немедленной обработкой этих данных. Первый случай практически нереализуем. Во втором случае быстродействие и надежность работы программы будет значительно снижена, т. к. скорость операций ввода/вывода (например, чтение данных с диска) данных небольшими порциями по отдельности на порядок ниже, чем сразу большими объемами. Можно упрощенно сравнить процесс однообразной обработки больших объемов данных с необходимостью натаскать литров 200 воды из колодца в баню. Если воспользоваться для этого парой стаканов, то задача решаема, но за слишком длительное время из-за необходимости многократного выполнения вспомогательных действий (ходить туда-сюда, набирать воду из колодца, сливать в бак в бане и т.д.). Если же использовать пару ведер, то задачу можно решить за существенно меньшее время. Если перенести аналогию на задачу повышения эффективности программ, то станет понятным, что быстродействие программ можно значительно увеличить, если обеспечить одновременное хранение данных в достаточном количестве для исключения слишком частых операций ввода/вывода и упрощения их обработки. Для этого существуют различные способы представления данных6, но наиболее широко используют массивы. Определение массива Массив – индексированная именованная совокупность однотипных элементов, размещенная в непрерывной области оперативной памяти. Другими словами, массив – это объект (сложная переменная), в котором хранится множество (1 или более) значений некоторого типа. Слово «индексированный» означает, что в программе получить доступ к любому элементу массива (для его чтения либо изменения) достаточно указать вместе с именем массива порядковый номер элемента, называемый индексом. Такой способ доступа к значениям элементов в массиве очень удобен и позволяет обращаться к элементам массива в произвольном порядке, хоть по очереди, хоть вразброс. 6 Помимо массивов, существуют и другие способы организации данных, называемые структурами данных. К ним относят списки, стеки, очереди, деревья и др. Выбор конкретной структуры для реализации в программе зависит от характера наиболее часто выполняемых операций с данными. Более полное знакомство с этими структурами данных можно получить из многочисленной литературы по алгоритмам и структурам данных. Особенности массивов Можно различать массивы, рассматривая тип его элементов. В качестве типа элементов массива может быть практически любой тип. Так, например, вещественным массивом можно назвать массив, элементы которого имеют тип double или float, а символьным будет массив, элементы которого будут иметь тип char. Символьные массивы используют для хранения символьных строк. Элементы массива могут быть сложных типов. Часто каждый элемент массива сам хранит некоторую совокупность значений. Массив также характеризуется размером. Размер массива определяет, сколько элементов всего в массиве. Размер массива задается при создании массива и в дальнейшем не может быть изменен. Это связано с тем, что массив обязательно должен располагаться в непрерывном участке оперативной памяти, и расширить его может быть невозможно по той же причине, как увеличить площадь садового участка, когда вокруг вплотную соседние участки. Бывают массивы, у которых размер всего один. Такие массивы называются одномерными. Их называют векторами. В математике аналогом одномерного массива размером n будет вектор, заданный в n-мерном пространстве, т.е. имеющий n координат (чисел). Для обращения к элементу такого массива требуется указать всего один индекс (номер элемента). Бывают массивы, у которых несколько размеров. Такие массивы можно представить как двумерные (плоские), трехмерные (объемные), многомерные (в общем случае) таблицы значений. Соответсвенно, сами массивы называются двумерными (матрицы), трехмерными, многомерными. Для обращения к элементу двумерного массива потребуется указать уже два индекса (номер строки, номер столбца, на пересечении которых находится элемент), трехмерного – три индекса и так далее. Количество измерений размеров массива называется его размерностью. Размерность выражается целым числом. Для вектора размерность равна 1, для матрицы – 2 и т.д. Массивы еще различаются временем своего создания. Если массив создается сразу при запуске программы, а размер массива указан при его объявлении, то такой массив будем называть обычным7. Время жизни такого массива определяется временем выполнения программы. Уничтожение обычного массива происходит при ее завершении. Выделение (резервирование) памяти для размещения в ней обычного массива осуществляет компилятор, т.к. ему уже известно, сколько элементов будет в массиве, и какого они типа (то есть размера). Такое выделение памяти называется статическим8. Если создавать обычные массивы слишком большого размера, то это приведет и к соответствущему увеличению размера самой программы, что нежелательно. Массивы могут создаваться и по-другому – уже во время выполнения готовой программы. При этом появляется возможность создавать массивы, размер которых во время написания программы еще неизвестен (что бывает довольно часто). Этот размер может, например, вычисляться или вводиться при выполнении программы перед созданием самого массива. Массивы, создаваемые таким способом, когда память для них выделяется операционной системой при выполнении программы, называются динамическими. Достоинством применения динамических массивов является возможность выделять для них ровно столько памяти, сколько требуется, без запаса «на всякий случай», что свойственно обычным массивам. Недостатком является необходимость предусматривать в программе инструкции не только для выделения памяти, но еще и для ее своевременного освобождения (удаление массива), причем это удаление можно выполнить в любой момент после создания массива. Работа с динамическими массивами в C++ требует большей квалификации и внимательности программиста. Рассмотрим далее, как «по-простому» применять массивы в программе. 7 Это не специальный термин. Более правильно, но менее удобно называть такие массивы нединамическими, в противовес динамическим массивам (см. далее в тексте). 8 Поэтому иногда обычные массивы называют еще статическими. 6.2. Объявление и использование массивов в C++ Здесь пока будем рассматривать только обычные массивы. Их использовать проще, и, если они относительно небольшого размера (порядка сотни элементов), то и вполне оправданно. Объявление массивов Объявление одномерного массива, допустим с целочисленными элементами отличается от объявления простой целочисленной переменной только наличием квадратных скобок, в которых указан размер массива. Например int OneIntValue; //обычная целочисленная переменная, хранит одно число int IntVector[30]; //обычный целочисленный массив, хранит до 30 чисел В квадратных скобках указывается размер, в качестве которого может выступать натуральное число либо целочисленная константа. Вовсе необязательно, чтобы в программе использовались все имеющиеся элементы массива. Например, в массиве IntVector из примера выше в программе могут использоваться всего несколько элементов. Но размер памяти, выделенной для массива, меньше все равно не станет. Еще пример объявления массивов: const int N(100); double Weights[N]; double Lengths[N]; Здесь для задания размера массивов объявлена специальная целочисленная константа N. Именно так рекомендуется делать во всех случаях, т.к. одну и ту же константу можно многократно использовать в разных местах программы, а при необходимости изменить ее значение это понадобиться сделать всего в одном месте. При объявлении массивов в вышеприведенных примерах значения элементов сразу после создания массива в памяти будут неопределенными. До тех пор, пока где-нибудь в программе значения элементов не будут заданы тем или иным образом. Начальные значения элементов массива (если они известны сразу) можно указать при объявлении массивов в виде списка инициализаторов в фигурных скобках после имени массива и знака «равно». Например: int Digits[10] = {0,1,2,3,4,5,6,7,8,9}; double Point[2] = {0.0, 0.0}; Создаваемый массив можно сделать константным. У такого массива значения элементов обязательно задаются при его объявлении и не могут далее в программе изменяться, как и обычные константы. Вот так выглядит создание трех константных массивов, вещественного целочисленного и символьного: const double cdArray[5] = {1.0, 5.0, 2.13, -0.14, 0}; const int ciArray[] = {0, 2, 4, 6, 8, 10, 12}; const char ccArray[] = {'П','р','и','м','р',' ','с','т','р','о','к','и','\0'}; Обратите внимание, что для массивов ciArray и ccArray не указаны их размеры. Это объясняется тем, что компилятор сам может определить размеры по количеству инициализаторов, указанных в фигурных скобках. А в первом случае нужно проследить, чтобы указанный размер и число инициализаторов совпали. Итак, запишем спецификацию общего вида объявления массива: Спецификатор Тип_элементов Имя_массива [Конст_размер] Инициализирующая_часть; [ ]. Обязательными элементами являются Тип_элементов, Имя_массива, квадратные скобки Спецификатор (например, const) необязателен. Обязательно наличие или Конст_размера, или Инициализирующей_части. Чтобы объявить многомерный массив, следует указать каждый из его размеров в своих квадратных скобках. Например, объявление вещественной матрицы размером 10100 примет вид const int N(10), M(100); double dMatrix[N][M]; Обращение к данным массивов Важнейшим принципом для работы с массивом является принцип поэлементного обращения к его данным. Он означает, что, несмотря на то, что массив является единым объектом в памяти, со значениями, которые в нем храняться, можно выполнять любые операции только с каждым по отдельности. На первый взгляд, это неудобно. На самом деле чаще всего со всеми элементами массива или их частью требуется выполнять одни и те же действия, что легко реализуется с помощью циклов. Именно циклы являются непременными спутниками массивов в программах, позволяя один раз задать последовательность действий, которые нужно выполнить с элементами массива, и обеспечить их повтор соответствующее количество раз, при необходимости изменяя параметры этих действий. При всем этом нужно уметь обращаться к конкретному элементу в массиве. Для этого после имени массива в квадратных скобках указывается индекс элемента. Например: // объявим массив A из 3 элементов int A[] = [10, 20, 40]; // выведем его значения на экран printf("1-й элемент: %d\n", A[0]); printf("2-й элемент: %d\n", A[1]); printf("3-й элемент: %d\n", A[3]); // то же самое с помощью цикла int i; for (i = 0; i < 3; ++i) printf("%d-й элемент: %d\n", i+1, A[i]); // умножим каждый элемент на его номер в массиве плюс 1 A[0] *= 1; A[1] *= 2; A[2] *= 3; // естественно, в цикле удобней: for (i = 0; i < 3; ++i) A[i] *= i+1; Следует иметь в виду, что в C++ элементы нумеруются всегда с нуля. Поэтому в массиве из n элементов индекс начального элемента равен 0, а индекс последнего – n–1. Для обращения к элементам многомерных массивов следует указывать уже не один, а несколько индексов, каждый в собственных квадратных скобках. Например, обращение к матрице вещественных элементов с целью ввода их значений можно выполнить так: // размеры матрицы в виде констант const int N(10), M(5); // объявление вещественной матрицы double dMatrix[N][M]; // теперь выполним ввод ее значений, // естественно, в цикле, вернее, в двух int i, j; for (i = 0; i < N; ++i) for (j = 0; j < M; ++j) { printf("Введите элемент матрицы A[%d,%d]: ", i,j); scanf("%lf", &dMatrix[i][j]); } // а теперь выведем элементы, чтобы было похоже на матрицу for (i = 0; i < N; ++i) { printf("["); for (j = 0; j < M; ++j) { printf(" %5.1f", dMatrix[i][j]); } printf(" ]\n"); } Важное замечание! В программах на C++ следует избегать применения многомерных массивов. Их использование делает программы менее гибкими и стесняет свободу действий программиста9. Вместо них в тех же целях успешно используются одномерные массивы. Понять, как можно вместо матрицы использовать вектор, очень легко, если учесть, что вектор должен будет иметь столько же элементов, что и заменяемая им матрица. Кроме того, нужно представлять, что с точки зрения расположения элементов массива в памяти безразлично, одномерный это массив, или многомерный. Элементы матрицы располагаются в памяти в соседних ячеках, строка за строкой, по сути, в виде одномерного массива, размер которого равен произведению числа строк на число столбцов матрицы. Тем не менее, даже несмотря на замену в программе матрицы на одномерный массив соответствующей длины удобнее работать с ним, используя для обращения к элементам номер строки и номер столбца «как в матрице». Для этого придется для каждого обращения к элементу вычислять по номеру строки и номеру столбца его индекс в одномерном массиве. Для этого используется формула: Индекс = НомерСтроки  КоличествоСтолбцов + НомерСтолбца Для примера переделаем пример с матрицей, рассмотренный выше, в вариант с одномерным массивом. // размеры матрицы в виде констант const int N(10), M(5); // вместо матрицы - одномерный массив double dMatrix[N*M]; // те же циклы для ввода элементов int i, j; for (i = 0; i < N; ++i) for (j = 0; j < M; ++j) { printf("Введите элемент матрицы A[%d,%d]: ", i,j); scanf("%lf", &dMatrix[i*M + j]); } // а теперь выведем элементы, чтобы было похоже на матрицу for (i = 0; i < N; ++i) { printf("["); for (j = 0; j < M; ++j) { printf(" %5.1f", dMatrix[i*M + j]); } printf(" ]\n"); } Как можно увидеть, приглядевшись, разница с предыдущим примером – в объявлении массива и при обращении к его элементам – вместо пары индексов всего один, вычисляемый по приведенной формуле. Имея в виду возможность работы с многомерными массивами в C++, желательно все же приучиться использовать вместо них одномерные. 9 Есть и более формальное ограничение на использование многомерных массивов: их практически невозможно передавать и обрабатывать в функциях. Поэтому указанное замечание при наличии функций, оперирующих с переданными им массивами, обретает особую актуальность. Пример программы Решим задачу нахождения максимального абсолютного значения mx попарных произведений элементов двух векторов A и B одинаковой длины n по формуле mx  max  A0 Bn 1 , A1 Bn  2 , ..., An  2 B1 , An 1 B0  . Соответствующая программа будет иметь вид: #include #include void main() { // объявляем два массива const int Nmax(100); double A[Nmax], B[Nmax]; int i, n; //ввод исходных данных // длина векторов printf("Задайте длину векторов: "); scanf("%d", &n); //элементы векторов printf("Вводите элементы векторов, разделяя значения пробелами: \n"); printf("Значения вектора А: "); for (i = 0; i < n; ++i) scanf("%lf", &A[i]); printf("Значения вектора B: "); for (i = 0; i < n; ++i) scanf("%lf", &B[i]); //обработка массивов double mx(abs(A[0]*B[n-1])), p; for (i = 1; i < n; ++i) { p = abs(A[i] * B[n-1-i]); if (mx < p) mx = p; } //вывод результата printf("Максимум из полученного множества равен %0.1f.\n", mx); printf("\nНажмите любую клавишу для завершения программы...\n"); getch(); } Приведенных сведений об обычных массивах достаточно для создания несложных программ, где используются массивы относительно небольшого размера. Разработка же сложных, эффективных программ невозможна без применения динамических массивов. Работа с динамическими массивами в программе, начиная от их создания и заканчивая их уничтожением, требует тесного знакомства с одним очень важным типом данных языка C++, который называется типом указателя. Далее в лекции приводятся начальные сведения об указателях. Более подробное изучение принципов работы с указателями и типичных проблем, вызванных их неправильным применением, будет дано в последующих лекциях. 6.3. Понятие об указателях Тип указателя является одним из наиболее широко применяемых в программах на C++ типов данных. Этот тип относится к встроенным типам данных. Указателями часто пугают новичков в программировании, имея в виду «недосягаемую» сложность их использования в программах. С другой стороны, те, кто успешно освоил работу с указателями, могут считать этот факт одним (впрочем, далеко не единственным) из признаков их квалификации как программиста. Чтобы понять предназначение этого типа при создании программ, понадобится краткий экскурс во внутренности типичного персонального компьютера. Адресация данных в оперативной памяти Любой компьютер (и даже простейший мобильник) является вычислительным устройством. Для хранения тех данных, с которыми непосредственно работают выполняющиеся программы, используется оперативная память (рис.1). С точки зрения программиста, который при создании программы определяет, как и для чего будет использоваться память, структура ее представляет собой последовательность ячеек, каждая из которых имеет размер 1 байт. Каждая из таких ячеек памяти имеет свой уникальный порядковый номер, начиная с 1, называемый ее адресом. Программы, чтобы записывать туда либо считывать оттуда данные, могут обращаться к любой нужной ячейке памяти по ее адресу. Скорость обращения к ячейке памяти не зависит от ее адреса, поэтому оперативная память еще называется «памятью с произвольным доступом» (RAM). Рис. 2 Модули оперативной памяти для персонального компьютера Доступ к данным через указатели Обычным способом организации хранения данных в оперативной памяти для программиста является определение переменных и констант (объектов), позволяющих хранить значения некоторого типа в какой-то области памяти. Обращение к таким данным обычно осуществляется по именам соответствующих объектов. Наряду с этим способом во многих (не во всех) языках программирования имеется альтернативный способ доступа к данным программы – по адресам начальных ячеек памяти, в которых они расположены10. В языках C++, Pascal этот способ реализован в полной мере, для чего в них и включен специальный тип данных – тип указателя. Значением этого типа является адрес ячейки оперативной памяти. То есть, если в программе объявить переменную типа указателя, то она будет предназначена для хранения в оперативной памяти адреса, по которому в памяти находится некоторый объект с данными. Эта переменная называется указателем. Указатели позволяют обращаться к данным в памяти не по именам соответствующих объектов, а по их адресам. Для некоторых объектов в программе вообще не объявляются имена, и использование указателей на них является практически единственным способом доступа к 10 Учитывая, что большинство объектов в памяти занимают больше одного байта, то будем называть адресом произвольного объекта адрес начальной ячейки участка памяти, в котором и размещается этот объект. данным. Несмотря на то, что указатели сами по себе являются полноценным переменными, их непосредственные значения редко интересуют программиста. В большинстве случаев конкретные адреса, по которым в памяти располагаются данные, программиста не волнуют. Он лишь должен обеспечить в программе корректное использование указателей для работы с данными. Области использования указателей В программировании указатели имеют две основных области применения. Первая связана с использованием динамического размещения данных в памяти. Такой способ организации хранения данных позволяет весьма эффективно использовать память, выделяя ее для данных во время выполнения программы по мере необходимости и в нужном объеме, и освобождать память, как только данные станут больше не нужны. Этот вопрос является достаточно сложным и будет предметом отдельной лекции. Вторая область связана с применением в программах подпрограмм, т.е. функций. Здесь указатели используются для передачи в функцию адресов внешних по отношению к функции объектов, давая им возможность извлекать из них данные (исходные) или записывать в них данные (результат). Более подробно этот вопрос будет рассмотрен при изучении функций. Объявление указателей Рассмотрим примеры того, как в программе объявляются указатели. int * piVal; // указатель на целочисленный объект double * pA; // указатель на вещественный объект Тип указателя состоит из имени типа тех данных, адрес которых будет храниться в указателе, и символа «*», который здесь выступает как оператор объявления указателя11. Указатель при этом сможет сохранять адрес данных только соответствующего типа. Это несмотря на то, что сами адреса как таковые ничем друг от друга не отличаются – все они являются целыми натуральными числами (их принято записывать в шестнадцатеричном коде, чтобы отличать адреса от просто целых значений, например: 0x00FA327E). Так, указатель piVal может хранить адреса только переменных типа int, а pA – адреса переменных типа double. Элементарные действия с указателями В программе можно вычислить адрес любой переменной или константы. Для этого используется специальный оператор, называемый оператором разадресации. Он обозначается символом «&», является унарным12. Результат этой операции можно присвоить указателю, если типы указателя и разадресуемой переменной соответствуют. Для осуществления доступа к адресумому значению к указателю применяют операцию разыменования, обозначаемую «*». Пусть имеется некоторая переменная A типа T и указатель pA типа T* на переменную A. Тогда значение переменной А можно получить по ее имени: A, либо с помощью разыменования указателя: *pA. Пример: int IntVal(10); // целочисленная переменная double DblVal(-0.72); // вещественная переменная int * piVal; // указатель на целочисленный объект double * pA; // указатель на вещественный объект piVal = &IntVal; // присвоили указателю адрес переменной IntVal pA = &IntVal; // Ошибка! Несоответствие типа переменной типу указателя! 11 Символ * используется для обозначения трех различных операторов: умножения, объявления указателя и разадресации. Чтобы их не путать, следует знать, какой оператор в каком месте может использоваться. 12 Именно этот оператор и использовался при вызове функции scanf для того, чтобы сообщать функции адреса переменных, куда она должна сохранять вводимые пользователем значения. pA = &DblVal; // присвоили указателю адрес переменной DblVal int * piVal1; // объявили еще один указатель на целочисл. объект piVal1 = pA; // Ошибка! несоответствие типов указателей! piVal1 = piVal; // присвоили указателю значение другого указателя // выведем значение переменной IntVal на экран... // ... обычным способом: printf("IntVal = %d\n", IntVal); // ... или через указатель (разыменовав его): printf("IntVal = %d\n", *piVal); Пример также иллюстрирует ограничения для программиста, которые возникают из-за наличия в типе указателя информации о типе данных, адреса которых могут храниться в этом указателе. Эти ограничения должны помочь программисту не допустить ошибок в программе, вызванных неверным использованием данных при доступе к ним через указатель. Более подробное изучение указателей и действий над ними – предмет отдельной темы. 6.4. Связь указателей и массивов В C++ существует явная, тесная связь между указателями и массивами. Эта связь вытекает из принципов организации хранения элементов массива в памяти и доступа программы к ним. Представление массивов в языке C++ является наиболее простым и «низкоуровневым». В результате этого в программах, написанных на C++, работа с массивами осуществляется с максимальной достижимой скоростью. Обратной стороной медали является необходимость контроля корректности работы с массивом со стороны программиста, т.к. встроенные средства для этого практически отсутствуют. Связь типа массива с типом указателя выражается в том, что имя массива может всегда восприниматься, как указатель на начальный элемент массива (но не наоборот). При объявлении массива переменная, которую мы обычно называем просто массивом, фактически хранит адрес начального элемента такого массива, т.е. является неявно заданным указателем на начало массива. Убедиться в этом можно, в режиме пошаговой отладки в среде Visual Studio наведя курсор мыши на имя массива. Во всплывающей подсказке отобразится не что иное, как адрес начального элемента массива. При обращении к массиву мы указываем имя массива, после чего указываем в квадратных скобках индекс. При этом на самом деле квадратные скобки являются оператором индексации, который работает таким образом. Левым операндом оператора является имя массива, воспринимаемое как указатель на начало массива. Используя значение индекса элемента массива (правый операнд), оператор вычисляет адрес соответствующего элемента массива, а по указателю – ссылку на его значение. То есть результатом оператора индексации является ссылка на элемент массива, индекс которого был задан в квадратных скобках. Кроме оператора индексации к указателям применимы арифметические операторы инкремента/декремента, а также сложения и вычитания с целым числом. Результат применения к указателям арифметических операторов +, -, ++ (увеличение на 1 – инкремент) и -- (уменьшение на 1 – декремент) зависит от типа объекта, который адресуется указателем (точнее, от его размера в байтах). Если к указателю p типа T* применяется арифметический оператор, то предполагается, что p указывает на элемент массива типа T. Тогда p+1 указывает на следующий элемент массива, а p-1 – на предыдущий элемент массива, и целое значение p+1 будет на sizeof(T) больше, чем целое значение p (здесь выражение sizeof(T) возвращает число байт для хранения объектов типа T). Также допускается вычитать из указателя указатель, если они указывают на элементы одного и того же массива. Результатом будет целое число, определяющее количество элементов массива между этими указателями. Сложение указателей смысла не имеет и поэтому запрещено. В остальных случаях результат применения к указателям арифметических операторов имеет тип указателя. Пример программы для иллюстрации двух различных способов доступа к элементам массива и применения арифметических операций к указателю на начало массива. #include #include void main() { const int N(5); int a[N], i; // ввод элементов массива printf("Введите %d целых чисел ...\n", N); for (i=0; i #include void main() { // задание размеров будущего массива int n; printf("Введите количество вводимых значений... "); scanf("%d", &n); if (n <= 0) { printf("Ошибка! Некорректное значение.\n"); return; } double * pMas; // объявляем указатель на значение типа double pMas = new double[n]; // создаем массив из n элементов типа double // и сохраняем его адрес в указателе pMas // вводим элементы массива (привычным образом) printf("Введите %d значений через пробел... \n", n); for (int i(0); i avg) ++count; // удаляем массив из памяти delete[] pMas; // выводим результат printf("Из введенных значений %d больше общего среднего" " арифметического, равного %0.2f.\n", count, avg); getch(); } ЛЕКЦИЯ 7. ФУНКЦИИ В С++ Изучаемые разделы: Понятие о подпрограммах Создание функций в С++ Вызов функции. Передача аргументов в функцию и возврат результата Функции и массивы 7.1. Понятие о подпрограммах В начальный период развития технологий программирования создание программ было основано на использовании управляющих структур – следования, ветвлений, циклов. По мере роста размера программ их структура постепенно усложнялась. Программный код становился все более запутанным, затрудняя внесение изменений, поиск и устранение ошибок. Времени на разработку программы требовалось все больше, но распределить разработку программы между несколькими программистами не было возможности. Таким образом сформировалась необходимость структурировать программу, разделяя ее код на относительно автономные «куски», каждый из которых позволял бы решить некоторую, относительно небольшую, часто типовую задачу. Решение общей задачи складывалось бы из решения отдельных подзадач в определенной последовательности. Средством структурирования больших программ стали подпрограммы. На их применении базируется идеология процедурного программирования. Суть процедурного программирования заключается в следующем. При разработке алгоритмов решения сложных задач применяется метод нисходящего проектирования для решения задачи. Задача поэтапно разбивается на все более простые подзадачи до тех пор, пока эти подзадачи не смогут быть реализованы достаточно простыми алгоритмами. Эти алгоритмы и оформляются в виде подпрограмм. Детализация задачи на более простые подзадачи позволяет:  упростить разработку алгоритмов решения этих подзадач, их тестирование и отладку вследствие их относительной простоты;  распределить разработку алгоритмов и составных частей программы между несколькими разработчиками; Подпрограмма – относительно самостоятельный фрагмент программы, содержащий описание определенного набора действий, оформленный особым образом и имеющий имя. Подпрограмма является реализацией алгоритма решения какой-то задачи, то есть содержит соответствующий набор инструкций. Таким образом, подпрограмма напоминает программу в целом. Также, как и программе, подпрограмме для работы требуются исходные данные, а выполнение подпрограммы должно давать некоторый результат. Между программой и подпрограммой есть существенные отличия: Программа получает исходные данные с помощью операций ввода (с клавиатуры, жесткого диска, по сети и т.д.). Результат работы программы должен быть выведен (на экран, сохранен на жестком диске, передан по сети и т.д.) Подпрограмма может получить свои исходные данные только от вызывающей ее программы (или вызывающей ее другой подпрограммы). При этом операции ввода не используются13. Если результатом работы подпрограммы является некоторое значение, то оно не выводится, а возвращается обратно в вызвавшую ее программу (или другую подпрограмму). Для передачи исходных данных в подпрограмму и возврата результата используются специальный механизм. Этот механизм основан на использовании аргументов подпрограмм и будет рассмотрен далее. 13 если это не является частью алгоритма подпрограммы На этапе разработки подпрограммы (еще до того, как программист начнет писать саму подпрограмму) четко определяется, какой набор исходных данных (сколько значений, смысл и тип каждого) потребуется ей для работы, и какой результат должен быть получен. Результатом выполнения подпрограммы могут быть какие-либо значения, но необязательно. Самостоятельность подпрограмм обеспечивается за счет того, при выполнении подпрограмма должна использовать только заданные ей исходные данные и собственные переменные. Пример 1. Пусть необходимо разработать подпрограмму для вычисления суммы двух чисел. Следует четко оговорить следующее: для работы в подпрограмму должны быть переданы 2 вещественных числа (слагаемые), так как не сказано, что это должны быть целые числа. Результатом подпрограммы, который она должна вернуть в вызвавшую ее программу, будет одно вещественное число (сумма). Пример 2. Пусть необходимо разработать подпрограмму для вычисления корней 2 квадратного уравнения общего вида ax  bx  c  0 . Следует четко оговорить следующее: для работы в подпрограмму должны быть переданы три вещественных числа (коэффициенты уравнения a, b, c). Действительные корни в таком уравнении могут отсутствовать. Поэтому результат подпрограммы – два действительных числа и логическое значение, равное true, если действительные корни есть, и false, если действительных корней нет. При необходимости выполнить некоторую подпрограмму, она должна быть определенным образом вызвана. При вызове подпрограммы указывается ее имя, а также исходные данные, необходимые для выполнения подпрограммы. Результат выполнения подпрограммы зависит от исходных данных, указанных при ее вызове. Вызов подпрограммы может быть самостоятельной инструкцией либо частью инструкции (например, в выражении, см. следующий пример). Подпрограммы в программе на C++ всегда вызываются из других подпрограмм. Та подпрограмма, которую вызвали, называется вызываемой подпрограммой (что-то вроде подчиненного сотрудника). Подпрограмма, в которой содержится вызов другой подпрограммы, называется вызывающей (аналогично начальнику). Одна и та же подпрограмма, как правило является и вызываемой (ее где-то вызывают для выполнения), и вызывающей (в ней вызываются другие подпрограммы). Одну и ту же подпрограмму можно вызывать сколько угодно раз в программе, причем с различными исходными данными. Пример 3. Для вычисления формулы в программе следует вычислять соответствующее выражение: 5 * pow(sin(y), 2) – 2 * (pow(sin(x), 2) * sin(x*y); В этом выражении трижды вызывается стандартная подпрограмма (функция) sin, а исходными значениями для нее (угол в радианах) являются значения вещественных переменных y, x и их произведения соответственно. Кроме того, дважды вызывается функция pow для возведения в квадрат значений, возвращаемых первыми двумя вызовами функции sin. Выясним теперь, как в языке C++ реализовано создание и применение подпрограмм. И в языке C, и в C++ все подпрограммы называются функциями. Но в начале рассмотрим понятия локальных, глобальных переменных, области видимости переменных. 7.2. Локальные и глобальные переменные. Область видимости До сих пор ваши программы представляли собой определение единственной подпрограммы – главной функции (main). Все переменные, необходимые для хранения данных ваших программ, вы определяли в теле главной функции. Точно также переменные можно определять и в других создаваемых программистом функциях. Переменные, определяемые в теле любой функции (в том числе и главной), называются локальными. Локальные переменные создаются в перед каждым выполнением «своей» подпрограммы и уничтожаются при ее завершении. Существует еще возможность объявлять переменные (и константы) вне какой-либо функции. Такие переменные будут называться глобальными. Обычно глобальные переменные объявляют в начале программы, до начала определения функций. Глобальные переменные создаются перед началом выполнения программы и уничтожаются при завершении программы. Место программы, где объявлена та или иная переменная, имеет важное значение. От этого зависит, в какой части программы эту переменную можно будет использовать, а где – нельзя. Часть программы, в которой переменная доступна для использования, называется ее областью видимости. Область видимости локальной переменной начинается с места ее объявления и ограничивается блоком14, внутри которого она объявлена. Область видимости переменной, объявленной в заголовке цикла, ограничена заголовком и телом цикла. Областью видимости глобальной переменной является часть программы, начиная с места ее объявления и до конца данного исходного файла. Таким образом глобальная переменная доступна для использования в любой функции в пределах области видимости. На рис.0 представлен пример программы, демонстрирующей использование локальных и глобальных переменных с обозначением областей их видимости. #include переменная доступна по полному имен ::x переменная скрыта переменная доступна по полному имен ::x int х = 1; // Глобальная переменная x void f() // Определение функции f() { int x = 2; // Локальная переменная x { int x = 3; // Вторая локальная переменная x cout << x << endl; // Выведет число 3 cout << ::x << endl;// Выведет число 1 } cout << x << endl; // Выведет число 2 } void main() // Главная функция программы { f(); // Вызов функции f() int x; // локальная переменная x for (int i(1); i<=3; ++i) { x = i*2; printf("%d\n", x); } cout << x << " " << ::х << endl;// Выведет числа 6 и 1 } обозначение области видимости переменной Рисунок 0. Области видимости переменных 14 Напоминаю: блок – часть программы, ограниченная фигурными скобками. Например, тело цикла – блок, тело функции – тоже блок. В программе могут быть объявлены несколько одноименных переменных в различных блоках. Например, в примере на рис. 0 объявлены несколько локальных переменных x и глобальная переменная x. Их области видимости частично перекрываются, из-за чего возникает конфликт имен. Этот конфликт разрешается путем сокрытия внешних имен для данного блока. Это означат, что, если в данный блок является областью видимости нескольких локальных переменных, то доступной будет та, которая объявлена в блоке с наибольшим уровнем вложенности (напр., вторая локальная переменная x на рис. 0). Остальные одноименные локальные переменные будут скрыты и недоступны. Если на область видимости глобальной переменной накладывается область видимости одноименной локальной переменной, то локальная переменная будет доступна обычным образом, а к глобальной переменной можно будет обратиться по полному имени, при помощи оператора разрешения области видимости (::). Например, на рис.0 к глобальной переменной доступ выполняется так: ::x. Следует по возможности давать переменным разные, информативные имена для лучшей читаемости программы. 7.3. Создание функций в С++ С функциями в языке C++ вы уже сталкивались, начиная с самой первой своей программы. Вопервых, вы использовали (вызывали) в своих программах стандартные математические функции – самые настоящие подпрограммы. Во-вторых, в каждой свой программе вы создаете (т.е. определяете) функцию с именем main – главную функцию программы. Несмотря на свои «главные15» качества, главная функция является самой настоящей подпрограммой и оформляется по тем же правилам, что и все остальные подпрограммы. Создать, или написать, собственную функцию означает определить ее в программе. Определение функции состоит из двух основных частей (рис. 1). Одной из них является тело функции. Выше уже говорилось о том, что любая подпрограмма, подобно программе в целом, содержит инструкции (команды), выполнение которых приведет к решению некоторой задачи. Эти инструкции прописываются именно в теле функции. Тело функции заключается в фигурные скобки, то есть представляет собой блок. Второй частью определения функции является ее заголовок. Он располагается непосредственно над телом функции и содержит имя функции, список ее аргументов в круглых скобках и тип значения, возвращаемого функцией. Заголовок функции еще называют её прототипом, или интерфейсом. Рисунок 1. Структура определения функции Имя функции (ИмяФункции) является идентификатором и используется для обращения к функции (ее вызова) по имени. Имена функций должны отражать их предназначение и различаться для разных функций16. Круглые скобки ( ) после имени функции являются обязательными и служат 15 Выше говорилось, что практически все функции в программе на C++ являются одновременно и вызывающими, и вызываемыми. Исключение представляет главная функция программы. Она не является вызываемой другими функциями, т.к. ее вызов осуществляет Windows при запуске программы. 16 Допускается в C++ создавать функции с одинаковыми именами. При этом функции обязательно должны различаться своими формальными аргументами (количеством, типами). Создание таких одноименных функций в программе называется перегрузкой имен. Подробнее о перегрузке имен функций можно узнать, например, здесь или здесь. отличительной особенностью функций. В круглых скобках указываются так называемые формальные аргументы17 функции (СписокФормАргументов). Формальные аргументы используются для обмена данными между вызываемой функцией и вызывающей программой (подпрограммой), т.е. для передачи в вызываемую функцию исходных данных и, возможно, получения вызывающей функцией результата вызова функции. Количество формальных аргументов может быть произвольным и зависит от количества передаваемых в функцию и возвращаемых из нее данных и их типов. Подробнее формальные аргументы рассматриваются ниже. ТипРезультата – это некоторый тип данных, определяющий тип значения (результата вызова функции), которое функция будет возвращать через свое имя. ТипРезультата может быть практически любым, однако следует помнить, что через свое имя функция может возвратить только одно значение (один объект) того типа, который указан как ТипРезультата. То есть, например, функция может возвращать через свое имя целое число (одно!), символ (один!), но не сможет возвратить массив, даже небольшой. ТипРезультата может быть и пустого типа (void) – это будет указывать на то, что данная функция вообще ничего не возвращает через свое имя – следовательно, нельзя будет, например, запомнить результат вызова функции, присвоив его какой-нибудь переменной. Вызов функции означает команду на ее выполнение и имеет общий вид, представленный на рис. 2. Вызов функции осуществляется по ее имени ИмяФункции, после которого обязательно указываются круглые скобки ( ), в которых, при необходимости, указывается СписокФактАргументов. СписокФактАргументов используется для указания конкретных данных, которые функция будет использовать при выполнении. СписокФактАргументов может состоять из значений, имен переменных, констант, выражений, перечисляемых через запятую. Количество фактических аргументов, их типы и порядок перечисления должны строго соответствовать18 количеству, типам и порядку следования соответствующих формальных аргументов. Рисунок 2. Общий вид вызова функции При вызове функции выполняются следующие действия (см. также пример 6). 1. В самом начале вызова формальные аргументы принимают значения соответствующих фактических аргументов. 2. Создаются локальные переменные, т.е. переменные, объявленные в теле самой функции. 3. Выполняются инструкции, составляющие тело функции. 4. Функция завершается, выполняется возврат результата через имя функции в точку вызова (если предусмотрено) Пример 4. Рассмотрим пример создания простой функции для вычисления среднего арифметического двух чисел. Предварительные рассуждения. Исходными данными будут два числа; так как 17 Во многих источниках по программированию вместо термина «аргумент» часто применяется другой термин – «параметр». 18 В C++ и других языках есть возможность часть формальных аргументов оформить таким образом, что для них не потребуется обязательно указывать соответствующие фактические аргументы. В случае, если фактический аргумент не указан, соответствующий формальный аргумент принимает значение по умолчанию. Такой формальный аргумент называется аргументом по умолчанию. Подробнее см., например, здесь или здесь. конкретный тип не указан, как более универсальный, выбираем вещественный (double). Результатом функции будет одно число – среднее арифметическое. Тип результата, очевидно, также будет вещественным. Зависимость результата от исходных данных можно записать в виде формулы Так как результатом функции будет одно значение, то удобнее будет возвращать его через имя функции. Определение функции в соответствии с проделанными рассуждениями, примет вид: // Функция для вычисления среднего арифметического двух чисел // начало определения функции double AvgVal( double v1, double v2 ) // заголовок { // начало тела функции --double res; // объявляем локальную переменную res = (v1 + v2) / 2; // вычисляем результат (ср. арифм.) return res; // возвращаем результат и завершаем функцию } // конец тела функции --// конец определения функции Пояснения. Заголовок функции включает её имя AvgVal, список формальных аргументов v1 и v2, каждый типа double, тип возвращаемого результата double. В теле функции объявляется локальная переменная res. Далее вычисляется среднее арифметическое и результат вычисления запоминается в переменной res. В конце значение переменной res возвращается с помощью инструкции return, которая при этом завершает выполнение функции. Если немного поразмыслить логически, то можно сделать вывод о том, что локальная переменная res не так уж и нужна. Функцию можно определить гораздо проще, обойдясь без нее: double AvgVal( double v1, double v2 ) { return (v1 + v2) / 2; // вычисляем и сразу возвращаем результат // и завершаем функцию } В этом варианте среднее арифметическое вычисляется непосредственно при выполнении инструкции return и сразу же возвращается в точку вызова. Но этот пример вовсе не означает, что локальные переменные вообще не нужны в функциях. Чтобы это проще было представить, вспомните, что, определяя главную функцию любой программы, вы никак не сможете обойтись без хотя бы одной переменной. А ведь создаваемые в главной функции переменные тоже являются локальными! Пример 6. Рассмотрим пример простейшей программы, в которой среднее арифметическое вычисляется с помощью функции, приведенной в предыдущем примере. Пусть в программе должен выполняться ввод данных пользователем (два числа), вычисление их среднего арифметического с помощью вызова функции AvgVal и печать на экране результата. Определение главной функции будет следующим: void main() { double avg, n1, n2; // ввод исходных данных printf("Введите два числа через пробел...\n"); scanf("%lf %lf", &n1, &n2); // вызов функции для вычисления среднего арифметического // заданных значений и сохранение его в переменной res res = AvgVal( n1, n2 ); // вывод результата на экран printf("Среднее арифметическое чисел %0.1f и 0.1f равно %0.1f.\n", n1, n2, res); printf("\n\nНажмите любую клавишу для завершения программы..."); getch(); } Здесь вызов функции AvgVal является частью инструкции присваивания, которая сохраняет возвращаемый функцией результат в переменную res. Фактическими аргументами здесь выступают переменные n1 и n2. Кстати, подумайте, нельзя ли и в этом примере, аналогично проделанному в предыдущем примере, избавиться от переменной res? 7.4. Аргументы функций Как уже упоминалось выше, аргументы используются в функциях прежде всего тогда, когда необходимо передавать в функцию данные, необходимые для ее выполнения. Так как функция является автономной частью программы, в ней нельзя непосредственно использовать переменные, константы, объявленные не в ней. В то же время, выше также говорилось о том, что, в функции не должен выполняться ввод и вывод данных, если только функция специально не создавалась для этого. Откуда же тогда функция может получить данные, от которых зависит результат ее выполнения? Как раз для этого и используются аргументы. Аргументы бывают двух разновидностей. Аргументы первой из них называются формальными. Они объявляются в заголовке функции при ее объявлении. Их роль сводится к тому, чтобы перед выполнением функции принять и сохранить значения исходных данных, указанных при вызове. Аргументы второй разновидности называются фактическими. Они указываются при вызове функции, содержат конкретные значения, которые и передаются в функцию, сохраняясь в ее формальных аргументах. Формальные аргументы очень похожи на обычные локальные переменные. Они также создаются в начале выполнения функции, во время выполнения функции хранят значения некоторого типа, которое может изменяться. При завершении работы функции формальные аргументы, подобно локальным переменным, уничтожаются. Отличия в следующем: формальные аргументы всегда объявляются в заголовке функции, а локальные переменные – в теле функции. И самое важное: начальными значениями формальных аргументов являются значения соответствующих им фактических аргументов, то есть они задаются вне определения функции. Начальные значения переменных задаются при их объявлении, т.е. в теле функции. В теле функции можно изменять значение формального аргумента, как и обычной переменной. При этом нужно понимать, что на фактический аргумент это не окажет никакого влияния, даже если его имя совпадает с именем формального аргумента. Например, изменим главную функцию из примера 6 следующим образом: void main() { double avg, v1, v2; printf("Введите два числа через пробел...\n"); scanf("%lf %lf", &v1, &v2); // имена факт. арг. такие же, как и формальных в функции AvgVal res = AvgVal( v1, v2 ); printf("Среднее арифметическое чисел %0.1f и 0.1f равно %0.1f.\n", v1, v2, res); printf("\n\nНажмите любую клавишу для завершения программы..."); getch(); } Здесь для хранения исходных значений и в качестве фактических аргументов используются переменные v1 и v2. Несмотря на то, что фактические аргументы функции имеют те же имена, что и формальные аргументы, они являются разными объектами и занимают разные ячейки памяти. Изменение значений переменных v1 и v2 в теле функции невозможно никаким способом! Еще один пример для более явной иллюстрации сказанного: #include #include // функция fun1 int fun1(int x) { x = 15; // локальная переменная функции fun1 printf("Функция fun1: x = %d\n", x); return x; } // главная функция void main() { int x(10); // локальная переменная главной функции printf("До вызова функции: x = %d\n", x); printf("Результат вызова функции: %d\n", fun1(x)); printf("После вызова функции: x = %d\n", x); printf("\n\nНажмите любую клавишу для завершения программы..."); getch(); } В результате выполнения на экране появится следующее: До вызова функции: x = 10 Функция fun1: x = 15 Результат вызова функции: 15 После вызова функции: x = 10 Нажмите любую клавишу для завершения программы... Как вы уже знаете, переменную можно легко превратить в константу, добавив в начало ее объявления ключевое слово const, запретив таким образом изменять ее значение в программе (функции). Точно также можно исключить возможность изменения значения формального аргумента при выполнении функции, сделав его константным. Для этого нужно в начале объявления формального аргумента также указать слово const. Использование константных аргументов позволяет избежать непреднамеренного изменения их значений в тех случаях, когда этого не требуется. При этом снижается вероятность появления связанных с этим ошибок. Подробнее о константных аргументах (и не только) можно узнать здесь. 7.5. Возврат результата из функции Функции были бы бесполезны, если бы не имели возможности «поделиться» результатом своего выполнения с вызывающими их функциями. Если результатом выполнения функции является некоторое значение (объект), то перед завершением работы функция должна вернуть этот результат вызвавшей его функции. Всего существует два способа вернуть из функции данные, полученные при ее выполнении: 1) через имя функции; 2) через формальные аргументы типа указателя либо типа ссылки. Первый способ мы уже упоминали и использовали в примерах выше. Его особенности:  можно вернуть только одно значение (объект) некоторого типа;   результат передается в точку вызова функции; тип результата (не пустой) указывается при объявлении функции перед ее именем;  в теле функции возврат осуществляется с помощью инструкции return выражение; тип выражения должен соответствовать типу, указанному в заголовке функции. Первый способ является типичным для функций, вычисляющих в ходе своего выполнения одно значение. Примерами таких функций могут служить стандартные математические функции: sin, cos, pow и др. Вызов функций, использующих первый способ возврата результата, можно осуществлять в составе выражений. Пример 7. Создадим две функции: MaxVal для определения максимального из двух заданных чисел, и MinVal для определения минимального из двух заданных чисел. Используя созданные функции, а также функцию AvgVal для вычисления среднего арифметического двух чисел из примера 4, напишем программу для определения среднего арифметического максимального и минимального из трех заданных пользователем значений: #include #include // чистое объявление функции (определена в другом месте) double AvgVal( double v1, double v2 ); // определение минимального из двух значений double MinVal( double v1, double v2) { // используем условный оператор ?: return (v1 < v2 ? v1 : v2); } // определение максимального из двух значений double MaxVal( double v1, double v2) { // используем условный оператор ?: return (v1 > v2 ? v1 : v2); } // главная функция void main() { double x1, x2, x3; double minv, maxv, res; // ввод исходных значений printf("Введите три числа через пробел...\n"); scanf("%lf %lf %lf", &x1, &x2, &x3); // определяем максимальное и минимальное значения среди заданных minv = MinVal( MinVal(x1, x2), x3); //вложенный вызов MinVal maxv = MaxVal( MaxVal(x1, x2), x3); //вложенный вызов MaxVal //находим их среднее арифметическое res = AvgVal( minv, maxv ); // вывод результата printf("Срденее арифметическое минимального и максимального " "значений равно %0.1f\n", res); printf("\n\nНажмите любую клавишу для завершения программы..."); getch(); } Функции, возвращающие значение логического типа, часто вызывают в развилках в качестве условия, определяющего выбор варианта выполнения развилки. Пример 8. Пусть в программе необходимо выполнять проверку попадания точки, заданной двумя координатами на плоскости, в квадрат заданного размера с центром в начале координат. Создадим для этой проверки функцию, которая будет возвращать значение true, если точка с координатами x, y попадает в квадрат со стороной sqsize, и false в противном случае: // проверка попадания точки (x,y) в квадрат со стороной sqsize bool PointInSquare(double x, double y, double sqsize) { bool r1, r2; r1 = abs(x) <= sqsize/2; r2 = abs(y) <= sqsize/2; return r1 && r2; } В программе, проверку попадания точки, заданной двумя переменными x1 и y1, в квадрат с длиной стороны 2, можно выполнить следующим образом: //... // пример развилки: if (PointInSquare(x1, y1, 2)) printf("Точка (%0.1f, %0.1f) находится в квадрате\n", x1, y1); else printf("Точка (%0.1f, %0.1f) не попала в квадрат\n", x1, y1); //... Второй способ возврата результата функции используется обычно в двух случаях (не исключающих друг друга):  когда функция должна возвратить сразу несколько значений (объектов);  когда возвращаемое значение (объект) занимают много места в памяти; тогда возврат такого объекта через формальный аргумент будет более быстрым и экономичным по расходу памяти. Пример 9, иллюстрирующий первый случай. Необходимо создать функцию для вычисления координат середины отрезка, заданного на плоскости координатами своих концов. Таким образом, исходными данными для функции должны быть две пары координат, т.е. 4 вещественных значения. Результатом будет пара вещественных чисел – координат середины отрезка. Учитывая, что невозможно через имя функции возвратить два значения одновременно, воспользуемся вторым способом, а именно, для возврата результата создадим дополнительно два формальных аргумента типа указателя. При вызове через эти два аргумента функция получит адреса двух переменных. Координаты середины отрезка будут записаны в эти переменные по их адресам в памяти. Функция таким образом примет вид: // вычисление координат середины отрезка ((x1,y1), (x2,y2)) void Center(double x1, double y1, double x2, double y2, double *xc, double *yc) { *xc = (x2+x1)/2; *yc = (x2+x1)/2; } Для получения доступа к переменным по их адресам к указателям xc и yc применяется операция разыменования *. Вызов функции может быть выполнен следующим образом: double Xc, Yc; Center(12, 10, 0, -44, &Xc, &Yc); printf("Середина отрезка имеет координаты " "(%0.1f, %0.1f ).\n", Xc, Yc); Переменными, в которые функция записывает свой результат, здесь являются Xc и Yc. Их адреса, получаемые с помощью операции разадресации &, являются 5-м и 6-м фактическими аргументами при вызове функции Center. Пример позволяет сделать вывод, что функции, подобные Center, благодаря формальным аргументам типа указателя получают возможность обращаться к переменным (для чтения значений и/или изменения их), объявленным вне функции (т.е. внешним по отношению к ней), что напрямую сделать было бы невозможно. 7.6. Функции и массивы Массивы применяются для хранения данных чуть ли не в каждой программе. Очень часто возникает необходимость массив, созданный в одной функции (например, в главной), передавать для обработки в другие функции. При этом требуется учитывать ряд моментов, связанных с внутренним устройством массивов в C++, таких как:  массив в программе на C++ неявно представляет собой указатель на начальный элемент, т.е. для получения адреса массива в памяти нужно просто указать имя массива;  в массиве не хранится никакой информации о его размере. Поэтому при передаче массивов в функцию используются:  один формальный аргумент типа указателя на начальный элемент массива;  один (для одномерных массивов) или несколько (для многомерных массивов) формальных аргументов беззнакового целого типа для передачи размера(ов) массива. Пример 10. Создадим функцию, для поиска максимального значения в одномерном целочисленном массиве. В соответствии со сказанным выше функция будет иметь один формальный аргумент типа указателя на целое значение для получения адреса начального элемента массива и еще один аргумент целочисленного типа для получения количества элементов в массиве. Тип возвращаемого через свое имя значения будет таким же, как и тип элементов массива. Функция будет иметь вид: // поиск максимального значения в массиве int MaxItem(int * Arr, int size) { int i; int res(Arr[0]); for (i=0; i lim) Arr[i] = lim; } // никакого return не требуется - результат // уже "возвратился" в вызывающую программу } Программа для иллюстрации работы функции: #include #include // функция определена выше, поэтому здесь – ее чистое объявление void LimitArray(double * Arr, int size, double lim); void main() { const int N(10); int i; // объявляем массив с инициализацией его элементов double X[N] = {-3, 0.1, -90.3, 5, 62, 3.2, 0, -7, 52, 89.1}; // выведем исходный массив на экран printf("Массив до изменения...\n"); for (i=0; i ) ВСЕ функции работают только с C-строками! //ввод с клавиатуры C-строки (можно с пробелами) в массив b выполняемая при создании в памяти самой переменной (константы). Сами начальные значения называются инициализаторами и указываются при объявлении переменной (константы). Простой пример объявления с инициализацией: double x(0.18); // полужирным выделен инициализатор переменной x. char *gets(char *b); //вывод на экран C-строки из массива b int puts(char *b); // Копирование из q в p (включая конец строки) char *strcpy(char *p, const char *q); // Добавление q в p (включая конец строки) char *strcat(char *p, const char *q); // Копирование n символов из q в p char *strncpy(char *p, const char *q, int n); // Добавление n символов из q в p char *strncat(char *p, const char *q, int n); // Длина p (не считая конца строки) size_t strlen(const char *p); // Сравнение p и q int strcmp(const char *p, const char *q); // Сравнение первых n символов в p и q int strncmp(const char *p, const char *q, int n); // Поиск первого вхождения c в p char *strchr(char *p, int c); const char *strchr(const char *p, int c); // Поиск последнего вхождения c в p char *strrchr(char *p, int c); const char *strrchr(const char *p, int c); // Поиск первого вхождения q в p char *strstr(char *p, const char *q); const char *strstr(const char *p, const char *q); // Поиск в p первого вхождения символа из q char *strpbrk(char *p, const char *q); const char *strpbrk(const char *p, const char *q); // Номер первого символа из p (нумерация с нуля), // не встретившегося в q size_t strspn(const char *p, const char *q); // Номер первого символа из p (нумерация с нуля), // встретившегося в q size_t strсspn(const char *p, const char *q); Простой пример программы, для обработки строковых данных: // библиотека консольного ввода/вывода в стиле C #include // библиотека доп. функций консольного ввода/вывода #include // библиотека стандартн. строковых функций #include // Главная функция программы void main() { // 1-я строка char szS1[] = "В лесу родилась елочка, \n"; // 2-я строка char szS2[] = "в лесу она росла..."; // символьный массив для поэмы целиком char szPoem[100]; //копирование 1-й строки из szS1 в szPoem strcpy(szPoem, szS1); //добавление 2-й строки из szS2 в szPoem strcat(szPoem, szS2); // выводим поэму printf("Поэма:\n\n\n"); // некий набор (множество) символов char szSymSet[] = "ёклмн"; // ищем номер 1-го символа из szPoem, совпавшего // с символом из множества szSymSet size_t num = strcspn(szPoem, szSymSet); // выводим результат поиска printf("\nПервым символом из набора \"%s" "\", встреченным в поэме, \nстал символ " "\'%c\'.\n", szSymSet, szPoem[num]); // ожидаем нажатия клавиши перед завершением программы getch(); } Результат выполнения программы: Поэма: В лесу родилась елочка, в лесу она росла... Первым символом из набора "ёклмн", встреченным в поэме, стал символ 'л'. Пример задачи на обработку строковых данных Задача: разработать алгоритм и программу для поиска заданной пользователем последовательности символов в строке, также вводимой пользователем. Программа должна находить все последовательности, совпадающие с заданной, и выводить номера символов в начале каждой найденной последовательности. Пример готового решения задачи: Дана искомая последовательность символов: Таня Дана строка: Наша Таня громко плачет – наша Таня плачет в рупор Результат, выводимый программой: 5 32 Алгоритм решения задачи Предварительные замечания:  для хранения C-строк будем использовать обычные символьные массивы  для ввода строк с клавиатуры будем использовать стандартную функцию gets  для определения длины C-строки (не учитывая «нулевой» символ) ипользуем стандартную функцию strlen  для поиска последовательности символов в строке будем использовать стандартную функцию strstr  для представления строковых данных будем использовать C-строки  будем использовать связь массивов и указателей: имя массива можно использовать как указатель на начальный элемент массива Справка: Функция strstr(str, strSearch) ищет в строке str первую встреченную последовательность символов, совпадающую с заданной в строке strSearch. Если последовательность найдена, то возвращается адрес первого её символа в строке str. Иначе функция возвращает ноль. Алгоритм (неформализованная форма записи): Вводим строку в массив S Вводим последовательность символов в массив FS Определим и запомним в переменной FSlen длину строки FS Определим и запомним в переменной Slen длину строки S Запомним адрес начала строки S в указателе pS Создадим указатель pT и скопируем в него pS Выведем на экран строку: "Результат: номера начальных символов, с которых начинается последовательность <такая-то>: " Цикл-пока pS < S + Slen (пока адрес в pS не станет больше адреса последнего символа строки S) Вызываем функцию: pT = strstr(pS, FS) Если pT равен 0, то прерываем цикл Все-если Вычисляем номер символа в найденной последовательности через разность указателей: num = pT-S Выводим на экран значение num Указатель pS изменяем так, чтобы он хранил адрес символа, следующего за последним символом в найденной последовательности: pS = pT + FSlen Все-цикл Программа: // подключение библиотек #include #include #include // главная функция void main() { // создаем символьные массивы const size_t Ssize(100); char S[Ssize], FS[Ssize]; // ввод исходной строки printf("Введите строку: "); gets(S); // ввод искомой последовательности символов printf("Введите искомую последовательность" "символов: "); gets(FS); // вычисление длины C-строк FS и S size_t FSlen = strlen(FS); size_t Slen = strlen(S); //объявляем указатели и целочисл. переменную char *pS, *pT; size_t num; // копируем адрес первого символа строки S // в оба указателя pT = pS = S; printf("Результат: номера начальных " "символов, с которых начинается\n " "последовательность \"%s\": \n\n", FS); // начинаем цикл поиска while(pS < S + Slen) { // ищем искомую последовательность в строке, // начинающейся в ячейке памяти с адресом pS pT = strstr(pS, FS); // если ничего больше не найдено, // то останавливаем цикл if (!pT)// то же самое, если (pT == 0) break; // вычисляем номер первого символа // найденной последовательности num = pT - S; // печатаем его на экране printf(" %d\n", num); // вычисляем адрес символа, следующего за // последним в найденной последовательности // в строке S pS = pT + FSlen; } // завершаем работу программы printf("\nДля завершения программы " "нажмите любую клавишу..."); getch(); } ЛЕКЦИЯ 9. ФАЙЛОВЫЙ ВВОД-ВЫВОД (ДОПОЛНИТЕЛЬНАЯ ТЕМА) Изучаемые разделы: Общие сведения о файлах Общая процедура работы с файлами. Типы файлов в языке C/С++. Файловый ввод/вывод в стиле языка C Файловый ввод/вывод в стиле языка C++ 9.1. Общие сведения о файлах Файл представляет собой именованную последовательность однотипных элементов (в общем случае байтов), хранимых на внешнем устройстве, чаще всего на диске (далее будем подразумевать, что файл находится именно на диске). Организация хранения информации на некотором устройстве хранения в виде файлов, а также доступ к ним, обеспечиваются с помощью файловой системы. Примерами распространенных файловых систем являются FAT32, NTFS, ext, HFS и др. Любой файл имеет три характерные особенности:  у него есть имя, что позволяет программе одновременно работать с несколькими файлами; имя файла однозначно идентифицирует его в файловой системе;  информация, хранимая в файле может быть однородной, представимой в виде совокупности однотипных элементов (структур, значений, символов и т.п.) или неоднородной, в виде совокупности значений и структур данных различного типа и размера, записанных в файл в некоторой определенной последовательности;  размер файла определяется только объемом хранящихся в нем данных, может динамически изменяться в процессе работы с ним и ограничивается только емкостью дисковой памяти. Файл имеет много общего с одномерным динамическим массивом, однако размещается не в оперативной, а во внешней памяти и не требует предварительного указания размера. Имя файла — строка символов, однозначно определяющая файл в некотором пространстве имён файловой системы (ФС), обычно называемом каталогом, директорией или папкой. Имена файлов строятся по правилам, принятым в той или иной файловой и операционной системах (ОС). Имя файла (иногда называемое коротким именем файла) является частью полного имени файла, также называемого полным или абсолютным путём к файлу. Полное имя включает путь доступа к файлу, формат которого зависит от используемой операционной системы и/или типа устройства, на котором хранится файл. Имя файла необходимо для того, чтобы его уникальным образом идентифицировать в пределах каталога, которому принадлежит файл. В одном каталоге не может быть двух файлов с одинаковыми именами. Полное имя файла уникальным образом идентифицирует файл в пределах операционной системы (на компьютере в целом). Короткое имя файла обычно состоит из двух частей, разделенных точкой:  название (до точки, часто также называют именем);  расширение (необязательная часть). Расширение в среде Windows используется операционной системой для распознавания типа файла и связывания его с приложением, предназначенным для работы с файлами данного типа. Но расширение файла физически никак не связано с фактическим содержимым файла и может ему не соответствовать (например, никто не запрещает изменить расширение файла изображения в формате JPEG с jpg на txt, в этом случае содержимое файла никак не изменится, однако программой по умолчанию для этого файла станет текстовый редактор Блокнот). В программах на языке C имена файлов задаются с помощью C-строк. Например, имена файлов могут иметь вид: "list.dat", "c:\\Мои документы\\Отчеты\\report01.txt" и т.п. Двойной слеш в полных именах файлов объясняется тем, что сам символ '\' в строках на языке C/C++ воспринимается не как самостоятельный символ, а как часть составных символов, например, таких как '\0', '\n', '\t', '\"' и др. Для того, чтобы задать символ «слеш» как самостоятельный символ в составе строки, используется также специальное составное обозначение '\\'. 9.2. Общая процедура работы с файлами. Типы файлов в языке C/С++ Операции, в которых участвуют файлы, можно разделить на две группы:  операции, выполняемые над файлом, как единым объектом файловой системы;  операции, выполняемые над данными, хранящимися в файле; В первую группу входят такие операции, как создание, удаление, копирование, переименование файла, изменение его атрибутов («скрытый», «системный», дата создания и др.). Эти операции реализованы в виде функций, входящих в библиотеки в составе языков программирования. Эти операции далее в лекции не рассматриваются, информацию о реализации этих действий в программе можно получить в литературе, в справочной документации или в интернете. Вторая группа включает операции, основными из которых являются операции файлового ввода-вывода:  операции записи данных в файл (относятся к операциям вывода20 данных);  чтения данных из файла (относятся к операциям ввода данных). Кроме того, к этой группе относятся вспомогательные операции, используемые для подготовки и в процессе работы с файлом. К ним относятся функции для открытия, закрытия файла, определения и задания положения указателя текущей позиции в файле, определения момента достижения конца файла при чтении и другие. Существует стандартная схема осуществления доступа к файлу для чтения или записи из/в него данных, включающая этапы: 1) открытие файла для чтения, записи или в комбинированном режиме; 2) чтение и/или запись данных, а также, возможно, выполнение вспомогательных операций; 3) закрытие файла. Открытие файла подразумевает его «бронирование» конкретной программой для осуществления этой программой некоторых разрешенных для этого режима операций файлового ввода-вывода. Это бронирование будет действовать до тех пор, пока файл не будет закрыт. На время, пока файл открыт одной программой, некоторые операции с ним будут для других программ заблокированы операционной системой. Например, если файл открыт одной программой для записи в него данных, то все остальные программы не смогут в то же время ни прочитать из него, ни записать в него данные. Если же файл 20 Следует помнить, что операции ввода – это операции, в которых данные считываются с устройства ввода и записываются в оперативную память для последующей работы с ними. В операциях вывода данные, наоборот, из оперативной памяти направляются на некоторое устройство вывода. В случае чтения/записи в файл устройством и ввода и вывода выступает устройство (например, жесткий диск, флешка или сетевое хранилище), на котором хранится файл, причем физическая суть и расположение этого устройства не имеют значения с точки зрения программного кода, реализующего эти операции. открыт для чтения, то другие программы в то же время смогут читать из этого файла данные, но не смогут ничего записать. Поэтому режим, в котором открывается файл, часто очень важен, т.к. дает возможность регулировать одновременный доступ к данным файла нескольким программам. Реализация приведенной схемы может быть выполнена на базе различных библиотек и различаться по «внешнему виду» в программном коде. Однако указанные этапы обязательны21 независимо от используемых средств и языка программирования. Все файлы в зависимости от того, как интерпретируется22 их содержимое, делятся в языке C/C++ на две группы:  бинарные файлы;  текстовые файлы. Бинарный файл – файл, содержащий данные, которые в общем случае могут быть произвольного типа и структуры. На самом низком уровне данные, содержащиеся в бинарном файле, можно воспринимать, как последовательность байтов данных, нумеруемых от 0 до последнего байта данных в этом файле (аналогично тому, как организована оперативная память). Большинство файлов следует относить к этому типу. Работа с бинарными файлами естественным образом подразумевает возможность произвольного доступа к данным файла, т.е. можно равно легко записывать и считывать данные из любого места файла. Текстовый файл – файл, содержащий информацию, которая может быть интерпретирована как текст, воспринимаемый человеком. Текстовые файлы содержат информацию в виде совокупности символьных строк произвольной длины, разделяемых символами конца строки. В операциях ввода-вывода с текстовыми файлами элементом данных может выступать как отдельный символ, так и строка. В основном, при работе с текстовыми файлами реализуется последовательный доступ к данным. Текстовый файл, при необходимости, можно обрабатывать и как бинарный. Для каждого типа файла предусмотрен «собственный» набор функций, реализующих основные и вспомогательные операции, часть функций доступна для использования с любым типом файла. Тип файла вместе с режимом доступа указывается при открытии файла. Задавая режим открытия файла, в особенности тип файла, необходимо понимать, что в первую очередь указанный тип файла определяет то, каким образом будет организован процесс чтения и/или записи данных. Решая вопрос, в файл какого типа (бинарный или текстовый) записать, например числовые данные из матрицы, нужно учесть следующее:  если нужна возможность открыть созданный файл в текстовом редакторе, чтобы непосредственно воспринимать или даже редактировать информацию в нем, то однозначно выбирается тип «текстовый»;  файл используется как бинарный, если: o важна скорость выполнения файлового ввода-вывода (операции с текстовым файлом медленнее); o структура данных, записываемых в файл, соответствуют некоторому стандартному формату, который должны понимать и другие программы (например, нужно записать изображение в стандартном формате JPEG или аудиоданные в формате mp3 и т.д.); o записываемые данные не предназначены для непосредственного восприятия человеком – например, те же аудиоданные в виде сплошного потока чисел интереса для человека не представляют; 21 При использовании некоторых библиотек (стилей) для осуществления файлового ввода-вывода операции открытия, закрытия файла могут выполняться неявно и не требуют использования специальных инструкций. 22 Любой файл можно воспринимать и как текстовый, и как бинарный. Однако имеет смысл тип файла определять, исходя из того, какие данные, и каким образом, в него были записаны. o записываемые данные заранее подготовлены в памяти в виде одного сплошного непрерывного «куска» данных – их можно записать в файл за одну операцию вывода. Так же можно и прочитать данные одним куском, а затем, если нужно, уже в памяти разложить данные «по полочкам». Такой подход позволяет дополнительно повысить скорость обмена данными с файлом. Рассмотрим далее, как реализуется приведенная выше схема работы с файлами, если ввод-вывод осуществляется средствами языка C (в стиле языка С). Эти средства доступны и вполне актуальны и при программировании на языке C++, хотя там имеются собственные, и гораздо более разнообразные инструменты, основанные на объектно-ориентированном подходе. 9.3. Файловый ввод/вывод в стиле языка C «Представителем» файла, который участвует в операциях ввода-вывода, в программном коде является специальная переменная, которая называется файловой переменной. В различных языках программирования называться эта переменная может по-разному, но ее предназначение одно и то же – в ней хранится информация об открытом файле, режиме доступа к нему, а также параметры текущего состояния процесса ввода-вывода, такие как номер текущей позиции в файле, признак достижения конца файла и др. В языке C эта переменная фактически является структурой стандартного типа FILE, а в программе объявляется в виде указателя на FILE, например: FILE * file; // объявление файловой переменной Само по себе объявление файловой переменной еще не означает выполнения каких-либо операций над файлом, но все последующие файловые операции обязательно требуют указания файловой переменной в качестве одного из параметров. Открытие файла После того, как файловая переменная объявлена, можно начинать реализовывать стандартную схему работы с файлом. И первым делом файл необходимо открыть в определенном режиме доступа, указав тип открываемого файла. Для этого используется функция fopen с двумя формальными аргументами: FILE * fopen(const char * FileName, const char * ModeAccess); Аргументами функции являются: FileName – строка, содержащая полное или короткое имя файла; ModeAccess – строка, в которой закодирован режим доступа к файлу и тип файла. Режимы доступа могут быть следующими:  режим чтения – аргумент ModeAccess должен содержать символ 'r'; при открытии проверяется, существует ли файл, если да, то открывается, в противном случае возникает ошибка доступа к файлу;  режим чтения и записи – аргумент ModeAccess должен содержать символ 'w', при открытии файла, если он не существует, то создается новый пустой файл с именем заданным в аргументе FileName, если существует, то его содержимое уничтожается.  режим чтения с добавлением в конец – аргумент ModeAccess должен содержать символ 'a'; при открытии файл не уничтожается, данные могут добавляться только в конец файла. Тип файла кодируется символами 'b' (бинарный) и 't' (текстовый), также включаемыми в строку ModeAccess. Функция fopen возвращает адрес (указатель) структуры FILE, которая в дальнейшем будет использоваться в последующих операциях с файлом вплоть до его закрытия. Примеры вызова функции fopen для открытия файлов в различных режимах: FILE * file, *file1, *file2; file = fopen("list.dat", 'rb'); // режим чтения бинарного файла list.dat file1 = fopen("image.gif", 'wb'); // режим записи и чтения бинарного файла file2 = fopen("input.ini", 'tr'); // режим чтения текстового файла После открытия файла необходимо убедиться, что файл был открыт успешно, т.к. если открыть файл не удалось, то дальнейшие операции с ним будут невозможны. Файл был открыт успешно, если значение файловой переменной стало ненулевым. В противном случае файл не был открыт по некоторой причине23. Например так: char [] fname = "list.dat"; FILE * file, *file1, *file2; file = fopen(fname, 'rb'); // режим чтения бинарного файла if (file == 0) { printf("Не удалось открыть файл %s. Возможно, файл не fname); exit(-1); } // продолжаем работу с файлом... существует.\n", Закрытие файла Эта операция завершает работу с открытым ранее файлом. Реализуется функцией fclose. Функция имеет всего один формальный аргумент – файловую переменную: int fclose( FILE * file); Если файл успешно закрыт, то функция возвращает 0. В противном случае возвращается ненулевой код ошибки. Обычно проверка результата, возвращаемого этой функцией, не требуется. Рассмотрим далее операции чтения и записи в бинарный файл. Ввод и вывод в бинарных файлах Запись в файл Запись данных в файл является операцией вывода. Рассмотрим вначале, как данные записываются в бинарный файл. Для этого используется функция fwrite, называемая функцией блочного вывода: int fwrite( const void *buffer, int size, int count, FILE *file ); Функция имеет 4 аргумента:  buffer - указатель на записываемые данные;  size - размер элемента, в байтах;  count - максимальное число записываемых элементов;  file – файловая переменная. Функция fwrite записывает count элементов (каждый длиной size) из buffer в файл file. Номер текущей позиции файла, связанный с file, возрастает на число фактически записанных байт. С помощью однократного вызова этой функции в файл можно записать одиночное 23 Например, файл, открываемый для чтения, не существует; открываемый в любом режиме файл уже открыт другой программой для записи; или устройство ввода/вывода недоступно… Узнать, произошла ли ошибка в последней выполненной операции с файлом, можно, вызвав функцию ferror, которая вернет 0, если ошибок нет, и ненулевое значение в противном случае. значение некоторой переменной, в том числе типа структуры, массив произвольной длины, весь, или частично. Например, необходимо записать в файл, заданный файловой переменной file, одно целое значение из переменной value (во всех приведенных ниже примерах предполагается, что файл предварительно открыт в подходящем режиме, а файловой переменной является file): int value = 100; fwrite (&value, sizeof(int), 1, file); Для вычисления размера переменной используется специальный оператор sizeof. Таким образом, функция запишет в файл file один элемент данных размером 4 байта (размер значения типа int), расположенный в памяти в переменной по адресу, вычисленному с помощью разадресации переменной value. Еще пример – запись в файл массива элементов типа double: double array[] = {0.0, 10.5, -5.32, -0.01, -0.01}; // например, такой массив fwrite (array, sizeof(double), 5, file); Здесь функция записала в файл file 5 элементов данных, каждый размером 8 байт, из массива array. Разадресация имени массива не нужна, т.к. имя массива неявно является указателем на начальный элемент массива. Если нужно записать в файл несколько значений, хранящихся в разных переменных, то понадобится несколько раз вызвать функцию fwrite. Например, запишем в файл значения трех переменных различных типов, включая массив: int x = 19; const double pi = 3.14159; char st[100] = "Сьешь еще мягких французских булок!"; fwrite(&x, sizeof(int), 1, file); fwrite(&pi, sizeof(double), 1, file); fwrite(st, sizeof(char), 100, file); Каждая последующая операция записи в файл записывает данные непосредственно за данными, записанными в предыдущей операции записи, т.е. начинает запись в ту позицию файла, на которой установлен указатель текущей позиции. После записи данных указатель автоматически перемещается на байт файла, следующий за последним записанным байтом (или на конец файла). Это избавляет программиста от необходимости каждый раз вручную указывать место в файле, куда надо записать очередное значение. Чтение из файла Используется функция fread. Схема ее применения аналогична функции fwrite, с учетом изменения направления передачи данных на противоположное. Функция также имеет 4 аргумента: size_t fread( void *buffer, size_t size, size_t count, FILE *stream ); Смысл аргументов тот же, что и в fwrite:  buffer - указатель на область памяти, куда запишутся прочитанные из файла данные;  size - размер одного элемента, в байтах;  count - максимальное число читаемых из файла элементов;  file – файловая переменная. Функция fread считывает до count элементов размером size байт из входного file и сохраняет их в buffer. Указатель файла, связанный с file увеличивается на число фактически считанных байтов. Примеры (надеюсь, в пояснениях не нуждаются): Чтение из файла одного целочисленного значения: int value; fread (&value, sizeof(int), 1, file); Чтение из файла пяти вещественных значений и запись их в массив double array[10]; // например, в такой массив (далее будет заполнен наполовину) fread (array, sizeof(double), 5, file); Чтение из файла целочисленного значения, затем вещественного, затем 100 символов (строку) int x; double pi; char st[100]; fread (&x, sizeof(int), 1, file); fread (&pi, sizeof(double), 1, file); fread (st, sizeof(char), 100, file); Ввод и вывод в текстовых файлах Для работы с текстовыми файлами предусмотрено гораздо большее количество функций, как для ввода, так и для вывода. Рассмотрим примерную классификацию различных способов файлового ввода-вывода текстовых данных. Файловый ввод/вывод может отличаться наличием преобразования данных в/из различных типов данных в строковый:  средства ввода-вывода данных различных типов из/в текстовых файлов;  средства ввода-вывода данных символьного или строкового типов данных без преобразования. И здесь также два варианта: o посимвольный ввод-вывод; o построчный ввод-вывод. Ввод-вывод данных различных типов из/в текстовых файлов Для записи в файл значений различного типа (возможна запись целочисленных, вещественных, символьных значений) применяется функция fprintf. Эта функция работает аналогично известной функции printf, которая используется для вывода данных на экран в текстовом виде. Функция fprintf отличается от нее только тем, что вместо вывода на экран текст записывается в указанный текстовый файл. Например, если в программе выполнится команда вида printf("%d", 100); то на экране отобразится строка 100 Если же выполнится команда fprintf(file, "%d", 100); то вместо экрана строка "100" будет записан в заданный файловой переменной file текстовый файл в текущую позицию (обычно в конец файла). Еще пример: int a=10, b=3, c=-250; const double pi = 3.14159; fprintf(file, "%d %d, %d", a, b, c); fprintf(file, "\n%10.4f\n", pi); fprintf(file, "To be continued..."); в результате выполнения которого в файле окажется следующее содержимое: 10 3 -250 3.1416 To be continued... Чтение данных из текстового файла с их преобразованием к некоторому типу и сохранением в переменных может быть осуществлено с помощью функции fscanf. Эта функция работает также, как и функция scanf, используемая для ввода значений с клавиатуры, однако строку символов, которую функция scanf получает с клавиатуры, функция fscanf считывает из файла. Окончанием операции ввода считается считанный из файла символ пробела, символ окончания строки либо символ конца файла. На практике функция fscanf редко используется для чтения текстовых файлов, поэтому далее не рассматривается. Посимвольный ввод-вывод из/в текстовых файлов Для посимвольного чтения данных из файла используется функция fgetc. Она имеет следующий формат: int fgetc( FILE *file ); Ее единственным аргументом является файловая переменная file. Возвращает функция целочисленный код считанного из файла символа. Несмотря на «целочисленность» возвращаемого результата, его можно смело присваивать символьной переменной (имеющей тип char), при этом будет автоматически выполнено неявное преобразование целого числа в символьное значение. Например: char c, c1; c = fgetc(file); c1 = fgetc(file); При этом из файла будет прочитано два символа, начиная с текущей позиции файла, первый символ будет сохранен в переменной c, а второй – в c1. Обычно посимвольное чтение из файла используют тогда, когда алгоритм обрабатывает каждый символ по отдельности. Но все же, если файл большой, чтение из него будет выполняться быстрее, если читать из него данные не посимвольно, а построчно. Для посимвольной записи данных в файл используется функция fputc. Ее формат следующий: int fputc( int c, FILE *file); Функция записывает в файл file символ с. Пример ее использования: char c; scanf("%c", &c); // вводится символ с клавиатуры и записывается в переменную c fputc(c, file); // введенный ранее символ из переменной c записывается в файл file Построчный ввод-вывод из/в текстовых файлов Для построчной записи в файл используется функция fputs. Ее формат следующий: int fputs( const char *str, FILE *file ); В отличие от функции fputc, здесь первым аргументом является указатель на символьный массив, содержащий C-строку. Эта C-строка записывается в файл, заданный файловой переменной file. Нулевой символ в файл не записывается. Функция также не записывает в файл символы конца строки, т.е. при необходимости эти символы надо включать в сами строки, например: char s1[] = "Первая строка"; char s2[] = "Следующая строка\n"; // в конец добавлен символ - разделитель строки fputs(s1, file); fputs(s2, file); fputs("И последняя строка", file); Содержимое файла в этом случае получится таким: Первая строкаСледующая строка И последняя строка Построчное чтение реализуется функцией fgets. Функция имеет формат: char *fgets( char *str, int n, FILE *file ); Аргументы функции:  str – указатель на массив, в который будет записана прочитанная из файла строка;  n – наибольшее число символов для чтения из файла (эта величина должна быть равна длине массива str);  file – файл, из которого выполняется чтение строки. Функция из файла считывает символы, начиная с текущей позиции, и до выполнения любого из следующих условий:  считан первый символ перевода строки,  достигнут конец файла,  число считанных символов стало равно n – 1. К результату, помещенному в str, добавляется символ '\0'. Символ конца строки ('\n'), если он прочтен, включается в str. Пример использования функции fgets: const int N(5); // задано маленькое значение для наглядности примера ниже char buffer[N]; while (!feof(file)) // пока конец файла не достигнут... { fgets(buffer, N, file); // читаем строку из файла puts(buffer); // выводим строку на экран из buffer } В примере для сохранения считанных строк используется символьный массив buffer длиной 5 символов. Чтение строк из файла и их вывод на экран осуществляется в цикле, который прекращает работу, если функцией fgets при очередном вызове достигнут конец файла. Для определения момента достижения конца файла в заголовке цикла вызывается функция feof, которая возвращает ненулевое значение, если конец файла достигнут, и ноль в противном случае. Например, если текстовый файл имеет вид Мячик. Наша Таня громко плачет: Уронила в речку мячик. – Тише, Танечка, не плачь: Не утонет в речке мяч. В тексте выделены фрагменты, которые будут считаны из файла в последовательных вызовах функции fgets. Можно проанализировать, какое из приведенных условий окончания чтения строки срабатывает в каждом случае вызова функции fgets. Пример Во всех вышеприведенных примерах предполагалось, что файл, с которым работают функции ввода-вывода, уже предварительно открыт в требуемом режиме. Рассмотрим содержательный пример, в котором технология работы с файлом демонстрируется полностью. Пусть дан исходный текстовый файл source.txt. Необходимо, чтобы наша программа записала в выходной файл firstsymbols.txt первые символы каждой строки файла source.txt, разделяя их запятыми с пробелом. Если в исходном файле строка начинается с пробелов и/или символов табуляции ('\t'), то должен быть считан первый символ – не пробел и не табуляция. Листинг программы: #include #include #include #include int main() { setlocale(LC_ALL, "Rus"); const char srcFName[] = "d:\\temp\\source.txt"; const char destFName[] = "d:\\temp\\firstsymbols.txt"; FILE * fin, *fout; // файловые переменные (файловые потоки) fin = fopen(srcFName, "rt"); // открываем входной файл для чтения if (!fin) { printf("Ошибка при открытии файла %s\n", srcFName); getch(); return -1; } fout = fopen(destFName, "wt"); // открываем выходной файл для записи if (!fout) { printf("Ошибка при открытии файла %s\n", destFName); getch(); return -1; } const int N(255); char buffer[N]; char c; int sLen; int count(0); // буферный массив для строк // длина прочитанной строки // счетчик прочитанных строк printf("Начинаем обработку данных...\n\n"); while(!feof(fin)) // пока не достигнем конца выходного файла { fgets(buffer, N, fin); // читаем строку sLen = strlen(buffer); // определяем ее длину c = '\0'; for (int i(0); i 0) fputs(", ", fout); // записываем в выходной файл // разделительные символы fputc(c, fout); // записываем символ } if (ferror(fin)) // если произошла ошибка чтения вх. файла { printf("Ошибка чтения файла %s\n", srcFName); break; } if (ferror(fout)) // если произошла ошибка записи в вых. файл { printf("Ошибка записи в файл %s\n", destFName); break; } ++count; } // после завершения ввода-вывода необходимо закрыть оба открытых файла fclose(fin); fclose(fout); printf("Обработка данных завершена.\n"); getch(); return 0; } В программе одновременно открываются и входной, и выходной файлы, соответственно, для чтения и для записи. Если файлы открыты успешно, начинается процесс построчного чтения данных из входного файла, обработки и записи обработанных данных в выходной файл. Запись осуществляется с применением посимвольного (функция fputc) и построчного вывода (fputs). Операции ввода и вывода выполняются в цикле, завершение работы которого происходит в случае, если достигнут конец файла (функция feof возвращает ненулевое значение) или произошла ошибка чтения входного файла либо записи в выходной файл (функция ferror вернула ненулевое значение). После завершения вводавывода оба открытых файла закрываются. Пример исходного файла: CloneSpy v2.11 ~~~~~~~~~~~~~~ Application for finding and deleting duplicate files. For Windows 98se, ME, NT4.0, 2000, and XP. Why was CloneSpy written? ~~~~~~~~~~~~~~~~~~~~~~~~~ Do you often download files from the Internet? Is your hard drive crowded with these files? Have you ever asked yourself which files you have downloaded more than once? Perhaps you have burned files to a CD and retrieved them again? Do you want to find these files and eliminate the duplicates? Maybe you want to find duplicate files without checking your entire collection of backup CDs every time? Then CloneSpy is the right tool for you! Выходной файл получится таким: C, ~, A, F, W, ~, D, t, t, y, f, e 9.4. Файловый ввод/вывод в стиле языка C++ Файловый ввод/вывод в стиле языка C++, так же, как и консольный вывод, использует объектно-ориентированный подход и основан на использовании операторов ввода ">>" и вывода "<<" совместно со специальными объектами, обозначающими файловые потоки. ЛЕКЦИЯ 10. СТРУКТУРЫ (ДОПОЛНИТЕЛЬНАЯ ТЕМА) Во многих экономических и информационных задачах, например, при обработке различных списков, ведомостей и т.п. возникает необходимость объединения значений (данных) различного типа в одну сущность (группу). Ранее уже рассматривались сложные типы данных, позволяющие объединять однотипные данные под одним именем – массивы. В C++ существует также возможность определять пользовательские составные типы данных, называемые структурами позволяющие группировать данные различных типов, как правило, логически взаимосвязанные между собой. Чаще всего объединяемые данные относятся к одному объекту (являются характеристиками этого объекта). Например, характеристиками книги, хранящейся в библиотеке, являются ее название, автор, категория (учебник, художественная литература, учебное пособие и пр.), библиографический идентификатор, код книги, год издания, издательство. Структура – это пользовательский тип данных в языке C/C++, включающий описание совокупности переменных-членов (элементов структуры), логически относящихся к одному объекту. В отличие от массива, элементы структуры, называемые полями структуры, могут быть разного типа. В качестве типов полей структуры могут выступать любые фундаментальные типы (кроме void), пользовательские типы (в том числе массивы и другие структуры), типы указателей. Если типом поля некоторой структуры является тип, описанный в программе, то этот тип должен быть описан до объявления данной структуры. 10.1. Объявление типа структуры Общий синтаксис объявления обычной записи имеет вид: struct <ИмяТипаСтруктуры> { ТипПоля1 ИмяПоля1; ТипПоля2 ИмяПоля2; ... ТипПоляN ИмяПоляN; }; Пример 10.1. Объявление структуры, описывающей данные о студенте const int N = 10; struct trstud { char FIO[31]; int BY; int RecBookID; int MYear; int Group; char Faculty[6]; int Year; int SesGrs[5]; }; //trstud //trstud – тип структуры // поля структуры: ФИО (строка до 30 симв.) //год рождения //номер зач. книжки //год поступления //номер группы //факультет (строка до 5 симв.) //курс //оценки за сессию ... int main() { trstud st, st1; ... } //переменные типа структуры (объекты типа структуры) Основные правила для работы со структурами:  Имена полей должны быть уникальными в пределах структуры.  Обращение к объекту-структуре в целом допускается: o в инструкции присваивания, например: st = st1; // объект st1 скопирован в объект st o при разадресации объекта-структуры, например, для передачи адреса объекта в функцию в качестве аргумента, например: fwrite(&st1, sizeof(trstud), 1, file); o при передаче объекта структуры в функцию в качестве аргумента, например: PrintObjectOnScreen(st); // формальный аргумент функции // должен иметь тип trstud (см. пример объявления выше)  Для доступа к какому-либо конкретному полю структуры используется имя этой структуры (объекта) и имя данного поля в этой структуре, разделенные точкой: ИмяОбъекта_Структуры.ИмяПоля Например: st.FIO, st1.SesGrs  Поле структуры используется в программе так же, как и обычная (отдельная) переменная, над ним можно выполнять любые действия (присваивание, вводвывод), допустимые для соответствующего типа данных. Например: st1.BY = 1985; fgets(st1.FIO); strcpy(st.FIO, st1.FIO); cout << st.FIO; Поле структуры не может иметь тип самой структуры, struct TExam { ... TExam exam; ... }; // запрещено!! Тип TExam еще не определен до конца! однако может иметь тип указателя на элемент типа этой структуры struct TExam { ... TExam * pexam; // Разрешено: поле будет хранить адрес объекта типа TExam ... }; Структура как тип может использоваться при определении других типов, в частности, выступать как тип элемента массива. В этом случае для обращения к конкретному полю некоторого элемента массива структур следует указать имя переменной-массива, затем индекс (индексы) данного элемента массива и после точки имя поля. Например: const int N = 1000; struct trbook { char Title[50]; int Year; int BookID; //тип структуры }; void main() // главная функция (но может быть и любая другая) { trbook b1; //объект-структура типа trbook trbook BList[N]; //массив структур размером N элементов int i(1); char c; do { printf ("Ввод данных %d-й книги... ", i); printf ("Наименование: "); gets (BList[i].Title, 50); printf ("Год издания: "); scanf (BList[i].Year); printf ("Код книги: "); scanf (BList[i].BookID); ++i; printf ("Продолжить ввод (Y/N)? "); c = getch(); } while ( i>N || c == 'N' || c == 'n' ); //... } Рассмотрим пример программы, использующей структуры. Пример 10.2. Пример программы, обрабатывающей перечень данных, содержащий сведения о контроле деталей и сортирующей все детали на две группы: годная деталь, брак. #include #include #include struct trdet { int lotID; double d1; }; //тип структуры, описывающей деталь //номер партии деталей //фактический (измеренный) размер int main() { setlocale(LC_ALL, "Rus"); const int N = 1000; const double ltol = 9.94; const double htol = 10.04; //размер массива //нижнее предельное значение размера //верхнее предельное значение размера trdet dlist[N]; //исходный массив структур о деталях trdet Accepted[N]; //массивы деталей годн.; с испр.браком; //с неиспр. браком int i; int dsize; //количество деталей в списке int AccSize, RejSize; //количество годных и бракованных деталей int AccLotID; //номер партии, в которой надо найти кол-во годных деталей int AccLotIDnum; //кол-во годных деталей в заданной партии double NotAcceptedNum; //доля брака от общего числа деталей char c; // ввод исходных данных о деталях i=0; do { printf ("Ввод данных %d-й детали... ", i); printf("Номер партии: "); scanf("%d", &dlist[i].lotID); printf("Контролируемый размер: "); scanf("%lf", &dlist[i].d1); ++i; //увеличиваем на 1 счетчик введенных деталей printf("Продолжить ввод (Y/N)?"); c = getch(); } while (i>N || c == 'N' || c == 'n'); dsize = i; //количество введенных структур о деталях printf("Задайте номер партии, для которой нужно вывести кол-во годных деталей"); scanf("%d", &AccLotID); //обработка списка деталей: сортировка на группы AccSize = 0; RejSize = 0; for (i = 0; i htol) //если брак ++RejSize; else //если годная деталь { Accepted[AccSize++] = dlist[i]; //копируем элемент массива } } //for //обработка групп деталей: формирование статистики //определение числа годных деталей в заданной партии (AccLotID) AccLotIDnum = 0; for (i = 0; i item, а указатель на следующий узел – выражением pN -> link. Чаще всего выполняются следующие действия при работе со связными списками:  создание списка,  удаление списка,  вставка узла в список,  удаление узла из списка,  определение длины списка,  поиск узла,  сортировка списка,  обращение списка24,  вывод элементов списка. Для удаления узла (в рх -> link) из списка выполняются действия (см. Рис. 1): pt = рх -> link; рх -> link = pt -> link; delete pt; 24 Изменение порядка следования узлов на обратный. Рис.1. Удаление узла из односвязного списка Для вставки узла (в pt) в список выполняются действия (см. Рис. 2): TPNode pt(new TNode); pt -> link = px -> link; px -> link = pt; Рис.2. Вставка узла в односвязный список Ниже приведен листинг исходного файла программы, демонстрирующей создание линейного односвязного списка, его обращение и вывод на экран всех элементов обращенного списка. Листинг 1. Программа создания, обращения и вывода линейного односвязного списка. // // // // // // // // // // // // // // Модуль: SimpleList.срр Назначение: Модуль реализации программы создания и обращения линейного списка. Пояснения: Для выполнения этих действий реализованы соответствующие функции. Разработчик: © Романовский г. Набережные Переработано: © Романовский г. Набережные Э.А., Российская Федерация, р. Татарстан, Челны, КамПИ, каф. АиИТ, 15.04.2004. Э.А., Российская Федерация, р. Татарстан, Челны, КамПИ, каф. АиИТ, 16.04.2004. #include #include using namespace std; typedef double TItem; struct TNode { TItem item; TNode *link; }; typedef TNode *TPNode; // TItem - синоним типа элемента узла. // TNode - тип узла. // Элемент узла. // Указатель на следующий узел. // PTNode - синоним типа указателя на узел. // Создание списка (возвращает указатель на начальный узел списка). TPNode LstCreate(const size_t size) // Аргумент - количество узлов списка. { size_t i; TPNode pN, plist(O); if (size) // Если size != 0. { pN = plist = new TNode; // Создание начального узла, for (i = 1; i < size; ++i) // Создание остальных узлов. pN = pN -> link = new TNode; pN -> link =0; // Последний узел содержит пустой указатель. } return plist; } // Удаление списка. void LstRemove(TPNode plist) // Аргумент - указатель на начальный узел. { TPNode pN(plist); while (plist) // Пока список непустой. { pN = plist -> link; delete plist; // Удаление очередного узла, plist = pN; } } // Обращение списка (возвращает указатель на начальный узел списка). TPNode LstReverse(TPNode plist) // Аргумент - указатель на начальный узел. { TPNode ptemp, pnrev(plist), prev(O); while (pnrev) { ptemp = pnrev -> link; pnrev -> link = prev; prev = pnrev; pnrev = ptemp; } return prev; } int main() { setlocale(LC_ALL, "Rus"); size_t i, IstLength; TItem item; cout << "Программа создания и обращения связного списка.\n\n"; cout << "Введите число узлов списка: "; cin >> IstLength; TPNode pList(LstCreate(IstLength)), pN(pList); for (i = 0; i < IstLength; ++i) { cout << "Введите " << i << "-й узел: "; cin >> item; pN -> item = item; pN = pN -> link; } cout << "Обращение списка ... " << endl; pList = LstReverse(pList); cout << "Результат обращения:\n"; pN = pList; for (i = 0; i < IstLength; ++i) { cout << i << "-Й узел: " << pN -> item << endl; pN = pN -> link; } cout << "Удаление списка ... " << endl; LstRemove(pList); cout << "Удаление завершено.\n\n"; return 0; } СПИСОК ЛИТЕРАТУРЫ Основная литература 1 Липпман, С. Язык программирования С++. Полное руководство [Электронный ресурс] / С. Липпман, Ж. Лажойе; Пер. с англ. - СПб.: "Невский диалект", М.: ДМК Пресс, 2006. - 1104 с., ил. - ISBN 5-7940-0070-8, ISBN 5-94074-040-5. – Точка доступа : http://www.bibliorossica.com/book.html?currBookId=5490 Дополнительная литература 2 Серебряков В. А. Теория и реализация языков программирования [Текст] / В. А. Серебряков. - Москва : Физматлит, 2012. - 235 с. : табл., рис. - Библиогр.: с. 234-235. - ISBN 978-5-9221-1417-2 – Точка доступа : http://e.lanbook.com/books/element.php?pl1_id=5294 3 Немцова Т. И. Программирование на языке высокого уровня. Программир. на языке С++: Уч. пос. / Т.И.Немцова и др.; Под ред. Л.Г.Гагариной - М.: ИД ФОРУМ: ИНФРА-М, 2012. - 512 с.: ил. – ISBN 978-5-8199-0492-3. – Точка доступа : http://znanium.com/bookread.php?book=244875 4 Дейл Н., Уимз Ч., Хедингтон М. Программирование на С++: Пер. с англ. – М.: ДМК Пресс. – 672 с.: ил. – ISBN 5-93700-008-0. – Точка доступа : http://www.bibliorossica.com/book.html?currBookId=5505 5 Канцедал С. А. Алгоритмизация и программирование : Учебное пособие / С.А. Канцедал. - М.: ИД ФОРУМ: НИЦ Инфра-М, 2013. - 352 с.: ил. – ISBN 978-5-8199-0355-1. – Точка доступа : http://znanium.com/bookread.php?book=391351 Интернет-ресурсы: 6 Основы программирования : электронный курс [электронный ресурс] : Режим доступа: http://www.intuit.ru/studies/courses/2193/67/info. – Загл. с экрана (дата обращения 10.12.2015). 7 RSDN : сайт, посвященный разработке программного обеспечения [электронный ресурс] : Режим доступа: http://rsdn.ru/. – Загл. с экрана (дата обращения 10.12.2015). 8 Qt Coding Style [электронный ресурс] : Режим доступа: http://habrahabr.ru/post/150329/. – Загл. с экрана (дата обращения 10.12.2015). 9 Клуб программистов [электронный ресурс] : Режим доступа: http://www.programmersclub.ru// – Загл. с экрана (дата обращения 10.12.2015). 10 MSDN – сеть разработчиков Microsoft [электронный ресурс] : Режим доступа: https://msdn.microsoft.com/ru-ru/dn308572.aspx. – Загл. с экрана (дата обращения 10.12.2015).