Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

Dim i As Integer

    ' Переместить записи в начало массива.

    For i = QueueFront To QueueBack - 1

        Queue(i - QueueFront) = Queue(i)

    Next i

    QueueBack = QueueBack - QueuePront

    QueueFront = 0

    ' Изменить размер массива.

    want_free = WANT_FREE_PERCENT * (QueueBack - QueueFront)

    If want_free < MIN_FREE Then want_free = MIN_FREE

    Max = QueueBack + want_free - 1

    ReDim Preserve Queue(0 To Max)

    ' Если QueueFront > ResizeWhen, изменить размер массива.

    ResizeWhen = want_free

End Sub

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

Имейте в виду, что при каждом изменении размера очереди, вначале все используемые элементы перемещаются в начало массива. При этом на изменение размера очередей на основе массива уходит больше времени, чем на изменение размера описанных выше связных списков и стеков.

=======54

Программа ArrayQ2 аналогична программе ArrayQ, но она использует для управления очередью класс ArrayQueue.

Циклические очереди

Очереди, описанные в предыдущем разделе, требуется переупорядочивать время от времени, даже если размер очереди почти не меняется. Даже при неоднократном добавлении и удалении одного элемента будет необходимо переупорядочивать очередь.

Если заранее известно, насколько большой может быть очередь, этого можно избежать, создав циклическую очередь (circular queue). Идея заключается в том, чтобы рассматривать массив очереди как будто он заворачивается, образуя круг. При этом последний элемент массива как бы идет перед первым. На рис. 3.2 изображена циклическая очередь.

Программа может хранить в переменной QueueFront индекс элемента, который дольше всего находится в очереди. Переменная QueueBack может содержать конец очереди, в который добавляется новый элемент.

В отличие от предыдущей реализации, при обновлении значений переменных QueueFront и QueueBack, необходимо использовать оператор Mod для того, чтобы индексы оставались в границах массива. Например, следующий код добавляет элемент к очереди:

Queue(QueueBack) = value

QueueBack = (QueueBack + 1) Mod QueueSize

На рис. 3.3 показан процесс добавления нового элемента к циклической очереди, которая может содержать четыре записи. Элемент C добавляется в конец очереди. Затем конец очереди сдвигается, указывая на следующую запись в массиве.

Таким же образом, когда программа удаляет элемент из очереди, необходимо обновлять указатель на начало очереди при помощи следующего кода:

value = Queue(QueueFront)

QueueFront = (QueueFront + 1) Mod QueueSize

@Рис. 3.2. Циклическая очередь

=======55

@Рис. 3.3. Добавление элемента к циклической очереди

На рис. 3.4 показан процесс удаления элемента из циклической очереди. Первый элемент, в данном случае элемент A, удаляется из начала очереди, и указатель на начало очереди обновляется, указывая на следующий элемент массива.

Для циклических очередей иногда бывает сложно отличить пустую очередь от полной. В обоих случаях значения переменных QueueBottom и QueueTop будут равны. На рис. 3.5 показаны две циклические очереди, пустая и полная.

Простой вариант решения этой проблемы — сохранять число элементов в очереди в отдельной переменной NumInQueue. При помощи этого счетчика можно узнать, остались ли в очереди еще элементы, и осталось ли в очереди место для новых элементов.

@Рис. 3.4. Удаление элемента из циклической очереди

@Рис. 3.5 Полная и пустая циклическая очереди

=========56

Следующий код использует все эти методы для управления циклической очередью:

Queue() As String          ' Массив очереди.

QueueSize As Integer       ' Наибольший индекс в очереди.

QueueFront As Integer      ' Начало очереди.

QueueBack As Integer       ' Конец очереди.

NumInQueue As Integer      ' Число элементов в очереди.

Sub NewCircularQueue(num_items As Integer)

    QueueSize = num_items

    ReDim Queue(0 To QueueSize - 1)

End Sub

Sub EnterQueue(value As String)

    ' Если очередь заполнена, выйти из процедуры.

    ' В настоящем приложении потребуется более сложный код.

    If NumInQueue >= QueueSize Then Exit Sub

    Queue(QueueBack) = value

    QueueBack = (QueueBack + 1) Mod QueueSize

    NumInQueue = NumInQueue + 1

End Sub

Sub LeaveQueue (value As String)

    ' Если очередь пуста, выйти из процедуры.

    ' В настоящем приложении потребуется более сложный код.

    If NumInQueue <= 0 Then Exit Sub

    value = Queue (QueueFront)

    QueueFront = (QueueFront + 1) Mod QueueSize

    NumInQueue = NumInQueue - 1

End Sub

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

Когда изменяется размер массива, конец очереди может не совпадать с концом массива. Если просто увеличить массив, то вставляемые элементы будут находиться в конце массива, так что они попадут в середину списка. На рис. 3.6 показано, что может произойти при таком увеличении массива.

===========57

При уменьшении размера массива возникают похожие проблемы. Если элементы огибают конец массива, то элементы в конце массива, которые будут находиться в начале очереди, будут потеряны.

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

Private Sub EnterQueue(value As String)

    If NumInQueue >= QueueSize Then ResizeQueue

    Queue(QueueBack) = value

    QueueBack = (QueueBack + 1) Mod QueueSize

    NumInQueue = NumInQueue + 1

End Sub

Private Sub LeaveQueue(value As String)

    If NumInQueue <= 0 Then Exit Sub

    value = Queue (QueueFront)

    QueueFront = (QueueFront + 1) Mod QueueSize

    NumInQueue = NumInQueue - 1

    If NumInQueue < ShrinkWhen Then ResizeQueue

End Sub

Sub ResizeQueue()

Dim temp() As String

Dim want_free As Integer

Dim i As Integer

    ' Скопировать элементы во временный массив.

    ReDim temp(0 To NumInQueue - 1)

    For i = 0 To NumInQueue - 1

        temp(i) = Queue((i + QueueFront) Mod QueueSize)

    Next i

    ' Изменить размер массива.

    want_free = WANT_FREE_PERCENT * NumInQueue

    If want_free < MIN_PREE Then want_free = MIN_FREE

    QueueSize = NumInQueue + want_free

    ReDim Queue(0 To QueueSize - 1)

    For i = 0 To NumInQueue - 1

        Queue(i) = temp(i)

    Next i

    QueueFront = 0

    QueueBack = NumInQueue

    ' Уменьшить размер массива, если NunInQueue < ShrinkWhen.

    ShrinkWhen = QueueSize - 2 * want_free

    ' Не менять размер небольших очередей. Это может вызвать

    ' проблемы с "ReDim temp(0 To NumInQueue - 1)" выше и

    ' просто глупо!

    If ShrinkWhen < 3 Then ShrinkWhen = 0

End Sub

Программа CircleQ  демонстрирует этот подход к реализации циклической очереди. Введите строку и нажмите кнопку Enter (Ввести) для добавления нового элемента в очередь. Нажмите на кнопку Leave (Покинуть) для удаления верхнего элемента из очереди. Программа будет при необходимости изменять размер очереди.

Программа CircleQ2 аналогична программе CircleQ, но она использует для работы с очередью класс CircleQueue.

Помните, что при каждом изменении размера очереди в программе, она копирует элементы во временный массив, изменяет размер очереди, а затем копирует элементы обратно. Эти дополнительные шаги делают изменение размера циклических очередей более медленным, чем изменение размера связных списков и стеков. Даже очереди на основе массивов, в которых также требуются дополнительные действия для изменения размера, не требуют такого объема работы.

С другой стороны, если число элементов в очереди не сильно меняется, и если правильно задать параметры изменения размера, может никогда не понадобиться менять размер массива. Даже если иногда это все‑таки придется делать, уменьшение частоты этих изменений стоит дополнительных усилий на программирование.

Очереди на основе связных списков

Совсем другой подход к реализации очередей состоит в использовании двусвязных списков. Для отслеживания начала и конца списка можно использовать сигнальные метки. Новые элементы добавляются в очередь перед меткой в конце очереди, а элементы, следующие за меткой начала очереди, удаляются. На рис. 3.7 показан двусвязный список, который используется в качестве очереди.

===========58-59

Добавлять и удалять элементы из двусвязного списка легко, поэтому в этом случае не потребуется применять сложных алгоритмов для изменения размера. Преимущество этого метода также в том, что он интуитивно понятнее по сравнению с циклической очередью на основе массива. Недостаток его в том, что для указателей связного списка NextCell и PrevCell требуется дополнительная память. В отношении занимаемой памяти очереди на основе связных списков немного менее эффективны, чем циклические списки.

Программа LinkedQ  работает с очередью при помощи двусвязного списка. Введите строку, нажмите на кнопку Enter, чтобы добавить элемент в конец очереди. Нажмите на кнопку Leave для удаления элемента из очереди.

Программа LinkedQ2 аналогична программе LinkedQ, но она использует для управления очередью класс LinkedListqueue.

Применение коллекций в качестве очередей

Коллекции Visual Basic представляют собой очень простую форму очереди. Программа может использовать метод Add коллекции для добавления элемента в конец очереди, и метод Remove с параметром 1 для удаления первого элемента из очереди. Следующий код управляет очередью на основе коллекций:

Dim Queue As New Collection

Private Sub EnterQueue(value As String)

    Queue.Add value

End Sub

Private Function LeaveQueue() As String

    LeaveQueue = Queue.Item(1)

    Queue.Remove 1

Еnd Function

@Рис. 3.7. Очередь на основе связного списка

=======60

Несмотря на то, что этот код очень прост, коллекции в действительности не предназначены для использования в качестве очередей. Они предоставляют дополнительные возможности, такие как ключи элементов, и поддержка этих дополнительных возможностей делает коллекции более медленными, чем другие реализации очередей. Тем не менее, очереди на основе коллекций настолько просты, что они могут быть приемлемым выбором для приложений, в которых производительность не является проблемой.

Программа CollectQ  демонстрирует очередь на основе коллекций.

Приоритетные очереди

Каждый элемент в приоритетной очереди (priority queue) имеет связанный с ним приоритет. Если программе нужно удалить элемент из очереди, она выбирает элемент с наивысшим приоритетом. Как хранятся элементы в приоритетной очереди, не имеет значения, если программа всегда может найти элемент с наивысшим приоритетом.

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

Концепция приоритетных очередей также используется при управлении авиаперевозками. Наивысший приоритет имеют самолеты, у которых кончается топливо во время посадки. Второй приоритет имеют самолеты, заходящие на посадку. Третий приоритет имеют самолеты, находящиеся на земле, так как они находятся в более безопасном положении, чем самолеты в воздухе. Приоритеты изменяются со временем, так как у самолетов, которые пытаются приземлиться, в конце концов, закончится топливо.

Простой способ организации приоритетной очереди — поместить все элементы в список. Если требуется удалить элемент из очереди, можно найти в списке элемент с наивысшем приоритетом. Чтобы добавить элемент в очередь, он помещается в начало списка. При использовании этого метода, для добавления нового элемента в очередь требуется только один шаг. Чтобы найти и удалить элемент с наивысшим приоритетом, требуется O(N) шагов, если очередь содержит N элементов.

Немного лучше была бы схема с использованием связного списка, в котором элементы были бы упорядочены в прямом или обратном порядке. Используемый в списке класс PriorityCell мог бы объявлять переменные следующим образом:

Public Priority As Integer        ' Приоритет элемента.

Public NextCell As PriorityCell   ' Указатель на следующий элемент.

Public Value As String     ' Данные, нужные программе.

Чтобы добавить элемент в очередь, нужно найти его правильное положение в списке и поместить его туда. Чтобы упростить поиск положения элемента, можно использовать сигнальные метки в начале и конце списка, присвоив им соответствующие приоритеты. Например, если элементы имеют приоритеты от 0 до 100, можно присвоить метке начала приоритет 101 и метке конца — приоритет ‑1. Приоритеты всех реальных элементов будут находиться между этими значениями.

На рис. 3.8 показана приоритетная очередь, реализованная на основе связного списка.

=====61

@Рис. 3.8. Приоритетная очередь на основе связного списка

Следующий фрагмент кода показывает ядро этой процедуры поиска:

Dim cell As PriorityCell

Dim nxt As PriorityCell

    ' Найти место элемента в списке.

    cell = TopSentinel

    nxt = cell.NextCell

    Do While cell.Priority > new_priority

        cell = nxt

        nxt = cell.NextCell

    Loop

    ' Вставить элемент после ячейки в списке.

        :

Для удаления из списка элемента с наивысшим приоритетом, просто удаляется элемент после сигнальной метки начала. Так как список отсортирован в порядке приоритетов, первый элемент всегда имеет наивысший приоритет.

Добавление нового элемента в эту очередь занимает в среднем N/2 шагов. Иногда новый элемент будет оказываться в начале списка, иногда ближе к концу, но в среднем он будет оказываться где‑то в середине. Простая очередь на основе списка требовала O(1) шагов для добавления нового элемента и O(N) шагов для удаления элементов с наивысшим приоритетом из очереди. Версия на основе упорядоченного связного списка требует O(N) шагов для добавления элемента и O(1) шагов для удаления верхнего элемента. Обеим версиям требует O(N) шагов для одной из этих операций, но в случае упорядоченного связного списка в среднем требуется только (N/2) шагов.

Программа PriList  использует упорядоченный связный список для работы с приоритетной очередью. Вы можете задать приоритет и значение элемента данных и нажать кнопку Enter для добавления его в приоритетную очередь. Нажмите на кнопку Leave для удаления из очереди элемента с наивысшим приоритетом.

Программа PriList2 аналогична программе PriList, но она использует для управления очередью класс LinkedPriorityQueue.

========63

Затратив еще немного усилий, можно построить приоритетную очередь, в которой добавление и удаление элемента потребуют порядка O(log(N)) шагов. Для очень больших очередей, ускорение работы может стоить этих усилий. Этот тип приоритетных очередей использует структуры данных в виде пирамиды, которые также применяются в алгоритме пирамидальной сортировки. Пирамиды и приоритетные очереди на их основе обсуждаются более подробно в 9 главе.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48