ГоловнаЗворотній зв'язок

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

ТЕМА 2

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

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

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

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

В математике список представляет собой последовательность элементов определенного типа, который в общем случае будем обозначать как elementtype (тип элемента). Мы будем часто представлять список в виде последовательности элементов, разделенных запятыми: a1, а2, ..., аn, где n≥  0 и всё ai имеют тип elementtype. Количество элементов п будем называть длиной списка. Если п  1, то а1  называется первым элементом, а аnпоследним элементом списка. В случае  n = 0 имеем пустой список, который не содержит элементов.

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

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

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

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

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

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

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

4.    DELETE(p, L). Этот оператор удаляет элемент в позиции расписка L. Так, если список L состоит из элементов a1, а2, ..., аn, то после выполнения этого оператора он будет иметь вид а1, а2, .... ap-1, ap+1, ..., аn. Результат не определен, если в списке L нет позиции р или р = END(L).

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

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

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

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

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

type

elementtype = record

acctno:   integer;

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

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

end

Теперь можно задать, чтобы функция sате (х, у) принимала значение true всякий раз, когда

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

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

 

Листинг 2.1.

 

procedure PURGE ( var L: LIST );

var

p, q: position; { p — "текущая" позиция в списке L,

g перемещается вперед от позиции р }

begin

(1)                     р:= FIRST(L);

(2)                     while р <> END(L)   do begin

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

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

(5)                                             if same (RETRIEVE (p, L),  RETRIEVE(q, L))  then

(6)                                                                    DELETE (q, L)

else

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

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

end

end;   {   PURGE  }

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

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

Необходимо сделать замечание о внутреннем цикле, состоящем из строк (4) - (8) листинга 2.1. При удалении элемента в позиции q, строка (6), элементы в позициях q + 1, q + 2, ... и т.д. переходят на одну позицию влево. Иногда может случиться, что q является последней позицией в списке, тогда после удаления элемента позиция q становится равной END(L). Если теперь мы выполним оператор в строке (7), NEXT(END(L), L), то получим неопределенный результат. Но такая ситуация невозможна, так как между очередными проверками q <> END(L) в строке (4) может выполниться или строка (6), или строка (7), но не обе сразу.

 

17