Моделирование работы стека

Begin

Var

Const

Uses

Begin

Begin

Begin

Var

Begin

Const

D=5; { максимальное количество цифр в числе }

P=10; { основание системы счисления }

{ возвращает значение n-ой цифры в числе v }

function Digit(v, n: Integer): Integer;

for n:=n downto 2 do

v:=v div P;

Digit:=v mod P;

end;

procedure DigitSort;

{ индекс элемента, следующего за последним в i-ой группе }

b: array [0..P-2] of Integer;

i, j, k, m, N: Integer;

x: Pointer;

N:=aList.Count-1;

for m:=1 to D do

{ перебор цифр, начиная с младшей }

for i:=0 to P-2 do b[i]:=1;

{ нач. значения индексов }

for i:=1 to N do

{ перебор массива }

{ определение m-ой цифры }

k:=Digit(LongWord(aList.Items[i]^),m);

x:=aList.Items[i];

{ сдвиг - освобождение места в конце k-ой группы }

for j:=i downto b[k]+1 do

aList.Items[j]:=aList.Items[j-1];

{ запись в конец k-ой группы }

aList.Items[b[k]]:=x;

{ модификация k-го индекса и всех больших }

for j:=k to P-2 do b[j]:=b[j]+1;

end;

end;

end;

end.

В следующем примере показан способ применения приведенных модулей.

program demo;

{$APPTYPE CONSOLE}

Classes,

SysUtils,

Windows,

srch in 'srch.pas',

common in 'common.pas',

sort in 'sort.pas';

LoadFileName = 'c:\data.txt';

SaveFileName = 'c:\data_sort.txt';

w, Id: Word;

t, Size: LongWord;

tmpList: PPointerList;

{ Открытие выборки }

OpenList(LoadFileName, Size);

WriteLn('Samples size: '+IntToStr(Size));

WriteLn('');

WriteLn('Select command:');

WriteLn(' 0 - Exit');

WriteLn(' 1 - Linear search');

WriteLn(' 2 - Selection sort');

WriteLn(' 3 - Insert bubble sort');

WriteLn(' 4 - Shell sort');

WriteLn(' 5 - Quick Hoar standard sort');

WriteLn(' 6 - MSS sort');

{ Выбор пункта меню }

repeat ReadLn(Id); until Id <= 6;

{ Обработка команды меню }

case Id of

0: Exit;

1: begin

Write('Input key: ');

ReadLn(w);

{ Зафиксировать момент времени }

t:=GetTickCount;

WriteLn('Serial number: '+

IntToStr(LineNonSortedSearch(List, @w, CompareLongWord)));

{ Время выполнения алгоритма }

t:=GetTickCount-t;

WriteLn('Linear search time: '+IntToStr(t));

ReadLn;

end;

2: begin

t:=GetTickCount;

SelectionSort(List,0,List.Count-1, CompareLongWord);

t:=GetTickCount-t;

WriteLn('Selection sort time: '+IntToStr(t));

end;

3: begin

t:=GetTickCount;

InsertionBublSort(List,0,List.Count-1, CompareLongWord);

t:=GetTickCount-t;

WriteLn('Insert bubble sort time: '+IntToStr(t));

end;

4: begin

t:=GetTickCount;

ShellSort(List, CompareLongWord);

t:=GetTickCount-t;

WriteLn('Shell sort time: '+IntToStr(t));

end;

5: begin

t:=GetTickCount;

QuickHoarStd1Sort(List, 0,List.Count-1, CompareLongWord);

t:=GetTickCount-t;

WriteLn('Quick Hoar standard sort time: '+IntToStr(t));

end;

6: begin

New(tmpList);

t:=GetTickCount;

MSS(List, 0,List.Count-1, CompareLongWord, tmpList);

t:=GetTickCount-t;

WriteLn('MSS sort time: '+IntToStr(t));

Dispose(tmpList);

end;

end;

{ Сохранение отсортированных данных }

if Id > 1 then SaveList(SaveFileName);

ReadLn;

end.

Модуль содержит вариант реализации стека на структуре данных «вектор». Стек расширяется в сторону уменьшения адресов. Указатель стека всегда указывает на первый свободный элемент. Перед использованием модуля должен быть определен предельный размер стека и структура элемента данных стека.

unit Stack;

Дата добавления: 2014-01-07