6.5. Упражнения 265

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

C-6.12

C-6.13

C-6.14

C-6.15

C-6.16

C-6.17

C-6.18

C-6.19

C-6.20

Опишите структуру и псевдокодекс для основанного на множестве внедрения вектора ADT, который достигает O (1) время для вставок и удалений в индексе 0, а также вставок и удалений в конце вектора. Ваше внедрение должно также предусмотреть постоянное время elemAtRank функция. Опишите эффективный способ поместить вектор, представляющий палубу n карт в случайный заказ. Вы можете использовать функцию, randomInteger (n), который

возвращает случайное число между 0 и n- 1, включительно. Ваш метод

должен гарантировать, что каждый возможный заказ одинаково вероятен. Что

продолжительность Вашей функции? Проектируйте круглый список узла ADT, который резюмирует циркулярный связанный список таким же образом, что список узла ADT резюмирует вдвойне связанный список. Множество редко, если большинство его записей ПУСТОЕ. Список L может использоваться, чтобы осуществить такое множество, A, эффективно. В частности для каждой непустой клетки [я] мы можем сохранить вход (я, e) в L, где e - элемент, сохраненный во [мне]. Этот подход позволяет нам представлять использование O (m) хранение, где m - число непустых записей в A. Опишите и проанализируйте эффективные способы выполнить функции вектора ADT на таком представлении.

Покажите, что только n- 1 проход необходим в выполнении вида пузыря на

последовательность с n элементами.

Дайте псевдокодовое описание внедрения алгоритма вида пузыря, который использует только два стека и, самое большее, пять дополнительных переменных, чтобы сортировать коллекцию объектов, хранивших первоначально в одном из стеков. Вы можете воздействовать на стеки, используя только функции стека ADT. Заключительная продукция должна быть одним из стеков, содержащих все элементы так, чтобы последовательность популярных операций перечислила бы элементы в заказе. Полезная операция в базах данных - естественное соединение. Если мы рассматриваем базу данных как список приказанных пар объектов, то естественное соединение баз данных A и B - список всех заказанных, утраивается (x, y, z) таким образом, что пара (x, y) находится в A, и пара (y, z) находится в B. Опишите и проанализируйте эффективный алгоритм для вычисления естественного соединения списка A n пар и списка B m пар. Когда Боб хочет послать Элис сообщение M в Интернете, он ломает M в n пакеты данных, нумерует пакеты последовательно и вводит их в сеть. Когда пакеты достигают компьютера Элис, они не могут работать, таким образом, Элис должна собрать последовательность n пакетов в заказе, прежде чем она сможет быть уверена, что у нее есть все сообщение. Опишите эффективную схему Элис сделать это. Какова продолжительность этого алгоритма?

Учитывая список L n положительных целых чисел, каждый представленный с k =⌈log n ⌉ + 1

биты, опишите O (n) разовая функция для нахождения целого числа k-долота не в L.

266

Глава 6. Список и Iterator ADTs C-6.21 Обсуждают, почему любое решение предыдущей проблемы должно управлять вW (n) временем. C-6.22 Учитывая список L n произвольных целых чисел, проектируйте O (n) разовая функция для

нахождение целого числа, которое не может быть сформировано как сумма двух целых чисел в L.

Проекты

P-6.1 Осуществите вектор ADT посредством растяжимого множества, используемого в a

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

P-6.2 Осуществите вектор ADT использование вдвойне связанного списка. Покажите experimen-

счет, что это внедрение хуже, чем основанный на множестве подход.

P-6.3 Напишите простому редактору текста, который хранит ряд знаков, использующих список

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

• оставленный: Двиньтесь курсор оставил один характер (или ничто если вначале)

• право: Двиньтесь курсор исправляют один характер (или ничего не сделайте если в конце),

• удалите: Удалите характер направо от курсора (или ничего не сделайте

если в конце)

• вставка c: Вставьте характер c сразу после курсора

P-6.4 Осуществите последовательность ADT посредством растяжимого множества, используемого в a

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

P-6.5 Осуществите последовательность ADT посредством отдельно связанного списка. P-6.6 Напишите полный класс адаптера, который осуществляет последовательность использование ADT

векторный объект STL.

Примечания к главе

Последовательности и iterators - распространяющиеся понятия в C ++ Standard Template Library (STL) [81], и они играют фундаментальные роли в JDSL, библиотеку структур данных в Яве. Для получения дополнительной информации о векторе STL и классах списка, см. книги Страустрапа [91], Липпман и Лэджои [67], и Musser и Saini [81]. ADT списка был предложен несколькими авторами, включая Aho, Хопкрофта и Ульмана [5], кто вводит абстракцию «положения» и Вуда [104], кто определяет список ADT, подобный нашему. Внедрения последовательностей через площадь - лучи и связанные списки обсуждены в оригинальной книге Нута, Фундаментальные Алгоритмы [56]. Сопутствующий объем Нута, Сортируя и Ища [57], описывает функцию вида пузыря и историю этого и других алгоритмов сортировки.

Глава

7

Деревья

Содержание

7.1

Общие деревья...................

.

.

.

268

7.1.1 Определения дерева и свойства........

.

.

..

269

7.1.2 Функции дерева.................

.

.

..

272

7.1.3 C ++ интерфейс дерева.............

.

.

..

273

7.1.4 Связанная структура для общих деревьев.....

.

.

..

274

7.2 Алгоритмы пересечения дерева.............

.

.

.

275

7.2.1 Глубина и высота...............

.

.

..

275

7.2.2 Пересечение перед заказом...............

.

.

..

278

7.2.3 Пересечение постзаказа..............

.

.

..

281

7.3 Двоичные деревья....................

.

.

.

284

7.3.1 Двоичное дерево ADT.............

.

.

..

285

7.3.2 C ++ интерфейс двоичного дерева.........

.

.

..

286

7.3.3 Свойства двоичных деревьев..........

.

.

..

287

7.3.4 Связанная структура для двоичных деревьев.....

.

.

..

289

7.3.5 Основанная на векторе структура для двоичных деревьев..

.

.

..

295

7.3.6 Пересечения двоичного дерева..........

.

.

..

297

7.3.7 Образец функции шаблона.......

.

.

..

303

7.3.8 Представление общих деревьев с двоичными деревьями

.

.

..

309

7.4 Упражнения......................

.

.

.

310