Стеки используются в случае, когда требуется вычислить элементы в обратном порядке, а затем перестроить их в прямой порядок. Одним из самых простых примеров может служить изменение порядка символов в строке. При наличии стека символов задание становится очень простым: затолкнуть символы из строки в стек, а затем вытолкнуть их в обратном порядке. (Разумеется, существуют и другие методы изменения порядка символов в строке.) Интересной вариацией этой темы является преобразование целого значения в строку. В языке Object Pascal имеются функции str и intToStr, которые позволяют решать поставленную задачу далеко не с нуля, но, тем не менее, задача остается достаточно интересной.

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

Внутри функции нужно будет вычислять цифры, соответствующие целочисленному значению. Простейший метод таких вычислений - вычислить остаток от деления значения на 10 (это будут числа от 0 до 9 включительно), сохранить его где-нибудь, поделить значение на 10 (чтобы избавиться от только что вычисленного нами значения) и повторить процесс. Цикл вычислений продолжается до тех пор, пока не будет получено значение 0.

Давайте применим описанный алгоритм (да-да, это алгоритм!) к числу 123. Остаток от деления 123 на 10 равен 3. Записываем остаток. Делим 123 на 10. Получаем 12. Остаток от деления 12 на 10 равен 2. Записываем остаток. Делим 12 на 10. Получаем 1. Остаток от деления 1 на 10 равен 1. Записываем остаток. Делим 1 на 10. Получаем 0. Завершаем вычисления. Цифры были вычислены в следующем порядке: 3, 2, 1. Однако в строке они должны находиться в обратном порядке. Мы не можем записывать цифры в строку по мере их вычисления (какой длины должна быть строка?).

Можно предложить заталкивать цифры в стек по мере их вычисления, а после выполнения вычислений определить количество элементов в стеке (т.е. длину строки) и постепенно выталкивать их в строку. Соответствующий код приведен в листинге 3.25.

Листинг 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 цифр (поскольку максимальное значение типа Іопдіхгі: - 2 147 483 648 - 10-значное число). Эту длину нужно увеличить на 1 - возможный знак минус. Столь короткую строку вполне можно поместить в стек.

Стеки на основе массивов || Оглавление || Очереди


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



Новости за месяц

  • Апрель
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс