Министерство образования и науки Российской Федерации Федеральное агентство по образованию

Московский государственный университет печати

Попов Д.И Демидов Д.Г.

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ВЫСОКОГО УРОВНЯ СИ

Конспект лекций

для студентов высших учебных заведений, обучающихся по специальности 230102.65 «Автоматизированные системы обработки информации и управления»

Москва

2009

УДК

ББК

П

Рецензенты:

Попов Д.И. Демидов Д.Г.

Программирование на языке высокого уровня Си: конспект лекций / Д.И.Попов, Демидов Д.Г. – М.: МГУП, 2009. – 202 с.

ISBN

Конспект лекций рассчитан на студентов, владеющих минимальными знаниями и навыками в области информатики и математики. В конспекте лекций представлены основные темы из Государственного образовательного стандарта по дисциплине «Программирование на языке высокого уровня» для студентов высших учебных заведений, обучающихся по специальности 230102.65 «Автоматизированные системы обработки информации и управления». Особое внимание уделяется изучению следующих разделов: основные этапы решения задач на ЭВМ, жизненный цикл и критерии качества программы, проект и спецификация программы, схемы алгоритмов и способы записи алгоритмов, структура программы на языке высокого уровня Си, стандартные типы данных, представление основных управляющих структур программирования, функции, массивы, структуры, работа с файлами, динамические структуры данных, способы реализации линейных списков, стека, деревьев, рекурсивные определения и алгоритмы, программирование рекурсивных алгоритмов.

ISBN	© Попов Д.И., 2009
	© Демидов Д.Г., 2009
	© Московский государственный
	университет печати, 2009

2

Тема 1. Основные этапы решения задач на ЭВМ..............................................................................	5
Постановка задачи разработки программного обеспечения.........................................................	5
Анализ формальной постановки задачи.........................................................................................	6
Выбор или разработка математической модели и метода решения.............................................	7
Разработка алгоритма ......................................................................................................................	9
Базовые структуры алгоритма ......................................................................................................	13
Тема 2. Жизненный цикл программы. Критерии качества программы.........................................	19
Техническое задание и спецификация программы......................................................................	21
Разработка проекта программной системы .................................................................................	26
Программирование (кодирование) или программная реализация алгоритмов........................	26
Тестирование и отладка..................................................................................................................	30
Эксплуатация и сопровождение....................................................................................................	32
Критерии качества программного обеспечения...........................................................................	32
Тема 3. Схемы алгоритмов, данных, программ...............................................................................	38
Символы данных.............................................................................................................................	41
......................................................................................................................................................	41
Отображает данные, вводимые в ручную, во время обработки с устройств любого типа
(клавиатура, переключатели, кнопки, световое перо, полоски со штрих кодом и т.д.).......	41
Символ отображает хранимые данные в виде, пригодном для обработки. Носитель
данных не определен. В схемах алгоритмов он предназначен для обозначения ввода-
вывода данных в случае использования запоминающего устройства, управляемого
процесса.......................................................................................................................................	41
Символы процесса..........................................................................................................................	43
Символы линий...............................................................................................................................	44
Специальные символы....................................................................................................................	45
Правила применения символов в схемах......................................................................................	45
Правила выполнения соединений.................................................................................................	48
Специальные условные обозначения............................................................................................	49
Тема 4. Язык программирования высокого уровня Си...................................................................	50
Общие сведения о языке Си...........................................................................................................	50
Алфавит языка Си...........................................................................................................................	51
Грамматика для описания языка, синтаксические диаграммы...................................................	52
Структура программы на языке Си...............................................................................................	56
Имена объектов в программе.........................................................................................................	59
Выражения, операции и приоритеты............................................................................................	62
Тема 5. Стандартные типы данных...................................................................................................	64
Тема 6. Составные типы данных.......................................................................................................	68
Данные регулярного типа (массивы) ...........................................................................................	68
Строки..............................................................................................................................................	70
Данные комбинированного типа (структуры)..............................................................................	76
Перечисления..................................................................................................................................	79
Объединения....................................................................................................................................	81
Указатели.........................................................................................................................................	81
Тема 7. Представление основных управляющих структур программирования...........................	87
Оператор присваивания..................................................................................................................	87
Составной оператор .......................................................................................................................	88
Оператор перехода Goto.................................................................................................................	88
Условный оператор If.....................................................................................................................	89
Оператор выбора switch..................................................................................................................	91
Операторы цикла while, do – while, for.........................................................................................	92
Операторы прерывания циклов.....................................................................................................	96
Форматированный ввод данных....................................................................................................	97

3

Форматированный вывод данных.................................................................................................	99
Преобразование типов..................................................................................................................	101
Инициализация данных................................................................................................................	105
Тема 8. Функции...............................................................................................................................	107
Определение функций в языке Си...............................................................................................	107
Вызов функций в языке Си..........................................................................................................	114
Рекурсивные функции..................................................................................................................	116
Тема 9. Файлы...................................................................................................................................	131
Тема 10. Приемы программирования. Примеры алгоритмов.......................................................	137
Алгоритмы сортировки................................................................................................................	137
Алгоритмы поиска........................................................................................................................	142
Динамические структуры данных ..............................................................................................	147
Линейные списки..........................................................................................................................	149
Стек, очередь, дек.........................................................................................................................	156
Деревья...........................................................................................................................................	162
Приложение 1. Стандартные библиотеки языка Си......................................................................	168
Приложение 2. Примеры реализации алгоритмов.........................................................................	176
Не рекурсивный алгоритм решения задачи Ханойская башня.................................................	198
Рекурсивный алгоритм решения задачи Ханойская башня......................................................	201
Приложение 3. Лабораторные работы............................................................................................	216
Лабораторная работа №1..............................................................................................................	216
Лабораторная работа №2..............................................................................................................	216
Лабораторная работа №3..............................................................................................................	217
Лабораторная работа №4..............................................................................................................	217
Лабораторная работа №5..............................................................................................................	218
Лабораторная работа №6..............................................................................................................	218
Лабораторная работа №7..............................................................................................................	219
Лабораторная работа №8..............................................................................................................	219
Лабораторная работа №9..............................................................................................................	220
Лабораторная работа №10............................................................................................................	220
Лабораторная работа №11............................................................................................................	221
Лабораторная работа №12............................................................................................................	221
Список литературы...........................................................................................................................	221

4

Тема 1. Основные этапы решения задач на ЭВМ

Постановка задачи разработки программного обеспечения

Решение любой прикладной задачи с использованием электронных вычислительных машин (ЭВМ) состоит из следующих этапов: анализ требований и формальная постановка задачи; выбор или разработка математической модели; анализ способов решения; логическое проектирование и разработка алгоритма; кодирование (написание программы); тестирование и отладка программного обеспечения; внедрение, использование и сопровождение программного обеспечения.

Постановка задачи разработки программного обеспечения является самым первым и наиболее важным этапом при проектировании программного обеспечения. Именно здесь закладывается фундамент будущей программы. Если на этом этапе допущены ошибки или не предусмотрены какие-то важные детали, то это отразится на конечном результате, а вносить изменения и исправления в такой проект будет крайне проблематично. Более того, если задача поставлена неверно, то её дальнейшее решение не имеет смысла. На этапе постановки задачи необходимо ответить на следующие вопросы:

∙существуют ли методы или способы решения задачи без использования ЭВМ, нужно ли решать данную задачу на ЭВМ;

∙какие «дивиденды» принесет использование ЭВМ для решения задачи, что будет улучшено, ускорено, оптимизировано, сэкономлено при использовании ЭВМ, какова основная цель применения ЭВМ;

∙что необходимо из оборудования, кроме универсальной ЭВМ, какой тип ЭВМ необходим для решения задачи, какая платформа(ы) ЭВМ может подойти, какая операционная система будет управлять работой ЭВМ, какое дополнительное программное обеспечение нужно;

∙каковы бизнес-процессы и документооборот прикладной предметной области, где будет применяться разрабатываемое программное обеспечение;

5

∙каков формат исходных (входных) данных, какие данные и в какой форме необходимы для решения задачи;

∙каков формат промежуточных и выходных данных, какие данные и в какой форме необходимо получить;

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

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

Анализ формальной постановки задачи

Итак, самый первый шаг в проектировании программного обеспечения заключается в точном формулировании целей внедрения программы. В постановке задачи должны принять участие заказчики и разработчики программного обеспечения. Необходимо, чтобы этот процесс был гибко организован и продолжался в течение длительного времени, поскольку на любом этапе разработки или внедрения могут вскрываться ранее не предусмотренные трудности, требующие внесения определенных изменений в проект. В то же время с целью упрощения разработки следует запретить радикальный пересмотр требований на стадии кодирования (реализации) программы. Необходимо также заранее определить условия внесения несущественных изменений в проект. Все договоренности такого плана должны оформляться разработчиком и заказчиком программы в официальном порядке в виде некоторых пунктов в договоре на разработку программного обеспечения, дополнительных протоколов или актов.

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

6

пользователям. Часто сами программисты являются соответствующей стороной и выполняют предварительную работу вместе с пользователями.

Официальному заключению договора обычно предшествуют:

∙выяснение реальной необходимости такой системы;

∙оценка возможности ее разработки и примерного объема затрат;

∙определение ожидаемого эффекта от внедрения.

После завершения этапа предварительных исследований составляют список требований, предъявляемых к программному обеспечению. Сюда входят:

∙анализ обстановки (совокупность условий, в которых предполагается эксплуатировать программную систему: используемые аппаратные и программные ресурсы, внешние условия ее функционирования, состав людей и работ, относящихся к системе);

∙описание выполняемых программной системой функций (четкое описание того, что должна делать система, на основании каких входных данных, какие данные являются выходными);

∙ограничения, которые должны учитываться в процессе проектирования (сроки завершения; ресурсы, имеющиеся в наличии, в том числе и

финансовые организационные мероприятия, обеспечивающие сохранность информации).

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

Выбор или разработка математической модели и метода решения

Модель представляет собой описание объекта (предмета, процесса или явления) на каком-либо формализованном языке, составленное с целью изучения его свойств. Если речь идет о математической модели, значит она представлена на формализованном языке математики, с помощью математических понятий. Соответствие свойств модели исходному объекту характеризуется

7

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

1.Приближение (параметры считаются очень большими или очень малыми). Если можно построить уравнения, описывающие исследуемую задачу, то это не значит, что их можно решить даже с помощью компьютера. Общепринятый прием в этом случае – использование приближений. Например, модель идеального газа для описания достаточно разреженных газов, где потенциальной энергией молекул можно пренебречь (т.е. считать бесконечно малой) по сравнению с их кинетической энергией.

2.Упрощение (опускаются некоторые детали). В модели отбрасываются детали, которые могут заметно и не всегда контролируемо повлиять на результат. Одни и те же уравнения могут служить моделью типа приближение или упрощение – это зависит от объекта, для изучения которого используется модель. Например, некоторые сложные нелинейные уравнения заменяются линейными, т.е. все нелинейные детали «для ясности» опускаются.

3.Эвристика (количественного подтверждения нет, но модель способствует более глубокому проникновению в суть дела). Эвристическая модель сохраняет лишь качественное подобие реальности и даёт описания объекта только «по порядку величины». Типичный пример – приближение средней длины свободного пробега в кинетической теории. Она даёт простые формулы для коэффициентов вязкости, диффузии, теплопроводности,

согласующиеся с реальностью по порядку величины.

Чтобы построить математическую модель решаемой задачи, необходимо: внимательно изучить постановку задачи; выбрать или разработать математические методы, позволяющие правильно описать задачу; чётко представить на языке математики описание задачи и цели решения. Грамотное

8