Процедуры и функции работы с динамической памятью

1. Процедура New{var p: Pointer).

Выделяет место в динамической области памяти для размещения динамической переменной p', и ее адрес присваивает указателю p.

2. Процедура Dispose(var p: Pointer).

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

3. Процедура GetMem(var p: Pointer; size: Word).

Выделяет участок памяти в heap-области, присваивает адрес его начала указателю p, размер участка в байтах задается параметром size.

4. Процедура FreeMem(varp: Pointer; size: Word).

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

5. Процедура Mark{var p: Pointer) записывает в указатель p адрес начала участка свободной динамической памяти на момент ее вызова.

6. Процедура Release(var p: Pointer) освобождает участок динамической памяти, начиная с адреса, записанного в указатель p процедурой Mark, т. е. очищает ту динамическую память, которая была занята после вызова процедуры Mark.

7. Функция MaxAvail: Longint возвращает длину в байтах самого длинного свободного участка динамической памяти.

8. Функция MemAvail: Longint возвращает полный объем свободной динамической памяти в байтах.

9. Вспомогательная функция SizeOf(X):Word возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа.

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

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими. К ним относятся стеки, очереди, списки, деревья и др.

Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

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

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

1) добавление элемента к списку;

2) удаление элемента из списка с заданным ключом;

3) поиск элемента с заданным значением ключевого поля;

4) сортировка элементов списка;

5) деление списка на два и более списков;

6) объединение двух и более списков в один;

7) другие операции.

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

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO(Last-In, First-Out) – «Поступивший последним, обслуживается первым».

Обычно над стеками выполняется три операции:

1) начальное формирование стека (запись первой компоненты);

2) добавление компоненты в стек;

3) выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа «указатель», первая из которых определяет вершину стека, а вторая – вспомогательная.

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

Program STACK;

uses Crt;

type

Alfa = String[10];

PComp = ^Comp;

Comp = Record

sD: Alfa;

pNext: PComp

end;

var

pTop: PComp;

sC: Alfa;

Procedure CreateStack(var pTop: PComp; var sC: Alfa);

begin

New(pTop);

pTop^.pNext:= NIL;

pTop^.sD:= sC;

end;

Procedure AddComp(var pTop: PComp; var sC: Alfa);

var pAux: PComp;

begin

NEW(pAux);

pAux^.pNext:= pTop;

pTop:= pAux;

pTop^.sD:= sC;

end;

Procedure DelComp(var pTop: PComp; var sC: ALFA);

begin

sC:= pTop^.sD;

pTop:= pTop^.pNext;

end;

begin

Clrscr;

writeln( ВВЕДИ СТРОКУ );

readln(sC);

CreateStack(pTop, sC);

repeat

writeln( ВВЕДИ СТРОКУ );

readln(sC);

AddComp(pTop, sC);