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

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

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

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

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

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

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

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

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

Указатели - динамические типы данных

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

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

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

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

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

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

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

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

Динамическая переменная

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

type 
	point = ^ct;

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

Ссылочную переменную R можно описать двумя способами:

a)

type 
	point = ^ct;
var
	R: point;

б)

var 
	R: ^ct;

Переменная R указывает на компоненту типа ct.

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

Например, компоненты, содержащие числа 5, 10, 15, 8, должны иметь еще информацию о том, где находится предыдущий элемент, т.к. это не массив и компоненты размещаются необязательно подряд.

Опишем тип таких данных, обозначив его ct. Очевидно, этот тип есть «запись» с двумя полями: полем целого значения (I) и полем ссылки (P):

type
	ct = record
		I: integer;
		P: point
	end;

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

type 
	point = ^ct;

Как мы видим, возник порочный круг: для описания типа point привлекается понятие ct, а при описании типа ct необходимо использовать point.

Условились в этом случае сначала описывать тип ссылочной переменной, а затем уже тип компоненты:

type 
	point = ^ct;
	ct = record
		I: integer;
		P: point
	end;

Правила языка Паскаль только при описании ссылок допускают использование идентификатора (ct) до его описания; во всех остальных случаях, прежде чем упомянуть идентификатор, необходимо описать его тип. Рассмотрим схему образования цепочки динамических данных, содержащих числа 5, 10.

Машине необходимо произвести следующие действия:

  1. Найти и зарезервировать место в памяти для компоненты.
  2. Заслать ссылку на эту компоненту (адрес) в ссылочную переменную R.
  3. Присвоить полю I значение 5.
  4. Присвоить некоторой ссылочной переменной Q значение R (скопировать).
  5. Найти и зарезервировать место в памяти для новой компоненты.
  6. Заслать в переменную R адрес этой компоненты.
  7. Заслать в поле I значение 10.
  8. Заслать в поле P значение Q.

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

Последовательность подобных действий создает цепочку динамических переменных.

Взято из: Г.Л. Семашко, А.И. Салтыков «Программирование на языке Паскаль».
Схема переработана.

Процедура New

Резервирование места в памяти под динамическую переменную и засылка ее адреса в ссылочную переменную R выполняется при обращении new(R). При этом выделяется столько ячеек памяти, сколько требует динамическая переменная, с которой связана R. Эти все данные система получает из раздела описания типов в программе.

Динамические переменные, созданные посредством процедуры new(R), называют также указанными переменными (указатель R).

Пример. Пусть переменная R имеет тип point. Тогда при обращении к процедуре new(R) будет создана указанная переменная, в которой предусмотрено поле под значение типа integer и поле ссылки. При этом ссылочная переменная R содержит адрес указанной переменной. Через R^ обозначается сама указанная переменная; R^.I – поле целого значения I; R^. P – поле ссылки P.

Указанная и ссылочная переменные в языке Паскаль

Операции над указателями

Значение ссылочной переменной R можно присваивать другой ссылочной переменной того же типа.

Пример 1. Пусть Q, R: ^point; тогда оператор Q := R; зашлет в Q тот же адрес, что хранится в R.

Рассмотрим действия со ссылочными переменными на следующей схеме. Пусть Q и R указывают на различные компоненты динамических переменных типа C:

C = record
	I: integer;
	P: point
end;

Пусть в памяти машины размещены две цепочки динамических переменных. Выполним четыре различных операций: Q := R; Q^ := R^; Q^.I := R^.I; Q^.P := R^.P;

a) После выполнения оператора Q := R; переменная Q указывает на ту же динамическую переменную, что и R.

б) После выполнения оператора Q^ := R^; (из исходного состояния) получим, что на место указанной переменной “20”, указывающей на “30”, заслана переменная “15”, указывающая на “25”.

в) После выполнения оператора Q^.I := R^.I; из исходного состояния получим, что на место целого значения 20 заслано значение 15; поле указателя не изменилось.

г) После выполнения оператора Q^.P := R^.P; из исходного состояния получим, что на место ссылки на компоненту “30” заслана ссылка на компоненту “25”, поле целого значения не изменилось.

Операции над указателями (ссылочными переменными

Ссылочные переменные могут указывать на одну и ту же переменную, т.е. быть равными, как R и Q в случае а).

Ссылочные переменные можно сравнивать посредством операций = и <>. Логическое выражение Q = R имеет значение True для случая a) и значение False для случаев б) и в), т.к. для б) ссылочные переменные Q и R указывают на разные динамические переменные, имеющие, правда, равные значения.

В качестве аналога нуля для ссылочных переменных принято специальное значение Nil: если переменная имеет значение Nil, то это означает, что она не указывает ни на какую переменную. Значение Nil в поле указателя имеет всегда первая компонента цепочки динамических переменных.

Значение Nil в поле указателя первого компонента

Значение Nil можно заслать оператором присваивания: L := nil; если L = nil, то цепочки пуста.

Чтобы определить, что данный элемент является первым в цепочке переменных, достаточно проверить на Nil значение поля указателя этой переменной.

Пример. if L^.P = nil then

Замечание. Попытка обратиться к указанной переменной с указателем, имеющим значение Nil, приводит к ошибке. Диагностика в этом случае не всегда выдается.

Процедура Dispose

Динамическая переменная, созданная процедурой New, может быть «стерта» только процедурой Dispose.

Общий вид:

dispose(R);

Здесь R – ссылочная переменная, указывающая на ту динамическую переменную, которую следует стереть. После стирания динамической переменной R^ нельзя использовать значение R, такая ошибка может привести к порче памяти и другим серьезным последствиям.

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

Алгоритмы работы с динамическими структурами

Добавление элемента в стек

Пусть указатель a содержит адрес вершины стека, b - другой объявленный указатель.

  1. Выделяем память под данные, на которые указывает b.
  2. Записываем в эту память смысловые данные и ссылку на вершину стека, которая хранится в a.
  3. a присваиваем значение b, т.е. a начинает указывать на новую вершину стека.

Извлечение элемента из стека

a - указатель на вершину, b - другой указатель

  1. Извлекаем смысловые данные по указателю a.
  2. В b сохраняем значение a.
  3. a присваиваем значение поля-указателя элемента, на который она указывала.
  4. Очищаем память, на которую указывает b.

Стек ("магазин")

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

Пример стека

Подобным образом можно организовать и данные. Стек – такая структура динамических данных, которая состоит из переменного числа компонент одинакового типа. Компоненты извлекаются из стека таким образом, что первой выбирается та компонента, которая была помещена последней. Извлеченная компонента в стеке не сохраняется.

Пример. Рассмотрим последовательные этапы засылки с стек чисел 1, 2, 3.

Заполнение стека

На этапе б) обращение к процедуре извлечения из стека дает число 2, на этапе в) – число 3.

Опишем стек, в который можно помещать цепочку динамических переменных:

type
	stackp = ^stackcomp;
	stackcomp = record
		I: integer;
		P: stackp
	end;
var
	S: stackp;

Если помещать в этот стек последовательность 1, 2, 3, то получится следующий вид:

Стек, состоящий из трех компонентов

Поместить в такой стек компоненту можно, например, процедурой SN:

S := nil;
…
procedure SN(k: integer);
	var 
		inew: stackp;
	begin
		{резервируется память под новую компоненту, 
		в inew засылается адрес этой компоненты}
		new(inew);
		with inew do begin
			I := k;
			P := S
		end;
		S := inew;
	end;

Если со стеком вида как на рисунке выше обратиться к процедуре SN для засылки числа 4, то получим стек вида:

Стек, состоящий из четырех компонентов

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

procedure OUT(var k: integer);
	var
		iold: stackp;
	begin
		iold := S;
		{значение последней компоненты}
		k := iold^.I;
		{извлекается и засылается в S значение
		соответствующего указателя на 3}
		S := iold^.P;
		dispose(iold);
	end;

После обращения к процедуре OUT стек вернется к первоначальному виду (1, 2, 3).

Пустым стеком называется стек, не содержащий компонент. Такой стек можно получить, присвоив значение Nil соответствующей ссылочной переменной (в нашем случае S := nil;).

Если к пустому стеку применить несколько раз процедуру SN, а затем столько же раз процедуру OUT, то получим снова пустой стек.

Замечание. Нельзя применять процедуру OUT к пустому стеку.

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

Очередь

Очередь – такая структура данных, при которой изъятие компонент происходит из начала цепочки, а запись – в конец цепочки.

В этом случае вводят два указателя: один на начало очереди, другой – на ее конец.

Запись новых компонент

Пример. Пусть имеется цепочка динамических переменных:

Цепочка динамических переменных

Переменные имеют тип stackcomp:

type
	…
	stackcomp = record
		I: integer;
		P: stackp
	end;

Требуется вставить в цепочку новую компоненту “3” перед компонентой “4”, если известен указатель newp -> “3”.

Для записи этой новой компоненты достаточно выполнить операторы:

newp^.P := L^.P;
L^.P := newp;

Первый оператор засылает в поле указателя новой компоненты

Динамическая переменная

ссылку на компоненту “2”. Эта ссылка находится в поле указателя последней компоненты

Динамическая переменная

т.е. получается следующий вид:

Засылка ссылки на компоненту

Второй оператор помещает в поле указателя компоненты “4” ссылку на компоненту “3”. Получается следующая картина:

Вставка элемента

Нелинейные структуры

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

Примеры нелинейных структур:

a) Текст

Пример нелинейной динамической структуры - текст

б) Двоичное дерево

Двоичное дерево

можно представить так:

Динамическая структура - двоичное дерево

в) Направленный граф

Направленны граф

можно представить так:

Динамическая структура - направленный граф

a) Текст – это связанная структура. Ее элементы представляют собой записи с тремя полями: первое поле содержит текстовую информацию (например, слово), второе поле либо указывает на первый элемент следующей строки, либо имеет значение Nil, третье – на следующий элемент данной строки.

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

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

Узлом называют переменную, содержащую два различных, отличных от Nil, значения указателя. Так, узловые элементы текста содержат ссылки на очередной элемент данной строки и на первый элемент следующей строки.

Нелинейные структуры удобны для задач поиска. Список упорядоченных элементов в виде двоичного дерева:

Упорядоченность элементов двоичного дерева

Узел 4 называется корнем дерева. Вход в дерево происходит только через корень. Для каждого узла различаются левое и правое поддеревья. Упорядоченность элементов следующая: элементы левого поддерева меньше узла и меньше элементов правого поддерева.

Время поиска в двоичном дереве сокращается по сравнению с линейной структурой с ~N до log2N, где N – число узлов в дереве. Компоненту двоичного дерева можно представить переменной типа

birec = record
	I: integer;
	pred, succ: intp
end;

Каждая такая переменная содержит три поля: поле целого значения – поле I, поле указателя на предыдущий (в смысле упорядоченности) элемент – поле pred и поле указателя на последующий элемент – поле succ.