Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Давайте применим описанный алгоритм (да-да, это алгоритм!) к числу 123. Остаток от деления 123 на 10 равен 3. Записываем остаток. Делим 123 на 10. Получаем 12. Остаток от деления 12 на 10 равен 2. Записываем остаток. Делим 12 на 10. Получаем 1. Остаток от деления 1 на 10 равен 1. Записываем остаток. Делим 1 на 10. Получаем 0. Завершаем вычисления. Цифры были вычислены в следующем порядке: 3, 2, 1. Однако в строке они должны находиться в обратном порядке. Мы не можем записывать цифры в строку по мере их вычисления (какой длины должна быть строка?).
Можно
Листинг 3.25. Преобразование целочисленного значения в строку
function tdlntToStr(aValue : longint): string;
var
ChStack : array [0..10] of char;
ChSP : integer;
IsNeg : boolean;
i : integer;
begin
{установить нулевую длину стека}
ChSP := 0;
{установить, чтобы значение было положительным}
if (aValue < 0) then begin
IsNeg true;
aValue :=-aValue;
end else
IsNeg := false;
{если значение равно нулю, записать в стек символ 'О'}
if (aValue = 0) then begin
ChStack[ChSP] := '0';
inc(ChSP);
end
{в противном случае вычислить цифры значения в обратном порядке с помощью описанного алгоритма и затолкнуть их в стек}
else begin
while (aValue <> 0) do
begin
ChStack[ChSP] := char((aValue mod 10) +ord('0'> );
inc(ChSP);
aValue := aValue div 10;
end;
end;
{если исходное значение было отрицательным, затолкнуть в стек знак минус}
if IsNeg then begin
ChStack[ChSP] :=;
inc(ChSP);
end;
{теперь выталкиваем значения из стека (их количество равно ChSP) в результирующую строку}
SetLength(Result, ChSP);
for i := 1 to ChSP do
begin
dec(ChSP);
Result[i] := ChStack[ChSP];
end;
end;
В приведенной функции присутствует несколько особенностей, о которых стоит упомянуть. Первая особенность состоит в том, что функция требует, чтобы исходное значение перед выполнением алгоритма было положительным. Если мы изменяем знак значения, то устанавливаем флаг IsNeg, который позволит в дальнейшем записать в строку знак минус. Вторая особенность - отдельно обрабатывается случай, когда значение равно 0. Без этого при нулевом входном значении мы бы получили пустую строку.
Следующий аспект. Стек символов был написан "с нуля". Почему? Мы уже имеем два класса стеков. Разве мы не можем использовать их?
Ответы на эти вопросы возвращают нас к тому, о чем уже ранее говорилось в книге: иногда эффективнее написать простой контейнер (в нашем случае стек) с самого начала. При написании кода преобразования целочисленного значения в строку максимальная длина значения будет составлять 10 цифр (поскольку максимальное значение типа iопдiхгi: - 2 147 483 648 - 10-значное число). Эту длину нужно увеличить на 1 - возможный знак минус. Столь короткую строку вполне можно поместить в стек.
Очереди
И, наконец, последним моментом, который мы рассмотрим в этой главе, будут очереди - последняя базовая структура данных. В то время как извлечение элементов из стека происходит в порядке, обратном тому, в котором они вносились, в очереди элементы выбираются в порядке их добавления. Таким образом, очередь относится к структурам типа "первый пришел, первый вышел" (FIFO - first in, first out). С очередью связаны две основные операции: постановка в очередь (т.е. добавление нового элемента в очередь) и снятие с очереди (т.е. извлечение из нее самого старого элемента).
Рисунок 3.9. Постановка в очередь и снятие с очереди
Иногда эти операции ошибочно называют заталкиванием и выталкиванием. Это абсолютно неверные термины для очереди. Ближе к истине будут слова включение и исключение.
Как и стеки, очереди можно реализовать на основе односвязных списков или массивов. Тем не менее, в отличие от стеков, очень трудно добиться высокой эффективности реализации на основе массивов. К тому же организация очередей на базе связных списков ничуть не сложнее. Поэтому давайте для начала рассмотрим построение очереди на базе односвязных списков.
Очереди на основе односвязных списков
Фактически мы должны смоделировать обычную очередь в универмаге. С помощью списков это можно сделать очень легко, поскольку сами списки по своей сути являются очередями. Просто для моделирования очереди элементы должны добавляться с одной стороны и удаляться с другой. При использовании односвязного списка снятие с очереди будет выполняться с начала списка, а постановка в очередь - в конец списка. Для двухсвязных списков для постановки или снятия с очереди может выбираться как начало, так и конец. Но в этом случае очередь будет требовать больший объем памяти. Очевидно, что обе операции с очередью не зависят от количества элементов в ней, т.е. они принадлежат к классу O(1).
Как и для класса TtdStack, код класса TtdQueue будет разрабатываться на основе главных принципов. Аргументы за использование такой схемы мы рассматривали во время написания кода для класса стека.
Листинг 3.26. Класс TtdQueue
TtdQueue = class private
PCount : longint;
FDispose : TtdDisposeProc;
FHead : PslNode;
FName : TtdNameString;
FTail : PslNode;
protected
procedure qError(aErrorCode : integer;
const aMethodName : TtdNameString);