Основы программирования: язык С++

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ ФЕДЕРАЦИИ
УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ 
ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б. Н. ЕЛЬЦИНА
Д. Р. Кувшинов, С. И. Осипов
ОСНОВЫ
ПРОГРАММИРОВАНИЯ
Язык C++
Учебное пособие
Рекомендовано методическим советом 
Уральского федерального университета в качестве учебного пособия 
для студентов, обучающихся по направлениям подготовки 
01.03.03 «Механика и математическое моделирование», 
01.03.04 «Прикладная математика»
Екатеринбург
Издательство Уральского университета 

УДК 
004.43(075.8)
ББК 
32.973.26-018.1я73 
К88
Под общей редакцией Д. Р. Кувшинова
Рецензенты:
сектор отдела динамических систем 
Института математики и механики УрО РАН 
(заведующий сектором, доктор физико-математических наук 
А. А. Успенский);
С. С. Александрова, кандидат технических наук 
(Московский авиационный институт (Национальный исследовательский
университет))
Кувшинов, Д. Р.
K88 
Основы программирования : язык C++ : учебное пособие / 
Д. Р. Кувшинов, С. И. Осипов ; под общ. ред. Д. Р. Кувшинова ; 
Министерство науки и высшего образования Российской Федерации, Уральский федеральный университет. — Екатеринбург : Изд-во 
Урал. ун-та, 2021. — 490 с. : ил. — Библиогр.: с. 488-489. — 30 экз. — 
ISBN 978-5-7996-3257-1. — Текст : непосредственный.
ISBN 978-5-7996-3257-1
На примере языка программирования C4—+17 вводятся основные концепции структурного программирования. 
Рассматривается широкий 
спектр тем: базовые конструкции C+—+, концепция неопределенного поведения, управление памятью, форматы представления чисел, концепция 
объекта, си-строки, конечные автоматы, простые структуры данных и 
алгоритмы сортировки, введение в вопросы организации процесса разработки программ.
Для студентов бакалавриата, обучающихся по направлениям «Механика и математическое моделирование» и «Прикладная математика».
УДК 
004.43(075.8) 
ББК 
32.973.26-018.1я73
На обложке: рисунок Д. Р. Кувшинова
ISBN 978-5-7996-3257-1
©  Уральский федеральный университет, 2021

Оглавление
Предисловие 
7
Введение 
8
Глава 1. 
Элементарные понятия 
13
Глава 2. 
Значения и переменные 
29
Глава 3. 
Функции 
50
Глава 4. 
Ветвления и циклы 
60
4.1. Ветвления 
................................................................... 
60
4.2. Циклы............................................................................. 
67
4.3. Перебор вариантов 
................................................... 
76
Глава 5. 
Логические вычисления 
84
5.1. Логика и множества................................................... 
84
5.2. Целочисленные типы C++ 
......................................  
90
5.3. Представление отрицательных ч и сел ................... 
99
5.4. Поразрядные операции............................................. 
102
Глава 6. 
Процедурное программирование 
112
6.1. Константы и ссылки 
................................................ 
112
6.2. Неопределенное поведение......................................  
116
6.3. Процедурное программирование............................. 
119
6.4. Модульное программирование................................ 

Глава 7. Элементарные вычисления 
134
7.1. Числа с плавающей запятой................................... 
134
7.2. Математические ф у н к ц и и ......................................  
144
7.3. Настройки арифметики чисел с плавающей запятой ................................................................................... 
150
Глава 8. Указатели и массивы 
154
8.1. Указатели......................................................................  
154
8.2. Статические м ассивы ................................................ 
158
8.3. Массивы и указатели................................................ 
163
8.4. О линейном п о и с к е ................................................... 
170
8.5. Цикл for для диапазона............................................. 
172
Глава 9. Управление памятью 
175
9.1. Классификация переменных................................... 
175
9.2. Стек вызовов................................................................ 
178
9.3. Динамическая память................................................ 
181
9.4. Тип string......................................................................  
185
9.5. Динамическая память: средства C 
......................  
189
Глава 10. Составные типы данных 
196
10.1. Многомерные статические массивы......................  
196
10.2. Алгебраические структуры......................................  
198
10.3. Гетерогенные типы данных......................................  
207
10.4. Файлы............................................................................  
215
Глава 11. Объекты 
219
11.1. Многомерные динамические массивы................... 
219
11.2. Объекты 
......................................................................  
226
11.3. Правило тр ех................................................................ 
233
11.4. Сокрытие д ан н ы х......................................................  
236
11.5. Static-члены к л а сса ................................................... 
242
11.6. Ссылки на временные значения ............................. 
243
Глава 12. Введение в численные методы 
256
12.1. Погрешность и то ч н о ст ь .......................................  

12.2. Некоторые частные вопросы ................................... 
261
12.3. Решение уравнений................................................... 
278
12.4. Поиск экстремума......................................................  
284
Глава 13. Си-строки 
287
13.1. Функционал cstrin g ................................................... 
288
13.2. Функционал c s tlib ......................................................  
293
13.3. Функционал cstdio......................................................  
293
13.4. Функционал cctype 
................................................... 
301
13.5. Тип strin g_view .........................................................  
303
Глава 14. Инварианты и разработка программ 
307
14.1. Инварианты 
................................................................ 
307
14.2. Обработка ош ибок......................................................  
321
14.3. Метрики исходного к о д а .........................................  
328
14.4. Процесс разработки................................................... 
330
14.5. Верификация................................................................ 
335
14.6. Протоколирование ......................................................  
337
14.7. Тестирование ................................................................ 
338
Глава 15. Рекурсия 
342
15.1. Р екур си я ......................................................................  
342
15.2. Префиксный калькулятор......................................  
348
15.3. Постфиксный калькулятор ......................................  
355
15.4. Инфиксный калькулятор .........................................  
360
Глава 16. Конечные автоматы 
368
16.1. Определения................................................................ 
368
16.2. Пример простого Д К А ............................................. 
373
16.3. Символьные константы............................................. 
377
16.4. Классификация последовательности ................... 
383
16.5. Нормализация переводов строк ............................. 
386
Глава 17. Элементарные структуры данных 
393
17.1. Статический м ассив................................................. 
17.1.1. Статический массив в качестве стека . . . 393

17.1.2. Кольцевой б у ф е р ........................................ 
395
17.2. Связанный сп и сок......................................................  
401
17.2.1. Линейный список в качестве стека . . . .  
401
17.2.2. Двусвязный сп и с о к ......................................  
404
17.2.3. Кольцевой односвязный список ................ 
404
17.3. Двоичное дерево.........................................................  
408
17.4. Упакованное двоичное д е р е в о ................................ 
416
Глава 18. Дополнительный материал 
418
18.1. Сравнение C++ с Pascal............................................. 
418
18.2. Препроцессор................................................................ 
432
18.3. Классы сложности алгоритмов 
............................. 
439
18.4. Алгоритмы сортировок............................................. 
447
18.4.1. Квадратичные алгоритм ы .........................  
448
18.4.2. Линеарифмические ал гори тм ы ................ 
454
18.4.3. Линейные алгоритмы ................................... 
468
18.5. И склю чения................................................................ 
Список рекомендуемой литературы и источников 488

Предисловие
Книга предлагает вводный курс в программирование с использованием C++17 в качестве языка программирования. Объем книги разбит на 18 глав. Можно условно отождествить главы с учебными неделями. Последняя глава содержит дополнительный материал, полное освоение которого на данном этапе 
не требуется.
Авторы не ставят целью полное описание языка или его 
стандартной библиотеки. За исключением небольшого введения в последней главе, в книге не представлено обобщенное 
программирование (шаблоны C++), а объектно-ориентированное программирование дано в объеме, позволяющем ввести 
управление ресурсами в стиле C++, наследование и виртуальные функции не рассматриваются. Отдельное внимание уделено некоторым теоретическим и практическим аспектам, большинство из которых так или иначе проявляются при программировании независимо от выбранного языка. В частности, это 
касается вопросов вычислительного характера. Подробно рассмотрены числа с плавающей запятой.
Упражнения помечены знаком [V].

Введение
В 1950-е годы происходит взрывное развитие компьютеров — универсальных вычислительных машин. Их универсальность заключается в возможности загрузить в устройство программу, определяя таким образом его поведение. Естественно, 
программы создавались в той форме, которую принимал компьютер, — в машинном коде. К сожалению, машинный код 
привязан к конкретной архитектуре компьютера, примитивен 
и неудобен для человека. Для избавления от необходимости писать программы в машинном коде создаются более удобные для 
человека «языки высокого уровня» (машинный код — «язык 
низкого уровня»). Причем задачу перевода программы с языка высокого уровня в машинный код может решать сам компьютер. Для этого требуется написать программу-переводчик 
(транслятор).
Один из ранних языков высокого уровня — Fortran1, получивший широкое распространение и актуальный поныне2, создан под руководством Дж. Бэкуса в компании IBM в 1957 г. 
Целью Fortran было упрощение решения научно-технических 
вычислительных задач. Затем появился ряд других широко 
известных языков высокого уровня, однако сами транслято1 От англ. formula translation — «перевод формул».
2 Текущая версия Fortran 2018 определена международным стандартом ISO/IEC 1539-1:2018. См.: ISO/IEC 1539-1-2018. Information 
technology. Programming languages. Fortran. Pt. 1: Base language (дата 
введения 28.11.2018).

ры, базовое программное обеспечение (операционные системы, 
драйверы устройств и т. п.) продолжали писать в машинных 
кодах для конкретных семейств компьютеров.
Идея универсального языка высокого уровня, позволяющего решать любые задачи без необходимости иметь дело с машинным кодом, появилась довольно рано. Плодом таких усилий стал проект языка Algol3, реализованный «в коде» в 1960 г. 
Сам Algol так и не стал популярным средством разработки программного обеспечения, оставшись, по большому счету, университетским проектом, но послужил фундаментом большого 
числа новых языков программирования.
Одним из языков, основанных на Algol, стал амбициозный 
проект универсального языка программирования P L /I4 компании IBM. В случае IBM развитие универсального языка высокого уровня естественным образом следовало из концепции 
единой архитектуры машинного кода, реализованной в серии 
суперкомпьютеров IBM System/360. Устройства данной серии 
были совместимы с точки зрения машинного кода, но могли 
иметь разный уровень его аппаратной поддержки: какие-то команды могли выполняться непосредственно, а какие-то — с помощью автоматически загружаемых программ («программная 
эмуляция»).
На деле PL/I оказался слишком сложным, первые трансляторы (1964 г.) не поддерживали его полностью. Однако это 
не помешало Массачусетскому технологическому институту и 
компаниям General Electric и Bell Labs в 1964 г. начать проект 
многопользовательской операционной системы Multics5, основная часть которой должна была быть реализована на языке высокого уровня — PL/I. Таким образом, PL/I был использован 
в качестве языка системного программирования. Использование языка высокого уровня теоретически позволяет перенести
3 От англ. algorithmic language — «алгоритмический язык».
4 От англ. programming language — «язык программирования».
5 От англ. multiplexed information and computing service — «мультиплексируемая информационная и вычислительная служба».

написанную на нем операционную систему на любые компьютеры, для которых есть транслятор с этого языка высокого 
уровня, выполнив сравнительно небольшой набор работ по переписыванию модулей, написанных в машинном коде. Первая 
версия Multics была представлена в 1969 г.
В начале 1960-х годов в Кембридже разрабатывали свой 
универсальный язык программирования CPL6. CPL был сложным Algol-подобным языком. В процессе написания докторской 
диссертации М. Ричардсом с целью реализации переносимого между различными семействами компьютеров транслятора CPL была создана упрощенная версия CPL под названием BCPL7 (представлен в 1967 г.). Концепция переносимости 
BCPL основывалась на разделении транслятора на две части: 
транслятор с BCPL на низкоуровневый язык под названием 
«O-код» и транслятор с O-кода в машинный код конкретного 
компьютера. После этого для переноса компилятора BCPL на 
новый компьютер было достаточно написать для него транслятор с O-кода. Далее, можно было использовать BCPL для 
написания транслятора любого другого языка и сделать его 
переносимым. Таким образом, BCPL стал не универсальным 
языком программирования, а специализированным языком системного программирования.
С языком BCPL были знакомы сотрудники Bell Labs 
К. Томпсон и Д. Ричи, принимавшие также участие в проекте Multics. На основе BCPL в 1969 г. ими был создан язык 
с более компактным синтаксисом (что было важно в те времена из-за очень небольших объемов доступной оперативной 
памяти), названный B. Данный язык они начали использовать 
для реализации собственного проекта переносимой операционной системы, названной Unics. Спустя небольшое время проект 
был «перезапущен»: язык B заменили его развитием — языком 
C (1972 г.). Название Unics превратилось в Unix. Дальнейший
6 От англ. combined programming language — «комбинированный 
язык программирования».
7 От англ. basic CPL — «базовый CPL».