Главная Промышленная автоматика.

return (true)

else

return(falae)

end; { EMPTY }

function FRONT { var Q: QUEUE ): elementtype; begin

if EMPTY (0) then

error(Очередь пустая)

else

return (C.eIements[Q. front] )

end; { FRONT }

procedure ENQUEUE { x: elementtype; var Q: QUEUE ); begin

if addone(addone {Q.rear)) = Q.front then

error(Очередь полная) else begin

Q.rear:= addonelQ. rear) ;

Q. elements IQ. rear] := x

end; { ENQUEUE }

procedure DEQUEUE( var Q: QUEUE ); begin

if EMPTY(Q) then

error(Очередь пустая)

else

Q. front := addone(,Q. front) end; { DEQUEUE }

2.5. Отображения

Отображение - это функция, определенная на множестве элементов (области определения) одного типа (будем обозначать его domaintype - тип области определения функции) и принимающая значения из множества элементов (области значений) другого типа, этот тип обозначим rangetype - тип области значений (конечно, типы domaintype и rangetype могут совпадать). Тот факт, что отображение М ставит в соответствие элемент d типа domaintype из области определения элементу г типа range-type из области значений, будем записывать как M(d)= г.

Некоторые отображения, подобные square(i)= i, легко реализовать с помощью функций и арифметических выражений языка Pascal. Но для многих отображений нет очевидных способов реализации, кроме хранения для каждого d значения M(d). Например, для реализации функции, ставящей в соответствие работникам их недельную зарплату, требуется хранить текущий заработок каждого работника. В конце этого раздела мы опишем методы реализации таких функций.

Рассмотрим операторы, которые можно выполнить над отображением М. Например, по заданному элементу d типа domaintype мы хотим получить M{d) или узнать, определено ли M(d) (т.е. узнать, принадлежит ли элемент d области определения М). Или хотим добавить новые элементы в текущую область определения М и поставить им в соответствие элементы из области значений. Очевидна также необходимость иметь оператор, который изменял бы значение M(d). Кроме того, нужно средство "обнуления" отображения, переводящее любое отображение в пустое отображение,



т.е. такое, у которого область определения пуста. Наши пожелания можно обобщить в следующие три команды.

1. MAKENULL(M). Делает отображение М пустым.

2. ASSIGN(M, d, г). Делает M(d) равным г независимо от того, как M(d) было определено ранее.

3. COMPUTE(M, d, г). Возвращает значение true и присваивает переменной г значение M(d), если последнее определено, и возвращает false в противном случае.

Реализация отображений посредством массивов

Во многих случаях тип элементов области определения отображения является простым типом, который можно использовать как тип индексов массивов. В языке Pascal типы индексов включают все конечные интервалы целых чисел, например 1..100 или 17..23, строковый тип, диапазоны символов, подобные A...Z,n нечисловые типы, например север, восток, юг, запад. В частности, в программах кодирования можно применить отображение crypt (шифратор) с множеством A...Zh в качестве области определения, и в качестве области значений, так что сгурЦтекст)буд.ет кодом текста текст.

Такие отображения просто реализовать с помощью массивов, предполагая, что некоторые значения типа rangetype могут иметь статус "неопределен". Например, для отображения crypt, описанного выше, область значений можно определить иначе, чем A...Z,n использовать символ .для обозначения "неопределен".

Предположим, что элементы области определения и области значений имеют соответственно типы domaintype и rangetype и что тип domaintype является базовым типом языка Pascal. Тогда тип MAPPING (Отображение) можно объявить следующим образом:

type

MAPPING - array [domaintype] of rangetype;

Предполагая, что "неопределен" - это константа типа rangetype и что константы firstvalue и lastvalue равны первому и последнему элементу области определения, можно реализовать три перечисленных выше оператора, выполняемых над отображениями, как показано в листинге 2.12.

Листинг 2.12. Реализация операторов отображений посредством массива

procedure MAKENULL { var Mi MAPPING ) ; var

i: domaintype; begin

for i;= firstvalue to lastvalue do M[i] : = неопределен end; { MAKENULL }

procedure ASSIGN { var M: MAPPING; d: domaintype; r: rangetype); begin

Mid] := r

end; { ASSIGN }

function COMPUTE { var M: MAPPING;

d: domaintype; r: rangetype): boolean; begin

Например, firstvalue = Аи lastvalue = Z, если область определения совпадает с множеством A..Z.



if Mid]:= неопределен then

return(false) else begin

r: = M[d] ;

return(true)

end; { COMPUTE }

Реализация отображений посредством списков

Существует много реализаций отображений с конечной областью определения. Например, во многих ситуациях отличным выбором будут хэш-таблицы, которые мы рассмотрим в главе 4. Другие отображения с конечной областью определения можно представить в виде списка пар (rfj, п), («(г. "г)» (dt, г), где di, «(2 d» - все текущие элементы области определения, а rj, Гг, - значения, ассоциированные с rf; (i = 1, 2, Л). Далее можно использовать любую реализацию списков.

Абстрактный тип данных MAPPING можно реализовать как список типа elementtype, если сделано объявление

type

elementtype = record

domain: domaintype range: rangetype

end;

и затем объявлен тип MAPPING так, как мы ранее объявляли тип LIST (элементов типа elementtype), и в соответствии с той реализацией списков, которую мы выбрали. В листинге 2.13 приведены листинги трех операторов отображения, записанные через операторы списков типа LIST.

Листинг 2.13. Реализация отображения посредством списков

procedure MAKENULL { var М: MAPPING );

{ точно такая же, как и для списков }

procedure ASSING ( var М: MAPPING; d: domaintype; г: rangetype ) ; var

x: elementtype; { пара (d, r) }

p: position; { используется для перехода по списку М } begin

X. domain := d;

X. range:= г;

p: = FIRST (М) ;

whill p <> END(M) do

if RETRIEVE (p, M) .domain = d then DELETE (p, M)

{удаляется элемент со значением d в поле domain)

else

р:= NEXT(p, М) ; INSERT(x, FIRST(M), М)

{ пара (d, г) помещена в начало списка } end; { ASSIGN }

function COMPUTE { var M: MAPPING;

d: domaintype; var r: rangetype ): boolean;

p: position;





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 [18] 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0026