Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Реклама
Сейчас на сайте
Гостей: 2
На сайте нет зарегистрированных пользователей

Пользователей: 13,139
новичок: atlantix
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Программа тестирования и обучающая программа по математике на Turbo Pasc...
Моделирование автовокзала + Отчет + Блок схема
Поиск пути в графе заданном списками инцедентности на Turbo Pascal

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Очереди с приоритетом
Каждый элемент в очереди с приоритетом (priority queue) имеет определен-
ный приоритет. Когда программа должна удалить элемент из очереди, она выби-
рает элемент с самым высоким приоритетом. При этом не имеет значения, в каком
порядке элементы хранятся в очереди, так как программа всегда может найти эле-
мент с самым высоким приоритетом.
Некоторые операционные системы используют очереди с приоритетом для
планирования задания. В операционной системе UNIX все процессы имеют раз-
ные приоритеты. Когда процессор освобождается, выбирается готовый к исполне-
нию процесс с максимальным приоритетом. Процессы с меньшим приоритетом
должны ждать завершения или блокировки (например, внешнего события, такого
как чтение данных с диска) процессов с более высокими приоритетами.
Концепция очередей с приоритетами также используется при управлении
авиаперевозками. Самолеты, идущие на посадку из-за отсутствия топлива, име-
ют высший приоритет. Второй приоритет присваивается самолетам, заходящим
на посадку. Самолеты на земле имеют третий приоритет, потому что они нахо-
дятся в более безопасном положении, чем самолеты в воздухе. Через какое-то вре-
мя некоторые приоритеты могут измениться, так как у самолетов, которые пыта-
ются приземлиться, может кончится топливо.
Простой способ организации очереди с приоритетами - поместить всё элемен-
ты в список. Если требуется удалить элемент из очереди, надо найти в списке эле-
мент с наивысшем приоритетом. При использовании этого метода новый элемент
добавляется в очередь всего за один шаг. Чтобы добавить элемент к очереди, вы
размещаете новый элемент в начале списка. Если очередь содержит N элементов,
требуется O(N) шагов, чтобы определить положение и удалить из очереди элемент
с максимальным приоритетом.
Немного удобнее использовать связанный список и хранить элементы, распо-
лагая их в порядке уменьшения приоритета. Тип данных списка TPriorityCell
можно определить следующим образом:
type
String10 = String[10];
PPriorityQCell = ^TPriorityQCell;
TPriorityQCell = record
Value : StringlO;
Priority : Longint;
NextCell : PPriorityQCell;
end;



Чтобы добавить элемент в очередь, необходимо найти для него правильную по-
зицию в списке и поместить его туда. Упростить поиск положения элемента можно
с помощью меток в начале и конце списка, присвоив им соответствующие приори-
теты. Например, если элементы имеют приоритеты от 0 до 100, можно присвоить
метке начала приоритет 101, а метке конца - приоритет -1. Любые приоритеты
реальных элементов будут находиться между этими значениями.
На рис. 3.8 показана очередь с приоритетами, реализованная с помощью свя-
занного списка.
Очередь с приоритетами на основе связанного списка
Рис. 3.8. Очередь с приоритетами на основе связанного списка
В следующем фрагменте кода приведена основа подпрограммы поиска:
var
new_cell, cell_ptr, next_cell : PPriorityQCell;
begin
// Определение места для нового элемента.
Cell_ptr := @TopSentinel;
next_cell := cell_ptr^.NextCell;
while (next_cell^.Priority>new_priority) do
begin
cell_ptr := next_cell;
next_cell := cell_ptr^.NextCell;
end;
// Вставка новой ячейки.
cell_ptr^.NextCell := new_cell;
new_cell^.NextCell := next_cell;



Чтобы удалить из списка .элемент с самым высоким приоритетом, достаточно
удалить элемент после метки начала. Поскольку список отсортирован в порядке
уменьшения приоритета, первый элемент всегда имеет наивысший приоритет.
Добавление нового элемента в эту очередь в среднем занимает N/2 шагов. Иног-
да новый элемент оказывается в начале списка, а иногда ближе к концу, но в сред-
нем он будет попадать приблизительно в середину. Предыдущая простая очередь
с приоритетом на основе списка требовала О( 1) шагов для добавления нового эле-
мента в очередь и O(N) шагов для удаления элемента с максимальным приорите-
том. В версии на основе сортированного связанного списка элемент добавляется
за O(N) шагов и за О(1) удаляется верхний элемент. Обеим версиям требуется
O(N) шагов для одной из этих операций, но в случае упорядоченного связанного
списка обычно приходится выполнять только N/2 шагов.
Программа PriorQ использует сортируемый связанный список для обработки
очереди с приоритетом. Вы можете задать приоритет и значение элемента данных
и с помощью кнопки Enter добавить его в очередь. Для удаления из очереди эле-
мента с наивысшим приоритетом щелкните по кнопке Leave.
Немного доработав этот пример, можно сформировать очередь с приоритетом,
где добавление и удаление элементов будут занимать O(logN) шагов. Для очень
больших очередей ускорение работы окупит затраченные усилия. Этот тип очере-
дей с приоритетом использует структуры данных в виде пирамиды, которые так-
же применяются в алгоритмах с древовидной сортировкой.

http://mbl-na-dom.ru/kuhni-zakaz/index.html
Опубликовал Kest Октябрь 18 2009 18:21:07 · 0 Комментариев · 11978 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
32 урока по Delphi
Sztransppanel
PBEditPack
Java в примерах -...
C# в кратком изло...
Фильтры изображений
Импорт новостей ...
Пример работы с р...
Scrrlcaptoin
JanComp
Visual Studio 200...
TsHintManager
3D Тетрис [Исходн...
PDJ Scrollers
EditButton
База игр
Atb
INSTANT BOOSTER v...
Язык программиров...
VFW

Топ загрузок
Приложение Клие... 100634
Delphi 7 Enterp... 94487
Converter AMR<-... 20163
GPSS World Stud... 16357
Borland C++Buil... 13629
Borland Delphi ... 9588
Turbo Pascal fo... 7194
Калькулятор [Ис... 5424
Visual Studio 2... 5093
FreeSMS v1.3.1 3600
Случайные статьи
и режим ядра гаран...
Выбор размеров
Размер фотографий ...
Документы СС/РР
Некоторые фрагмент...
Решение вэтом случ...
На какие устройств...
Компромиссы
Программа cursive ...
Задача о супружеск...
7.8. Быстрые вычис...
Листинг 9.8. Двоич...
Несколько примеров...
Полная пропускная ...
Управление медиафа...
Конструктор Remote...
Типы данных
Процедура GetFillP...
• Контроллеры хран...
Операционная систе...
WQTABLE (ВЗВЕШЕННА...
Приём создания qua...
Дополнение структу...
Добавляем к титлам...
7.1. Словарь в в...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?