yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 2.1.1. Реализация очередей с помощью циклических массивов

Алгоритмы структуры данных

Листинг 2.1.1. Реализация очередей с помощью циклических массивов

function addone   (   і:   integer  ):   integer;

begin

return((i mod maxlength)   +  1)

end;   {   addone  }

 

procedure MAKENULL   (  var Q:   QUEUE   );

begin

Q.front:=   1;

Q.rear:= maxlength

end;   {  MAKENULL  }

 

function EMPTY   (  var Q:   QUEUE   ):   boolean;

begin

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

return(true)

else

return(false)

end; { EMPTY }

 

function FRONT ( var Q: QUEUE ): elementtype;

begin

if EMPTY(Q) then

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

else

return(Q.elements[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:= addone(Q.rear);

Q.elements[Q.rear]:= x

end

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) = r.

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

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

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

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

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

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

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

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

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

type

MAPPING = array!domaintype]   of  rangetype;

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

 

 

26