|
|
|
|
|
|
|
|
|
|
|
|
|
они делают (восстанавливает в массиве признак пирамидальности, вероятно, нарушенного на одном из его концов). Выполняя разработку на хорошем уровне, мы один раз формируем черные ящики, а потом используем их для компоновки двух различных систем.
Абстрактные типы данных. Реализованные в языках программирования типы данных с некоторыми ограничениями абстрактно определены с помощью математических объектов и операций над этими объектами (пользователю не требуется знать, как они реализованы); "Словари" в разд. 11.3 и очереди с приоритетами в этой главе можно отнести к подобным типам данных:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Математическая Целое число модель
|
|
|
|
|
|
|
|
|
|
Операции Присваивание, Начальная очистка,
суммирование Insert (вставка) и т. д.
ExtractMin (удаление минимального элемента)
|
Начальная очистка, Insert, Member (проверка принадлежности)
PrintlnOrder (распечатка в заданном порядке
|
|
|
|
|
|
|
|
|
Максимальный Максимальный размер н минимальный множества размеры Размер элементов
|
Максимальный размер
множества
Размер элементов
|
|
|
|
|
|
|
|
|
Дополнение до числа 2, десятичные числа со знаком
|
Упорядоченный массив, пирамида
|
Битовый вектор, "карманы", массивы, деревья
|
|
|
|
|
|
|
|
Некоторые современные языки программирования позволяют программистам определить свои собственные типы данных, такие, как очереди с приоритетами. В последующих командах можно объявить, что переменная имеет тип "очередь с приоритетом"; программа будет воспринимать только эту абстракцию и может ничего не знать о ее реализации. Прог рамма такого типа приведена в решении задачи 10; описанная дисципли на программирования упрощает повторное использование программно го обеспечения.
|
|
|
|
|
|
|
|
12.6. ЗАДАЧИ
1. Модифицируйте процедуру SiftDown так, чтобы она имела следук щую спецификацию:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
