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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ ФЕДЕРАЦИИ

УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ 
ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б. Н. ЕЛЬЦИНА

Д. Р. Кувшинов, С. И. Осипов

ОСНОВЫ

ПРОГРАММИРОВАНИЯ

Язык C++

Учебное пособие

Рекомендовано методическим советом 
Уральского федерального университета в качестве учебного пособия 
для студентов, обучающихся по направлениям подготовки 
01.03.03 «Механика и математическое моделирование», 
01.03.04 «Прикладная математика»

Екатеринбург

Издательство Уральского университета 
2021

УДК 
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. Модульное программирование................................ 
123

3

Глава 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. Погрешность и то ч н о ст ь .......................................  
256

4

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. Статический м ассив................................................. 
393

17.1.1. Статический массив в качестве стека . . . 393

5

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. И склю чения................................................................ 
482

Список рекомендуемой литературы и источников 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).

8

ры, базовое программное обеспечение (операционные системы, 
драйверы устройств и т. п.) продолжали писать в машинных 
кодах для конкретных семейств компьютеров.

Идея универсального языка высокого уровня, позволяющего решать любые задачи без необходимости иметь дело с машинным кодом, появилась довольно рано. Плодом таких усилий стал проект языка 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 — «мультиплексируемая информационная и вычислительная служба».

9

написанную на нем операционную систему на любые компьютеры, для которых есть транслятор с этого языка высокого 
уровня, выполнив сравнительно небольшой набор работ по переписыванию модулей, написанных в машинном коде. Первая 
версия 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».

10