- •Основы алгоритмизации и программирования. Язык Си
- •Содержание
- •Глава 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. Разветвляющиеся алгоритмы
- •Второй уровень сложности
- •Глава 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
2.9. Данные символьного типа (char)
Под величину символьного типа отводится такое количество байт, которое достаточно для любого символа. Поэтому символьная переменная занимает в памяти один байт. Закрепление конкретных символов за кодами производится кодовыми таблицами.
Для персональных компьютеров (ПК) наиболее распространена ASCII (American Standard Code for Information Interchenge) таблица кодов (см. прил. 1). Данные типа char рассматриваются компилятором как целые, поэтому возможно использование signed char: величины со знаком (по умолчанию) – символы с кодами от –128 до +127 и unsigned char – беззнаковые символы с кодами от 0 до 255. Этого достаточно для хранения любого символа из 256-символьного набора ASCII. Величины типа char применяют еще и для хранения целых чисел из указанных диапазонов.
Примеры: char res, simv1, simv2;
char let= 's'; – декларация символьной переменной с инициализацией символомs.
2.10. Данные вещественного типа (float, double)
Данные вещественного типа в памяти занимают (табл. 2.2): float – 4 байта(одинарная точность),double(удвоенная точность) – 8 байт;long double(повышенная точность) – 10 байт. Для размещения данных типаfloatобычно 8 бит выделено для представления порядка и знака и 24 бита под мантиссу.
Таблица 2.2
Тип |
Точность (мантисса) |
Порядок |
float(4 байта) |
7 цифр после запятой |
38 |
double (8 байт) |
15 |
308 |
long double (10 байт) |
19 |
4932 |
Типы данных с плавающей десятичной точкой хранятся в оперативной памяти иначе, чем целочисленные. Внутреннее представление вещественного числа состоит из двух частей: мантиссы и порядка (см. разд. 3.2 «Константы вещественного типа»). В IBMсовместимых ПК, как вы уже знаете, переменная типаfloatзанимает 4 байта, из которых один двоичный разряд отводится под знак мантиссы, 8 разрядов под порядок и 23 под мантиссу. Мантисса – это число больше единицы и меньше двух. Поскольку старшая цифра мантиссы всегда равна единице, то ее не хранят.
Для величин типа doublе, занимающих 8 байт, под порядок и мантиссу отводится 11 и 52 разряда соответственно. Длина мантиссы определяет точность числа, а порядок – его диапазон. Как можно видеть из приведенных выше таблиц, при одинаковом количестве байт, отводимом под величины типаfloatиlong int, диапазоны их допустимых значений сильно различаются из-за внутренней формы представления значений таких данных.
При переносе программы с одной платформы на другую нельзя делать предположений, например, о типе int, так как для оперативной системы (ОС) MS DOS этот тип имеет размер в два байта, а для ОС Windows 9X – четыре байта. В стандарте ANSI поэтому диапазоны значений для основных типов не задаются, а определяются только соотношения между их размерами, например:
sizeof (float) < sizeof (double) < sizeof (long double) ,
sizeof (char) < sizeof (short) < sizeof (int) < sizeof (long) ,
где операция sizeof– возвращает количество байт для указанного аргумента – скалярного типа данных.
2.11. Использование модификаторов при декларации производных типов данных
Ключевые слова int,float,charи т.д. называют конечными атрибутами декларации объектов программы. При декларации так называемых производных объектов используют еще дополнительные – промежуточные атрибуты или, как их иногда называют, «модификаторы».
К символам модификации текущего типа относятся:
– символ * перед идентификатором, обозначающий декларацию указателя на объект исходного типа (левый промежуточный атрибут);
– символы [ ] после идентификатора объекта – декларация массива объектов;
– символы ( ) после идентификатора объекта – декларация функции (правые промежуточные атрибуты).
Допускается использование более одного модификатора типа с учетом следующих правил:
1) чем ближе модификатор к IDобъекта, тем выше его приоритет;
2) при одинаковом расстоянии от идентификатора объекта модификаторы [ ] и ( ) обладают приоритетом перед атрибутом звездочка *;
3) дополнительные круглые скобки позволяют изменить приоритет объединяемых ими элементов описания;
4) квадратные и круглые скобки, имеющие одинаковый приоритет, рассматриваются слева направо.
Конечный атрибут декларации принимается во внимание в последнюю очередь, т.е. тогда, когда все промежуточные атрибуты уже проинтерпретированы.
Примеры декларации объектов с конечным атрибутом int:
int a; – переменная типаint;
int a[5]; – массив из пяти элементов типаint;
int*a; – указатель на объект типаint;
int**a; – указатель на указатель на объект типаint;
int*a[5]; – массив из пяти указателей на элементы типаint;
int(*a)[10]; – указатель на массив из десяти элементов типаint;
int*a[3][4]; – 3-элементный массив указателей на одномерные целочисленные массивы по четыре элемента каждый;
inta[5][2]; – двухмерный массив элементов типаint;
inta(void); – функция без параметров, возвращающая значение типаint;
int*a(void); – функция без параметров, возвращающая указатель на элемент типаint;
int(*a)(void); – указатель на функцию без параметров, возвращающую значение типаint;
int*a(void)[6]; – функция без параметров, возвращающая указатель на массив элементов типаint;
int*a[4](void); – массив указателей на функцию без параметров, возвращающую значение типаint.
Существуют и недопустимые последовательности промежуточных атрибутов, например, массив не может состоять из функций, а функция не может возвращать массив или другую функцию.