книги / Технологии разработки объектно-ориентированных программ на язык C++. Основы структурного программирования на алгоритмическом языке C++
.pdfМинистерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермский национальный исследовательский политехнический университет»
О.А. Полякова, О.Л. Викентьева
ТЕХНОЛОГИИ РАЗРАБОТКИ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ПРОГРАММ НА ЯЗЫКЕ С++
В двух частях
ЧАСТЬ I. ОСНОВЫ СТРУКТУРНОГО ПРОГРАММИРОВАНИЯ НА АЛГОРИТМИЧЕСКОМ ЯЗЫКЕ С++
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
Издательство Пермского национального исследовательного
политехнического университета
2019
1
ББК 004.438(075.8) УДК 004.438(075.8)
П12
Рецензенты:
д-р экон. наук, проф. Р.А. Файзрахманов (Пермский национальный исследовательский политехнический университет);
д-р пед. наук, проф. Е.Г. Плотникова (Пермский филиал Национального исследовательного
университета «Высшая школа экономики»)
Полякова, О.А.
П12 Технологии разработки объектно-ориентированных программ на языке С++ : учеб. пособие : в 2 ч. / О.А. Полякова, О.Л. Викентьева. – Пермь : Изд-во Перм. нац. исслед. политехн. ун-та, 2019.
ISBN 978-5-398-02186-8
Ч. I. Основы структурного программирования на алгоритмическом языке С++. – 196 с.
ISBN 978-5-398-02187-5
Рассмотрены вопросы применения основных принципов структурного программирования в сложных программных системах на языке высокого уровня С++, которые демонстрируются на содержательных примерах. Разработано в сотрудничестве с авторским коллективом студентов группы РИС 17-1б: Е. Бартовым, А. Граничниковой, Н. Ерохиным, Е. Селиверстовым, М. Торопицыным, Р. Шириновым.
Предназначено для студентов следующих направлений: 09.03.01 – «Информатика и вычислительная техника»; 09.03.04 – «Программная инженерия»; 10.05.03 – «Обеспечение информационной безопасности распределенных информационных систем»; 15.03.04 – «Автоматизация технологических процессов и устройств»; 27.03.04 – «Управление и информатика в технических системах»; 38.03.05 – «Бизнес – Информатика».
|
ББК 004.438(075.8) |
|
УДК 004.438(075.8) |
ISBN 978-5-398-02187-5 (ч. 1) |
|
ISBN 978-5-398-02186-8 |
© ПНИПУ, 2019 |
2
ОГЛАВЛЕНИЕ |
|
Глава 1. Основы теории алгоритмов..................................................... |
6 |
1.1. Свойства алгоритмов ................................................................. |
6 |
1.2. Виды записи алгоритмов ........................................................... |
6 |
Глава 2. Константы и переменные ........................................................ |
9 |
2.1. Переменные................................................................................. |
9 |
2.2. Константы ................................................................................. |
10 |
Глава 3. Базовые средства С++............................................................ |
12 |
3.1. Идентификаторы ...................................................................... |
12 |
3.2. Комментарии............................................................................. |
12 |
3.3. Представление комментариев |
|
в блок-схемах алгоритмов .............................................................. |
13 |
Глава 4. Типы данных в С++ ............................................................... |
14 |
4.1. Основные типы данных ........................................................... |
14 |
4.2. Объявление типа переменной величины................................ |
14 |
4.3. Спецификаторы типов ............................................................. |
15 |
4.4. Объявление констант ............................................................... |
15 |
4.5. Выражения в С++ ..................................................................... |
15 |
4.6. Объявление переменных в блок-схемах................................. |
17 |
Глава 5. Операторы ввода-вывода ...................................................... |
19 |
5.1. Оператор вывода ...................................................................... |
19 |
5.2. Оператор ввода ......................................................................... |
20 |
Глава 6. Блок-схемы и операторы базовых конструкций |
|
структурного программирования........................................................ |
22 |
6.1. Линейные алгоритмы ............................................................... |
22 |
6.2. Алгоритмы ветвления .............................................................. |
22 |
6.3. Логические операторы ............................................................. |
29 |
Глава 7. Циклические алгоритмы ....................................................... |
32 |
7.1. Виды циклических процессов ................................................. |
32 |
7.2. Операторы циклических процессов........................................ |
32 |
Глава 8. Структура программы на С++ .............................................. |
40 |
8.1. Основная часть программы – функция main.......................... |
40 |
3
8.2. Пространство имен................................................................... |
42 |
8.3. Основные арифметические операции..................................... |
42 |
8.4. Отладка программы.................................................................. |
44 |
8.5. Пример построения программы на С++ ................................. |
47 |
Глава 9. Массивы и указатели ............................................................. |
53 |
9.1. Статические массивы ............................................................... |
53 |
9.2. Указатели .................................................................................. |
55 |
9.3. Виды указателей ....................................................................... |
56 |
9.4. Инициализация указателей...................................................... |
60 |
9.5. Освобождение памяти.............................................................. |
62 |
9.6. Динамические массивы............................................................ |
63 |
9.7. Операции с указателями .......................................................... |
64 |
9.8. Многомерные массивы. ........................................................... |
66 |
9.9. Массивы символов – строки.................................................... |
73 |
Глава 10. Функции................................................................................ |
79 |
10.1. Объявление и определение функций.................................... |
79 |
10.2. Глобальные и локальные переменные.................................. |
82 |
10.3. Параметры функции............................................................... |
85 |
10.4. Перегрузка функций............................................................... |
88 |
10.5. Указатели на функции ........................................................... |
90 |
Глава 11. Рекурсивные функции ......................................................... |
94 |
11.1. Понятие рекурсии................................................................... |
94 |
11.2. Когда рекурсия не используется ........................................... |
95 |
11.3. Виды рекурсии........................................................................ |
96 |
11.4. Рекурсивные функции работы со стеком ........................... |
100 |
11.5. Ханойская башня .................................................................. |
101 |
Глава 12. Структуры данных. ............................................................ |
104 |
12.1. Поиск в массиве структур.................................................... |
105 |
12.2. Структуры в динамической памяти .................................... |
107 |
Глава 13. Работа с файлами ............................................................... |
110 |
13.1. Открытие файла для записи. |
|
Работа с файлом в режиме записи ............................................... |
110 |
13.2. Открытие файла для чтения. |
|
Работа с файлом в режиме чтения ............................................... |
112 |
13.3. Режимы открытия................................................................. |
113 |
4
Глава 14. Динамические структуры данных. ................................... |
115 |
14.1. Одно- и двунаправленные списки....................................... |
115 |
14.2. Реализация однонаправленного списка через класс ......... |
121 |
14.3. Реализация двунаправленного списка |
|
через библиотеку STL ................................................................... |
128 |
14.4. Реализация двунаправленного списка |
|
через структуры ............................................................................. |
130 |
14.5. Реализация двунаправленного списка через класс............ |
137 |
14.6. Стеки...................................................................................... |
144 |
14.7. Реализация стека через библиотеку STL............................ |
145 |
14.8. Реализация стека через структуры...................................... |
148 |
14.9. Реализация стека через класс. ............................................. |
153 |
14.10. Очереди ............................................................................... |
158 |
14.11. Реализация очереди через библиотеку STL ..................... |
158 |
14.12. Реализация очереди через структуры. .............................. |
161 |
14.13. Реализация очереди через класс........................................ |
167 |
Глава 15. Сортировка и поиск ........................................................... |
172 |
15.1. Поиск в линейных структурах............................................. |
172 |
15.2. Поиск в упорядоченных структурах................................... |
173 |
15.3. Поиск в массивах.................................................................. |
175 |
15.4. Поиск подстроки в строке ................................................... |
178 |
15.5. Методы быстрой сортировки .............................................. |
186 |
15.6. Сортировки методами естественного |
|
и многофазного слияния ............................................................... |
191 |
Список литературы............................................................................. |
194 |
5
Глава 1. ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ
Для решения любой задачи очень важно уметь составить план действий. В программировании такой план называется алгоритмом.
Алгоритм – это понятный исполнителю порядок операций, который гарантированно приведет к достижению цели.
1.1.Свойства алгоритмов
Дискретность – цель достигается за конечное число шагов.
Понятность – исполнителю должно быть понятно, какое действие и для чего делается на каждом шаге.
Детерминированность – все шаги алгоритма должны быть однозначно понятны и конкретны.
Результативность – выполнение алгоритма приводит к заданной цели.
Массовость – алгоритм должен работать не только для набора данных с определенным значением, но и для любых других значений такого набора данных. Например, вычислять площадь прямоугольного треугольника не только с катетами длиной 2 и 4 см, но с катетами любой другой длины.
1.2.Виды записи алгоритмов
Текстуально (словами).
Блок-схемами.
Программным кодом.
Текстуальная форма записи алгоритмов
Необходимо сделать бутерброд из трех ингредиентов: хлеба и двух любых других подходящих продуктов. Словесный алгоритм приготовления бутерброда выглядит следующим образом:
Выбираем хлеб и два ингредиента из имеющихся. Назовем все три компонента данными.
6
Производим операции с этими данными: складываем их друг с другом. Полученный бутерброд является результатом сложения всех исходных данных.
Забираем бутерброд.
Изображение алгоритмов в виде блок-схем
Алгоритм создания бутерброда состоит всего из трех шагов, реальные же алгоритмы могут содержать несколько тысяч шагов. Исходя из этого удобнее изображать их в виде блок-схем. Правила проектирования алгоритмов в виде блок-схем описаны в ГОСТ 19.701–90.
Получение (ввод) данных (в описанном выше примере это получение информации об имеющихся продуктах) изображается в виде параллелограмма (рис. 1.1). Выдача (вывод) данных (например, получение готового бутерброда) на блок-схемах изображается так же.
Любое действие, производимое над данными в алгоритме (в примере это сложение ингредиентов), изображается в виде прямоугольника (рис. 1.2).
Ввод/вывод |
|
Действие |
|
|
|
|
|
данных |
|
|
|
Рис. 1.1. Блок ввода/вывода данных |
|
|
|
Рис. 1.2. Блок выполнения |
|||
|
|
действия |
|
Начало и конец работы алгоритмов изображаются в виде прямоугольника с закругленными углами (рис. 1.3).
Начало/конец
Рис. 1.3. Блок начала/конца алгоритма
7
Блоки соединяются между собой линиями.
В целом блок-схема алгоритма приготовления бутерброда выглядит так, как показано на рис. 1.4.
Рис. 1.4. Представление алгоритма в виде блок-схемы
Задания для самостоятельной работы:
Разработать и представить в словесном виде и в виде блоксхемы алгоритм раскладывания трех разных книг на полки книжного шкафа.
Разработать и представить в словесном виде и в виде блоксхемы алгоритм перехода пешеходом перекрестка со светофором
идвухполосным типом движения.
8
Глава 2. КОНСТАНТЫ И ПЕРЕМЕННЫЕ
Любое действие в программе происходит с данными, которые в программировании называются операндами. В примере с бутербродом роль операндов выполняли ингредиенты и приготовленный бутерброд. Каждый операнд может быть как переменной величиной, так и величиной постоянной (константой), выражением (например, суммой двух переменных) или функцией.
Понятно, что каждый из операндов (данных) отличается от другого своими свойствами, видом, вкусом. В программировании принято говорить, что каждый операнд имеет свой тип данных. Данные разных типов по-разному хранятся в памяти компьютера, поразному обрабатываются, отличаются разным набором операций и функций, разрешенных для каждого типа, а также отличаются множеством значений, разрешенных для величин каждого типа.
2.1. Переменные
Переменная – это именованная область памяти, в которой хранятся данные определенного типа. Например, три коробки – «Овощи», «Мясо» и «Напитки» – иллюстрируют, как выглядит область памяти компьютера, которая готова хранить данные определенного типа. Имя коробки служит для обращения к области памяти (например, к коробке с именем «Овощи»), в которой хранится значение переменной (например, «Огурец»). Невозможно положить огурец в коробку с именем «Напитки», но его можно положить в коробку с именем «Овощи», и тогда огурец займет все пространство коробки, а область памяти с именем «Овощи» будет не пустой. Если захочется положить в коробку помидор, то придется достать оттуда огурец и заменить его новым овощем.
Таким образом, переменная может содержать только одно значение! При попытке записать в переменную что-то новое старое значение не сохраняется, а заменяется новым.
9
В примере по приготовлению бутерброда роль переменных величин выполняют два ингредиента из имеющихся в холодильнике (это могут быть сыр, салат, ветчина и др.) – «Ингредиент 1» и «Ингредиент 2». Величина с именем «Хлеб» должна быть в составе любого бутерброда, поэтому она не является переменной величиной.
Таким образом, представить алгоритм приготовления бутерброда можно следующим образом: ячейка памяти с именем «Хлеб» заполнена постоянным значением, две пустые ячейки памяти с именами «Ингредиент 1» и «Ингредиент 2» заполняются любыми двумя выбранными продуктами из имеющихся, т.е. переменные «Ингредиент 1» и «Ингредиент 2» получают значения (данные). Третья переменная, назовем ее именем «Бутерброд», будет принимать сложение значений из переменных «Ингредиент 1», «Ингредиент 2» и значения из области памяти с именем «Хлеб».
Понятно, что во время выполнения алгоритма приготовления бутерброда значение таких типов, как переменные, можно изменять.
Перед использованием любой переменной в программе необходимо зарезервировать для нее область памяти компьютера. Это действие называется описанием переменной.
2.2. Константы
Кроме переменных величин, которые могут изменять свои значения во время выполнения программы, существуют неизменяемые величины. Такие величины называются константами. В примере с бутербродом такой константой является хлеб. Точно известно, что он используется в приготовлении любого бутерброда.
Константы также участвуют в действиях, но результат операции нельзя поместить в область памяти, где хранится константа в течение программы.
Математические константы часто используют в программах, например число Pi ≈ 3,14. Изменять это значение в программе никому и в голову не придет.
10