Навигация
Главная
Поиск
Форум
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
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 65104
Модуль Forms 64884
Пример работы с... 63348
ТЕХНОЛОГИИ ДОСТ... 61582
Имитационное мо... 57446
Реклама
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

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

Моделирование станции технического обслуживания на GPSS + Отчет
Меры близости на векторах в Delphi + Блок схемы
База данных студентов на Delphi + Microsoft SQL Server

Реклама



Подписывайся на 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 October 18 2009 18:21:07 · 0 Комментариев · 10849 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Задача о 8ми ладьях
База данных фильм...
Delphi 2005. Разр...
Crypt32
Battle.Net - мони...
Proeffectimage
AJAX и PHP. разра...
Архив значков
Scrrlcaptoin
Text3D
Matrix2D
PHP 5. Полное рук...
Prolog Interprete...
Шаблон для новост...
PHP: обучение на ...
DS_Group
WinPopup
Самоучитель C++
Удаление своего EXE
PRNDbgrid

Топ загрузок
Приложение Клие... 100466
Delphi 7 Enterp... 86645
Converter AMR<-... 20077
GPSS World Stud... 12670
Borland C++Buil... 11760
Borland Delphi ... 8558
Turbo Pascal fo... 7037
Visual Studio 2... 4998
Калькулятор [Ис... 4760
FreeSMS v1.3.1 3541
Случайные статьи
Результаты работы ...
Следует определить...
Окно «Параметры Wo...
Вычисление простог...
Если поискать в Ин...
Гарантирует, что п...
File not open for ...
Структура коллекци...
ОПИСАНИЕ ПРЕДМЕТНО...
Промежуточный вари...
Специальные встрое...
Особенности MediaP...
Как работает опера...
Каковы параметры с...
Виртуализация внеш...
Организация информ...
Программирование: ...
Явная загрузка мод...
Microsoft Internet...
Испытание имитацио...
Процедура ClearVie...
Что подразумевает ...
придется задавать ...
ПАМЯТИ В GPSS
• Инициализация во...
Статистика



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


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