Батура, М. П.

Б 28 Основы алгоритмизации и программирования. Язык Си : учеб. пособие / М. П. Батура, В. Л. Бусько, А. Г. Корбит, Т. М. Кривоносова. – Минск : БГУИР, 2007. – 240 с. : ил.

ISBN 978-985-488-192-8

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

Содержание пособия охватывает темы, посвященные основным конструкциям языка Си. Приведенные примеры, иллюстрирующие основные возможности языка, прошли проверку в качестве консольных приложений среды программирования Visual C++ 6.0.

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

УДК 621.3 (075.8)

ББК 22.193 я 73

ISBN 978-985-488-192-8 ã УО «Белорусский государственный

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

и радиоэлектроники», 2007

СОДЕРЖАНИЕ

ПРЕДИСЛОВИЕ. 8

ГЛАВА 1. Введение в алгоритмы.. 10

1.1. Этапы решения задач на ЭВМ.. 10

1.2. Понятие алгоритма. 10

1.3. Свойства алгоритмов. 11

1.4. Сложность алгоритма. 11

1.5. Способы описания алгоритмов. 12

1.6. Способы реализации алгоритмов. 14

1.7. Пример простейшего линейного процесса. 14

1.7. Пример циклического процесса. 15

ГЛАВА 2. Базовые средства языка Си. 17

2.1. Алфавит языка Си. 17

2.2. Лексемы.. 17

2.3. Идентификаторы и ключевые слова. 18

2.4. Комментарии. 19

2.5. Простейшая программа. 19

2.6. Основные типы данных. 20

2.7. Декларация объектов. 21

2.8. Данные целого типа (integer) 22

2.9. Данные символьного типа (char) 22

2.10. Данные вещественного типа (float, double) 23

2.11. Использование модификаторов при декларации производных типов данных 24

ГЛАВА 3. Константы в программах. 25

3.1. Целочисленные константы.. 25

3.2. Константы вещественного типа. 26

3.3. Символьные константы.. 26

3.4. Строковые константы.. 27

ГЛАВА 4. Обзор операций. 27

4.1. Операции, выражения. 27

4.2. Арифметические операции. 28

4.3. Операция присваивания. 28

4.4. Сокращенная запись операции присваивания. 29

4.5. Преобразование типов операндов арифметических операций. 30

4.6. Операция приведения типа. 31

4.7. Операции сравнения. 31

4.8. Логические операции. 32

4.9. Побитовые логические операции, операции над битами. 33

4.10. Операция «,» (запятая) 35

ГЛАВА 5. Обзор базовых инструкций языка Си. 35

5.1. Стандартная библиотека языка Си. 35

5.2. Стандартные математические функции. 35

5.3. Функции вывода данных на дисплей. 36

5.4. Функции ввода информации. 38

Советы по программированию.. 39

ЗАДАНИЕ 1. Составление линейных алгоритмов. 40

Первый уровень сложности. 40

Второй уровень сложности. 41

ГЛАВА 6. Составление разветвляющихся алгоритмов. 44

6.1. Краткая характеристика операторов языка Си. 44

6.2. Условные операторы.. 44

6.3. Условная операция «? :». 47

6.4. Оператор выбора альтернатив (переключатель) 48

ГЛАВА 7. Составление циклических алгоритмов. 52

7.1. Понятие циклического кода. 52

7.2. Оператор с предусловием while. 52

7.3. Оператор цикла с постусловием do – while. 54

7.4. Оператор цикла с предусловием и коррекцией for 55

ГЛАВА 8. Операторы и функции передачи управления. 58

8.1. Оператор безусловного перехода goto. 58

8.2. Операторы continue, break и return. 58

8.3. Функции exit и abort 59

Советы по программированию.. 59

ЗАДАНИЕ 2. Разветвляющиеся алгоритмы.. 60

Первый уровень сложности. 60

Второй уровень сложности. 61

ЗАДАНИЕ 3. Циклические алгоритмы.. 62

Первый уровень сложности. 62

Второй уровень сложности. 63

ГЛАВА 9. Указатели. 64

9.1. Определение указателей. 64

9.2. Операция sizeof 67

9.3. Инициализация указателей. 67

9.4. Операции над указателями. 69

ГЛАВА 10. Массивы.. 70

10.1. Понятие массива. 70

10.2. Одномерные массивы.. 71

10.3. Связь указателей и массивов. 72

10.4. Строки как одномерные массивы данных типа char 73

10.5. Указатели на указатели. 76

10.6. Многомерные массивы.. 77

10.7. Адресная функция. 79

10.8. Работа с динамической памятью.. 80

10.9. Библиотечные функции. 81

10.10. Пример создания одномерного динамического массива. 81

10.11. Пример создания двухмерного динамического массива. 83

ГЛАВА 11. Функции пользователя. 83

11.1. Декларация функции. 84

11.2. Вызов функции. 86

11.3. Передача аргументов в функцию.. 87

11.4. Операция typedef 88

11.5. Указатели на функции. 89

11.6. Рекурсивные функции. 93

11.7. Параметры командной строки функции main. 96

ГЛАВА 12. Классы памяти и область действия объектов. 97

12.1. Классы памяти объектов в языке Cи. 97

12.2. Автоматические переменные. 98

12.3. Статические и внешние переменные. 98

12.4. Область действия переменных. 101

Советы по программированию.. 103

ЗАДАНИЕ 4. Обработка массивов. 104

Первый уровень сложности. 104

Второй уровень сложности. 105

ЗАДАНИЕ 5. Функции пользователя. 106

Первый уровень сложности. 106

Второй уровень сложности. 106

ГЛАВА 13. Структуры, объединения, перечисления. 108

13.1. Структуры.. 108

13.2. Декларация структурного типа данных. 108

13.3. Создание структурных переменных. 109

13.4. Обращение к полям структур. 110

13.5. Вложенные структуры.. 111

13.6. Массивы структур. 112

13.7. Размещение структурных переменных в памяти. 113

13.8. Объединения. 114

13.9. Перечисления. 115

13.10. Битовые поля. 116

ГЛАВА 14. Файлы в языке Си. 117

14.1. Открытие файла. 118

14.2. Закрытие файла. 119

14.3. Запись – чтение информации. 120

14.4. Позиционирование в файле. 121

14.5. Дополнительные файловые функции. 122

Советы по программированию.. 124

ЗАДАНИЕ 6. Создание и обработка структур. 124

Первый уровень сложности. 124

Второй уровень сложности. 125

ЗАДАНИЕ 7. Создание и обработка файлов. 126

Первый уровень сложности. 126

Второй уровень сложности. 126

ГЛАВА 15. Динамические структуры данных. 127

15.1. Линейные списки. 127

15.2. Структура данных СТЕК.. 128

15.2.1. Алгоритм формирования стека. 129

15.2.2. Алгоритм извлечения элемента из стека. 131

15.2.3. Просмотр стека. 131

15.2.4. Алгоритм освобождения памяти, занятой стеком. 132

15.2.5. Алгоритм проверки правильности расстановки скобок. 133

15.3. Структура данных ОЧЕРЕДЬ. 133

15.3.1. Формирование очереди. 134

15.3.2. Алгоритм удаления первого элемента из очереди. 136

15.4. Двунаправленный линейный список. 136

15.4.1. Формирование первого элемента. 137

15.4.2. Добавление элементов в конец списка. 138

15.4.3. Алгоритм просмотра списка. 138

15.4.4. Алгоритм поиска элемента в списке по ключу. 138

15.4.5. Алгоритм удаления элемента в списке по ключу. 139

15.4.6. Алгоритм вставки элемента в список после элемента
с указанным ключом. 140

15.5. Нелинейные структуры данных. 141

15.5.1. Бинарные деревья. 142

15.5.2. Основные алгоритмы работы с бинарным деревом. 143

15.5.3. Формирование дерева. 144

15.5.4. Вставка нового элемента. 144

15.5.5. Удаление узла. 146

15.5.6. Алгоритмы обхода дерева. 148

15.5.7. Функция просмотра. 150

15.5.8. Освобождение памяти. 150

15.6. Построение обратной польской записи. 151

15.6.1. Алгоритм, использующий дерево. 151

15.6.2. Алгоритм, использующий стек. 152

15.6.3. Пример реализации. 153

15.7. Понятие хеширования. 156

15.7.1. Хеш-таблица и хеш-функции. 156

15.7.2. Примеры хеш-функций. 157

15.7.3. Схемы хеширования. 159

15.7.4. Примеры реализации схем хеширования. 160

ЗАДАНИЕ 8. Обработка списков. 162

Вариант 1. Однонаправленные списки. 162

Вариант 2. Двунаправленные списки. 163

ЗАДАНИЕ 9. Деревья и польская запись. 164

Вариант 1. Создание и обработка структур типа «дерево». 164

Вариант 2. Создание и использование польской записи. 165

ГЛАВА 16. Переход к ООП.. 166

16.1. Потоковый ввод-вывод. 166

16.2. Управление выводом. 166

16.3. Проблема ввода-вывода кириллицы в среде Visual C++.. 169

16.4. Операции new и delete. 170

16.5. Дополнительные возможности при работе с пользовательскими функциями 172

16.6. Шаблоны функций. 175

Советы по программированию.. 180

ЗАДАНИЕ 10. Перегрузка функций. 181

Первый уровень сложности. 181

Второй уровень сложности. 182

ПРИЛОЖЕНИЕ 1. Таблицы символов ASCII 184

ПРИЛОЖЕНИЕ 2. Операции языка Си. 185

ПРИЛОЖЕНИЕ 3. Возможности препроцессора. 187

ПРИЛОЖЕНИЕ 4. Интегрированная среда программирования Visual C++. 191

ПРИЛОЖЕНИЕ 5. Некоторые возможности отладчика Visual C++. 198

ПРИЛОЖЕНИЕ 6. Некоторые возможности графической подсистемы.. 204

6.1. Основные понятия. 204

6.2. Контекст устройства. 204

6.3. Примитивы GDI 204

6.4. Пример вывода текста. 205

6.5. Получение описателя контекста устройства. 216

6.6. Основные инструменты графической подсистемы.. 217

6.7. Закрашивание пустот. 223

6.8. Рисование линий и кривых. 223

6.9. Пример изображения графика функции sin. 225

6.10. Рисование замкнутых фигур. 227

6.11. Функция Polygon и режим закрашивания многоугольника. 229

6.12. Пример отображения линий. 229

6.13. Управление областями вывода и отсечением. 230

6.14. Растровая графика. 233

ЗАДАНИЕ 11. Создание графических изображений. 236

ЛИТЕРАТУРА.. 238

ПРЕДИСЛОВИЕ

Алгоритмический язык Си был разработан в 1972 г. сотрудником фирмы AT&T Bell Laboratory Денисом Ритчи на базе языка В (автор К.Томпсон), который в свою очередь основывался на языке системного программирования BCPL. Первая версия языка была опубликована в книге авторов Б. Кернигана и Д. Ритчи и получила название стандарт K&R. Минимальная стандартная реализация, поддерживаемая любым компилятором, содержала всего 27 ключевых слов. Началось успешное развитие языка и, чтобы избежать путаницы, Американский институт стандартизации (American National Standart Institute) ввел в 1983 г. общий стандарт языка – ANSI-стандарт.

Язык продолжает развиваться, и в 1985 г. появляется язык С++, который в основном сохраняет все черты обычного Си, но дополнен новыми существен­ными возможностями, которые позволили реализовать объектно-ориентирован­ный стиль программирования.

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

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

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

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

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

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

Текст программы, записанный на языке высокого уровня и введенный с помощью клавиатуры в память компьютера, – исходный модуль. Программы, написанные в среде программирования, предназначенной для языка Си, например Turbo C, имеют расширение *.с. Расширение *.cpp имеют программы, написанные в интегрированных средах Borland C++, Visual C++, Builder C++, предназначенных для написания программ как на языке Си, так и на языке С++.

Большинство трансляторов языка Си – компиляторы.

Результат обработки исходного модуля компилятором – объектный модуль(расширение *.obj). На этом этапе компилятор выделяет лексемы (элементарные конструкции языка), затем на основе грамматики распознает выражения и операторы, построенные из этих лексем. При этом компилятор выявляет синтаксические ошибки и, в случае их отсутствия, создает объектный модуль.

Исполняемый (абсолютный, загрузочный) модуль создает вторая специальная программа – «компоновщик». Ее еще называют редактором связей (Linker). Она и создает загрузочный модуль (расширение *.exe) на основе одного или нескольких объектных модулей – это программный модуль, представленный в форме, пригодной для выполнения.

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