Иванова Г.С. - Основы программирования

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

Серрш основана в 2000 году

РЕДАКЦИОННАЯ КОЛЛЕГИЯ:

д-р техн. наук И.Б, Федоров — главный редактор д-р техн. наук И.П, Норенков — зам. главного редактора

д-р техн. наук iD.M Смирнов — зам. главного редактора д-р техн. наук В,В, Девятков

д-р техн. наук В.В, Емельянов

канд. техн. наук ИМ, Иванов д-р техн. наук ВА, Матвеев канд. техн. наук ИЗ. Медведев д-р техн. наук В,В, Сюзев д-р техн. наук Б,Г. Трусов

д-р техн. наук В,М, Черненький

д-р техн. наук ВА, Шахнов

ГС. Иванова

Основы

программирования

Издание второе, переработанное и дополненное

Допущено Министерством образования Российской Федерации

в качестве учебника для студентов высших учебных заведений, обучающихся по направлению

«Информатика и вычислительная техника», специальностям: «Вычислительные машины, комплексы, системы и сети», «Автоматизированные системы обработки информации и управления», «Программное обеспечение вычислительной техники и информационных систем»

Москва Издательство МГТУ имени Н.Э. Баумана

2002

УДК 681.3.06(075.8) ББК 32.973-018

И201

Рецензенты:

профессор Л.Д. Забродин (Московский государственный инженернофизический институт); кафедра «ЭВМ, комплексы и сети» Московского государственного авиационного института (зав. кафедрой профессор О.М. Брехов)

Иванова Г.С.

И201 Основы программирования: Учебник для вузов. - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. ~ 416 с: ил. (Сер. Информатика в техническом университете.)

ISBN 5-7038-1957-1

Изложены основные теоретические положения разработки программного обеспе­ чения с использованием структурного и объектно-ориентированных подходов. По­ дробно рассмотрены основные приемы решения задач различных классов, в том чис­ ле приемы создания и обработки динамических структур данных, без которых невоз­ можно современное программирование. Особое внимание уделено оценке точности получаемых результатов и анализу вычислительной сложности алгоритмов и методов. Большое количество примеров и поясняющих рисунков помогает лучшему усвоению материала.

Во втором издании (1-е — 2001 г) для описания объектно-ориентированных про­ грамм использован Универсальный язык моделирования (UML). Добавлен материал по разработке приложений в Delphi, проиллюстрированный примерами.

Содержание учебника соответствует курсу лекций, которые автор читает в МГТУ им. Н.Э. Баумана.

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

УДК 681.3.06(075.8) ББК 32.973-018

	© Г.С. Иванова, 2002
	© Издательство МГТУ
ISBN 5-7038-1957-1	им. Н.Э. Баумана, 2002

Оглавление
Предисловие	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

Оглавление
4.3. Практикум. Сортировка массивов. Оценка вычислительной		96
сложности алгоритма
4.4. Практикум. Обработка матриц		104
4.5. Строки		113
А.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

Оглавление
Часть 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
И. Иерархии классов	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
компонентов
Приложение	384
П1. Основные стандартные процедуры и функции	384
П2. Русская кодовая таблица для MS DOS	385
ПЗ. Расширенные scan-коды	386
П4. Основные отличия Delphi Pascal от Borland Pascal 7.0	387
П5. Создание приложений Windows с использованием среды
программирования Delphi	391
Список литературы	413
Предметный указатель	414

ПРЕДИСЛОВИЕ

Преподавание основ программирования в вузах сопряжено с целым ря­ дом проблем. Во-первых, современное программирование - сложная и быс­ тро развивающаяся наука. Если сравнить то, что студент должен знать в этой области сейчас и 20 лет назад, то разница окажется ошеломляющей. В то же время реальные часы, отводимые в программах вузов для изучения основ программирования, практически не изменились. Во-вторых, подготовка сту­ дентов, осуществляемая в данной области школой, очень различна: от полно­ го отсутствия каких-либо знаний по предмету до относительно свободного владения каким-либо языком программирования.

Кроме того, программирование - наука, неразрывно связанная с практи­ кой. Невозможно научиться программировать, не проведя много часов за со­ ставлением алгоритмов, написанием и отладкой программ. Причем учебнопрактическую работу желательно совмещать с процессом изучения методов разработки программ и освоением особенностей конкретного языка про­ граммирования. Следовательно, элементы технологии программирования и алгоритмизации должны изучаться параллельно с языком программирова­ ния. Таким образом, один курс как бы включает в себя несколько курсов.

Решение перечисленных проблем потребовало тщательного отбора и структуризации материала, включенного в учебник. Данный учебник - ре­ зультат 20-летнего преподавания программирования в МГТУ им. Н.Э. Баума­ на. Курс,.читаемый автором в настоящее время, построен следующим обра­ зом.

Лекционно излагаются основы технологии программирования, сведе­ ния, необходимые для решения тех или иных задач, и поясняются конкрет­ ные языковые средства. Лекции иллюстрируются большим количеством ри­ сунков и примеров (программ и схем алгоритмов), желательно минимально­ го размера, чтобы конкретные возможности и особенности было легко по­ нять и запомнить.

Семинары посвящаются обсуждению определенных проблем, связан­ ных с решением некоторого класса задач. Как правило, на семинарах анали­ зируются не программы, а алгоритмы или подходы. Например, рассматрива­ ется метод пошаговой детализации и его применение для разработки алго-

Предисловие

ритмов, понятие и способы оценки точности полученных результатов, вы­ числительной и емкостной сложности разрабатываемого программного обеспечения и т. д.

Во время лабораторного практикума студенты самостоятельно под кон­ тролем преподавателей разрабатывают программы решения индивидуально­ го набора задач по изучаемым темам. Задание каждому студенту выдается в начале семестра, поэтому он имеет возможность выполнять задания по мере освоения материала, что обеспечивает определенную степень индивидуали­ зации обучения.

Изложение материала курса в учебнике следует той же схеме. Главы со­ держат необходимые сведения из теории программирования, описание кон­ кретных средств Borland Pascal и особенностей взаимодействия программ с техническими и программными средствами. При этом особое внимание уде­ лено наиболее важным моментам, без рассмотрения которых дальнейшее изучение программирования практически невозможно. Это, в частности, проблемы создания рекурсивных программ, работа с динамическими струк­ турами данных и объектно-ориентированный подход. Материал проблемных семинаров курса выделен в специальные разделы, названные практикумами. В конце большинства разделов приведены вопросы и задачи для самопровер­ ки.

Данная книга представляет собой второе издание учебника. В связи с новой редакцией программ обучения основам программирования в него включены материалы по основам событийного программирования и отличи­ ям Delphi Pascal от Borland Pascal 7.0. Кроме того, изменена графическая но­ тация, используемая для пояснения основ объектно-ориентированного про­ граммирования, что связано с практическим утверждением UML (Unified Modeling Language - Универсальный язык моделирования) в качестве меж­ дународного стандарта описания объектно-ориентированных разработок.

Автор глубоко признателен канд. техн. наук, доценту Т.Н.Ничушкиной за предоставленные материалы и огромную помош,ь в подготовке книги, а также рецензентам: заведующему кафедрой «Компьютерные системы и тех­ нологии» МИФИ д-ру техн. наук, профессору Л. Д. Забродину и коллективу кафедры «ЭВМ, комплексы и сети» МАИ во главе с д-ром техн. наук, про­ фессором О.М.Бреховым за полезные замечания и советы.

Хочется также выразить особую благодарность студентам, принявшим активное участие в обсуждении первого издания учебника, за их советы и за­ мечания, учтенные автором в данном издании.

ВВЕДЕНИЕ

Язык программирования Паскаль был создан в 1971 г. профессором Цю­ рихского университета Никлаусом Виртом и предназначался для обучения студентов как основам алгоритмизации и программирования, так и основам конструирования компиляторов. Язык полностью отвечал принципам струк­ турного программирования, сформулированным к тому'моменту, имел ярко выраженную блочную структуру и развитое представление данных. Однако, будучи учебным, он имел ограниченные средства реализации ввода-вывода и создания библиотек подпрограмм.

В разные годы было разработано несколько вариантов компиляторов с Паскаля для различных типов ЭВМ. Наибольшее распространение получил Turbo (Borland) Pascal, предложенный фирмой Borland Internation (США). Существовало несколько версий. Последняя версия, предназначенная для со­ здания программного обеспечения «под MS DOS» - версия 7.0, включает:

•интегрированную среду разработки программ, ставшую в некоторой степени прототипом создания аналогичных сред для других языков програм­ мирования;

•средства разработки многомодульных программ;

•средства управления экраном в текстовом и графических режимах;

•средства объектно-ориентированного программирования;

•усовершенствованную систему типов данных.

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

Весомым аргументом в пользу изучения основ программирования имен­ но на базе Паскаля также является существование профессиональной визу­ альной среды разработки программного обеспечения Delphi, которая исполь­ зует в качестве базового языка именно Паскаль. Практика показывает, что пе­ реход к разработке программного обеспечения в этой среде после изучения базового курса происходит достаточно безболезненно, хотя и требует некото­ рых дополнительных знаний,

10