Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

количество активных записей;

и, наконец, порядковый номер первой удаленной записи (здесь значение этого поля устанавливается равным cEndOfDetectedChain или -2).

Метод считывания служебного заголовка должен содержать определенную проверку, которая будет гарантировать, что данный заголовок является действительным. Для этого сначала выполняется проверка сигнатуры, затем проверка того, что количество активных записей меньше или равно емкости потока и имеет ли поток достаточный объем для объявленной емкости. Если все проверки проходят успешно, считается, что служебный блок содержит корректные данные, и поля класса обновляются значениями, считанными из потока.

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

Листинг 2.22. Добавление новой записи в постоянный массив

function TtdRecordStream.Add(var aRecord): longint;

begin

{если цепочка удаленных записей пуста, в поток добавляется новая запись}

if (FHeaderRec^.hr1stDelRec = cEndOfDeletedChain) then begin

Result :=FCapacity;

inc(FCapacity);

inc(FHeaderRec^.hrCapacity);

end

{в противном случае используется первая удаленная запись, обновляется значение поля удаленной записи в служебном заголовке для указания на следующую удаленную запись}

else begin

Result := FHeaderRec^.hr1stDelRec;

rsSeekStream(rsCalcRecordOffset(FHeaderRec^.hr1stDelRec))/ rsReadStream(FHeaderRec^.hr1stDelRec, sizeof(longint));

end;

{определить смещение записи и сохранить новую запись}

rsSeekStream(rsCalcRecordOffset(Result));

PLongint(FRecord)^ := cActiveRecord;

Move(aRecord, FRecord^[sizeof(longint)], FRecordLen);

rsWritestream(FRecord^, FRecordLen4);

{количество записей увеличилось на единицу}

inc(FCount);

inc(FHeaderRec^.hrCount);

{обновить служебный заголовок}

rsSeekStream(FZeroPosition);

rsWriteStream(FHeaderRec^, sizeof(TtdRSHeaderRec));

end;

Если цепочка удаленных записей не пуста, определить первую удаленную запись (именно поверх нее будет сохраняться новая запись). Мы считываем флаг удаления для этой записи и обновляем поле первой удаленной записи служебного заголовка. Затем мы определяем положение начала удаленной записи, устанавливаем значение флага удаления равным cActiveRecord (-1) и сохраняем запись, переданную методу во входном параметре.

При считывании и сохранении записей необходимо учитывать, удалена ли требуемая запись. Записи идентифицируются по их порядковым номерам.

Листинг 2.23. Чтение и обновление записи в постоянном массиве

procedure TtdRecordStream.Read(aIndex : longint; var aRecord; var alsDeleted : boolean);

begin

{проверить, действителен ли порядковый номер записи}

if (aIndex < 0) or (aIndex >= Capacity) then

rsError(tdeRSOutOfBounds, 'Read', aIndex);

{определить смещение записи и считать ее}

rsSeekStream(rsCalcRecordOffset(aIndex));

rsReadStream(FRecord^, FRecordLen4);

if (PLongint(FRecord)^ = cActiveRecord) then begin

alsDeleted := falser-Move (FRecord^[sizeof(longint)], aRecord, FRecordLen);

end

else begin

alsDeleted := true;

FillChar(aRecord, FRecordLen, 0);

end;

end;

procedure TtdRecordStream.Write(aIndex : longint; var aRecord);

var

DeletedFlag : longint;

begin

{проверить, действителен ли порядковый номер записи}

if (aIndex < 0) or (aIndex >= Capacity) then

rsError(tdeIndexOutOfBounds, 'Write', aIndex);

{проверить, что запись не была удалена}

rsSeekStream(rsCalcRecordOffset(aIndex));

rsReadStream(DeletedFlag, sizeof(longint));

if (DeletedFlag <> cActiveRecord) then

rsError(tdeRSRecIsDeleted, 'Write', aIndex);

{сохранить запись}

rsWriteStream(aRecord, FRecordLen);

end;

Метод Read возвращает флаг, который показывает, была ли удалена запись. Если запись не удалена, буфер записи, переданный во входном параметре, заполняется записью, считанной из потока. Код просто в один прием считывает всю запись и ее флаг удаления и действует в соответствии со значением флага.

Метод Write, прежде всего, проверяет, была ли удалена требуемая запись. Если запись удалена, она недоступна для изменения, вследствие чего возникает исключение. В противном случае в поток помещается новое значение записи.

И последний метод, связанный с обработкой записей, - это метод Delete.

Листинг 2.24. Чтение и обновление записи в постоянном массиве

procedure TtdRecordStream.Delete(aIndex : longint);

var

DeletedFlag : longint;

begin

{проверить, действителен ли порядковый номер записи}

if (aIndex < 0) or (aIndex >= Capacity) then

rsError(tdeRSOutOfBounds, 'Delete', aIndex);

{проверить, что запись не была удалена}

rsSeekStream(rsCalcRecordOffset(aIndex));

rsReadStream(DeletedFlag, sizeof(longint));

if (DeletedFlag <> cActiveRecord) then

rsError(tdeRSAlreadyDeleted, 'Delete', aIndex);

{записать порядковый номер первой удаленной записи в первые 4 байта удаляемой записи}

rsSeekStream(rsCalcRecordOffset(aIndex));

rsWriteStream(FHeaderRec^.hr1stDelRec, sizeof(longint));

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

FHeaderRec^.hr1stDelRec := aIndex;

{количество записей уменьшилось на единицу}

dec(FCount);

dec(FHeaderRec^.hrCount);

{обновить служебный заголовок}

rsSeekStream(FZeroPosition);

rsWriteStream(FHeaderRec^, sizeof(TtdRSHeaderRec));

end;

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

Метод Clear аналогичен Delete, но он предназначен для удаления всех активных записей постоянного массива.

Листинг 2.25. Очистка содержимого постоянного массива

procedure TtdRecordStream.Clear;

var

Inx : longint;

DeletedFlag : longint;

begin

{выполнить цикл по всем записям и объединить их в одну цепочку удаленных записей}

for Inx := 0 to pred(FCapacity) do

begin

rsSeekStream(rsCalcRecordOffset(Inx));

rsReadStream(DeletedFlag, sizeof(longint));

if (DeletedFlag = cActiveRecord) then begin

{записать порядковый номер первой удаленной записи в первые 4 байта удаляемой записи}

rsSeekStream(rsCalcRecordOffset(Inx));

rsWriteStream(FHeaderRec^.hr1stDelRec, sizeof(longint));

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

FHeaderRec^.hr1stDelRec := Inx;

end;

end;

{записей нет}

FCount := 0;

FHeaderRec^.hrCount := 0;

{обновить служебный заголовок}

rsSeekStream(FZeroPosition);

rsWriteStream(FHeaderRec^, sizeof(TtdRSHeaderRec));

end;

Этот метод выполняет цикл по всем записям массива и, если запись активна, удаляет ее в соответствии с алгоритмом, используемым в методе Delete.

Класс TtdRecordStream позволяет также в один прием увеличивать емкость потока на несколько записей, а не добавлять записи по одной с помощью метода Add. Такая возможность позволяет зарезервировать место под постоянный массив, если заранее известно количество записей, которое будет в нем храниться. Запись свойства Capacity осуществляется через метод rsSetCapacity.

Листинг 2.26. Задание емкости постоянного массива

procedure TtdRecordStream.rsSetCapacity(aCapacity : longint);

var

Inx : longint;

begin

{допускается только увеличение емкости}

if (aCapacity > FCapacity) then begin

{заполнить текущую запись нулями}

FillChar(FRecord^, FRecordLen4, 0);

{найти конец файла}

rsSeekStream(rsCalcRecordOffset(FCapacity));

{создать дополнительные записи и внести их в цепочку удаленных записей}

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 добавляет в конец потока пустые записи и вносит их в цепочку удаленных записей. После этого обновляются поля служебного заголовка, и в массиве появляется несколько удаленных записей, которые можно заполнить с помощью метода Add

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

Листинг 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. Он существует только для того, чтобы быть перекрытым в дочерних классах, которые имеют дело с потоком, связанным с диском, например, файловым потоком.