Алгоритмизации
 Скачать 1.15 Mb.
|
|
М. П. Батура, В. Л. Бусько, А. Г. Корбит, Т. М. Кривоносова ОСНОВЫАЛГОРИТМИЗАЦИИИПРОГРАММИРОВАНИЯ. ЯЗЫК СИДопущеноМинистерствомобразованияРеспубликиБеларусь в качестве учебного пособия для студентов учреждений, обеспечивающих получение высшегообразованияпоспециальностям«Искусственныйинтеллект», «Программноеобеспечениеинформационныхтехнологий», «Автоматизированныесистемыобработкиинформации», «Электронныевычислительныесредства», «Инженерно-психологическоеобеспечениеинформационныхтехнологий» Минск БГУИР 2007 УДК 621.3 (075.8) ББК22.193 я 73 Б 28 Р е ц е н з е н т ы : зав. кафедрой алгоритмики и дискретной математики БГУ, д-р техн. наук, проф. В. М. Котов; начальник кафедры систем автоматического управления Военной академии Республики Беларусь, д-р техн. наук, проф. В. А. Куренев Батура, М. П. Б 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 � УО «Белорусский государственный университет информатики 2  и радиоэлектроники», 2007 СОДЕРЖАНИЕПРЕДИСЛОВИЕ 8 ГЛАВА 1. Введение в алгоритмы 10 Этапы решения задач на ЭВМ 10 Понятие алгоритма 10 Свойства алгоритмов 11 Сложность алгоритма 11 Способы описания алгоритмов 12 Способы реализации алгоритмов 14 Пример простейшего линейного процесса 15 1.7. Пример циклического процесса 16 ГЛАВА 2. Базовые средства языка Си 17 Алфавит языка Си 17 Лексемы 17 Идентификаторы и ключевые слова 18 Комментарии 19 Простейшая программа 19 Основные типы данных 20 Декларация объектов 21 Данные целого типа (integer) 22 Данные символьного типа (char) 22 Данные вещественного типа (float, double) 23 Использование модификаторов при декларации производных типов данных 24 ГЛАВА 3. Константы в программах 25 Целочисленные константы 25 Константы вещественного типа 26 Символьные константы 26 Строковые константы 27 ГЛАВА 4. Обзор операций 27 Операции, выражения 27 Арифметические операции 28 Операция присваивания 29 Сокращенная запись операции присваивания 29 Преобразование типов операндов арифметических операций 30 Операция приведения типа 31 Операции сравнения 31 Логические операции 32 Побитовые логические операции, операции над битами 33 Операция «,» (запятая) 35 ГЛАВА 5. Обзор базовых инструкций языка Си 35 Стандартная библиотека языка Си 35 Стандартные математические функции 36 Функции вывода данных на дисплей 36 Функции ввода информации 38 Советы по программированию 40 ЗАДАНИЕ 1. Составление линейных алгоритмов 40 Первый уровень сложности 40 Второй уровень сложности 42 ГЛАВА 6. Составление разветвляющихся алгоритмов 44 Краткая характеристика операторов языка Си 44 Условные операторы 44 Условная операция «? :» 47 Оператор выбора альтернатив (переключатель) 48 ГЛАВА 7. Составление циклических алгоритмов 52 Понятие циклического кода 52 Оператор с предусловием while52 Оператор цикла с постусловием do – while 54 Оператор цикла с предусловием и коррекцией for55 ГЛАВА 8. Операторы и функции передачи управления 58 Оператор безусловного перехода goto58 Операторы continue, break и return 58 Функции exit и abort 59 Советы по программированию 59 ЗАДАНИЕ 2. Разветвляющиеся алгоритмы 60 Первый уровень сложности 60 Второй уровень сложности 61 ЗАДАНИЕ 3. Циклические алгоритмы 62 Первый уровень сложности 62 Второй уровень сложности 63 ГЛАВА 9. Указатели 64 Определение указателей 64 Операция sizeof 67 Инициализация указателей 67 Операции над указателями 69 ГЛАВА 10. Массивы 71 Понятие массива 71 Одномерные массивы 72 Связь указателей и массивов 72 Строки как одномерные массивы данных типа char74 Указатели на указатели 77 Многомерные массивы 77 Адресная функция 79 Работа с динамической памятью 81 Библиотечные функции 81 Пример создания одномерного динамического массива 82 Пример создания двухмерного динамического массива 83 ГЛАВА 11. Функции пользователя 84 Декларация функции 85 Вызов функции 86 Передача аргументов в функцию 88 Операция typedef89 Указатели на функции 89 Рекурсивные функции 93 Параметры командной строки функции main96 ГЛАВА 12. Классы памяти и область действия объектов 97 Классы памяти объектов в языке Cи 97 Автоматические переменные 98 Статические и внешние переменные 99 Область действия переменных 101 Советы по программированию 104 ЗАДАНИЕ 4. Обработка массивов 105 Первый уровень сложности 105 Второй уровень сложности 106 ЗАДАНИЕ 5. Функции пользователя 107 Первый уровень сложности 107 Второй уровень сложности 107 ГЛАВА 13. Структуры, объединения, перечисления 108 Структуры 108 Декларация структурного типа данных 109 Создание структурных переменных 110 Обращение к полям структур 111 Вложенные структуры 112 Массивы структур 113 Размещение структурных переменных в памяти 114 Объединения 114 Перечисления 115 Битовые поля 117 ГЛАВА 14. Файлы в языке Си 118 Открытие файла 118 Закрытие файла 120 Запись – чтение информации 121 Позиционирование в файле 122 Дополнительные файловые функции 123 Советы по программированию 124 ЗАДАНИЕ 6. Создание и обработка структур 125 Первый уровень сложности 125 Второй уровень сложности 126 ЗАДАНИЕ 7. Создание и обработка файлов 126 Первый уровень сложности 126 Второй уровень сложности 127 ГЛАВА 15. Динамические структуры данных 128 Линейные списки 128 Структура данных СТЕК 129 Алгоритм формирования стека 130 Алгоритм извлечения элемента из стека 132 Просмотр стека 132 Алгоритм освобождения памяти, занятой стеком 133 Алгоритм проверки правильности расстановки скобок 133 Структура данных ОЧЕРЕДЬ 134 Формирование очереди 135 Алгоритм удаления первого элемента из очереди 137 Двунаправленный линейный список 137 Формирование первого элемента 138 Добавление элементов в конец списка 138 Алгоритм просмотра списка 139 Алгоритм поиска элемента в списке по ключу 139 Алгоритм удаления элемента в списке по ключу 140 Алгоритм вставки элемента в список после элемента с указанным ключом 141 Нелинейные структуры данных 142 Бинарные деревья 143 Основные алгоритмы работы с бинарным деревом 144 Формирование дерева 144 Вставка нового элемента 145 Удаление узла 146 Алгоритмы обхода дерева 149 Функция просмотра 150 Освобождение памяти 151 Построение обратной польской записи 151 Алгоритм, использующий дерево 152 Алгоритм, использующий стек 153 Пример реализации 154 Понятие хеширования 157 Хеш-таблица и хеш-функции 157 Примеры хеш-функций 158 Схемы хеширования 160 Примеры реализации схем хеширования 161 ЗАДАНИЕ 8. Обработка списков 163 Вариант 1. Однонаправленные списки 163 Вариант 2. Двунаправленные списки 164 ЗАДАНИЕ 9. Деревья и польская запись 165 Вариант 1. Создание и обработка структур типа «дерево» 165 Вариант 2. Создание и использование польской записи 166 ГЛАВА 16. Переход к ООП 168 Потоковый ввод-вывод 168 Управление выводом 168 Проблема ввода-вывода кириллицы в среде VisualC++171 Операции newи delete173 Дополнительные возможности при работе с пользовательскими функциями 174 Шаблоны функций 178 Советы по программированию 182 ЗАДАНИЕ 10. Перегрузка функций 183 Первый уровень сложности 183 Второй уровень сложности 184 ПРИЛОЖЕНИЕ 1. Таблицы символов ASCII186 ПРИЛОЖЕНИЕ 2. Операции языка Си 187 ПРИЛОЖЕНИЕ 3. Возможности препроцессора 189 ПРИЛОЖЕНИЕ 4. Интегрированная среда программирования VisualC++ 193 ПРИЛОЖЕНИЕ 5. Некоторые возможности отладчикаVisualC++ 200 ПРИЛОЖЕНИЕ 6. Некоторые возможности графической подсистемы 206 Основные понятия 206 Контекст устройства 206 Примитивы GDI206 Пример вывода текста 207 Получение описателя контекста устройства 218 Основные инструменты графической подсистемы 219 Закрашивание пустот 225 Рисование линий и кривых 225 Пример изображения графика функции sin227 Рисование замкнутых фигур 229 Функция Polygonи режим закрашивания многоугольника 231 Пример отображения линий 231 Управление областями вывода и отсечением 232 Растровая графика 235 ЗАДАНИЕ 11. Создание графических изображений 238 ЛИТЕРАТУРА 240 |