Книга: Борисенко В. В. «Основы программирования»

Серия: "Основы информатики и математики"

Книга предназначена для обучения основам программирования. Рассматриваются основные понятия программирования - алгоритма, исполнителя, алгоритмического языка, переменной, основные типы данных, управляющие конструкции алгоритмического языка и т. п. Излагаются общие приемы программирования, основанные на применении математики, такие, как вычисление функций на последовательностях с помощью применения теории индуктивных функций и схема построения цикла с помощью инварианта.
Рассматриваются общие принципы устройства и работы компьютера, типичные команды и регистры процессора, методы адресации, способы вызова функций и передачи параметров и т. п. Приводятся примеры записи программ как на виртуальном Ассемблере RTL, так и на Ассемблере процессора Intel 80386. Кратко рассмотрены аппаратные средства поддержки многозадачности. Значительная часть книги посвящена основам языка Си. Помимо основ языка, в ней приведено много примеров реализации алгоритмов на Си, таких как вычисление корня функции, приведение матрицы к ступенчатому виду методом Гаусса, работа с файлами и текстами и т. п.
Заключительная глава посвящена структурам данных и их реализациям. Рассматриваются структуры последовательного и прямого доступа, такие как стек, очередь, список, дерево, множество и нагруженное множество, а также их непрерывные и ссылочные реализации. Значительное место уделено реализациям множеста с помощью бинарного поиска, на базе сбалансированнных деревьев и с помощью хеш-функции.
Книга полезна студентам и преподавателям ВУЗов.

Содержание:

Глава 1. Общее понятие алгоритма...... 1 1. 1. Алгоритмические языки...... 2 1. 2. Управляющие конструкции алгоритмического языка...... 5 1. 3. Понятие переменной...... 10 1. 4. Типы переменных...... 14 1. 4. 1. Целочисленные переменные...... 14 1. 4. 2. Вещественные переменные...... 20 1. 4. 3. Символьные переменные...... 27 1. 4. 4. Логические переменные и выражения...... 29 1. 4. 5. Массивы...... 32 1. 4. 6. Текстовые строки...... 33 1. 5. Примеры алгоритмов...... 34 1. 5. 1. Вычисление функций на последовательностях...... 34 1. 5. 2. Построение цикла с помощью инварианта...... 51 Глава 2. Устройство компьютера...... 67 2. 1. Оперативная память...... 68 2. 2. Процессор...... 70 2. 2. 1. CISC и RISC-процессоры...... 73 2. 2. 2. Алгоритм работы компьютера...... 74 2. 3. Аппаратный стек...... 75 2. 3. 1. Команды вызова подпрограммы call и возврата return...... 77 2. 3. 2. Аппаратный стек и локальные переменные подпрограммы...... 78 2. 4. RTL: машинно-независимый Ассемблер...... 81 2. 4. 1. Примеры программ на RTL и Ассемблере Intel 80x86...... 84 2. 4. 2. Задачи по теме «Программирование на Ассемблере»...... 90 2. 5. Внешние устройства и аппаратные прерывания...... 91 2. 6. Виртуальная память и поддержка параллельных задач...... 93 2. 6. 1. Страничная организация памяти...... 93 2. 6. 2. Переключение между процессами и нитями...... 94 Глава 3. Основы языка Си...... 97 3. 1. Структура Си-программы...... 98 3. 2. Функции...... 101 3. 2. 1. Программа "Hello, World!"...... 102 3. 3. Типы переменных...... 104 3. 3. 1. Базовые типы...... 104 3. 3. 2. Конструирование новых типов...... 109 3. 4. Выражения...... 119 3. 4. 1. Оператор присваивания...... 119 3. 4. 2. Арифметические операции...... 120 3. 4. 3. Операции увеличения и уменьшения...... 121 3. 4. 4. Операции «увеличить на», «домножить на» и т. п...... 123 3. 4. 5. Логические операции...... 125 3. 4. 6. Операции сравнения...... 126 3. 4. 7. Побитовые логические операции...... 127 3. 4. 8. Операции сдвига...... 131 3. 4. 9. Арифметика указателей...... 132 3. 4. 10. Связь между указателями и массивами...... 134 3. 4. 11. Операция приведения типа...... 135 3. 5. Управляющие конструкции...... 137 3. 5. 1. Фигурные скобки...... 138 3. 5. 2. Оператор if...... 138 3. 5. 3. Выбор из нескольких возможностей: if...else if...... 140 3. 5. 4. Пример: решение квадратного уравнения...... 141 3. 5. 5. Цикл while...... 145 3. 5. 6. Пример: вычисление квадратного корня методом деления отрезка пополам...... 147 3. 5. 7. Выход из цикла break, переход на конец цикла continue...... 149 3. 5. 8. Оператор перехода на метку goto...... 151 3. 5. 9. Цикл for...... 152 3. 5. 10. Операция «запятая» и цикл for...... 154 3. 5. 11. Конструкции, которые лучше не использовать...... 156 3. 6. Представление программы в виде функций...... 160 3. 6. 1. Прототипы функций...... 160 3. 6. 2. Пример: вычисление наибольшего общего делителя...... 161 3. 6. 3. Передача параметров функциям...... 162 3. 6. 4. Пример: расширенный алгоритм Евклида...... 163 3. 7. Работа с памятью...... 166 3. 7. 1. Статическая память...... 166 3. 7. 2. Стековая, или локальная, память...... 169 3. 7. 3. Динамическая память, или куча...... 170 3. 7. 4. Пример: печать п первых простых чисел...... 172 3. 7. 5. Операторы new и delete языка С++...... 174 3. 8. Структуры...... 177 3. 8. 1. Структуры и указатели...... 179 3. 8. 2. Пример: рекурсивный обход дерева...... 181 3. 8. 3. Структуры и оператор определения типа typedef...... 183 3. 9. Технология программирования на Си...... 185 3. 9. 1. Представление матриц и многомерных массивов...... 185 3. 9. 2. Пример: приведение матрицы к ступенчатому виду методом Гаусса...... 188 3. 9. 3. Работа с файлами...... 196 3. 9. 4. Работа с текстами...... 219 3. 9. 5. Разработка больших проектов...... 240 3. 9. 6. Задачи по теме «Технология программирования на Си»...... 242 Глава 4. Структуры данных...... 246 4. 1. Общее понятие структуры данных...... 246 4. 2. Массив как базовая структура...... 248 4. 3. Реализация одних структур на базе других...... 249 4. 4. Простейшие структуры данных. Стек. Очередь...... 250 4. 4. 1. Очередь...... 250 4. 4. 2. Стек...... 253 4. 5. Ссылочные реализации структур данных...... 283 4. 5. 1. Массовые операции...... 284 4. 5. 2. Список...... 285 4. 5. 3. Ссылочная реализация списка...... 286 4. 5. 4. Деревья и графы...... 287 4. 6. Множество...... 291 4. 6. 1. Реализации множества: последовательный и бинарный поиск, хеширование...... 293 4. 6. 2. Бинарный поиск...... 294 4. 6. 3. Реализации множества на базе деревьев...... 297 4. 6. 4. Хеширование...... 304 4. 6. 5. Циклы «для каждого» и итераторы...... 306 4. 7. Задачи по теме «Структуры данных»...... 307 Литература...... 309 Предметный указатель...... 311

Издательство: "Интернет-Университет Информационных Технологий" (2005)

ISBN: 5955600396