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

ГЛАВА 2

Основные абстрактные тины данных

в этой главе мы изучим некоторые из наиболее общих абстрактных типов данных (АТД). Мы рассмотрим списки (последовательности элементов) и два специальных случая списков: стеки, где элементы вставляются и удаляются только на одном конце списка, и очереди, когда элементы добавляются на одном конце списка, а удаляются на другом. Мы также кратко рассмотрим отображения - АТД, которые ведут себя как функции. Для каждого из этих АТД разберем примеры их реализации и сравним по нескольким критериям.

2.1. Абстрактный тип данных ,,Список"

Списки являются чрезвычайно гибкой структурой, так как их легко сделать большими или меньшими, и их элементы доступны для вставки или удаления в любой позиции списка. Списки также можно объединять или разбивать на меньшие списки. Списки регулярно используются в приложениях, например в программах информационного поиска, трансляторах программных языков или при моделировании различных процессов. Методы управления памятью, которые мы обсудим в главе 12, широко используют технику обработки списков. В этом разделе будут описаны основные операции, выполняемые над списками, а далее мы представим структуры данных для списков, которые эффективно поддерживают различные подмножества таких операций.

В математике список представляет собой последовательность элементов определенного типа, который в общем случае будем обозначать как elementtype (тип элемента). Мы будем часто представлять список в виде последовательности элементов, разделенных запятыми: ai, аг, а„, где и > О и все а; имеют тип elementtype. Количество элементов п будем называть длиной списка. Если и > 1, то ai называется первым элементом, а а„ - последним элементом списка. В случае п = О имеем пустой список, который не содержит элементов.

Важное свойство списка заключается в том, что его элементы можно линейно упорядочить в соответствии с их позицией в списке. Мы говорим, что элемент а, предшествует a,+i для i = 1,2, п - 1 и а; следует за для i = 2, 3, п. Мы также будем говорить, что элемент а,- имеет позицию i. Кроме того, мы постулируем существование позиции, следующей за последним элементом списка. Функция END(I,) будет возвращать позицию, следующую за позицией п в п-элементном списке L. Отметим, что позиция END(I,), рассматриваемая как расстояние от начала списка, может изменяться при увеличении или уменьшении списка, в то время как другие позиции имеют фиксированное (неизменное) расстояние от начала списка.

Для формирования абстрактного типа данных на основе математического определения списка мы должны задать множество операторов, выполняемых над объекта-



ми типа LIST (Список). Однако не существует одного множества операторов, выполняемых над списками, удовлетворяющего сразу все возможные приложения. (Это ут-вервдение справедливо и для многих других АТД, рассматриваемых в этой книге.) В этом разделе мы предложим одно множество операторов, а в следующем рассмотрим несколько структур для представления списков и напишем соответствующие процедуры для реализации типовьгх операторов, выполняемых над списками, в терминах этих структур данных.

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

Теперь перейдем к непосредственному определению множества операторов списка. Примем обозначения: L - список объектов типа elementtype, х - объект этого типа, р - позиция элемента в списке. Отметим, что "позиция" имеет другой тип данных, чья реализация может быть различной для разных реализаций списков. Обьино мы понимаем позиции как множество целых положительньгх чисел, но на практике могут встретиться другие представления.

1. INSERT(jc,L). Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позициир и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов Дь аг, ...,а„, то после выполнения этого оператора он будет иметь вид а, а, ap-i, х, ар, а„. Если р принимает значение END(L), то будем иметь а, аг, а„, ж. Если в списке L нет позиции р, то результат выполнения этого оператора не определен.

2. LOCATE(x, L). Эта функция возвращает позицию объекта х в списке L. Если в списке объект ж встречается несколько раз, то возвращается позиция первого от начала списка объекта ж. Если объекта ж нет в списке L, то возвращается END(L).

3. RETRIEVE(p, L). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определен, если р - END(L) или в списке L нет позиции р. Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

4. DELETE(p, L). Этот оператор удаляет элемент в позиции р списка L. Так, если

список L состоит из элементов а, аг.....а„, то после выполнения этого оператора

он будет иметь вид aj, aj, > a-i, a+i, ...,a„. Результат не определен, если в списке L нет позиции р или р = END(I,).

5. NEXT(p, L) и PREVIOUS(p, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р - последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда р = END(L). Функция PREVIOUS не определена, еслир = \. Обе функции не определены, если в списке L нет позиции р.

6. MAKENULL(L). Эта функция делает список L пустым и возвращает позицию END(L).

Строго говоря, тип объекта определен словами "список элементов типа elementtype". Однако мы предполагаем, что реализация списка не зависит от того, что подразумевается под "elementtype", - именно это обстоятельство объясняет то особое внимание, которое мы уделяем концепции списков. Поэтому мы будем использовать термин "тип LIST", а не "список элементов типа elementtype", и в таком же значении будем трактовать другие АТД, зависящие от типов элементов.



7. FIRST(L). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

8. PRINTLIST(L). Печатает элементы списка L в порядке из расположения.

Пример 2.1. Используя описанные выще операторы, создадим процедуру PURGE (Очистка), которая в качестве аргумента использует список и удаляет из него повторяющиеся элементы. Элементы списка имеют тип elementtype, а список таких элементов имеет тип LIST (данного соглащения мы будем придерживаться на протяжении всей этой главы). Определим функцию same(x, у), где х и у имеют тип elementtype, которая принимает значение true (истина), если х п у "одинаковые" (same), и значение false (ложь) в противном случае. Понятие "одинаковые", очевидно, требует пояснения. Если тип elementtype, например, совпадает с типом действительных чисел, то мы можем положить, что функция same{,x, у) будет иметь значение true тогда и только тогда, когда х - у. Но если тип elementtype является типом записи, содержащей поля почтового индекса {acctno), имени (пате) и адреса абонента (address), этот тип можно объявить следующим образом:

type

elementtype = record acctno: integer;

name: packed array [1..20] of char; address: packed array [1..50] of char;

Теперь можно задать, чтобы функция same(x, у) принимала значение true всякий раз, когда jc.acctno = у.acctno.

В листинге 2.1 представлен код процедуры PURGE. Переменные ряд используются для хранения двух позиций в списке. В процессе выполнения программы слева от позиции р все элементы уже не имеют дублирующих своих копий в списке. В каждой итерации цикла (2) - (8) переменная q используется для просмотра элементов, находящихся в позициях, следующих за позицией р, и удаления дубликатов элемента, располагающегося в позиции р. Затем р перемещается в следующую позицию и процесс продолжается.

Листинг 2.1. Программа удаления совпадающих элементов

procedure PURGE { var Ь: LIST ); var

p, q: position; { p - "текущая" позиция в списке L, q перемещается вперед от позждии р }

begin

(1) р:= FIRST (X) ;

(2) while р о END(b) do begin

(3) q:= NEXT(p, L) ;

(4) while q <> END (L) do

(5) if sme (RETRIEVE fp, L), RETRIEVE (g, L}) then

(6) DELETE (g, L) else

(7) g:= NEXT(g, L) ;

(8) p:= NEXT(p, L)

end; { PURGE }

В следующем разделе мы покажем объявления типов LIST и position (позиция) и реализацию соответствующих операторов, так что PURGE станет вполне работающей про-

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





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.0037