Структуры данных и алгоритмы (1021739), страница 17
Текст из файла (страница 17)
Проблема заключается в том, что только по формальному признаку взаимного расположения указателей Q.rear и Q.front нельзя сказать, когдаочередь пуста, а когда заполнила весь массив. (Конечно, можно ввести специальнуюпеременную, которая будет принимать значение true тогда и только тогда, когда очередь пуста, но если мы не собираемся вводить такую переменную, то необходимопредусмотреть иные средства, предотвращающие переполнение массива.)1Отметим, что "последовательность" (непрерывность) позиций здесь понимается как"циклическая непрерывность".
Например, очередь из четырех элементов может последователь•но занимать две последние и две первые ячейки массива.64ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХmaxlengthQ.rearQ. frontочередь^Рис. 2.11, Реализация очереди посредством циклического массиваЧтобы разобраться в этой проблеме, предположим, что очередь состоит из maxlengthэлементов (рис. 2.11), т.е. полностью заполнила массив. Тогда указатель Q.rear указывает на позицию рядом с Q.front, но находящуюся против часовой стрелки. Что будет,если очередь пуста? Чтобы увидеть представление пустой очереди, сначала положим,что очередь состоит из одного элемента.
Тогда указатели Q.rear и Q.front указывают наодну и ту же позицию. Если мы удалим из очереди этот элемент, то указатель Q.frontпереместится на одну позицию по часовой стрелке, оформляя пустую очередь. Такимобразом, в случае пустой очереди указатель Q.rear указывает на позицию рядом сQ.front, находящуюся против часовой стрелки, т.е. точно так же, как и при полном заполнении массива. Отсюда следует вывод, что без введения каких-либо механизмов определения пустых очередей при максимальной длине массива maxlength мы не можемпозволить очереди иметь более maxlength - 1 элементов.Теперь представим пять команд, выполняемых над очередями, использующимиописанную реализацию.
Формально очереди здесь определяются следующим образом:typeQUEUE = recordelements: array[1..maxlength] of elementtype;front, rear: integerend;Соответствующие процедуры показаны в листинге 2.11. Функция addone(i) добавляет единицу к позиции i в "циклическом" смысле.Листинг 2.11. Реализация очередей с помощью циклических массивовfunction addone ( i: integer ) : integer;beginreturn((i mod maxlengtn) + 1)end; { addone }procedure MAKENULL ( var Q: QUEUE ) ;beginQ.front:= 1;Q.rear:= maxlengtftend; { MAKENULL }function EMPTY ( var Q: QUEUE ) : boolean;beginif addone(Q.rear) = Q.front then2.4. ОЧЕРЕДИ65return(true)elsereturn(false)end; { EMPTY }function FRONT ( var Q: QUEUE ): elementtype;beginif EMPTY(Q) thenerror('Очередь пустая')elsereturn (Q.
elements!Q. front])end; { FRONT }procedure ENQUEUE ( x: elementtype; var Q: QUEUE );beginif addone(addone(Q.rear)) = Q.front thenerror('Очередь полная')else beginQ.rear:= addone(Q.rear);Q.elements[Q.rear]:= xendend; { ENQUEUE }procedure DEQUEUE( var Q: QUEUE );beginif EMPTY(Q) thenerror('Очередь пустая')elseQ.front:= addone(Q.front)end; { DEQUEUE }2.5. ОтображенияОтображение — это функция, определенная на множестве элементов (области определения) одного типа (будем обозначать его domaintype — тип области определенияфункции) и принимающая значения из множества элементов (области значений) другого типа, этот тип обозначим rangetype — тип области значений (конечно, типыdomaintype и rangetype могут совпадать).
Тот факт, что отображение М ставит в соответствие элемент d типа domaintype из области определения элементу г типа rangetype из области значений, будем записывать как M(d) = г.Некоторые отображения, подобные square(i) = i2, легко реализовать с помощьюфункций и арифметических выражений языка Pascal. Но для многих отображенийнет очевидных способов реализации, кроме хранения для каждого d значения M(d).Например, для реализации функции, ставящей в соответствие работникам их недельную зарплату, требуется хранить текущий заработок каждого работника.
В конце этого раздела мы опишем методы реализации таких функций.Рассмотрим операторы, которые можно выполнить над отображением М. Например, по заданному элементу d типа domaintype мы хотим получить M(d) или узнать,определено ли M(d) (т.е. узнать, принадлежит ли элемент d области определения М).Или хотим добавить новые элементы в текущую область определения М и поставитьим в соответствие элементы из области значений. Очевидна также необходимостьиметь оператор, который изменял бы значение M(d).
Кроме того, нужно средство"обнуления" отображения, переводящее любое отображение в пустое отображение,66ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХт.е. такое, у которого область определения пуста. Наши пожелания можно обобщитьв следующие три команды.1.2.3.MAKENULL(M). Делает отображение М пустым.ASSIGN(M, d, r). Делает M(d) равным г независимо от того, как M(d) было определено ранее.COMPUTE(M, d, r). Возвращает значение true и присваивает переменной г значение M(d), если последнее определено, и возвращает false в противном случае.Реализация отображений посредством массивовВо многих случаях тип элементов области определения отображения являетсяпростым типом, который можно использовать как тип индексов массивов. В языкеPascal типы индексов включают все конечные интервалы целых чисел, например1..100 или 17..23, строковый тип, диапазоны символов, подобные 'A'...'Z", и нечисловые типы, например север, восток, юг, запад.
В частности, в программах кодирования можно применить отображение crypt (шифратор) с множеством 'A'...'Z' и в качестве области определения, и в качестве области значений, так что сгур1(текст) будеткодом текста текст.Такие отображения просто реализовать с помощью массивов, предполагая, чтонекоторые значения типа rangetype могут иметь статус "неопределен". Например,для отображения crypt, описанного выше, область значений можно определить иначе, чем 'A'...'Z\ и использовать символ '?' для обозначения "неопределен".Предположим, что элементы области определения и области значений имеютсоответственно типы domaintype и rangetype и что тип domaintype является базовым типом языка Pascal.
Тогда тип MAPPING (Отображение) можно объявить следующим образом:typeMAPPING = array[domaintype] of rangetype;Предполагая, что "неопределен" — это константа типа rangetype и что константыfirstvalue и lastvalue равны первому и последнему элементу области определения1,можно реализовать три перечисленных выше оператора, выполняемых над отображениями, как показано в листинге 2.12.•' ,. ' •'•'::•'';•: :••>":..• : •.:><••' .
>•* •'•>< > : : ; ' :: ' ' "": • ' . ; . : • ; - .'<• • /•,"'"••': .Г-™"Листинг 2.12. Реализация операторов отображений посредством массива:' •'procedure MAKENULL ( var M: MAPPING ) ;vari: domaintype;beginfor i:= firstvalue to lastvalue doM[i]:= неопределенend; { MAKENULL }procedure ASSIGN ( var M: MAPPING; d: domaintype; r: rangetype);beginM[d] := rend; { ASSIGN }function COMPUTE ( var M: MAPPING;d: domaintype; r: rangetype): boolean;begin1Например, firstvalue = 'А и lastvalue = 'Z', если область определения совпадает с множеством 'A'..'Z".2.5.
ОТОБРАЖЕНИЯ67end;if M[d]:= неопределен thenreturn(false)else beginr:= M[d] ;return(true)end{ COMPUTE }Реализация отображений посредством списковСуществует много реализаций отображений с конечной областью определения.Например, во многих ситуациях отличным выбором будут хэш-таблицы, которые мырассмотрим в главе 4. Другие отображения с конечной областью определения можнопредставить в виде списка пар (dlt rx), (dz, r2), ..., (dk, rt), где d t , d2d» •— все текущие элементы области определения, a rlt r2, ..., rk — значения, ассоциированные сrf; (t = 1, 2, ..., k). Далее можно использовать любую реализацию списков.Абстрактный тип данных MAPPING можно реализовать как список типа elementtype, если сделано объявлениеtypeelementtype = recorddoma in: doma int yperange: rangetypeend;и затем объявлен тип MAPPING так, как мы ранее объявляли тип LIST (элементовтипа elementtype), и в соответствии с той реализацией списков, которую мы выбрали.В листинге 2.13 приведены листинги трех операторов отображения, записанные через операторы списков типа LIST.Листинг 2.13.
Реализация отображения посредством списковprocedure MAKENULL ( var M: MAPPING );{ точно такая же, как и для списков }procedure ASSING ( var M: MAPPING; d: domaintype,- r: rangetype );varx: elementtype; { пара (d, r) }p: position; { используется для перехода по списку М }beginx.domain:= d;х.range:= r;p:= FIRST(M) ;whill p <> END(W) doif RETRIEVE(p, M) .domain = d thenDELETE (p, M){удаляется элемент со значением d в поле domain}elseр:= NEXT(p, M) ;INSERT(x, FIRST(M), M){ пара (d, r) помещена в начало списка }end; { ASSIGN }function COMPUTE ( var M: MAPPING;d: domaintype; var r: rangetype ): boolean;varp: position;68ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХbeginp:= FIRST(M) ;whill p <> END (Af) do beginif RETRIEVE(p, M) .domain = d then beginr:= RETRIEVE (p, Af) .range;return(true)end;p:= NEXT(p, M)end;return(false) { d не принадлежит области определения }end; { COMPUTE }1'• .
• • - • . . .2.6. Стеки и рекурсивные процедурыСтеки находят важное применение при реализации рекурсивных процедур в языкахпрограммирования. Организация выполнения процедур в языках программирования состоит в задании структур данных, которые используются для хранения значений программных переменных во время выполнения программы. Все языки программирования, допускающие рекурсивные процедуры, используют стеки активационных записейдля хранения всех значений переменных, принадлежащих каждой активной процедуре. При вызове процедуры Р новая активационная запись для этой процедуры помещается в стек независимо от того, есть ли в стеке другие активационные записи для процедуры Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
