- •СОДЕРЖАНИЕ
- •ПРЕДИСЛОВИЕ
- •ГЛАВА 1. Введение в алгоритмы
- •1.1. Этапы решения задач на ЭВМ
- •1.2. Понятие алгоритма
- •1.3. Свойства алгоритмов
- •1.4. Сложность алгоритма
- •1.7. Пример простейшего линейного процесса
- •1.7. Пример циклического процесса
- •ГЛАВА 2. Базовые средства языка Си
- •2.1. Алфавит языка Си
- •2.2. Лексемы
- •2.3. Идентификаторы и ключевые слова
- •2.4. Комментарии
- •2.5. Простейшая программа
- •2.7. Декларация объектов
- •2.8. Данные целого типа (integer)
- •2.9. Данные символьного типа (char)
- •2.10. Данные вещественного типа (float, double)
- •ГЛАВА 3. Константы в программах
- •3.2. Константы вещественного типа
- •3.4. Строковые константы
- •ГЛАВА 4. Обзор операций
- •4.1. Операции, выражения
- •4.3. Операция присваивания
- •4.4. Сокращенная запись операции присваивания
- •4.7. Операции сравнения
- •4.8. Логические операции
- •4.10. Операция «,» (запятая)
- •ГЛАВА 5. Обзор базовых инструкций языка Си
- •5.2. Стандартные математические функции
- •5.3. Функции вывода данных на дисплей
- •5.4. Функции ввода информации
- •ГЛАВА 6. Составление разветвляющихся алгоритмов
- •6.1. Краткая характеристика операторов языка Си
- •ГЛАВА 7. Составление циклических алгоритмов
- •7.1. Понятие циклического кода
- •7.2. Оператор с предусловием while
- •7.4. Оператор цикла с предусловием и коррекцией for
- •ГЛАВА 8. Операторы и функции передачи управления
- •8.1. Оператор безусловного перехода goto
- •8.2. Операторы continue, break и return
- •8.3. Функции exit и abort
- •Советы по программированию
- •ГЛАВА 9. Указатели
- •9.1. Определение указателей
- •9.2. Операция sizeof
- •9.3. Инициализация указателей
- •9.4. Операции над указателями
- •ГЛАВА 10. Массивы
- •10.1. Понятие массива
- •10.2. Одномерные массивы
- •10.4. Строки как одномерные массивы данных типа char
- •10.5. Указатели на указатели
- •10.8. Работа с динамической памятью
- •10.9. Библиотечные функции
- •10.10. Пример создания одномерного динамического массива
- •ГЛАВА 11. Функции пользователя
- •11.1. Декларация функции
- •11.2. Вызов функции
- •11.3. Передача аргументов в функцию
- •11.4. Операция typedef
- •11.5. Указатели на функции
- •ГЛАВА 12. Классы памяти и область действия объектов
- •ЗАДАНИЕ 4. Обработка массивов
- •Первый уровень сложности
- •Второй уровень сложности
- •ЗАДАНИЕ 5. Функции пользователя
- •Первый уровень сложности
- •Второй уровень сложности
- •12.3. Статические и внешние переменные
- •12.4. Область действия переменных
- •Советы по программированию
- •13.1. Структуры
- •13.5. Вложенные структуры
- •13.6. Массивы структур
- •13.7. Размещение структурных переменных в памяти
- •13.8. Объединения
- •13.9. Перечисления
- •13.10. Битовые поля
- •ГЛАВА 14. Файлы в языке Си
- •14.1. Открытие файла
- •14.2. Закрытие файла
- •14.3. Запись-чтение информации
- •14.5. Дополнительные файловые функции
- •Советы по программированию
- •ЗАДАНИЕ 7. Создание и обработка файлов
- •Первый уровень сложности
- •Второй уровень сложности
- •ГЛАВА 15. Динамические структуры данных
- •15.1. Линейные списки
- •15.2.1. Алгоритм формирования стека
- •15.2.2. Алгоритм извлечения элемента из стека
- •15.2.3. Просмотр стека
- •15.2.4. Алгоритм освобождения памяти, занятой стеком
- •15.2.5. Алгоритм проверки правильности расстановки скобок
- •15.3.1. Формирование очереди
- •15.3.2. Алгоритм удаления первого элемента из очереди
- •15.4. Двунаправленный линейный список
- •15.4.1. Формирование первого элемента
- •15.4.3. Алгоритм просмотра списка
- •15.4.5. Алгоритм удаления элемента в списке по ключу
- •15.5. Нелинейные структуры данных
- •15.5.1. Бинарные деревья
- •15.5.2. Основные алгоритмы работы с бинарным деревом
- •15.5.4. Вставка нового элемента
- •15.6. Построение обратной польской записи
- •15.6.1. Алгоритм, использующий дерево
- •15.6.2. Алгоритм, использующий стек
- •15.6.3. Пример реализации
- •15.7. Понятие хеширования
- •15.7.2. Примеры хеш-функций
- •15.7.3. Схемы хеширования
- •15.7.4. Примеры реализации схем хеширования
- •Вариант 2. Двунаправленные списки
- •ГЛАВА 16. Переход к ООП
- •16.1. Потоковый ввод-вывод
- •16.3. Проблема ввода-вывода кириллицы в среде Visual C++
- •16.4. Операции new и delete
- •16.6. Шаблоны функций
- •Первый уровень сложности
- •Второй уровень сложности
- •6.1. Основные понятия
- •6.3. Примитивы GDI
- •6.5. Получение описателя контекста устройства
- •6.6. Основные инструменты графической подсистемы
- •6.7. Закрашивание пустот
- •6.8. Рисование линий и кривых
- •6.9. Пример изображения графика функции sin
- •6.10. Рисование замкнутых фигур
- •6.11. Функция Polygon и режим закрашивания многоугольника
- •6.13. Управление областями вывода и отсечением
- •ЗАДАНИЕ 11. Создание графических изображений
- •ЛИТЕРАТУРА
– если тип указателей справа и слева от операции присваивания один и тот же.
Если переменная-указатель выходит из области своего действия, отведенная под нее память освобождается. Следовательно, динамическая переменная, на которую ссылался указатель, становится недоступной. При этом память, на которую указывала сама динамическая переменная, не освобождается. Такая ситуация называется «замусоривание оперативной
памяти». Еще одна причина появления «мусора» – когда инициализированному указателю присваивается значение другого указателя. При этом старое значение указателя теряется. Р
9.4. Операции над указателями
Помимо уже рассмотренных операций, с указателями можно выполнять арифметические операции сложения, инкремента (++), вычитания,
только к указателям одного типа и имеют смысл в основном при работе со структурами данных, последовательно р змещенными в памяти, например с
декремента (--) и операции сравнения. |
|
И |
|
Арифметические операции с указателями автоматически учитывают |
|||
размер типа величин, адресуемых указателями. Эти операцииУ |
применимы |
||
|
Г |
|
|
|
Б |
|
|
массивами. |
|
|
|
к |
||
Инкремент |
перемещает |
указатель |
следующему элементу массива, |
|||
декремент – к предыдущему. |
|
а |
||||
Указатель, таким образом, мож т использоваться в выражениях вида |
||||||
|
|
т |
|
|
|
|
|
p # iv, ## p, |
p ##, p # = iv, |
||||
p – указатель, iv – целочисленноеениевыраж |
, # – символ операции '+' или '–'. |
|||||
|
о |
|
|
|
|
|
Результатом таких выражений является увеличенное или уменьшенное |
||||||
|
ипа |
|
|
|
|
|
значение указателя на величину iv * sizeof(*p), т.е. если указатель на |
||||||
определенный т |
увел чивается или |
уменьшается на константу, его |
значение изменяетсялна величину этой константы, умноженную на размер объекта данного т .
Текущеебзначение указателя всегда ссылается на позицию некоторого объектарив памяти с учетом правил выравнивания для соответствующего типа данных. Так м о разом, значение p # iv указывает на объект того же типа, расположенныйБ в памяти со смещением на iv позиций.
П сравнении указателей могут использоваться отношения любого вида («>», «<» и т.д.), но наиболее важными видами проверок являются отношения равенства и неравенства («==», «!=»).
Отношения порядка имеют смысл только для указателей на последовательно размещенные объекты (элементы одного массива).
Разность двух указателей дает число объектов адресуемого ими типа в соответствующем диапазоне адресов, т.е. в применении к массивам разность указателей, например, на третий и шестой элементы равна 3.
69
Очевидно, что уменьшаемый и вычитаемый указатели должны принадлежать одному массиву, иначе результат операции не имеет практической ценности и может привести к непредсказуемому результату. То же можно сказать и о суммировании указателей.
Значение указателя можно вывести на экран с помощью функции printf, используя спецификацию %p (pointer), результат выводится в шестнадцатеричном виде.
Рассмотрим фрагмент программы:
int a = 5, *p, *p1, *p2; |
|
|
|
|
|
|
|
|
|
|
|
||||||
p = &a; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
p2 = p1 = p; |
|
|
|
|
|
|
|
|
|
|
|
|
И |
||||
++p1; |
|
|
|
|
|
|
|
|
|
|
|
|
|
Р |
|||
p2 += 2; |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
printf(“a = %d , p = %d , p = %p , p1 = %p , p2 = %p .\n”, a, *p, p, p1, p2); |
|||||||||||||||||
Результат может быть следующим: |
|
|
|
Г |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Б |
|
|
||
|
|
a = 5 , *p = 5 , p = FFF4 , p1 = FFF6, p2 = FFF8У. |
|||||||||||||||
Графически это выглядит следующим образом (в 16-разрядном |
|||||||||||||||||
процессоре на тип int отводится 2 байта): |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
FFF5 |
|
|
FFF7 |
|
|
|
FFF9 |
|
|
|
|
|
|
|
FFF4 |
|
FFF6 |
к |
|
|
FFF10 |
|
|
||||||
|
|
|
|
|
|
FFF8 |
|
|
|||||||||
|
|
|
|
|
|
|
е |
аp2 |
|
|
|||||||
|
|
|
р |
|
|
|
p1 |
|
|
|
|||||||
p = FFF4, |
|
|
т |
|
|
|
|
|
|
|
|
|
|||||
p1 = FFF6 = ( FFF4 + 1*sizeof(*p)) → FFF4 + 2 (int) |
|
|
|||||||||||||||
р2 = FFF8 = ( FFF4 + 2*sizeof(*p)) → FFF4 + 2*2 |
|
|
|||||||||||||||
|
|
|
|
ко |
|
|
|
|
|
|
|
|
|
|
|
||
На одну и ту же |
блас ь памяти (как видно из приведенного примера), |
||||||||||||||||
|
|
|
и |
|
указателей различного типа. Но примененная к |
||||||||||||
может ссылаться неск ль |
|||||||||||||||||
ним операция разадресации даст разные результаты. |
|
|
|||||||||||||||
|
|
л |
|
|
в |
выражении |
|
указателей разных типов явное |
|||||||||
При смеш ван |
|
||||||||||||||||
|
б |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
преобразование т пов требуется для всех указателей, кроме void*. |
|||||||||||||||||
Явное приведение типов указателей позволяет получить адрес объекта |
|||||||||||||||||
любого т па: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Б |
type *p; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
p = (type*) &object; |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
Значениеуказателя p позволяет работать с переменной object как объектом типа type.
70