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

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

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

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

ОСНОВЫ

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

Язык 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

успех Unix сделал используемый в ней язык C основным языком системного программирования в мире. Последняя на момент написания книги версия C представлена в 2018 г.8

Развитие компьютерной техники позволило ввести в арсенал доступных исследовательских средств имитационное моделирование 9 — использование математических моделей для 
прямого моделирования, т. е. исследования поведения изучаемого объекта на основе поведения модели при заданном сценарии развития. В качестве средства реализации имитационного моделирования О.-Й. Даль и К. Нюгард из Норвежского вычислительного центра разработали основанный на Algol 
язык Simula (1962 г.). Версия Simula 67 использовала такие 
понятия, как «объект», «класс», «подкласс», «наследование», 
«виртуальная процедура», «сборщик мусора», которые позднее 
стали широко использоваться в последующих языках программирования.

Б. Строуструп использовал Simula 67 для моделирования 
компьютерных сетей, однако возникла проблема с низкой производительностью интерпретатора Simula, в связи с чем было принято решение переписать программу моделирования на 
языке C. В результате им был создан набор расширений языка 
C под названием C with classes («C с классами», 1979 г.). Транслятор C with classes, названный cfront, переводил код в чистый 
C, который затем транслировался в машинный код. В 1983 г. 
развитие C with classes получило название C++. Данный подход 
затем применялся и при разработке других языков программирования: достаточно написать транслятор с нового языка на 
язык C, и вы можете использовать свой язык на всех компьютерах, для которых есть транслятор C.

Впоследствии C++ стал самостоятельным языком программирования. Более того, ряд современных трансляторов, используемых для трансляции кода на языке C, являются транс8 См.: ISO/IEC 9899-2018. Information technology. Programming 
languages. C (дата введения 05.07.2018).

9 В англ. языке используется термин simulation.

11

ляторами C++, поддерживающими режим «чистого 0». Общее 
подмножество C и C++ составляет большую часть стандартного C, из-за чего данные языки иногда не разделяют и обозначают как «C /C ++»10. И все же область системного программирования в основном принадлежит C, в то время как 
C++ стал широко используемым при решении прикладных задач универсальным языком программирования с корнями в 
системном программировании, который также популярен для 
решения вычислительных научно-технических задач.

Начиная с 1998 г. было выпущено шесть версий стандартного C++. Текущей на момент написания книги версией является 
C++2011, однако ее поддержка компиляторами пока не полна.

Значительную часть стандартов C и C++ занимает описание стандартной библиотеки — определений, которые не являются частью самого языка, но должны быть предоставлены 
любой, поддерживающей стандарт, реализацией транслятора. 
В частности, операции ввода-вывода не входят в состав языка, 
а предоставляются стандартной библиотекой. Существует также множество иных библиотек, не входящих в стандарт, предоставляющих средства для работы с сетью, графикой, звуком, 
базами данных и т. д.

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

10 Среди программистов на языке C использование такого обозначения часто встречает сильное неприятие.

11 См.: ISO/IEC 14882-2020. Information technology. Programming 
languages. C++ (дата введения 01.12.2020).

12

Глава 1

Элементарные понятия

Множество [set] — некая совокупность элементов [element].

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

Запись а £ А читается «(элемент) а принадлежит (множеству) А».

Запись А С B читается «(множество) А является подмножеством (множества) B », т. е. каждый элемент А является и 
элементом B . Если А С B и B С А, то эти два множества 
совпадают (А =  B).

Запись А С B читается «(множество) А является собственным подмножеством (множества) B», т. е. А С B и известно, 
что не все элементы B принадлежат А, а значит, эти два множества не совпадают.

Пустое множество [empty set] — множество, не содержащее 
ни одного элемента и являющееся подмножеством любого другого множества. Обозначается 0.

13

Конечное множество [finite set] — множество A, для которого найдется n £ N, что все элементы этого множества можно 
представить в виде последовательности A =  { ai,a2, ... ,an }, 
т. е. взаимно-однозначно отождествить с конечным натуральным рядом 1, 2 ,..., n. В этом случае число n называют размером множества A: |A| =  n.

Аксиома: множество 0  также причисляется к конечным, 
при этом 10 1 =  0.

Бесконечное множество [infinite set] — множество, для которого найдется взаимно-однозначное соответствие между им 
самим и каким-либо его собственным подмножеством.

Например, множество натуральных чисел N бесконечно, поскольку (с помощью умножения и деления на два) можно установить взаимно-однозначное соответствие между N и множеством четных натуральных чисел, которое, очевидно, является 
собственным подмножеством N.

Счетное множество [countable set] — бесконечное множество, 
для которого можно построить взаимно-однозначное соответствие с множеством N. Иными словами, элементы счетного 
множества можно пронумеровать натуральными числами.

Примеры счетных множеств: натуральные числа, четные 
числа, целые числа, простые числа, пары целых чисел.

Несчетное множество [uncountable set] — бесконечное множество, не являющееся счетным.

Мощность множества [set cardinality] — обобщение понятия 
«размер множества» на все множества. Для конечных множеств — то же, что и размер. Для бесконечных множеств 
используются специальные обозначения. Например, мощность 
любого счетного множества обозначается ^о («алеф-нуль»).

Множества, между которыми есть взаимно-однозначное соответствие, называются равномощными, т. 
е. имеющими 
одинаковую мощность.

14