Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
for Inx := FCapacity to pred(aCapacity) do
begin
PLongint(FRecord)^ := FHeaderRec^.hr1stDelRec;
rsWriteStream(FRecord^, FRecordLen4);
FHeaderRec^.hr1stDelRec := Inx;
end;
{сохранить новую емкость}
FCapacity := aCapacity;
FHeaderRec^.hrCapacity := aCapacity;
{обновить служебный заголовок}
rsSeekStream(FZeroPosition);
rsWriteStream(FHeaderRec^, sizeof(TtdRSHeaderRec));
end;
end;
Как видно из приведенного кода, метод rsSetCapacity добавляет в конец потока пустые записи и вносит их в цепочку удаленных записей.
Последние методы, которые мы рассмотрим, будут очень простыми. Это низкоуровневые методы, предназначенные для считывания из потока, записи в поток и поиска в потоке. Кроме того, в каждом из них имеется блок проверки результата.
Листинг 2.27. Низкоуровневые методы доступа к потоку
procedure TtdRecordStream.rsReadStream(var aBuffer;
a,BufLen : integer);
var
BytesRead : longint;
begin
BytesRead := FStream.Read(aBuffer, aBufLen);
if (BytesRead <> aBufLen) then
rsError(tdeRSReadError, 'rsReadStream', aBufLen);
end;
procedure TtdRecordStream.rsSeekStream(aOff set : longint);
var
NewOffset : longint;
begin
NewOffset := FStream.Seek(aOffset, soFromBeginning);
if (NewOffset <> aOffset) then
rsError(tdeRSSeekError, 'rsSeekStream', aOffset);
end;
procedure TtdRecordStream.rsWriteStream(var aBuffer;
aBufLen : integer);
var
BytesWritten : longint;
begin
BytesWritten := FStream.Write(aBuffer, aBufLen);
if (BytesWritten <> aBufLen) then
rsError(tdeRSWriteError, 'rsWriteStream', aBufLen);
Flush;
end;
Как видите, если результат выполнения одного из методов не соответствует ожидаемому, методы вызывают исключения.
Существует еще один метод, о котором мы не говорили, - rsWriteStream. Фактически это метод Flush - виртуальный метод, предназначенный для сброса содержащихся в потоке данных на связанное с потоком устройство (например, диск). Его реализация для нашего класса представляет собой пустую подпрограмму, поскольку мы не знаем, как сбросить данные из стандартного потока TStream. Он существует только для того, чтобы быть перекрытым в дочерних классах, которые имеют дело с потоком, связанным с диском, например, файловым потоком.
Листинг 2.28. Реализация постоянных массивов с помощью файлового потока
constructor TtdRecordFile.Create(const aFileName : string;
aMode : word;
aRecordLength : integer);
begin
FStream := TFileStream.Create(aFileName, aMode);
inherited Create(FStream, aRecordLength);
FFileName := aFileName;
Mode := aMode;
end;
destructor TtdRecordFile.Destroy;
begin
inherited Destroy;
FStream.Free;
end;
procedure TtdRecordFile.Flush;
{$IFDEF Delphi1}
var
DosError : word;
Handle : THandle;
begin
Handle := FStream.Handle;
asm
mov ah, $68
mov bx, Handle
call D0S3Call
jc @@Error
xor ax, ax
@6Error:
mov DosError, ax
end;
if (DosError <> 0) then
rsError(tdeRSFlushError, 'Flush', DosError)
end;
{$ENDIF}
{$IFDEF Delphi2Plus}
begin
if not FlushFileBuffers (FStream.Handle) then
rsError(tdeRSFlushError, 'Flush', GetLastError)
end;
{$ENDIF}
В
Полный код класса TtdRecordStream можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRecFil.pas.
Резюме
Эта глава была посвящена массивам - одной из фундаментальных структур данных. Были описаны их достоинства (доступ к отдельным элементам составляет O(1), поддерживается локальность ссылок) и недостатки (вставка и удаление элементов относятся к операциям класса О(n)). Приведена реализация класса массива TtdRecordList. Затем был подробно рассмотрен стандартный класс TList и его простой дочерний класс TtdObjectList.
Кроме того, мы познакомились с реализацией постоянных массивов в форме потока записей. Был приведен пример реализации класса постоянных массивов, TtdRecordStream, который позволяет выполнять чтение, запись и удаление отдельных записей.
Глава 3. Связные списки, стеки и очереди
Как и массивы, связные списки представляют собой универсальную структуру данных, широко используемую многими программистами. Однако, в отличие от массивов, связные списки не входят в состав стандартного языка Object Pascal. Тем не менее, в Object Pascal создать связный список достаточно просто. Все что для этого нужно - наличие в составе языка указателя, хотя фактически могут использоваться и классы или объекты.
На основе связных списков можно легко организовать стеки и очереди - еще две простые, но эффективные структуры данных. Несмотря на то что они, на первый взгляд, не имеют ничего общего со связными списками, их можно написать на базе односвязных списков. И, как мы увидим чуть позже, иногда удобнее реализовать стеки и очереди на базе массивов, а не связных списков.
Начнем наше рассмотрение со связного списка и операций, которые такой список должен поддерживать.
Односвязные списки
По своей сути связный список (linked list) представляет собой цепочку элементов или объектов с некоторыми описаниями (обычно называемых узлами). При этом каждый элемент содержит указатель, указывающий на следующий элемент в списке. Такая структура данных называется односвязным списком (singly linked list) - каждый элемент имеет только одну ссылку или указатель на следующий элемент. Сам список начинается с первого узла, от которого путем последовательных переходов по ссылкам можно обойти все остальные узлы. Обратите внимание, что определение связного списка отличается от определения массива, для которого следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.