Структуры данных и алгоритмы, страница 12

Авторы этой книги в более ранней работе [3] связали временную и емкостную сложности алгоритмов с различными моделями вычислений, такихкак машины Тьюринга и машины с произвольным доступом к памяти. Другие библиографические ссылки на работы, посвященные анализу алгоритмов и программ,приведены в библиографических замечаниях к главе 9.Дополнительный материал о структурном программировании вы найдете в [50],[60], [120] и [125]. Производственные и философские вопросы организации большихпрограммных проектов обсуждаются в работах [15] и [115]. В [61] показано, как создавать полезные программные инструменты для сред программирования.44ГЛАВА 1.

ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВГЛАВА 2,Основныеабстрактныетипы данныхВ этой главе мы изучим некоторые из наиболее общих абстрактных типов данных(АТД). Мы рассмотрим списки (последовательности элементов) и два специальныхслучая списков: стеки, где элементы вставляются и удаляются только на одном конце списка, и очереди, когда элементы добавляются на одном конце списка, а удаляются на другом. Мы также кратко рассмотрим отображения — АТД, которые ведутсебя как функции. Для каждого из этих АТД разберем примеры их реализации исравним по нескольким критериям.2.1. Абстрактный тип данных „Список"Списки являются чрезвычайно гибкой структурой, так как их легко сделатьбольшими или меньшими, и их элементы доступны для вставки или удаления влюбой позиции списка.

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

Методы управления памятью, которые мыобсудим в главе 12, широко используют технику обработки списков. В этом разделе будут описаны основные операции, выполняемые над списками, а далее мыпредставим структуры данных для списков, которые эффективно поддерживаютразличные подмножества таких операций.В математике список представляет собой последовательность элементов определенного типа, который в общем случае будем обозначать как elementtype (тип элемента). Мы будем часто представлять список в виде последовательности элементов,разделенных запятыми: а ь а2, ..., а„, где п > 0 и все а( имеют тип elementtype. Количество элементов п будем называть длиной списка. Если п > 1, то а\ называется первым элементом, а а„ — последним элементом списка.

В случае п = О имеем пустойсписок, который не содержит элементов.Важное свойство списка заключается в том, что его элементы можно линейноупорядочить в соответствии с их позицией в списке. Мы говорим, что элемент а,предшествует ai+i для i = 1, 2, ..., п — 1 и сц следует за a f _j для i = 2, 3, ..., п.Мы также будем говорить, что элемент а,; имеет позицию i. Кроме того, мы постулируем существование позиции, следующей за последним элементом списка.

Функция END(L) будет возвращать позицию, следующую за позицией п вл-элементном списке L. Отметим, что позиция END(L), рассматриваемая какрасстояние от начала списка, может изменяться при увеличении или уменьшении списка, в то время как другие позиции имеют фиксированное (неизменное)расстояние от начала списка.Для формирования абстрактного типа данных на основе математического определения списка мы должны задать множество операторов, выполняемых над объекта-••ми типа LIST1 (Список). Однако не существует одного множества операторов, выполняемых над списками, удовлетворяющего сразу все возможные приложения. (Это утверждение справедливо и для многих других АТД, рассматриваемых в этой книге.) Вэтом разделе мы предложим одно множество операторов, а в следующем рассмотримнесколько структур для представления списков и напишем соответствующие процедуры для реализации типовых операторов, выполняемых над списками, в терминахэтих структур данных.Чтобы показать некоторые общие операторы, выполняемые над списками, предположим, что имеем приложение, содержащее список почтовой рассылки, которыймы хотим очистить от повторяющихся адресов.

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

Отметим, что "позиция" имеет другой тип данных,чья реализация может быть различной для разных реализаций списков. Обычно мыпонимаем позиции как множество целых положительных чисел, но на практике могут встретиться другие представления.1.2.3.4.5.6.INSERT(x, р, L). Этот оператор вставляет объект ж в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию.Таким образом, если список L состоит из элементов аг, а2, .... а„, то после выполнения этого оператора он будет иметь вид oj, а2, ..., ep-i, ж, ар, ..., а„. Если рпринимает значение END(L), то будем иметь а\, az, ..., а„, ж.

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

Так, еслисписок L состоит из элементов а^ а2а„, то после выполнения этого оператораон будет иметь вид а1( «2. •••> «p-i. «p+i> •••» ап- Результат не определен, если всписке L нет позиции р или р = END(L).NEXT(p, L) и PREVIOUSQj, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L.

Если р — последняяпозиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда р = END(L). Функция PREVIOUS не определена, если р = 1. Обе функции неопределены, если в списке L нет позиции р.MAKENULL(L). Эта функция делает список L пустым и возвращает позициюEND(L).1Строго говоря, тип объекта определен словами "список элементов типа elementtype". Однако мы предполагаем, что реализация списка не зависит от того, что подразумевается под"elementtype", — именно это обстоятельство объясняет то особое внимание, которое мы уделяем концепции списков.

Поэтому мы будем использовать термин "тип LIST", а не "список элементов типа elementtype", и в таком же значении будем трактовать другие АТД, зависящие оттипов элементов.46ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ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), имени (name) и адреса абонента(address), этот тип можно объявить следующим образом: .typeelementtype = recordacctno: integer;name: packed array [1..20] of char;address: packed array [1..50] of char;endТеперь можно задать, чтобы функция aame(x, у) принимала значение true всякийраз, когда x.acctno = y.acctno1.В листинге 2.1 представлен код процедуры PURGE.

Переменные р и q используются для хранения двух позиций в списке. В процессе выполнения программы слеваот позиции р все элементы уже не имеют дублирующих своих копий в списке. В каждой итерации цикла (2) - (8) переменная q используется для просмотра элементов,находящихся в позициях, следующих за позицией р, и удаления дубликатов элемента, располагающегося в позиции р. Затем р перемещается в следующую позицию ипроцесс продолжается.Листинг 2.1. Программа удаления совпадающих элементов(1)(2)(3)(4)(5)(6)(7)(8)procedure PURGE ( var L: LIST );varp, q: position; { p — "текущая" позиция в списке Liq перемещается вперед от позиции р }beginр:= FIRST(L);while p <> END(i) do beginq:= NEXT(p, L) ;while q <> END(L) doif same (RETRIEVE (p, L\,. RETRIEVED, L).) thenDELETE(q, L)elseg:= NEXT(g, L) ;p:= NEXTtp, L)endend; { PURGE }В следующем разделе мы покажем объявления типов LIST и position (позиция) и реализацию соответствующих операторов, так что PURGE станет вполне работающей про1Конечно, если мы собираемся использовать эту функцию для удаления совпадающих записей, то в этом случае необходимо проверить также равенство значений полей имени и адреса.2.1.

АБСТРАКТНЫЙ ТИП ДАННЫХ "СПИСОК"47граммой. Как уже указывалось, программа не зависит от способа представления списков,поэтому мы свободны в экспериментировании с различными реализациями списков.Необходимо сделать замечание о внутреннем цикле, состоящем из строк (4) - (8)листинга 2.1. При удалении элемента в позиции q, строка (6), элементы в позициях5 + 1, <? + 2, ... и т.д. переходят на одну позицию влево. Иногда может случиться,что q является последней позицией в списке, тогда после удаления элемента позицияq становится равной END(L). Если теперь мы выполним оператор в строке (7),NEXT(END(L), L), то получим неопределенный результат.