Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 6 (всего у книги 36 страниц)
Есть еще один вопрос, который проще рассмотреть на примере кода. Было бы довольно глупо ограничить концепцию постоянных (устойчивых) массивов только до файлов на диске. Несмотря на то что в подавляющем большинстве случаев будут использоваться файлы, ничто не мешает нам организовать постоянный массив в памяти или на любом другом устройстве хранения данных. Было бы удобно иметь класс постоянного массива, который пользуется потоками. В Delphi предусмотрен богатый набор классов потоков, включая файловый поток. Таким образом, если мы напишем код, использующий класс TStream, его можно будет применять со всеми другими классами, порожденными от TStream.
Ниже приведен код класса TtdRecordStream – класса, предназначенного для постоянного хранения в потоке массива записей.
Листинг 2.18. Класс TtdRecordStream для хранения постоянных массивов.
type
TtdRecordStream = class private
FStream : TStream;
FCount : longint;
FCapacity : longint;
FHeaderRec : PtdRSHeaderRec;
FName : TtdNameString;
FRecord : PByteArray;
FRecordLen : integer;
FRecordLen4 : integer;
FZeroPosition : longint;
protected
procedure rsSetCapacity(aCapacity : longint);
procedure rsError(aErrorCode : integer; const aMethodName : TtdNameString; aNumValue : longint);
function rsCalcRecordOffset(aIndex : longint): longint;
procedure rsCreateHeaderRec(aRecordLen : integer);
procedure rsReadHeaderRec;
procedure rsReadStream(var aBuffer; aBufLen : integer);
procedure rsWriteStream(var aBuffer; aBufLen : integer);
procedure rsSeekStream(aOffset : longint);
public
constructor Create(aStream : TStream; aRecordLength : integer);
destructor Destroy; override;
procedure Flush; virtual;
function Add(var aRecord): longint;
procedure Clear;
procedure Delete(aIndex : longint);
procedure Read(aIndex : longint; var aRecord; var alsDeleted : boolean);
procedure Write(aIndex : longint; var aRecord);
property Capacity : longint read FCapacity write rsSetCapacity;
property Count : longint read FCount;
property RecordLength : integer read FRecordLen;
property Name : TtdNameString read FName write FName;
end;
К сожалению, для такого типа постоянных массивов очень сложно перегрузить операцию [], поэтому в классе TtdRecordStream свойство Items не используется. Вместо него введены простые методы Read и Write.
Конструктор Create может вызываться в двух режимах: для постоянного массива в потоке или не в потоке. Режим определяется самим конструктором и в случае, если используется новый поток, создается служебный блок.
Листинг 2.19. Конструктор класса TtdRecordStream
constructor TtdRecordStream.Create(aStream : TStream;
aRecordLength : integer);
begin
inherited Create;
{сохранить поток и его текущую позицию}
FStream := aStream;
FZeroPosition := aStream.Position;
{если размер потока равен нулю, нужно создать служебный заголовок}
if (aStream.Size – FZeroPosition = 0) then
rsCreateHeaderRec(aRecordLength) {в противном случае проверить, содержится ли в потоке действительный служебный заголовок, считать его и установить значения его полей}
else
rsReadHeaderRec;
{выделить память под запись}
FRecordLen4 := FRecordLen + sizeof(longint);
GetMem(FRecord, FRecordLen4);
end;
Обратите внимание, что конструктор считывает текущее положение потока и записывает его в FZeroPosition. Текущее положение, которое, как правило, равно нулю, будет использовать для указания положения служебного заголовка для постоянного массива. Это означает, что перед вызовом конструктора Create программист может записать в поток свой служебный заголовок, и методы класса не будут его изменять. Тем не менее, класс предполагает, что оставшаяся часть потока, начиная с положения FZeroPosition, принадлежит классу и в нее допускается вносить изменения.
Конструктор вызывает либо метод rsCreateHeaderRec, который создает новый служебный заголовок для пустого потока (т.е. при необходимости создания нового массива), либо метод rsReadHeaderRec, который считывает текущий служебный заголовок (и, кроме того, проверяет его корректность).
И, наконец, конструктор Create выделяет из кучи память для записи (память выделяется с учетом размера флага удаления). Деструктор Destroy освобождает память, выделенную под запись.
Листинг 2.20. Деструктор класса TtdRecordStream
destructor TtdRecordStream.Destroy;
begin
if (FHeaderRec <> nil) then
FreeMem(FHeaderRec, FheaderRec^.hrHeaderLen);
if (FRecord <> nil) then
FreeMem(FRecord, FRecordLen4);
inherited Destroy;
end;
А теперь давайте рассмотрим два вспомогательных метода, которые соответственно создают новый или считывают существующий служебный заголовок.
Листинг 2.21. Создание и считывание служебного заголовка
procedure TtdRecordStream.rsCreateHeaderRec(aRecordLen : integer);
begin
{выделить память под служебный заголовок}
if ((aRecordLen + sizeof(longint)) < sizeof(TtdRSHeaderRec)) then begin
FHeaderRec := AllocMem(sizeof(TtdRSHeaderRec));
FHeaderRec^.hrHeaderLen := sizeof(TtdRSHeaderRec);
end
else begin
FHeaderRec := AllocMem( aRecordLen + sizeof(longint));
FHeaderRec^.hrHeaderLen := aRecordLen + sizeof(longint);
end;
{задать значения остальных стандартных полей}
with FHeaderRec^ do
begin
hrSignature := cRSSignature;
hrVersion := $00010000; {Major=1; Minor=0}
hrRecordLen := aRecordLen;
hrCapacity := 0;
hrCount := 0;
hr1stDelRec := cEndOfDeletedChain;
end;
{обновить служебный заголовок}
rsSeekStream(FZeroPosition);
rsWriteStream(FHeaderRec^, FHeaderRec^.hrHeaderLen);
{задать значение поля длины записи}
FRecordLen := aRecordLen;
end;
procedure TtdRecordStream.rsReadHeaderRec;
var
StreamSize : longint;
TempHeaderRec : TtdRSHeaderRec;
begin
{если размер потока меньше размера служебного заголовка, это неверный поток}
StreamSize := FStream.Size – FZeroPosition;
if (StreamSize < sizeof(TtdRSHeaderRec)) then
rsError(tdeRSNoHeaderRec, 'rsReadHeaderRec', 0);
{считать служебный заголовок}
rsSeekStream(FZeroPosition);
rsReadStream(TempHeaderRec, sizeof(TtdRSHeaderRec));
{первая санитарная проверка: сигнатура и счетчик/емкость}
with TempHeaderRec do
begin
if (hrSignatureocRSSignature) or (hrCount > hrCapacity) then
rsError(tdeRSBadHeaderRec, 'rsReadHeaderRec', 0);
end;
{выделить память под реальный служебный заголовок, скопировать уже считанные данные}
FHeaderRec := AllocMem(TempHeaderRec.hrHeaderLen);
Move(TempHeaderRec, FHeaderRec^, TempHeaderRec.hrHeaderLen);
{вторая санитарная проверка: проверка данных записи}
with FHeaderRec^ do
begin
FRecordLen4 := hrRecordLen + 4;
{for rsCalcRecordOffset}
if (StreamSize <> rsCalcRecordOffset(hrCapacity)) then
rsError(tdeRSBadHeaderRec, 'rsReadHeaderRec', 0);
{установить значения полей класса}
FCount :=hrCount;
FCapacity := hrCapacity;
FRecordLen := hrRecordLen;
end;
end;
function TtdRecordStream.rsCalcRecordOffset(aIndex : longint): longint;
begin
Result := FZeroPosition + FHeaderRec^.hrHeaderLen + (aIndex * FRecordLen4);
end;
Приведенный метод создания служебного заголовка вызывается только в случае, когда поток пуст. Принцип его работы очень прост. Сначала служебный заголовок создается в памяти, а затем записывается в поток. Если длина записи больше, чем нормальный размер служебного заголовка, его размер увеличивает до размера записи. В служебном заголовке содержится семь полей: поле сигнатуры, которое может использоваться для контроля при считывании записи;
номер версии служебного заголовка (это позволит в будущем добавлять в заголовок новые поля и сохранять совместимость версий);
длина служебного заголовка;
длина записи;
емкость потока (т.е. количество записей как активных, так и удаленных, которые в данный момент находятся в потоке);
количество активных записей;
и, наконец, порядковый номер первой удаленной записи (здесь значение этого поля устанавливается равным 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. Он существует только для того, чтобы быть перекрытым в дочерних классах, которые имеют дело с потоком, связанным с диском, например, файловым потоком.
Листинг 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}
В приведенном коде присутствует перекрытый метод Flush, который сбрасывает данные в дескриптор, связанный с файловым потоком, содержащим постоянный массив. Реализации для Delphi1 и для 32-битных версий будут отличаться, поскольку процесс сброса данных в дескриптор в этих версиях различен.
Полный код класса TtdRecordStream можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRecFil.pas.
Резюме
Эта глава была посвящена массивам – одной из фундаментальных структур данных. Были описаны их достоинства (доступ к отдельным элементам составляет O(1), поддерживается локальность ссылок) и недостатки (вставка и удаление элементов относятся к операциям класса О(n)). Приведена реализация класса массива TtdRecordList. Затем был подробно рассмотрен стандартный класс TList и его простой дочерний класс TtdObjectList.
Кроме того, мы познакомились с реализацией постоянных массивов в форме потока записей. Был приведен пример реализации класса постоянных массивов, TtdRecordStream, который позволяет выполнять чтение, запись и удаление отдельных записей.
Глава 3. Связные списки, стеки и очереди
Как и массивы, связные списки представляют собой универсальную структуру данных, широко используемую многими программистами. Однако, в отличие от массивов, связные списки не входят в состав стандартного языка Object Pascal. Тем не менее, в Object Pascal создать связный список достаточно просто. Все что для этого нужно – наличие в составе языка указателя, хотя фактически могут использоваться и классы или объекты.
На основе связных списков можно легко организовать стеки и очереди – еще две простые, но эффективные структуры данных. Несмотря на то что они, на первый взгляд, не имеют ничего общего со связными списками, их можно написать на базе односвязных списков. И, как мы увидим чуть позже, иногда удобнее реализовать стеки и очереди на базе массивов, а не связных списков.
Начнем наше рассмотрение со связного списка и операций, которые такой список должен поддерживать.
Односвязные списки
По своей сути связный список (linked list) представляет собой цепочку элементов или объектов с некоторыми описаниями (обычно называемых узлами). При этом каждый элемент содержит указатель, указывающий на следующий элемент в списке. Такая структура данных называется односвязным списком (singly linked list) – каждый элемент имеет только одну ссылку или указатель на следующий элемент. Сам список начинается с первого узла, от которого путем последовательных переходов по ссылкам можно обойти все остальные узлы. Обратите внимание, что определение связного списка отличается от определения массива, для которого следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.
Рисунок 3.1. Односвязный список
А каким образом помечается конец списка? Самый простой способ – установить указатель ссылки в последнем элементе списка равным nil. Это будет означать, что следующий элемент отсутствует. Второй способ – ввести специальный узел, называемый конечным узлом, и установить так, чтобы ссылка последнего узла указывала на этот узел. И третий способ – установить так, чтобы ссылка последнего узла указывала на первый элемент. В этом случае мы получим круговой связный список.
А теперь рассмотрим, чем же связный список отличается от массива. Первое, что нужно отметить, – размер связного списка можно не устанавливать. Для массива нам всегда было нужно заранее знать, сколько элементов будет в нем храниться (чтобы можно было статически распределить непрерывный участок памяти) или разработать некоторую схему расширения массива (или его сокращения), чтобы массив мог разместить большее (или меньшее) количество элементов. В связном списке каждый узел является отдельным элементом. И в простых случаях распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется память, а затем элемент просто на него устанавливается ссылка из списка. При удалении узла нужно всего лишь удалить ссылки на него и освободить занимаемую им память.
Хорошо. Если связный список настолько удобен, почему бы его не использовать вместо массива? В чем состоят его недостатки? Первый, хотя и незначительный, состоит в том, что каждый элемент связного списка должен содержать указатель на следующий элемент. Таким образом, чтобы вставить элемент в список, его реальный размер необходимо увеличить на размер указателя (в настоящее время это 4 байта).
Хуже то, что память под каждый узел распределяется отдельно. Сравним эту ситуацию с аналогичной ситуацией для массива. Распределение памяти под n элементов массива, фактически, представляет собой операцию класса O(1): все элементы должны находится в одном непрерывном блоке памяти, поэтому одновременно распределяется целый блок. (Нужно помнить, что память для элементов массивов не обязательно должна распределяться из кучи. Массивы могут представлять собой, например, локальные переменные в стеке.) Для связного списка память под узлы распределяется отдельно, следовательно, это операция класса O(n). Даже если не учитывать быстродействие, подобное поведение может привести к фрагментации кучи.
Самым большим недостатком связного списка является получение доступа к некоторому элементу n. В массиве доступ к n-ному элементу требует проведения простых арифметических вычислений, поскольку все элементы содержатся в одном непрерывном блоке памяти. С другой стороны, в списке получение доступа к элементу n требует прохождения по ссылкам от первого элемента до n-ного. Другого метода доступа не существует, мы всегда должны следовать по ссылкам. (Обратите внимание, что можно применить определенные хитрости, например, хранить элемент и его позицию в рамках списка в кэш-памяти. В таком случае можно определять целесообразность начала прохождения списка с его первого элемента или с элемента, хранящегося в кэш-памяти.)
Узлы связного списка
Перед началом описания операций со связным списком давайте рассмотрим, как каждый узел списка будет представляться в памяти. Знание структуры узла позволит нам более детально рассматривать основные операции со связными списком. Структура узла списка, не использующего классы и объекты, выглядит следующим образом:
type
PSimpleNode = ^TSimpleNode;
TSimpleNode = record
Next : PSimpleNode;
Data : SomeDataType;
end;
Тип PSimpleNode представляет собой указатель на запись TSimpleNode, поле Next которой содержит ссылку на точно такой же узел, а поле Data – сами данные. В приведенном примере тип данных узла задан как SomeDataType. Для перехода по ссылке нужно написать примерно следующий код:
var
NextNode, CurrentNode : PSimpleNode;
begin
• • •
NextNode := CurrentNode^.Next;
Создание односвязного списка
Это тривиальная задача. В самом простом случае первый узел в связном списке описывает весь список. Первый узел иногда называют головой списка.
var
MyLinkedList : PSimpleNode;
Если MyLinkedList содержит nil, списка еще нет. Таким образом, это начальное значение связного списка.
{инициализация связного списка}
MyLinkedList := nil;
Вставка и удаление элементов в односвязном списке
А каким образом можно вставить новый элемент в связный список? Или удалить? Оказывается, что для выполнения этих операций требуется выполнить небольшую работу с указателями.
Для односвязного списка существует только один вариант вставки – после заданного элемента списка. Нужно установить так, чтобы указатель Next нашего нового узла указывал на узел после заданного, а указатель Next заданного узла – на наш новый узел. В коде это выглядит следующим образом:
var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data..
NewNode^.Next := GivenNode^.Next;
GivenNode^.Next := NewNode;
Рисунок 3.2. Вставка нового узла в односвязный список
Аналогично, для удаления простейшим вариантом является удаление элемента, находящегося после заданного узла. В этом случае мы устанавливаем, чтобы указатель Next заданного узла указывал на узел, расположенный после удаляемого. После этого удаляемый узел уже выделен из списка и может быть освобожден. В коде это выглядит следующим образом:
var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo := GivenNode^.Next;
GivenNode^.Next := NodeToGo^.Next;
Dispose(NodeToGo);
Рисунок 3.3. Удаление узла из односвязного списка
Тем не менее, для обеих операций существует специальный случай: вставка перед первым элементом списка (т.е. новый элемент становиться первым) и удаление первого элемента списка (т.е. первым становится другой элемент). Поскольку в наших рассуждениях первый элемент считается определяющим узлом всего списка, код для этих случаев нужно написать отдельно. Вставка перед первым узлом будет выглядеть следующим образом:
var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data..
NewNode^.Next := MyLinkedList;
MyLinkedList := NewNode;
а удаление будет выглядеть так:
var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo := GivenNode^.Next;
MyLinkedList := NodeToGo^.Next;
Dispose(NodeToGo);
Обратите внимание, что код вставки элемента будет работать даже в случае, когда исходный список пуст, т.е. содержит nil, а код удаления элемента правильно установит содержимое связного списка в случае удаления из него последнего узла.
Прохождение связного списка также не представляет никаких трудностей. Фактически мы переходим от узла к узлу по указателям Next до достижения указателя nil, который свидетельствует об окончании списка.
var
FirstNode, TempNode : PSimpleNode;
begin
• • •
TempNode := FirstNode;
while TempNode <> nil do
begin
Process(TempNode^.Data);
TempNode := TempNode^.Next;
end;
В этом простом цикле процедура Process (определенная в другом месте) выполняет обработку поля Data переданного ей узла. Очистка связного списка требует небольшого изменения алгоритма, чтобы гарантировать, что мы не ссылаемся на поле Next после освобождения узла (довольно-таки частая ошибка).
var
MyLinkedList, TempNode, NodeToGo : PSimpleNode;
begin
NodeToGo := MyLinkedList;
while NodeToGo <> nil do
begin
TempNode := NodeToGo^.Next;
Dispose(NodeToGo);
NodeToGo := TempNode;
end;
MyLinkedList :=nil;
Теперь, когда мы научились проходить по узлам связного списка, давайте вернемся к вопросу, который, наверное, появился у вас пару абзацев назад. А что если нам нужно вставить узел перед заданным узлом? Как это сделать? Единственным решением такой задачи для односвязного списка является прохождение списка и поиск узла, перед которым мы должны вставить новый узел. При прохождении будут использоваться две переменных: одна будет указывать на текущий, а вторая на предыдущий узел (родительский узел, если можно так сказать). Когда будет найден заданный узел, у нас будет указатель на предыдущий узел, что позволит использовать алгоритм вставки после заданного узла. В коде это выглядит следующим образом:
var
FirstNode, GivenNode, TempNode,
ParentNode : PSimpleNode;
begin
ParentNode := nil;
TempNode := FirstNode;
while TempNode <> GivenNode do
begin
ParentNode := TempNode;
TempNode := ParentNode^.Next;
end;
if TempNode = GivenNode then begin
if (ParentNode = nil) then begin
NewNode^.Next := FirstNode;
FirstNode := NewNode;
end
else begin
NewNode^.Next := ParentNode^.Next;
ParentNode^.Next := NewNode;
end;
end;
Обратите внимание на специальный код для случая вставки нового узла перед первым узлом (в этом случае родительский узел nil). Код для вставки перед заданным узлом медленнее кода вставки после заданного узла, поскольку он требует прохождения списка с целью обнаружения родительского узла заданного узла. В общем случае, при необходимости вставки нового узла перед заданным мы будет использовать двухсвязный список, который будет подробно рассмотрен немного ниже.
