Реализация абстрактных типов данных с помощью массивов.

19.2. Реализация абстрактных типов данных с помощью массивов.

Абстракции данных, где конкретные объекты могут быть фиксированного размера, может быть эффективно реализована с использованием массивов.

Типа данных массив реализует конечные списки с эффективным произвольным доступом к любому элементу. Файловый тип данных позволяет доступ к любому элементу, но только в последовательном порядке. Если требуемый элемент не находится в голове списка будущего файла, потребуется много операций READ, чтобы его считать.

19.2.1. Текстовые файлы ограниченного размера.

19.2.1. Стек ограниченного размера.

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

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

PROGRAM Reverse(INPUT, OUTPUT);

{Выводит первые Depth символов в INPUT в обратном порядке}

CONST

Depth = 20;

TYPE

EltType = CHAR;

Stack = RECORD

Val: ARRAY [1..Depth] OF EltType;

StackTop: 0..Depth

END;

VAR

S: Stack;

Elt: EltType;

PROCEDURE NewStack(VAR S: Stack);

{S := <>}

BEGIN {NewStack}

S.StackTop := 0;

END; {NewStack}

PROCEDURE Push(VAR S: Stack, E: EltType);

{S := S & <E>}

BEGIN {Push}

IF S.StackTop >= Depth

THEN

WRITELN(‘** OVERFLOW **’)

ELSE

BEGIN

S.StackTop := S.StackTop + 1;

S.Val[S.StackTop] := E

END

END; {Push}

PROCEDURE Pop(VAR S:Stack);

{Существуют Stack X, EltType E, такие что

S = X & <E> --> S := X}

BEGIN {Pop}

IF S.StackTop <= 0

THEN

WRITELN(‘** UNDERFLOW **’)

ELSE

S.StackTop := S.StackTop - 1

END; {Pop}

Function Top(VAR S: Stack);

{Существуют Stack X, EltType E, такие что

S = X & <E> --> Top := E}

BEGIN {Top}

IF S.StackTop <= 0

THEN

BEGIN

WRITELN(‘** READING EMPTY STACK **’);

Top := 0;

END

ELSE

Top := S.Val[S.StackTop]

END; {Top}

FUNCTION Empty(VAR S: Stack): BOOLEAN;

{Empty := (S = <>)}

BEGIN {Empty}

Empty := S.StackTop <= 0

END; {Empty}

FUNCTION Full(VAR S: Stack): BOOLEAN;

{Full := (Length(S) = Depth)}

BEGIN {Full}

Full := S.StackTop >= Depth

END; {Full}

BEGIN {Reverse}

NewStack(S);

WHILE NOT EOF AND NOT Full(S)

BEGIN

Read(Elt);

Push(S, Elt);

END;

WHILE NOT Empty(S)

BEGIN

WRITE(Top(S));

Pop(S)

END;

WRITELN

END. {Reverse}

Выполнение:

INPUT: abcdefghijklmnopqrstuvwxyz

OUTPUT: zyxwvutsrqponmlkjihgfedcba

⇐ Предыдущая 1 2 3 4 56