- •Основы алгоритмизации и программирования. Язык Си
- •Содержание
- •Глава 1. Введение в алгоритмы 11
- •Глава 2. Базовые средства языка Си 18
- •Глава 3. Константы в программах 26
- •Глава 4. Обзор операций 28
- •Глава 15. Динамические структуры данных 128
- •Глава 16. Переход к ооп 168
- •Предисловие
- •Глава 1. Введение в алгоритмы
- •1.1. Этапы решения задач на эвм
- •1.2. Понятие алгоритма
- •1.3. Свойства алгоритмов
- •1.4. Сложность алгоритма
- •1.5. Способы описания алгоритмов
- •1.6. Способы реализации алгоритмов
- •1.7. Пример простейшего линейного процесса
- •1.7. Пример циклического процесса
- •Глава 2. Базовые средства языка Си
- •2.1. Алфавит языка Си
- •2.2. Лексемы
- •2.3. Идентификаторы и ключевые слова
- •2.4. Комментарии
- •2.5. Простейшая программа
- •2.6. Основные типы данных
- •2.7. Декларация объектов
- •2.8. Данные целого типа (integer)
- •2.9. Данные символьного типа (char)
- •2.10. Данные вещественного типа (float, double)
- •2.11. Использование модификаторов при декларации производных типов данных
- •Глава 3. Константы в программах
- •3.1. Целочисленные константы
- •3.2. Константы вещественного типа
- •3.3. Символьные константы
- •3.4. Строковые константы
- •Глава 4. Обзор операций
- •4.1. Операции, выражения
- •4.2. Арифметические операции
- •4.3. Операция присваивания
- •4.4. Сокращенная запись операции присваивания
- •4.5. Преобразование типов операндов арифметических операций
- •4.6. Операция приведения типа
- •4.7. Операции сравнения
- •4.8. Логические операции
- •4.9. Побитовые логические операции, операции над битами
- •4.10. Операция «,» (запятая)
- •Глава 5. Обзор базовых инструкций языка Си
- •5.1. Стандартная библиотека языка Си
- •5.2. Стандартные математические функции
- •5.3. Функции вывода данных на дисплей
- •5.4. Функции ввода информации
- •Советы по программированию
- •Задание 1. Составление линейных алгоритмов Первый уровень сложности
- •Второй уровень сложности
- •Глава 6. Составление разветвляющихся алгоритмов
- •6.1. Краткая характеристика операторов языка Си
- •6.2. Условные операторы
- •If (выражение) оператор;
- •If (выражение) оператор 1 ;
- •If (выражение 1) оператор 1;
- •If (выражение 2) оператор 2;
- •If (выражение 3) оператор 3;
- •6.3. Условная операция «? :»
- •6.4. Оператор выбора альтернатив (переключатель)
- •Глава 7. Составление циклических алгоритмов
- •7.1. Понятие циклического кода
- •7.2. Оператор с предусловием while
- •7.3. Оператор цикла с постусловием do – while
- •7.4. Оператор цикла с предусловием и коррекцией for
- •Глава 8. Операторы и функции передачи управления
- •8.1. Оператор безусловного перехода goto
- •8.2. Операторы continue, break и return
- •8.3. Функции exit и abort
- •Советы по программированию
- •Задание 2. Разветвляющиеся алгоритмы Первый уровень сложности
- •Второй уровень сложности
- •Задание 3. Циклические алгоритмы Первый уровень сложности
- •Второй уровень сложности
- •Глава 9. Указатели
- •9.1. Определение указателей
- •9.2. Операция sizeof
- •9.3. Инициализация указателей
- •9.4. Операции над указателями
- •Глава 10. Массивы
- •10.1. Понятие массива
- •10.2. Одномерные массивы
- •10.3. Связь указателей и массивов
- •10.4. Строки как одномерные массивы данных типа char
- •10.5. Указатели на указатели
- •10.6. Многомерные массивы
- •10.7. Адресная функция
- •10.8. Работа с динамической памятью
- •10.9. Библиотечные функции
- •10.10. Пример создания одномерного динамического массива
- •10.11. Пример создания двухмерного динамического массива
- •Глава 11. Функции пользователя
- •11.1. Декларация функции
- •Тип_результата id_функции (список);
- •11.2. Вызов функции
- •11.3. Передача аргументов в функцию
- •11.4. Операция typedef
- •11.5. Указатели на функции
- •11.6. Рекурсивные функции
- •11.7. Параметры командной строки функции main
- •Глава 12. Классы памяти и область действия объектов
- •12.1. Классы памяти объектов в языке Cи
- •12.2. Автоматические переменные
- •12.3. Статические и внешние переменные
- •12.4. Область действия переменных
- •Советы по программированию
- •Задание 4. Обработка массивов Первый уровень сложности Составить программу, решающую указанную ниже задачу.
- •Второй уровень сложности
- •Задание 5. Функции пользователя Первый уровень сложности
- •Второй уровень сложности
- •Глава 13. Структуры, объединения, перечисления
- •13.1. Структуры
- •13.2. Декларация структурного типа данных
- •13.3. Создание структурных переменных
- •13.4. Обращение к полям структур
- •Id_структуры . Id_поля
- •13.5. Вложенные структуры
- •13.6. Массивы структур
- •13.7. Размещение структурных переменных в памяти
- •13.8. Объединения
- •13.9. Перечисления
- •13.10. Битовые поля
- •Глава 14. Файлы в языке Си
- •14.1. Открытие файла
- •14.2. Закрытие файла
- •14.3. Запись-чтение информации
- •14.4. Позиционирование в файле
- •14.5. Дополнительные файловые функции
- •Советы по программированию
- •Задание 6. Создание и обработка структур Первый уровень сложности
- •Второй уровень сложности
- •Задание 7. Создание и обработка файлов Первый уровень сложности
- •Второй уровень сложности
- •Глава 15. Динамические структуры данных
- •15.1. Линейные списки
- •15.2. Структура данных стек
- •15.2.1. Алгоритм формирования стека
- •15.2.2. Алгоритм извлечения элемента из стека
- •15.2.3. Просмотр стека
- •15.2.4. Алгоритм освобождения памяти, занятой стеком
- •15.2.5. Алгоритм проверки правильности расстановки скобок
- •15.3. Структура данных очередь
- •15.3.1. Формирование очереди
- •15.3.2. Алгоритм удаления первого элемента из очереди
- •15.4. Двунаправленный линейный список
- •15.4.1. Формирование первого элемента
- •15.4.2. Добавление элементов в конец списка
- •15.4.3. Алгоритм просмотра списка
- •15.4.4. Алгоритм поиска элемента в списке по ключу
- •15.4.5. Алгоритм удаления элемента в списке по ключу
- •15.4.6. Алгоритм вставки элемента в список после элемента с указанным ключом
- •15.5. Нелинейные структуры данных
- •15.5.1. Бинарные деревья
- •15.5.2. Основные алгоритмы работы с бинарным деревом
- •15.5.3. Формирование дерева
- •15.5.4. Вставка нового элемента
- •15.5.5. Удаление узла
- •15.5.6. Алгоритмы обхода дерева
- •15.5.7. Функция просмотра
- •15.5.8. Освобождение памяти
- •15.6. Построение обратной польской записи
- •15.6.1. Алгоритм, использующий дерево
- •15.6.2. Алгоритм, использующий стек
- •15.6.3. Пример реализации
- •15.7. Понятие хеширования
- •15.7.2. Примеры хеш-функций
- •15.7.3. Схемы хеширования
- •15.7.4. Примеры реализации схем хеширования
- •Задание 8. Обработка списков Вариант 1. Однонаправленные списки
- •Вариант 2. Двунаправленные списки
- •Задание 9. Деревья и польская запись Вариант 1. Создание и обработка структур типа «дерево»
- •Вариант 2. Создание и использование польской записи
- •Глава 16. Переход к ооп
- •16.1. Потоковый ввод-вывод
- •16.2. Управление выводом
- •16.4. Операции new и delete
- •16.5. Дополнительные возможности при работе с пользовательскими функциями Параметры со значениями по умолчанию
- •Перегрузка функций
- •Пример перегрузки функций
- •Функции с переменным числом параметров
- •16.6. Шаблоны функций Понятие шаблона функции
- •Перегрузка шаблонов функций
- •Советы по программированию
- •Задание 10. Перегрузка функций Первый уровень сложности
- •Второй уровень сложности
- •Стандартная часть таблицы символов ascii
- •Дополнительная часть таблицы символов
- •Операции языка Си
- •Возможности препроцессора
- •Директивы лексемного замещения идентификаторов
- •Директива отмены
- •Макрозамещение
- •Подключение файлов исходного текста
- •Условная компиляция
- •Изменение нумерации строк и идентификатора файла
- •Создание нового проекта
- •Добавление к проекту существующего файла
- •Создание и добавление к проекту нового файла
- •Компиляция, компоновка и выполнение проекта
- •Конфигурация проекта
- •Некоторые возможности графической подсистемы
- •6.1. Основные понятия
- •6.2. Контекст устройства
- •6.3. Примитивы gdi
- •6.4. Пример вывода текста
- •Стандартные функции Windows
- •Идентификаторы и типы данных
- •Основная программа
- •Регистрация класса окна
- •Создание окна
- •Отображение окна
- •Цикл обработки сообщений
- •Оконная процедура
- •Обработка сообщений
- •Сообщение wm_paint
- •Сообщение wm_destroy
- •6.5. Получение описателя контекста устройства
- •6.6. Основные инструменты графической подсистемы
- •Инструмент Pen
- •Инструмент Brush
- •Инструмент Font
- •6.7. Закрашивание пустот
- •6.8. Рисование линий и кривых
- •6.9. Пример изображения графика функции sin
- •6.10. Рисование замкнутых фигур
- •6.11. Функция Polygon и режим закрашивания многоугольника
- •6.12. Пример отображения линий
- •6.13. Управление областями вывода и отсечением
- •Работа с прямоугольниками
- •Создание и рисование регионов
- •Прямоугольники и регионы отсечения
- •6.14. Растровая графика
- •Задание 11. Создание графических изображений
- •Литература
- •Основы алгоритмизации и программирования. Язык Си
- •220013, Минск, п.Бровки, 6
Прямоугольники и регионы отсечения
Прямоугольники и регионы могут принимать участие в отсечении. Функция InvalidateRect делает недействительным прямоугольную область дисплея и генерирует сообщение WM_PAINT. Ее можно использовать, например, для обновления рабочей области:
InvalidateRect (hwnd, NULL, TRUE);
Получить координаты недействительного прямоугольника можно с помощью функции GetUpdateRect, а сделать действительным прямоугольник в рабочей области – ValidateRect.
Получая сообщение WM_PAINT, координаты недействительного прямоугольника доступны из полей структуры PAINTSTRUCT, заполняемой при вызове функции BeginPaint. Этот недействительный прямоугольник также определяет регион отсечения, за пределами которого нельзя рисовать.
Для создания региона отсечения (выбрав регион в контекст устройства) используются функции
SelectObject (hdc, hRgn); SelectClipRgn (hdc, hRgn);
регион отсечения задается в координатах устройства.
Среда Windows содержит несколько функций для манипуляции с регионом отсечения, таких как ExcludeClipRect – исключение прямоугольника из региона отсечения; IntersectClipRect – создание нового региона отсечения, который представляет собой пересечение предыдущего региона отсечения и прямоугольника; OffsetClipRgn – перемещение региона отсечения в другую часть рабочей области.
6.14. Растровая графика
Все рассмотренные выше функции базировались на вычерчивании графических примитивов определенными инструментами по заданным командам, т.е. по векторному принципу. Растровая графика предусматривает доступ к изображению на уровне образующих его точек.
Для большинства устройств отображения первичен растровый принцип формирования изображения. Некоторые контексты поддерживают не все функции растровой графики. Информацию о совместимости может предоставить функция GetDeviceCaps().
Простейшим и наиболее универсальным способом получения произвольных изображений является доступ к отдельным его точкам. Функции
COLORREF SetPixel (hdc, nX, nY, crColor);
BOOL SetPixelV (hdc, nX, nY, crColor);
COLORREF GetPixel (hdc, nX, nY);
выполняют соответственно изменение состояния (цвета) одной логической точки и получение текущего состояния. Функция SetPixelV() приводит значение цвета к ближайшему представимому в данном контексте цвету; возвращаемое значение – состояние точки на момент вызова функции (COLORREF), либо признак успешности выполнения (BOOL). Параметры
nX, nY – логические координаты точки (int);
crColor – новое значение цвета точки (COLORREF).
Более сложные и эффективные функции манипулируют не отдельными точками, а массивами точек – фрагментами изображений и битовыми образами.
Битовый образ (bitmap) – двухмерный массив числовых значений, характеризующий состояние точек некоторой области, обычно прямоугольной.
В простейшем случае битовый образ описывается структурой BITMAP, содержащей поля:
LONG bmType – тип образа, должен быть равен 0;
LONG bmWidth, LONG bmHeight – положительные значения ширины и высоты прямоугольной области в пикселах;
LONG bmWidthBytes – размер в байтах образа одной строки изображения, в среде Windows должен быть кратен 2, т.к. система предполагает, что массив состоит из слов;
WORD bmPlanes – количество цветовых планов (плоскостей), т.е. компонент, задающих цвет;
WORD bmBitsPixel – количество бит для кодирования цвета точки;
LPVOID bmBits – указатель на двухмерный массив данных, каждая строка которого соответствует одной строке изображения.
Используются монохромный и цветной типы образов. В случае монохромного – одноцветовой план и один бит на точку, единичное значение этого бита задает для точки цвет переднего плана (foreground), нулевое – заднего (backgroung).
Битовые образы – объекты, идентифицирующиеся их описателями – HBITMAP. Различают совместимые и контекстно-независимые объекты BITMAP.
Функции
HBITMAP CreateBitmap ( int nWidth, int nHeight, UINT cPlanes,
UINT cBitsPerPel, const void* lpvBits );
HBITMAP CreateBitmapIndirect (const BITMAP* lpBitmap);
создают объект BITMAP с указанными характеристиками, возвращаемое значение – описатель объекта или NULL в случае ошибки; параметры:
nWidth, nHeight – размеры образа в точках изображения;
cPlanes – количество цветовых планов;
cBitsPerPel – «глубина» цвета;
lpvBits – массив данных образа;
lpBitmap – структура BITMAP, содержащая перечисленные параметры.
Функция
HBITMAP CreateCompatibleBitmap (hdc, int nWidth, int nHeight);
создает объект BITMAP совместимого типа для заданного контекста с заданными размерами; в зависимости от контекста он может быть создан цветным или монохромным (если в контексте заданы данные раздела DIB – контекстно-независимым); возвращаемое значение – описатель объекта или NULL; nWidth и nHeight – размеры образа.
Для доступа к содержимому битового образа предусмотрены функции SetDlBits() и GetDlBits(), которые работают построчно, однако имеется возможность воздействовать на него всеми доступными инструментами. Для этого объект BITMAP связывается с некоторым контекстом с помощью универсальной функции SelectObject(), после чего все изменения в контексте будут отображаться и в битовом образе.
Функции:
BOOL BitBlt (HDC hDstDC, int nDstX, int nDstY, int nDstWidth,
int nDstHeight,HDC hSrcDC, int nSrcX, int nSrcY, DWORD dwRop);
BOOL StretchBlt (HDC hDstDC, int nDstX, int nDstY, int nDstWidth,
int nDstHeight, HDC hSrcDC, int nSrcX, int nSrcY, int nSrcWidth,
int nSrcHeight, DWORD dwRop);
BOOL MaskBlt (HDC hDstDC, int nDstX, int nDstY, int nDstWidth,
int nDstHeight, HDC hSrcDC, int nSrcX, int nSrcY,
HBITMAP hbmMask, int nMaskX, int nMaskY, DWORD dwRop);
BOOL PlgBlt (HDC hDstDC, const POINT* lpDstVertices, HDC hSrcDC,
int nSrcX, int nSrcY, HBITMAP hbmMask, int nMaskX, int nMaskY,
DWORD dwRop);
выполняют перенос прямоугольного фрагмента изображения из контекста-источника в контекст-приемник (с трансформацией и дополнительными операциями). Функция StretchBlt может изменять масштаб изображения фрагмента; MaskBlt позволяет маскировать часть изображения; PlgBlt осуществляет перенос в непрямоугольную область приемника с соответствующим искажением; возвращаемое значение – признак успешности выполнения; параметры:
hSrcDC, hDstDC – контексты источника и приемника данных;
nSrcX, nSrcY, nDstX, nDstY – координаты фрагмента в обоих контекстах;
nSrcWidth, nSrcHeight, nDstWidth, nDstHeight – размеры фрагментов;
hbmMask – битовый образ маски, монохромного типа, нулевые точки маски указывают на применение к данной точке изображения операции «заднего плана», единичные – «переднего плана»;
nMaskX, nMaskY – точка привязки в образе маски;
lpDstVertices – массив структур, задающих вершины параллелограмма, образующего фрагмент-приемник;
dwRop – дополнительная операция, применяемая к фрагменту при переносе: SRCCOPY – простое копирование, SRCAND – комбинация цветов источника и приемника по «И», SRCPAINT – комбинация по «ИЛИ», SRCINVERT – комбинация по «исключающему ИЛИ», SRCERASE – комбинация по «И» цвета источника и инверсии цвета приемника, NOTSRCCOPY, NOTSRCERASE – соответствует одноименным, но результирующий цвет инвертируется, DSTINVERT – инверсия фрагмента-приемника, BLACKNESS, WHITENESS – заполнение фрагмента-получателя цветом соответственно 0 и 1 физической палитры и другие. Для MaskBlt параметр включает операции для переднего и заднего фонов, формируется с помощью макроса MAKEROP4.
Для успешного применения этих функций требуется, чтобы оба контекста относились к одному устройству или идентичным устройствам.
При использовании функций следует учитывать, что в логических координатных системах, связанных с обоими контекстами, отсчитываются только координаты опорных точек и размеры границ фрагмента, содержимое же его всегда ориентировано одинаково.
Эффекты, возникающие при деформации битового образа, дополнительно управляются функцией SetStretchBltMode, текущая настойка –GetStretchBltMode.