1.3. Управление связанным списком записей (на примере)

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

type

TCheck = record

Amount: Real;

Month: 1..12;

Day: 1..31;

Year: 1990..2000;

Payee: string[39];

end.

Но при написании программы трудно предположить, с каким количеством счетов придется иметь дело. Одно из решений состоит в создании большого массива записей счетов, но это приведет к лишним затратам памяти. Более гибкое решение состоит в расширении определения записи и включении в нее указателя на следующую запись списка, что приведет к образованию связанного списка из элементов типа TCheck

type

PCheck = ^TCheck;

TCheck = record

Amount: Real;

Month: 1..12;

Day: 1..31;

Year: 1990..2000;

Payee: string[39];

Next: PCheck; {указывает на следующую запись}

end.

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

1.3.1. Построение списка

Ниже приведена процедура, которая строит связанный список записей, считывая их из файла. Здесь подразумевается, что открыт файл записей TCheck и именем CheckFile, который содержит, по крайней мере одну запись.

Var ListOfChecks, CurrentCheck: pCheck;

procedure ReadChecks;

begin

New(ListOfChecks); {выделить память для первой записи}

Read(CheckFile, ListOfChecks^); {считать первую запись}

CurrentCheck := ListOfChecks; {сделать первую запись текущей}

while not Eof(CheckFile) do

begin

New(CurrentCheck^.Next); {выделить память для следующей записи}

Read(CheckFile, CurrentCheck^.Next^); {считать следующую запись}

CurrentCheck := CurrentCheck^.Next; {сделать следующую запись текущей}

end;

CurrentCheck^.Next = nil; {после последней считанной записи следующей нет}

end.

1.3.2. Перемещение по списку

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

function FindCheckByAmount(AnAmount: Real): PCheck;

var Check: PCheck;

begin

Check := ListOfChecks; {указывает на первую запись}

while (Check^.Amount <> AnAmount) and (Check^.Next <> nil) do

Check := Check^.Next;

if Check^.Amount = AnAmount then

FindCheckByAmount := Check {возвращает указатель на найденную запись}

else FindCheckByAmount:= nil; {или nil, если таких записей нет}

end;

1.3.3. Освобождение выделенной для списка памяти

В процедуре DisposeChecks показано, как можно перебрать список, дойдя до каждого элемента и освободив его.

procedure DisposeChecks;

var Temp: PCheck;

begin

CurrentCheck := ListOfChecks; {указывает на первую запись}

while CurrentCheck <> nil do

begin

Temp := CurrentCheck^.Next {сохранить указатель Next}

Dispose(CurrentCheck); {освобождение текущей записи}

CurrentCheck:= Temp; {сделать сохраненную запись текущей}

end;

end;

1.4. Процедуры и функции для работы

с динамической памятью

Функции:

Addr(X) –возвращает результат типа Pointer, в котором содержится адрес аргумента.

Здесь Х – любой объект программы (имя любой переменной, процедуры, функции). Возвращаемый адрес совместим с указателем любого типа. Отметим, что аналогичный результат возвращает операция @.

CSeg – возвращает значение, хранящееся в регистре CS микропроцессора (в начале работы программы в регистре CS содержится сегмент начала кода программы). Результат возвращается в слове типе Word.

Dseg - возвращает значение, хранящееся в регистре DS микропроцессора (в начале работы программы в регистре DS содержится сегмент начала данных программы). Результат возвращается в слове типе Word.

MaxAvail – возвращает размер в байтах наибольшего непрерывного участка кучи. Результат имеет типа LongInt. За один вызов процедуры New или GetMem нельзя зарезервировать память больше, чем значение, возвращаемое этой функцией.

MemAvail – возвращает размер в байтах общего свободного пространства кучи. Результат имеет типа LongInt.

Ofs(x) – возвращает значение типа Word, содержащее смещение адреса указанного объекта. Х – выражение любого типа или имя процедуры.

Ptr(Seg , Ofs) –возвращает значение типа Pointer по заданному сегменту Seg и смещению Ofs. Здесь Seg – выражение типа Word содержащее сегмент, Ofs.- выражение типа Word, содержащее смещение. Значение, возвращаемое функцией, совместимо с указателем любого типа.

Seg(X) - возвращает значение типа Word, содержащее сегмент адреса указанного объекта. Здесь Х – выражение любого типа или имя процедуры.

SizEof(X) – возвращает длину в байтах внутреннего представления указанного объекта. Здесь Х – имя переменной, функции или типа. Например: вместо константы везде SizeOfReal можно было бы использовать обращение SizEof(Real).

Процедуры:

DisPose(TP) – возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем.

Здесь TP – типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения. При освобождении динамических объектов можно указывать вторым параметром обращения к DisPose имя деструктора.

FreeMem(P,Size) - возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. Здесь Р – нетипизированный указатель. Size – длина в байтах освобождаемого фрагмента.

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

GetMem(P,Size) – резервирует за нетипизированным указателем фрагмент динамической памяти требуемого размера.

За одно обращение к процедуре можно зарезервировать не более 65521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.

Mark(Ptr) – запоминает текущее значение указателя кучи HeapPtr. Здесь Ptr – указатель любого типа, в котором будет возвращено текущее значение HeapPtr. Используется совместно с процедурой Release(Ptr) для освобождения части кучи.

New(TP) – резервирует фрагмент кучи для размещения переменной. Здесь ТР – типизированный указатель. За одно обращение к процедуре можно зарезервировать не более 655521 байта динамической памяти. Если нет свободно памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.

Процедура New может вызываться как функция. В этом случае параметром обращения к ней является тип переменной, размещаемой в куче, а функция New возвращает значение типа указатель. Например:

Type Pint = ^integer;