4. Динамические структуры данных
4.1. Метод вычисляемого и хранимого адреса.
Последовательная и связанная организация памяти
В соответствии с двумя методами идентификации объекта существует два метода доступа к объектам: метод вычисляемого адресаиметод хранимого адреса. Согласно методувычисляемого адреса,на этапе компиляции исходного текста программы создается элемент хранения объекта, причем однозначная взаимосвязь между именем объекта и адресом его элемента хранения фиксируется в специальной таблице, формируемой компилятором, на все время работы программы. Доступ через имя всегда открывает один и тот же объект. Методу вычисляемого адреса соответствуетпоследовательная организация памяти. При такой организации объекты размещаются в смежных последовательно расположенных ячейках памяти, что характерно, например, для статической памяти (см. 3.2.2). Адреса объектов вычисляются от начала сегмента данных с учетом размеров их элементов хранения. Более сложные методы последовательной организации связаны с индексацией и соответственно вычислением адресов объектов (и их атрибутов) через индексы (рис. 16).
Const
N = …;
Type Array_Type = array [1..N ] of Type1;
Var M: Array_Type;
АдресAi i– го элемента массива M[i]
компилятор вычисляет по формуле Ai = A1 + sizeof( Type1 ) * ( i – 1 ).
Рис. 16. Последовательная организация памяти: индексирование
Достоинством последовательной организации является простота доступа к объектам по имени, а недостатком - проблемы при модификации структур объектов. Например, нельзя изменить размер массива в процессе выполнения программы. Для того чтобы включить в массив какое-либо новое значение по заданному индексу элемента, требуется «раздвинуть» массив за счет копирования всех элементов в элементы с большими индексами, начиная от заданного. Аналогичная проблема возникает, если какое-либо значение требуется из массива исключить, т.е. “сжать” массив. Кроме того, необходимо заранее резервировать такое количество памяти, которое потребуется для работы со структурой, содержащей максимальное количество объектов.
Согласно методу хранимого адреса,адреса объектов не вычисляются, а хранятся в указателях на эти объекты. Для доступа к объекту сначала необходимо получить ссылку на него (т.е. значение указателя), а затем выполнить операцию раскрытия ссылки. Каждый объект имеет возможность хранить в виде ссылок связи с другими объектами, с которыми он взаимодействует в программе. Для реализации этой возможности необходимо ввести в структуру объекта специальные атрибуты, называемые полями связи или ссылочными полями для хранения связей со смежными объектами. Методу хранимого адреса соответствуетсвязанная организация памяти. Графическая иллюстрация структур связанной организации памяти использует фигуры прямоугольников для изображения элементов хранения объектов и стрелки для изображения связей (указателей) между объектами. Необходим специальный указатель, который бы определял местонахождение начального объекта связанной структуры. На рис. 17 приведен пример графической иллюстрации связанной организации структуры из трех объектов. В полях “информация объекта” находятся атрибуты данных объекта, а в полях “адрес объекта” – ссылочные поля для хранения связей. Доступ к объекту 1 открывает указатель p. Доступ к объекту 2 возможен только через объект 1, а к объекту 3 – через объект 2 с использованием соответствующих полей связи.
Рис. 17. Графическое представление связанной организации памяти
На рис. 18 приведено упрощенное графическое представление связанной организации памяти.
Рис. 18. Упрощенное графическое представление связанной организации памяти
Достоинством связанной организации памяти является удобство модификации структур, т.к. в них соседние объекты могут располагаться в физически несмежных областях памяти. Необязательно сразу создавать структуру максимального размера. Включение / исключение объектов можно выполнять в процессе работы программы, что не потребует “раздвигать” или “сжимать” структуру за счет копирования информации. Однако “платой” за использование гибкой и эффективной связанной организации памяти являются дополнительные затраты памяти для хранения адресов соседних объектов и более сложный доступ к атрибутам объектов.