 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Кольцевые полустатические очереди. Операции над кольцевой очередью
|
|
Рис. 2.17
Рассмотрим пример. Предположим, что очередь содержит три элемента - в позициях 3, 4 и 5 пятиэлементного массива. Этот случай, показанный на рис. 2.17. Хотя массив и не заполнен, последний элемент очереди занят.
Если теперь делается попытка поместить в очередь элемент G, то он будет записан в первую позицию массива, как это показано на рис. 2.17. Первый элемент очереди есть Q(3), за которым следуют элементы Q (4), Q(5) и Q(l).
К сожалению, при таком представлении довольно трудно определить, когда очередь пуста. Условие R<F больше не годится для такой проверки, поскольку на рис. 2. 17 показан случай, при котором данное условие выполняется, но очередь при этом не является пустой.
Одним из способов решения этой проблемы является введение соглашения, при котором значение F есть индекс элемента массива, немедленно предшествующего первому элементу очереди, а не индексу самого первого элемента. В этом случае, поскольку R содержит индекс последнего элемента очереди, условие F = R подразумевает, что очередь пуста.
Отметим, что перед началом работы с очередью, в F и R устанавливается значение последнего индекса массива, а не О и 1, поскольку при таком представлении очереди последний
элемент массива немедленно предшествует первому элементу. Поскольку R = F, то очередь изначально пуста.
Основные операции с кольцевой очередью:
1. Вставка элемента q в очередь x
Insert(q,x);
2. Извлечение элемента из очереди x
Remove(q);
3. Проверка очереди на пустоту
Empty(q);
4. Проверка очереди на переполнение
Full(q).
Операция Empty(q)
if F = R
then empty = true
else empty = false
endif
return
Операция Remove(q)
empty (q)
if empty = true
then “пусто”
stop
endif
if F =maxQ
then F =1
else F = F+1
endif
x = q(F)
return
Отметим, что значение F должно быть модифицировано до момента извлечения элемента.
Переполнение очереди происходит в том случае, если весь массив уже занят элементами очереди, и при этом делается попытка разместить в ней еще один элемент.
Исходное состояние очереди
Поместим в очередь элемент G.
Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, то есть это соотношение как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью.
Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема, на единицу меньшего максимального. Предыдущий рисунок иллюстрирует именно это соглашение. Попытка разместить в очереди еще один элемент приведет к переполнению.
Проверка на переполнение в подпрограмме insert производится после установления нового значения для R, в то время как проверка на потерю значимости в подпрограмме remove производится сразу же после входа в подпрограмму до момента обновления значения F.
Подпрограмма Insert(q,x) может быть записана следующим образом:
if R = maxQ
then R = 1
else R = R+1
endif
‘проверка на переполнение’
if R = F
then print «переполнение очереди»
stop
endif
q (R) =x
return
Дек
От английского DEQ - Double Ended Queue (Очередь с
двумя концами)
Особенностью деков является то, что запись и считывание элементов может производиться с двух концов (рис. 2.18).
Рис. 2.18.
Дек можно рассматривать и в виде двух стеков, соединенных нижними границами. Возьмем пример, иллюстрирующий принцип построения дека. Рассмотрим состав на железнодорожной станции. Новые вагоны к составу можно добавлять либо к его концу, либо к началу. Аналогично, чтобы отсоединить от состава вагон, находящийся в середине, нужно сначала отсоединить все вагоны или вначале, или в конце состава, отсоединить нужный вагон, а затем присоединить из снова.
Операции над деками:
Ø Insert(d, x) - вставка элемента.
Ø Remove(d) - извлечение элемента из дека.
Ø Empty(d) - проверка на пустоту.
Ø Full(d) - проверка на переполнение.
10. Понятие Динамических структур данных. Организация односвяз. и двусвяз. списков. Простейшие операции над односвяз списками
До сих пор мы рассматривали только статические программные объекты. Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но также и того, будет ли существовать этот объект или нет. Такого рода программные объекты, которые возникают уже в процессе выполнения программы или размер значений которых определяется при выполнении программы, называются динамическими объектами.
Динамические структуры данных имеют 2 особенности:
1) Заранее не определено количество элементов в структуре.
2) Элементы динамических структур не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.
Чтобы связать элементы динамических структур между собой в состав элементов помимо информационных полей входят поля указателей (рис. 3.1) (связок с другими элементами структуры).
Рис.3.1
P1 и Р2 это указатели, содержащие адреса элементов, с которыми они связаны. Указатели содержат номер слота.
Связные списки
Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки.
В линейных списках связи строго упорядочены: указатель предыдущего элемента содержит адрес последующей элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки. К нелинейным - многосвязные.
Элемент списка в общем случае представляет собой после записи и одного или нескольких указателей.
Дата публикования: 2015-02-03; Прочитано: 370 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
