6 Представление динамических структур с помощью указателей

6.1 Указатели

Характерная особенность списковых структур данных (связных списков, стеков, очередей и т.д.) – это способность изменять число элементов. Это число заранее не определено и хранить в памяти пустые элементы списка накладно.

Лучше использовать так называемое динамическое распределение памяти, т.е. выделять память для эле­мента списковой структуры в тот момент, когда этот элемент появляется во время выполнения программы, а не во время её компиляции. В этом случае транслятор выделяет фиксированный объем памяти для хранения адре­сов динамически размещаемых элементов, а не самих элементов. Эти адреса называются указателями или ссылками.

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

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

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

TYPE TP = ^SP; SP = RECORD

INF : CHAR; { INF : T₀ }

LINK : TP END;

6.2 Представление стека

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

I TOP

L__T__

I I

TOP

[link i _r* ~L~_~_~_J

	LINK
	1

	LINK
	|

LINK

NEW(K)

Рис. 15 Представление стека в виде линейного списка

NIL

Для организации и ведения стека должны быть предусмотрены два указателя: ТОР и К: VAR ТОР, К : ТР;

СН : CHAR; Для добавления элемента в стек необходимо:

• образовать динамическую переменную по указателю К;

• занести в неё нужную информацию;

• в поле указателя нового элемента занести значение указателя ТОР;

• указателю ТОР присвоить значение указателя К. NEW(K);

KMNF := СН;

K^A.LINK := TOP;

TOP := К;

Для удаления элемента из стека достаточно:

• прочитать информацию СН := TOPMNF;

• в указатель ТОР занести указатель удаляемого элемента ТОР := TOP^A.LINK;

Но в этом случае удаленный из стека элемент образует "мусор". Лучше удалить из памяти этот элемент, предварительно сохранив значение указателя ТОР: К := ТОР; ТОР := K^A.LINK; СН := KMNF; DISPOSE(K);

Опять принцип обратности и зеркальности здесь выполняется. Формирование стека с самого начала. Стек из N элементов: ТОР := Nil; WHILE N > О DO BEGIN

NEW(K); READ(CH);

KMNF := CH;

K^A.LINK := TOP;

TOP := K; N := N -1

END;

Выбор всех элементов стека (самостоятельно): REPEAT

К := ТОР;

ТОР := K^A.LINK;

СН := KMNF; WRITE(CH);

DISPOSE(K); UNTIL TOP = NIL; или WHILE TOP <> NIL DO . . . ;

Сравнивая операции обработки элементов стека в последовательной памяти, обнаруживаем их идентич­ность (сравнение с массивами).

Однако в динамических структурах снимается проблема переполнения стека.