динамичная структура данных

Говорят, что тип point указывает (ссылается) на компоненты типа ct, или тип point связан с типом ct.

Обозначим тип ссылочной переменной через point, а тип динамической переменной через ct. Тогда этот факт описывается следующим образом:

Пример. Пусть в памяти машины имеется динамическая переменная, содержащая поле целого значения 2 и поле ссылки (указатель) на другую компоненту связанной структуры (цепочки). Адрес данной переменной (ссылка) содержится в ссылочной переменной R.

Динамические переменные, как правило, имеют тип "запись" (record), т.к. должны содержать, помимо значения (целого, вещественного и т.п.), ссылку на другую динамическую переменную связанной структуры.

Под ссылочную переменную транслятор отводит место в памяти машины; эта переменная имеет имя и явно упоминается в программе. Ссылочные переменные образуют новый тип данных "ссылки" (указатели).

Обращение к динамической переменной происходит посредством ссылочной переменной, которая содержит адрес соответствующей динамической переменной.

Ссылочные и динамические переменные

Новая динамическая компонента может быть размещена в любом свободном месте памяти, отведенном под такие переменные. Сама динамическая переменная не обозначается идентификатором. Динамическая переменная это «невидимка» в программе: идентификатором она не обозначается, транслятор ей места в памяти не отводит. Память под такую переменную резервируется и освобождается динамически в процессе счета (с помощью специальных процедур).

С помощью ссылок легко вставить новую компоненту в цепочку данных. Для этого достаточно изменить две ссылки.

Исключенный элемент теперь можно освободить от участия в работе блока и использовать занимаемый им участок памяти для других целей.

Пусть один из пациентов покидает очередь. Этот процесс не требует перемещения в пространстве остальных пациентов: просто стоящий за ушедшим теперь запоминает другого человека. То есть исключение элемента из цепочки данных сводится к изменению одной единственной ссылки и не требует перемещения остальных элементов, как это имело бы место для массива.

Чтобы проиллюстрировать преимущества динамических переменных, продолжим аналогию с очередью пациентов.

Подобным образом строится структура связанных данных, которые могут занимать память не подряд, а размещаться там, где есть свободное место. Каждый элемент такой структуры должен «знать», за кем он «стоит», т.е. содержать ссылку на предыдущий элемент цепочки.

Пример связанной структуры. В очереди на приеме к врачу каждый пациент запоминает человека, за которым занял очередь. Все пациенты связаны в цепочку согласно очереди, но в пространстве они размещены произвольным образом: вновь подошедший садится на любое свободное место, т.е. соседние элементы очереди могут находиться на произвольном расстоянии в пространстве.

Динамические переменные чаще реализуются как связанные структуры.

Данные можно представить в памяти компьютера по-другому. Данные можно хранить в некоторой области памяти, не обозначая именем переменной, а используя ссылку на эту область. Такой вид организации данных позволяет динамически захватывать и освобождать память в процессе работы блока программы. Поэтому и сами переменные, которые могут создаваться и ликвидироваться по мере надобности, называют динамическими.

Когда транслятор анализирует разделы var в программе (основная ветка, функции, процедуры), он отводит для каждой переменной соответствующее число ячеек памяти и закрепляет их за данной переменной на все время работы блока. Такие переменные называют статическими. Они не могут быть использованы системой под другие нужды, даже если в процессе дальнейшей работы программы эти переменные больше не понадобятся.

Указатели, или ссылки (Pointer)

Динамические структуры данных

Динамические структуры данных