Нетипизированные указатели

Нетипизированным называется указатель, не связанный с каким-то конкретным типом данных. Для его описания используется стандартный тип Pointer. Например,

Var p: pointer;

Нетипизированные указатели используются для динамического размещения данных, структура и тип которых могут меняться в ходе выполнения программы.

Для выделения памяти используется стандартная процедура

GetMem (p, size);

где p – указатель, переменная типа Pointer; size – размер выделяемого участка памяти, выражение типа Word (целочисленный тип). За одно обращение к процедуре GetMem возможно выделение не более 65521 байта памяти (максимальное значение типа Word).

Для освобождения памяти и возвращения ее в кучу используется стандартная процедура

FreeMem (p, size);

где p – указатель, переменная типа Pointer; size – размер освобождаемого участка памяти, выражение типа Word.

Константу Nil можно использовать и при работе с нетипизированными указателями.

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

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

Стек

Стеком называется структура данных, организованная по правилу LIFO: last input – first output, т.е последним вошел – первым вышел.

Глубина стека – количество элементов в нем.

Вершина стека – «верхний», т.е. доступный элемент.

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