У любой структуры данных есть две стороны. Если смотреть снаружи, спецификация определяет ее функционирование — очередь сохраняет порядок элементов при операциях вставки и извлечения (insert, extract). Реализация определяет то, как это делается — в основе может быть массив или связанный список. Мы начнем изучение очередей с приоритетом с описания их абстрактных свойств, а затем перейдем к реализациям.
Очередь с приоритетом изначально представляет собой нустой набор элементов, который мы обозначим буквой S. Функция insert добавляет в этот набор новый элемент. Ее можно определить с помощью предусловий и постусловий.
void 1nsert(t)
предусловие: |S| < максимального размера постусловие, текущее состояние S = предыдущее состояние S. объединенное с элементом t
Функция извлечения extractmin удаляет наименьший элемент из набора и возвращает его значение в своем единственном параметре t.
1nt ext ractmin()
предусловие |S| > 0
постусловие исходное состояние S = текущее состояние S. объединенное с результатом && результат = miп(исходное состояние S)
Эта функция, конечно же, может быть изменена так, чтобы возвращать и максимальный элемент или какой-либо другой крайний для данной операции порядка.
Мы можем описать класс C++, решающий эту задачу, с помощью шаблона, в котором тип Т элемента очереди может быть произвольным.
Листинг 14.3. Шаблон класса очереди с приоритетом
template <class Т> cl ass pnqueue { publ i с
pnqueue (int maxsize). // инициализация пусГым множеством void insert(T t). // добавление t в очередь S
T extractmin (). // возвращение наименьшего элемента из S
} .
Опубликовал vovan666
April 17 2013 00:04:14 ·
0 Комментариев ·
3419 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
