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

Информатика в техническом университетеИнформатика в техническом университетеСеррш основана в 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-018ISBN 5-7038-1957-1© Г.С.

Иванова, 2002© Издательство МГТУим. Н.Э. Баумана, 2002ОглавлениеПредисловиеВведениеЧасть 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ ИПРОЦЕДУРНОЕ ПРОГРАММИРОВАНИЕ810121. Этапы создания программного обеспечения1.1. Постановка задачи1.2. Анализ, формальная постановка и выбор метода решения1.3. Проектирование1.4. Реализация1.5. Модификация1.6. Практикум. Разработка алгоритмов методом пошаговойдетализации121213142023242. Простейшие конструкции языка2.1.

Синтаксис и семантика языка программирования2.2. Структура программы2.3. Константы и переменные. Типы переменных2.4. Выражения2.5. Оператор присваивания2.6. Процедуры ввода-вывода2.7. Практикум. Оценка точности результатов28283031384042453. Управляющие операторы языка3.1. Оператор условной передачи управления3.2. Практикум. Тестирование программ3.3. Оператор выбора3.4. Операторы организации циклической обработки3.5. Практикум.

Точность решения задач вычислительнойматематики3.6. Неструктурные алгоритмы и их реализация505052565863694. Структурные типы данных4.1. Массивы4.2. Практикум. Обработка одномерных массивов777787Оглавление4.3. Практикум. Сортировка массивов. Оценка вычислительнойсложности алгоритма4.4. Практикум. Обработка матриц4.5. СтрокиА.6. Практикум. Обработка и поиск символьной информации4.7. Множества4.8.

Записи5. Модульное программирование5.1. Процедуры и функции5.2. Практикум. Выделение подпрограмм методом пошаговойдетализации5.3. Модули5.4. Открытые массивы и строки5.5. Нетипизированные параметры5.6. Параметры процедурного типа5.7. Рекурсия5.8. Практикум. Полный и ограниченный перебор. Реализацияограниченного перебора с использованием рекурсии96104113120127136144144:.1501561591621661681796.

Файловая система. Файлы6.1. Файловая система MS DOS6.2. Файлы Borland Pascal6.3. Текстовые файлы6.4. Типизированные файлы6.5. Нетипизированные файлы6.6. Процедуры и функции библиотеки DOS для работы с файлами . . . .1881881901962012072097. Программирование с использованием динамической памяти7.1. Указатели и операции над ними7.2. Управление динамической памятью7.3. Динамические структуры данных7.4. Линейные односвязные списки7.5. Бинарные деревья7.6.

Практикум. Разбор арифметических выражений с использованиембинарных деревьев2122122182232262388. Управление техническими средствами и взаимодействие с MS DOS8.1. Управление экраном в текстовом режиме8.2. Управление клавиатурой8.3. Управление динамиком8.4. Практикум. Создание меню8.5. Управление экраном в графическом режиме8.6. Практикум. Построение графиков и диаграмм8.7. Практикум. Создание движущихся изображений8.8.

Взаимодействие с драйвером мыши8.9. Управление задачами. Вызов дочерних процессов254254260262264267279285293300247ОглавлениеЧасть 2. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕПРОГРАММИРОВАНИЕ3039. Основные теоретические положения9.1. Объектная декомпозиция9.2. Классы и объекты-переменные9.3. Методы построения классов9.4. Этапы реализации объектно-ориентированного подхода30330330530631210.

Классы и объекты в Borland Pascal10.1. Объявление класса. Поля и методы10.2. Объявление объекта. Инициализация полей10.3. Библиотеки классов. Ограничение доступа к полям иметодам10.4. Практикум. Создание универсальных объектов314314316И. Иерархии классов11.1. Наследование11.2.

Композиция11.3. Наполнение11.4. Простой полиморфизм11.5. Сложный полиморфизм. Конструкторы11.6. Практикум. Использование полиморфизма при созданиидвижущихся изображений11.7. Динамические полиморфные объекты. Деструкторы11.8. Практикум. Создание контейнеров12. Разработка библиотеки интерфейсных компонентов12.1. Анализ реальной программы и определение основныхинтерфейсных компонентов12.2. Проектирование классов12.3.

Реализация универсальных интерфейсных компонентов12.4. Создание программы с использованием библиотеки интерфейсныхкомпонентов319321327327330332334336344348354360360365367373ПриложениеП1. Основные стандартные процедуры и функцииП2. Русская кодовая таблица для MS DOSПЗ. Расширенные scan-кодыП4. Основные отличия Delphi Pascal от Borland Pascal 7.0П5. Создание приложений Windows с использованием средыпрограммирования Delphi384384385386387391Список литературы413Предметный указатель414ПРЕДИСЛОВИЕПреподавание основ программирования в вузах сопряжено с целым ря­дом проблем. Во-первых, современное программирование - сложная и быс­тро развивающаяся наука. Если сравнить то, что студент должен знать в этойобласти сейчас и 20 лет назад, то разница окажется ошеломляющей.

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

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

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

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