Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Для того чтобы запрограммировать операцию вставки, должна быть проанализирована ситуация, при которой возникает переполнение. Переполнение происходит в том случае, если весь массив уже занят элементами очереди и при этом делается попытка разместить в ней еще один элемент. Рассмотрим, например, очередь на рис. 2. 17. В ней находятся три элемента — С, D и Е, соответственно расположенные в Q (3), Q (4) и Q (5). Поскольку последний элемент в очереди занимает позицию Q (5), значение R равно 5. Так как первый элемент в очереди находится в Q (3), значение F равно 2. На рис. 2. 17 в очередь помещается элемент G, что приводит к соответствующему изменению значения R. Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, а это как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью Разумеется, такая ситуация удовлетворить нас не может
Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема на единицу меньшего максимального. Так, если  массив из 100 элементов объявлен как очередь, то очередь может содержать до 99 элементов. Попытка разместить в очереди 100-й элемент приведет к переполнению. Подпрограмма insert может быть записана следующим образом:

if R = max(q)
then R = 1
else R = R+1
endif
‘проверка на переполнение
if R = F
then print «переполнение очереди»
stop
endif
q (r) =x
return

Проверка на переполнение в подпрограмме insert производится после установления нового значения для R, в то время как проверка на потерю значимости в подпрограмме remove производится сразу же после входа в подпрограмму до момента обновления значения F.

2.4.3  Дек
От английского DEQ — Double Ended Queue (Очередь с двумя концами)

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

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

Операции над деками:
1. Insert — вставка элемента.
2. Remove — извлечение элемента из дека.
3. Empty — проверка на пустоту.
4. Full — проверка на переполнениe.

Контрольные  вопросы
1.Что такое  структуры  данных?
2.Назовите уровни  представления данных?
3.Какова классификация структур данных?
4.Какая статическая структура является самой простой?
5.Перечислите основные элементы таблицы.
6.Назовите их основные особенности.
7.Что такое вектор?
8.Что представляет из себя запись?

Страницы: 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники