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

Нетипизированным называется указатель, не связанный с каким-то конкретным типом данных. Для его описания используется стандартный тип 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:

Примеры решаемых задач

Пример 1. Составить программу, которая формирует стек из 10 элементов, а затем удаляет его из памяти.

Программа:

Program stack10;

Uses Crt;

Const n=10;

Type stack = ^elem;

elem = Record

num : Integer;

p : stack

End;

Var st,beg_st : stack;

i : Integer;

Begin

Clrscr;

beg_st := nil;

For i := 1 To n Do

Begin

New (st);

st^.p := beg_st;

beg_st := st;

Write ('введите ', i ,' элемент стека ');

Readln (st^.num)

End;

Writeln ('в динамической памяти создан стек:');

st := beg_st;

While st <> nil Do

Begin

Writeln (st^.num);

st:=st^.p

End;

Readln;

Writeln ('Освобождаем память - удаляем элементы стека из кучи ');

i := n;

st := beg_st;

While beg_st<>nil do

Begin

st := beg_st;

Writeln ('Удалили ', i ,' элемент ');

beg_st := st^.p;

i := i - 1;

Dispose (st);

End;

Readln

End.