Design Part 1

PROGRAM Encryption(INPUT, OUTPUT);

{Переводит символы из INPUT в код согласно Chiper

и печатает новые символы в OUTPUT}

CONST

Len = 20;

TYPE

Str = ARRAY [1 .. Len] OF ‘A’ .. ‘Z’;

Chiper = ARRAY [‘A’ .. ‘Z’] OF CHAR;

VAR

Msg: Str;

Code: Chiper;

BEGIN {Encryption}

{Инициализировать Code}

WHILE NOT EOF

DO

BEGIN

{читать строку в Msg и распечатать ее}

{дополнить Msg пробелами}

{распечатать кодированное сообщение}

END

END. {Encryption}

Инициализация массива шифра это длинная последовательность присваиваний, поэтому она объединяется в процедуру.

Design Part 1.1.

{Инициализировать Code}

Initialize(Code);

Design Part 1.1.1.

PROCEDURE Initialize(VAR Code: Chiper);

{Присвоить Code шифр замены}

BEGIN {Initialize}

Code['A'] := 'Z';

Code['B'] := 'Y';

Code['C'] := 'X';

Code['D'] := '#';

Code['E'] := 'V';

Code['F'] := 'U';

Code['G'] := 'T';

Code['H'] := 'S';

Code['I'] := 'I';

Code['J'] := 'Q';

Code['K'] := 'P';

Code['L'] := '!';

Code['M'] := 'N';

Code['N'] := 'M';

Code['O'] := '2';

Code['P'] := 'K';

Code['Q'] := '$';

Code['R'] := 'D';

Code['S'] := 'H';

Code['T'] := '*';

Code['U'] := 'F';

Code['V'] := 'E';

Code['W'] := 'T';

Code['X'] := 'C';

Code['Y'] := 'B';

Code['Z'] := 'A';

END; {Initialize}

Символы считываются в последовательные элементы Msg до тех пор, пока не встретится маркер конца строки.

Design Part 1.2.

{читать строку в Msg и распечатать ее}

I := 0;

WHILE NOT EOLN AND (I < Len)

DO

BEGIN

I := I + 1;

READ(Msg[I]);

WRITE(Msg[I])

END;

READLN;

WRITELN;

Индекс I теперь находится в позиции последнего символа в сообщении и для очистки оставшейся части строки необходимо заполнить ее пробелами.

Design Part 1.2.

{дополнить Msg пробелами}

FOR I := I+1 TO Len

DO

BEGIN

Msg[I] := ‘ ‘;

END

Поскольку шифрование Msg занимает несколько строк кода, они оформляются процедурой.

Design Part 1.4.

{распечатать кодированное сообщение}

Encode(Msg)

Элементы Msg с ‘A’ по ‘Z’ используются как индексы в массиве Code для получения их кодированных значений. Другие символы распечатываются без перевода.

Design Part 1.4.

PROCEDURE Encode(VAR S: Str);

{Выводит символы из Code, соответствующие символам из S}

VAR

Index: 1 .. Len;

BEGIN {Encode}

FOR Index := 1 TO Len

DO

IF S[Index] IN [‘A’ .. ‘Z’]

THEN

WRITE(Code[S[Index]])

ELSE

WRITE(S[Index]);

WRITELN

END; {Encode}

Ниже приведен финальный текст программы и примеры ввода/вывода.

PROGRAM Encryption(INPUT, OUTPUT);

{Переводит символы из INPUT в код согласно Chiper

и печатает новые символы в OUTPUT}

CONST

Len = 20;

TYPE

Str = ARRAY [1 .. Len] OF ‘A’ .. ‘Z’;

Chiper = ARRAY [‘A’ .. ‘Z’] OF CHAR;

VAR

Msg: Str;

Code: Chiper;

{Включить PROCEDURE Encode(VAR S: Str);}

{Включить PROCEDURE Initialize(VAR Code: Chiper);}

BEGIN {Encryption}

{Инициализировать Code}

Initialize(Code);

WHILE NOT EOF

DO

BEGIN

{читать строку в Msg и распечатать ее}

I := 0;

WHILE NOT EOLN AND (I < Len)

DO

BEGIN

I := I + 1;

READ(Msg[I]);

WRITE(Msg[I])

END;

READLN;

WRITELN;

{дополнить Msg пробелами}

FOR I := I+1 TO Len

DO

BEGIN

Msg[I] := ' ';

END

{распечатать кодированное сообщение}

Encode(Msg)

END

END. {Encryption}

Выполнение:

INPUT: NOW IS THE TIME

END

OUTPUT: NOW IS THE TIME

M2T IH *SV *INV

END

VM#

19.1.1. Синтаксис и семантика для массивов.

Следующие синтаксические правила описывают тип данных массив.

<составной тип> ::= <неупакованный структурированный тип>

<неупакованный структурированный тип> ::= SET OF <базовый тип>

| FILE OF <тип компонентов>

| RECORD <список полей> END

| ARRAY [<список индексного типа>] OF <тип компонентов>

<список индексного типа> ::= <список индексного типа>, порядковый тип

| <порядковый тип>

Поскольку значения массивов могут использоваться как другие переменные, определение <переменной> должно быть расширено, чтобы включить их.

<переменная> ::= <идентификатор переменной> | <переменная буфера>

| <переменная-компонент>

<переменная-компонент> ::= <описатель поля> | <индексированная переменная>

<индексированная переменная> ::= <переменная массива> [<список выражений>]

<переменная массива> ::= <переменная>

<список выражений> ::= <список выражений>, <выражение> | <выражение>

Формально, значения соответствующие переменным массивов в состоянии выполнения являются отношениями. В парах отношения массив-значения первые элементы принадлежат конечному множеству значений индексного типа, а вторые элементы множеству значений типа компонентов. Таким образом, количество возможных значений переменой массива велико. Каждый индекс может находится в паре с любым из возможных значений компонента, так что для N индексов и M возможных значений компонентов, массив может иметь M^N значений, каждое из которых представляет из себя соответствие значений индексам. Например, переменная:

VAR

Carray: ARRAY [1..3] OF CHAR;

имеет 128³ ~ 2 100 000 возможных значений для Паскаль-машины со 128 символьными значениями, одним из которых будет {<1, X>, <2, B>, <3, 3>}. Это значение может быть результатом присваивания:

CArray[1] := ‘X’;

CArray[2] := ‘B’;

CArray[3] := ‘3’;

Раз каждый индекс в массиве имеет присвоенный ему компонент, значение массива должно быть функцией. Однако, до тех пор пока индекс остается несвязанным, эта часть массива подобна неинициализированной переменной. Например, если к CArray были применены только первое и третье присваивания, его значение будет:

{<1, X>, <3, 3>}È{ <2, c>: c - символ},

которое мы обычно сокращаем до

{<1, X>, <3, 3> <2, ?> }.

Эти значения могут появляться в состоянии выполнения с идентификатором массива.

S = {CArray·{<1, X>, <3, 3> <2, ?> }, ...}

Значение <индексированной переменной> может быть получено может быть получено из значения соответствующего массива. Например для приведенного выше состояния S:

CArray[1](S) = X

В общем, для идентификатора массива A и индекса I, где I принадлежит типу J:

A[I] = {<s, v>: s(I) является значением типа J, v = (s(A))(s(I))}

Определение присваивания (раздел 6.2.1) применимо к массивам без изменений, но не покрывает случай, где элемент массива находится в левой части присваивания. В этом случае присваивание завершается с ошибкой, если значение индекс не является допустимым значением соответствующего типа. Формально, для индекса I типа J:

A[I] := E = {<s, t>: I(s) является значением типа J, t =s,

за исключением того, что A[I](t)=E(s)}

Во всех других случаях значение выражения становится присоединенным к идентификатору в левой части в состоянии выполнения после выполнения оператора.

Когда оператор присваивания присваивает один идентификатор массива другому идентификатору, его значением становится отношение, представляющее значение массива в целом.

19.1.2. Параметры-массивы.

Целые массивы компонентов могут появляться как фактические параметры в программах. Как и другие составные типы Паскаля, массивы обычно передаются по ссылке как параметры-переменные по соображениям эффективности. Если массив передается как параметр-значение, неявно присутствующая операция копирования должна будет скопировать каждый компонент. Однако, компоненты массивов могут эффективно связываться как с параметрами-значениями так и с параметрами-переменными. Определения раздела 9.1.4 не адекватны для случая алиасинга между индексным идентификатором и компонентом массива с таким индексом, переданным в параметре-значении.

Следующая программа обозначает некоторые сложности, которые могут возникнуть. Index передается параметру First, а Arr[Index] передается параметру Second. Таким образом, возникает алиасинг Second (через индекс Index) к First. First (или Index) инкрементируется до использования Second (или Arr[Index]). Однако, именно значение Arr[2], а не Arr[3] будет изменено, потому что связывание имени фактического параметра с именем формального параметра происходит при вызове процедуры, а не когда параметр-переменная используется.

PROGRAM Bind(INPUT, OUTPUT);

VAR

Arr: ARRAY [1..5] OF INTEGER;

Index: INTEGER;

PROCEDURE IncreaseParams(VAR First, Second: INTEGER);

BEGIN {IncreaseParams}

First := First + 1;

Second := Second + 1;

END; {IncreaseParams}

BEGIN {Bind}

FOR Index := 1 TO 5

DO

BEGIN

Arr[Index] := 1

END

Index := 2;

IncreaseParams(Index, Arr[Index]);

WRITELN(‘Index is’, Index:2);

FOR Index := 1 TO 5

DO

BEGIN

WRITELN(‘Arr[‘, Index:1, ‘] is ‘, Arr[Index] :2)

END

END. {Bind}

Выполнение:

OUTPUT: Index is 3

Arr[1] is 1

Arr[2] is 2

Arr[3] is 1

Arr[4] is 1

Arr[5] is 1

В этом особом случае, когда индекс в массиве и компонент с таким же индексом переданы как параметры-переменные, фактический параметр скопированный в тело процедуры должен иметь его индекс вычисленный в состоянии вызова, а не последующее состояние вычисленное в теле процедуры.

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)

DO

BEGIN

Read(Elt);

Push(S, Elt);

END;

WHILE NOT Empty(S)

DO

BEGIN

WRITE(Top(S));

Pop(S)

END;

WRITELN

END. {Reverse}

Выполнение:

INPUT: abcdefghijklmnopqrstuvwxyz

OUTPUT: zyxwvutsrqponmlkjihgfedcba

Дата добавления: 2014-11-01; просмотров: 242; Нарушение авторских прав

Мы поможем в написании ваших работ!