Основы программирования

Информатика в техническом университете 
 

Информатика в техническом университете 
Серия основана в 2000 году 
РЕДАКЦИОННАЯ КОЛЛЕГИЯ: 
чл.-кор. РАН И.Б. Федоров — главный редактор 
д-р техн. наук И.П. Норенков — зам. главного редактора 
д-р техн. наук В.В. Девятков 
канд. техн. наук И.П. Иванов 
д-р техн. наук В.А. Матвеев 
канд. техн. наук Н.В. Медведев 
д-р техн. наук В.В. Сюзев 
д-р техн. наук Б.Г. Трусов 
д-р техн. наук В.М. Черненький 
д-р техн. наук В.А. Шахнов 

Г.С. Иванова
Основы
программирования
Издание четвертое, стереотипное
«
Допущено Министерством образования
Российской Федерации
в качестве учебника для студентов
высших учебных заведений, обучающихся по направлению
«Информатика и вычислительная техника»,
специальностям: «Вычислительные машины, комплексы,
системы и сети», Автоматизированные системы обработки
информации и управления», «Программное обеспечение
вычислительной техники и информационных систем»
Москва
Издательство МГТУ имени Н.Э. Баумана
2007

УДК 681.3.06(075.8)
ББК 32.973-018
И201
Рецензенты:
профессор Л.Д. Забродин (Московский государственный инженернофизический институт); кафедра «ЭВМ, комплексы и сети» Московского
государственного авиационного института (зав. кафедрой профессор 
О.М. Брехов) 
Иванова Г.С.
И201    
Основы программирования: Учебник для вузов. – 4-е изд., стер. –
М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. – 416 с.: ил. (Сер. «Информатика в техническом университете».)
ISBN 978-5-7038-3027-7
Изложены основные теоретические положения разработки программного обеспечения с использованием структурного и объектно-ориентированных подходов. Подробно рассмотрены основные приемы решения задач различных классов, в том числе
приемы создания и обработки динамических структур данных, без которых невозможно современное программирование. Особое внимание уделено оценке точности получаемых результатов и анализу вычислительной сложности алгоритмов и методов.
Большое количество примеров и поясняющих рисунков помогает лучшему усвоению
материала. 
Содержание учебника соответствует курсу лекций, которые автор читает в МГТУ
им. Н.Э. Баумана.
Для студентов вузов, обучающихся по специальностям, связанным с информатикой. Может быть полезен всем изучающим программирование самостоятельно. 
УДК 681.3.06(075.8)
ББК 32.973-018
© Г.С. Иванова, 2004
© Оформление. Издательство  
ISBN 978-5-7038-3027-7
МГТУ им. Н.Э. Баумана, 2004

Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
8
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
10
Часть 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ  
И ПРОЦЕДУРНОЕ ПРОГРАММИРОВАНИЕ . . . . . . . . . . . 
12
1. Этапы создания программного обеспечения . . . . . . . . . . . . . . . . . . . . . . . 
12
1.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
12
1.2. Анализ, формальная постановка и выбор метода решения . . . . . . . . . 
13
1.3. Проектирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
14
1.4. Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
20
1.5. Модификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
23
1.6. Практикум. Разработка алгоритмов методом пошаговой 
детализации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
24
2. Простейшие конструкции языка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
28
2.1. Синтаксис и семантика языка программирования . . . . . . . . . . . . . . . . . 
28
2.2. Структура программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
30
2.3. Константы и переменные. Типы переменных . . . . . . . . . . . . . . . . . . . . 
31
2.4. Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
38
2.5. Оператор присваивания. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
40
2.6. Процедуры ввода-вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
42
2.7. Практикум. Оценка точности результатов . . . . . . . . . . . . . . . . . . . . . . . 
45
3. Управляющие операторы языка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
50
3.1. Оператор условной передачи управления . . . . . . . . . . . . . . . . . . . . . . . . 
50
3.2. Практикум. Тестирование программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
52
3.3. Оператор выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
56
3.4. Операторы организации циклической обработки . . . . . . . . . . . . . . . . . 
58
3.5. Практикум. Точность решения задач вычислительной математики. . . 
63
3.6. Неструктурные алгоритмы и их реализация . . . . . . . . . . . . . . . . . . . . . 
69
4. Структурные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
77
4.1. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
77
4.2. Практикум. Обработка одномерных массивов . . . . . . . . . . . . . . . . . . . . 
87
5

Оглавление
4.3. Практикум. Сортировка массивов. Оценка вычислительной 
сложности алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
96
4.4. Практикум. Обработка матриц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
104
4.5. Строки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
113
4.6. Практикум. Обработка и поиск символьной информации . . . . . . . . . 
120
4.7. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
127
4.8. Записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
136
5. Модульное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
144
5.1. Процедуры и функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
144
5.2. Практикум. Выделение подпрограмм методом пошаговой 
детализации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
150
5.3. Модули . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
156
5.4. Открытые массивы и строки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
159
5.5. Нетипизированные параметры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
162
5.6. Параметры процедурного типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
166
5.7. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
168
5.8. Практикум. Полный и ограниченный перебор. Реализация    
ограниченного перебора с использованием рекурсии . . . . . . . . . . . . 
179
6. Файловая система. Файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
188
6.1. Файловая система MS DOS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
188
6.2. Файлы Borland Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
190
6.3. Текстовые  файлы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
196
6.4. Типизированные файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
201
6.5. Нетипизированные файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
207
6.6. Процедуры и функции библиотеки DOS для работы с файлами . . . . 
209
7. Программирование с использованием динамической памяти . . . . . . 
212
7.1. Указатели и операции над ними . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
212
7.2. Управление динамической памятью . . . . . . . . . . . . . . . . . . . . . . . . . . . 
218
7.3. Динамические структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
223
7.4. Линейные односвязные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
226
7.5. Бинарные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
238
7.6. Практикум. Разбор арифметических выражений с использованием  
бинарных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
247
8. Управление техническими средствами и взаимодействие с MS DOS . 
254
8.1. Управление экраном в текстовом режиме . . . . . . . . . . . . . . . . . . . . . . . 
254
8.2. Управление клавиатурой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
260
8.3. Управление динамиком . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
262
8.4. Практикум. Создание меню . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
264
8.5. Управление экраном в графическом режиме . . . . . . . . . . . . . . . . . . . . 
267
8.6. Практикум. Построение графиков и диаграмм . . . . . . . . . . . . . . . . . . 
279
8.7. Практикум. Создание движущихся изображений . . . . . . . . . . . . . . . . 
285
8.8. Взаимодействие с драйвером мыши . . . . . . . . . . . . . . . . . . . . . . . . . . . 
293
8.9. Управление задачами. Вызов дочерних процессов . . . . . . . . . . . . . . . 
300
6

Оглавление
Часть 2. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ 
ПРОГРАММИРОВАНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
9. Основные теоретические положения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
303
9.1. Объектная декомпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
303
9.2. Классы и объекты-переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
305
9.3. Методы построения классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
306
9.4. Этапы реализации объектно-ориентированного подхода . . . . . . . . . . 
312
10. Классы и объекты в Borland Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
314
10.1. Объявление класса. Поля и методы . . . . . . . . . . . . . . . . . . . . . . . . . . . 
314
10.2. Объявление объекта. Инициализация полей . . . . . . . . . . . . . . . . . . . . 
316
10.3. Библиотеки классов. Ограничение доступа к полям и методам . . . 
319
10.4. Практикум. Создание универсальных объектов . . . . . . . . . . . . . . . . . 
321
11. Иерархии классов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
327
11.1. Наследование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
327
11.2. Композиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
330
11.3. Наполнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
332
11.4. Простой полиморфизм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
334
11.5. Сложный полиморфизм. Конструкторы . . . . . . . . . . . . . . . . . . . . . . . 
336
11.6. Практикум. Использование полиморфизма при создании     
движущихся изображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
344
11.7. Динамические полиморфные объекты. Деструкторы . . . . . . . . . . . . 
348
11.8. Практикум. Создание контейнеров . . . . . . . . . . . . . . . . . . . . . . . . . . . 
354
12. Разработка библиотеки интерфейсных элементов . . . . . . . . . . . . . . . . 
360
12.1. Анализ реальной программы и определение основных 
интерфейсных элементов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
360
12.2. Проектирование классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
365
12.3. Реализация универсальных интерфейсных элементов . . . . . . . . . . . 
367
12.4. Создание программы с использованием библиотеки интерфейсных  
элементов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
373
Приложение
П1. Основные стандартные процедуры и функции . . . . . . . . . . . . . . . . . . . 
384
П2. Русская кодовая таблица для MS DOS . . . . . . . . . . . . . . . . . . . . . . . . . . 
385
П3. Расширенные scan-коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
386
П4. Основные отличия Delphi Pascal от Borland Pascal 7.0 . . . . . . . . . . . . . 
387
П5. Создание приложений Windows с использованием среды 
программирования Delphi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
391
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414

ПРЕДИСЛОВИЕ
Преподавание основ программирования в вузах сопряжено с целым рядом проблем. Во-первых, современное программирование – сложная и быстро развивающаяся наука. Если сравнить то, что студент должен знать в этой
области сейчас и 20 лет назад, то разница окажется ошеломляющей. В то же
время реальные часы, отводимые в программах вузов для изучения основ
программирования, практически не изменились. Во-вторых, подготовка студентов, осуществляемая в данной области школой, может варьироваться от
полного отсутствия каких-либо знаний по предмету до относительно свободного владения каким-либо языком программирования.
Кроме того, программирование – наука, неразрывно связанная с практикой. Невозможно научиться программировать, не проведя много часов за составлением алгоритмов, написанием и отладкой программ. Причем учебнопрактическую работу желательно совмещать с процессом изучения методов
разработки программ и освоением особенностей конкретного языка программирования. Следовательно, элементы технологии программирования и
алгоритмизации должны изучаться параллельно с языком программирования. Таким образом, один курс как бы включает в себя несколько курсов. 
Решение перечисленных проблем потребовало тщательного отбора и
структуризации материала, включенного в учебник. Это результат 20-летнего преподавания программирования в МГТУ им. Н.Э. Баумана. Курс, читаемый автором в настоящее время, построен следующим образом. 
На лекциях излагаются основы технологии программирования, сведения, необходимые для решения тех или иных задач, и поясняются конкретные языковые средства. Лекции иллюстрируются большим количеством
рисунков и примеров (программ и схем алгоритмов), по возможности минимального размера, чтобы конкретные возможности и особенности было легко понять и запомнить. 
Семинары посвящаются обсуждению определенных проблем, связанных с решением некоторого класса задач. Как правило, на них анализируются не программы, а алгоритмы или подходы. Например, рассматривается
метод пошаговой детализации и его применение для разработки алгорит8

Предисловие
мов, понятия «точность полученных результатов», «вычислительная сложность алгоритма», «емкостная сложность алгоритма» и способы их оценки. 
Во время лабораторного практикума студенты самостоятельно под контролем преподавателей разрабатывают программы решения индивидуального набора задач по изучаемым темам. Задание каждому студенту выдается в
начале семестра, поэтому он имеет возможность выполнять задания по мере
освоения материала, что обеспечивает определенную степень индивидуализации обучения.
Изложение материала курса в учебнике следует той же схеме. Главы содержат необходимые сведения из теории программирования, описание конкретных средств Borland Pascal и особенностей взаимодействия программ с
техническими и программными средствами. При этом особое внимание уделяется наиболее важным моментам, без рассмотрения которых дальнейшее
изучение программирования практически невозможно. Это, в частности,
проблемы создания рекурсивных программ, работа с динамическими структурами данных и объектно-ориентированный подход. Материал проблемных
семинаров курса выделен в специальные разделы, названные практикумами.
В конце большинства разделов приведены вопросы и задачи для самопроверки.
Данная книга представляет собой четвертое издание учебника. В связи с
новой редакцией программ обучения основам программирования в него
включены материалы по основам событийного программирования и отличиям Delphi Pascal от Borland Pascal 7.0. Кроме того, изменена графическая нотация, используемая для пояснения основ объектно-ориентированного программирования, что связано с практическим утверждением UML (Unified
Modeling Language – Универсальный язык моделирования) в качестве международного стандарта описания объектно-ориентированных разработок. 
Автор глубоко признателен кандидату технических наук, доценту 
Т.Н. Ничушкиной за предоставленные материалы и огромную помощь в подготовке книги, а также  рецензентам: заведующему кафедрой «Компьютерные системы и технологии» МИФИ доктору технических наук, профессору
Л. Д. Забродину и коллективу кафедры «ЭВМ, комплексы и сети» МАИ во
главе с доктором технических наук, профессором  О.М. Бреховым за полезные замечания и советы.
Хочется также выразить особую благодарность студентам, принявшим
активное участие в обсуждении первого издания учебника, за их советы и замечания, учтенные автором во втором издании данной книги.  

ВВЕДЕНИЕ
Язык программирования Паскаль был создан в 1971 г. профессором Цюрихского университета Никлаусом Виртом и предназначался для обучения
студентов как основам алгоритмизации и программирования, так и основам
конструирования компиляторов. Язык полностью отвечал принципам структурного программирования, сформулированным к тому моменту, имел ярко
выраженную блочную структуру и развитое представление данных. Однако,
будучи учебным, он имел ограниченные средства реализации ввода-вывода и
создания библиотек подпрограмм.
В разные годы было разработано несколько вариантов компиляторов с
Паскаля для различных типов ЭВМ. Наибольшее распространение получил
Turbo (Borland) Pascal, предложенный фирмой Borland Internation (США).
Существовало несколько версий. Последняя версия, предназначенная для создания программного обеспечения «под MS DOS» – версия 7.0, включает:
• интегрированную среду разработки программ, ставшую в некоторой
степени прототипом создания аналогичных сред для других языков программирования; 
• средства разработки многомодульных программ;
• средства управления экраном в текстовом и графических режимах;
• средства объектно-ориентированного программирования;
• усовершенствованную систему типов данных.
Современным программистам приходится иметь дело с огромным количеством разнообразных языков программирования различных уровней и назначений. Но по-прежнему начинать изучение программирования целесообразно на базе Паскаля, так как при использовании этого языка у будущего
программиста быстрее формируется четкое алгоритмическое мышление.
Весомым аргументом в пользу изучения основ программирования именно на базе Паскаля также является существование профессиональной визуальной среды разработки программного обеспечения Delphi, которая использует в качестве базового языка Паскаль. Практика показывает, что переход к
разработке программного обеспечения в этой среде после изучения базового
курса происходит достаточно безболезненно, хотя и требует некоторых дополнительных знаний. 
10