- •1. Абстрагирование типов
- •1.1. Понятие типа данных
- •1.1.1. Простые типы
- •1.1.2. Абстрактные типы
- •2. Идентификация объектов
- •2.1. Именование
- •2.2. Указание
- •2.2.1. Организация адресного пространства оперативной
- •2.2.2. Понятие указателя
- •2.2.3. Действия над указателями
- •2.2.4. Связывание идентификатора объекта с его
- •3. Время жизни объекта. Классы памяти
- •3.1. Понятие “времени жизни” объекта
- •3.2. Классы памяти
- •3.2.1. Статическая память
- •3.2.2. Автоматическая память
- •3.2.3. Динамическая память
- •4. Динамические структуры данных
- •4.1. Метод вычисляемого и хранимого адреса.
- •4.2. Понятие динамической структуры данных
- •4.3. Линейные динамические структуры данных (списки)
- •4.3.1. Основные виды списков
- •4.4. Односвязные списки
- •4.4.1. Включение узла в начало списка
- •4.4.2. Создание списка из n узлов за счет добавления
- •4.4.3. Создание списка из n узлов за счет добавления
- •4.4.4. Исключение узла из начала списка
- •4.4.5. Перестановка указателя
- •4.4.6. Поиск в списке узла по заданному условию
- •4.4.7. Включение нового узла в список за тем узлом, на
- •4.4.8. Исключение из списка узла за тем узлом, на
- •4.4.9. Исключение из списка узла, на который предварительно
- •4.4.10. Разрушение списка
- •4.4.11. Программный модуль, реализующий операции
- •4.5. Односвязные циклические списки
- •4.6. Двусвязные списки
- •4.6.1. Включение нового узла в список за тем узлом, на
- •4.6.2. Исключение из списка узла, на который
- •4.7. Ортогональные списки (мультисписки)
- •4.8. Разнородные списки
- •4.9. Управление динамической памятью
- •4.9.1. Администратор кучи
- •4.9.2. Алгоритмы выделения участков памяти по запросу
- •4.9.3. Фрагментация
- •4.9.4. Накопление мусора
- •4.9.5. Висящие ссылки
- •5. Множественная интерпретация объектов
- •5.1. Совместимость типов. Приведение и преобразование типов
- •5.2. Методы совмещения типов
- •5.2.1. Запись с вариантной частью
- •5.2.2. Использование директивы absolute
- •5.2.3. Параметры без типа
- •5.2.4. Открытые массивы
- •5.2.5. Наложение масок с помощью указателей
- •6. Рекурсивные структуры данных
- •6.1. Итерация и рекурсия в программировании
- •6.1.1. Понятие рекурсии
- •6.1.2. Итеративная и рекурсивная схема организации
- •6.2. Задача о “ханойских башнях”
- •6.3. Виды рекурсивных структур данных
- •6.3.1. Арифметические выражения
- •6.3.2. Динамические линейные структуры данных: списки
- •6.3.3. Иерархические линейные структуры данных: наборы
- •6.4. Эффективность рекурсивных вычислений
- •7. ИерархическиеНелинейные структуры данных.Деревья
- •7.1. Деревья общего вида
- •7.2. Бинарные деревья
- •7.3. Представление бинарных деревьев
- •7.3.1. Представление бинарных деревьев на статической
- •7.3.2. Представление бинарных деревьев на
- •7.4. Алгоритмы обхода бинарных деревьев
- •7.5. Виды бинарных деревьев
- •7.5.1. Сбалансированные деревья
- •7.5.2. Дихотомические деревья (деревья поиска)
- •7.5.3. Деревья выражений
- •7.6. Программный модуль, реализующий операции
- •Список рекомендуемой литературы
2.2.4. Связывание идентификатора объекта с его
элементом хранения
Связывание– это определение взаимосвязи между идентификатором объекта (именем или указателем на объект) и элементом хранения объекта.
При идентификации именованием существует статическая связь между именем объекта и его элементом хранения (рис. 12).
Рис. 12. Связывание при идентификации именованием
При идентификации указанием существует статическая связь между именем указателя и элементом хранения указателя. Между элементом хранения указателя и тем объектом, на который он указывает, устанавливается динамическая связь (рис.13).
Рис. 13. Связывание при идентификации указанием
Т.к. элемент хранения указателя содержит адрес объекта, в процессе выполнения программы один и тот же указатель может открывать доступ к различным объектам одного и того же типа(и атрибутам этих объектов).
Var op1, op2: Point; p: PPoint; Begin |
|
Op1.X:=10; op1.Y:=20; |
{ заполнение атрибутов объекта op1 } |
Op2.X:=100; op2.Y:=200; |
{ заполнение атрибутов объекта op2 } |
P:=@op1; |
{ установка указателя p на объект op1}
|
Writeln( p^.X, p^.Y ); |
{ p^ .X =10, p^.Y =20 } |
P:=@op2; |
{ установка указателя p на объект op2 }
|
Writeln( p^.X, p^.Y ); |
{ p^ .X =100, p^.Y =200 } |
3. Время жизни объекта. Классы памяти
3.1. Понятие “времени жизни” объекта
Все объекты программы подразделяются настатическиеидинамические. Эти категории определяются через понятие “ времени жизни” объекта. Объекты, продолжительность существования которых равна времени выполнения программы, называют статическими, а объекты, время жизни которых меньше времени выполнения программы, - динамическими. С понятием времени жизниобъекта связаны его создание и уничтожение. Объекты, идентифицируемые именем, всегда являются статическими. Статические объекты создаются на этапе компиляции программы, до окончания работы программы для них сохраняется однозначное соответствие между элементом хранения объекта и именем объекта, по окончании работы программы они прекращают свое существование. Динамические объекты идентифицируются только через указатели, создаются и уничтожаются они в процессе выполнения программы.
3.2. Классы памяти
Распределение рабочего пространства оперативной памяти не является жестким, а происходит во время выполнения программы (см. рис. 14).
Рис. 14. Распределение рабочего пространства оперативной памяти
В нижних адресах располагаются системные программы. Выше располагается код исполняемого файла (файла с расширением .EXE), размер которого может превышать 64 К. Выполняемому файлу придается сегмент данных, размер которого не превышает 64 К. Далее располагается область системного стека, которая необходима для работы процедур и функций. Размер стека составляет не более 64 К. Стек заполняется от своей верхней границы по направлению к началу. Размер стека может быть назначен директивой $M. Выше стека располагается буфер для работы оверлеев – перекрывающихся частей программы. В верхних адресах оперативной памяти размещается куча (heap), необходимая для работы с динамическими объектами программы. Размером кучи пользователь может управлять при помощи директивы$M, которая имеет следующий формат:
{$M<stacksize>,<heapmin>,<heapmax>}– установить размеры памяти.
<stacksize> - размер стека, изменяется от 1024 до 65520 байт;
<heapmin> - минимальный размер динамической памяти, изменяется от 0
до 655360 байт;
<heapmax> - максимальный размер динамической памяти, изменяется от
<heapmin> до 655360 байт.
Размеры памяти по умолчанию - {$M 16384,0,655360}.
Создание объекта следует рассматривать как выделение памяти под его элемент хранения. Согласно такому подходу рабочее пространство оперативной памяти подразделяется на три класса: статическая память, автоматическая память, динамическая память.