Указатели и динамические структуры данных: стеки, списки, очереди, деревья.

Указатель – тип данных, хранящих адрес в памяти других данных. В зависимости от типизации указатель может быть нетипизированным (содержать просто адрес в памяти) и типизированным (указывать только на элемент определенного типа).

Стек – хранилише данных однородного типа с дисциплиной “последним пришел-первым вышел” (LIFO).

		SP

Над стеком определены операции PUSH, POP (затолкнуть, извлечь).

При операции PUSH указатель стека SP увеличится на 1, при извлечении уменьшится на 1.

Природа стека делает необходимым соответствие операций PUSH и POP. Если его нет, то возможно 2 ситуации:

а) переполнение – SP вышел за пределы верхнего значения

б) антипереполнение –“- нижнего.

Очередь – структура данных с дисциплиной FIFO – “первым вошел, первым вышел”.

	tp
	hp

Здесь HP – указатель на последнее значение, tp – номер последнего выбранного элемента. Если HP=TP – очередь пуста.

ENQ x - добавляем в очередь

HP=HP+1

A[HP]=x

DEQ x - извлекаем из очереди

TP=TP+1

x = A[TP]

Особые ситуации - так же как и со стеком.

Для реализации динамических структур данных используют т.н. кучу (heap). Это объем памяти, в котором можно выделить участок для произвольного элемента данных. Для кучи есть 2 операции: выделения памяти ALLOCATE и освобождения FREE. Эти функции не делают никаких действий с собственно памятью. При выделении программист получает адрес, а при освобождении доступный объем кучи становится больше. Одного адреса для этих операций недостаточно, требуется еще и размер элемента данных.

Списки – сложные динамические структуры данных, представляющие собой структуры, содержащие указатели на другие подобные структуры. Если такой указатель в структуре 1 – односвязный список, если 2 – двусвязный, если много – многосвязный. Стек и очередь можно легко представить в виде одно- и двусвязного списка. Списки характеризуются тем, что для них легко реализуется любая дисциплина ввода-вывода за счет простого добавления и удаления элемента.

Для добавления элемента достаточно выделить под него память и присвоить адрес памяти нового элемента соответствующему предыдущему элементу. Для удаления элемента память из-под него освобождается, а указателям на него присваивается некоторое зарезервированное значение NULL – “указатель на ничто”.

data; struct s *next;

data; struct s *next;

data; struct s *next;

NULL

Односвязный список

data; struct s *prev; struct s *next;

data; struct s *prev; struct s *next;

data; struct s *prev; struct s *next;

NULL

Двусвязный список

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

NULL NULL

NULL NULL NULL NULL

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