Оглавление Введение 1
В1. О названии 2
В2. О разработке 3
В3. В общих чертах о C++ 3
Глава 1. Знакомство с приложением 5
1.1. Установка C++ 5
1.2. Рабочее окно программы 7
1.3. Создание и сохранение документа 8
1.4. Компиляция программы 9
Глава 2. Основы программирования 13
2.1. Этапы разработки программы 13
Спецификация 14
Разработка алгоритма 14
Кодирование 14
Отладка 14
Тестирование 15
2.2. Элементы языка C++ 15
Алфавит 15
Комментарии 17
Переменные 17
Типы данных 18
Преобразование типов 21
Константы 22
Арифметические и логические операции 23
2.3. Директивы препроцессора С++ 25
Директива #include 25
Директива #define 26
Директива #undef 26
Директива #error 27
Директива #typedef 27
2.4. Ввод/вывод 28
2.5. Управляющие структуры 29
Структуры выбора 29
Структура выбора if/else 30
Структура выбора switch 32
Примеры структур выбора 33
Пример 1 33
Пример 2 34
Пример 3 35
Пример 4 36
Пример 5 38
2.6. Структуры повторения 38
Структура повторения for 38
Структура повторения while 39
Оператор цикла do...while c условием 39
Операторы continue и break 40
Оператор goto 42
Примеры структур повторения 43
Пример 1 43
Пример 2 44
Пример 3 45
Пример 4 47
Пример 5 49
Пример 6 51
2.7. Упражнения 52
Глава 3. Функции 55
3.1. Понятие функции 55
Свойства функции 56
Встроенные функции 56
Перегрузка функций 57
Арифметические и алгебраические функции 58
Тригонометрические функции 59
3.2. Функция-подпрограмма 59
Передача параметров функции main() 62
3.3. Ссылочный тип 62
Возврат значений из функции с помощью переменных ссылочного типа 63
3.4. Рекурсия 63
Шаблоны функций 65
3.5. Примеры программ с использованием функций 65
Пример 1 65
Пример 2 68
Пример 3 69
Пример 4 71
Пример 5 73
3.6. Упражнения 77
Глава 4. Массивы 79
4.1. Понятие массива 79
Ввод элементов массива 81
Вывод элементов массива 81
Операция sizeof 84
Передача одномерных массивов в функцию 84
Максимальный объем памяти, занимаемой массивом 85
4.2. Многомерные массивы 86
Обработка матриц 86
Обработка матрицы по столбцам и строкам 86
Обработка всей матрицы 87
Передача двумерных массивов в функцию 88
4.3. Символьные массивы 89
4.4. Сортировка 89
Пузырьковая сортировка 90
Выборочная сортировка 92
Быстрая сортировка 95
Сортировка методом Шелла 101
Сортировка массива при известном интервале значений элементов 104
4.5. Поиск заданного элемента в массиве 106
Последовательный поиск элемента 106
Двоичный поиск 107
4.6. Арифметика больших чисел 109
Вычитание чисел 109
Сложение чисел 117
Умножение чисел 121
4.7. Примеры использования массивов 124
Пример 1 124
Пример 2 127
Пример 3 129
Пример 4 131
Пример 5 134
4.8. Упражнения 136
Глава 5. Структуры данных 139
5.1. Очередь 139
Операции над очередями 141
Добавление элемента в очередь 141
Проверка очереди на наличие элементов 142
Удаление элемента из очереди 142
5.2. Стеки 142
Операции над стеками 143
Добавление элемента в стек 144
Проверка стека на наличие элементов 144
Удаление элемента из стека 144
5.3. Списки 145
Реализация операций над списками 146
Создание пустого списка 146
Добавление в список нового элемента 147
Поиск элемента в списке 149
Удаление элемента из списка 149
Добавление элемента в список после заданного элемента 150
Сортировка списков 151
Слияние списков 153
5.4. Примеры использования структур данных 154
Пример 1 154
Пример 2 159
Пример 3 163
Пример 4 165
Пример 5 167
5.5. Упражнения 173
Глава 6. Файлы 177
6.1. Обращение к файлам 178
Последовательная запись в файл 179
Последовательное чтение из файла 180
Произвольная запись в файл 181
Произвольное чтение из файла 181
6.2. Поиск в файле 182
Поиск и замена в файле 186
6.3. Примеры программ обработки файлов 189
Пример 1 189
Пример 2 190
Пример 3 192
Пример 4 194
Пример 5 198
6.4. Упражнения 200
Глава 7. Техника указателей 203
7.1. Понятие указателя 203
7.2. Указатели на массивы 204
Операции над указателями 206
Доступ к значениям, адресуемым указателями 207
7.3. Указатели на строку 208
7.4. Указатели на функцию 208
Функции, возвращающие указатель 209
7.5. Динамическое распределение памяти 210
Динамическое выделение памяти 210
Освобождение динамически выделенной памяти 212
7.6. Примеры использования указателей 213
Пример 1 213
Пример 2 215
Пример 3 219
Пример 4 221
Пример 5 223
Пример 6 225
7.7. Упражнения 227
Глава 8. Объектно-ориентированное программирование 231
8.1. Структуры 232
8.2. Классы 236
Вложенные классы 242
Дружественные функции 242
Производные классы 245
Построение производного класса 246
Инкапсуляция 248
Статические члены класса 249
Класс ios 251
Указатель this 251
8.3. Конструктор и деструктор 252
8.4. Наследование 256
8.5. Упражнения 257
Глава 9. Основы теории графов 261
9.1. Понятие графа 261
Представление неориентированного графа 262
Представление неориентированного графа в памяти компьютера 263
Представление ориентированного графа 266
Представление ориентированного графа в памяти компьютера 267
Смежность и инцидентность 270
Цепи и циклы 272
9.2. Обходы графов 273
Обход в ширину 273
Реализация поиска в ширину 275
Обход в глубину 282
Реализация поиска в глубину 288
9.3. Примеры графов 299
Связные и несвязные графы 300
Регулярные графы 303
Двудольные графы 305
Пустые и полные графы 310
9.4. Эйлеровы графы 312
Алгоритм и реализация построения эйлерова цикла 314
9.5. Построение кратчайших путей 316
Алгоритм Дейкстры 318
Вывод кратчайшего пути 328
9.6. Раскраска вершин графа 332
9.7. Примеры решения задач при помощи графов 336
Пример 1 336
Пример 2 342
9.8. Упражнения 345
Глава 10. Основы шифрования 349
10.1. Классы алгоритмов шифрования 349
10.2. Требования к криптографическим системам 350
Криптоанализ 352
Безопасность алгоритмов 354
10.3. Перестановочные алгоритмы 356
Простой столбцевой перестановочный шифр 356
Перестановочный шифр с ключевым словом 359
10.4. Подстановочные шифры 362
Шифр Полибия 362
10.5. Шифрование сдвигом ASCII-значений 366
10.6. Криптосистема RSA 368
Математические идеи алгоритма 369
Алгоритм шифрования 370
Алгоритм дешифрования 370
Пример использования алгоритма RSA 371
10.7. Цифровые подписи 372
Предметный указатель 374
VIII Оглавление VII Оглавление