АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Очередь удобно представлять в виде циклического (кольцевого) вектора (в котором за последним элементом следует первый), с указателями начала и конца (рис. 3.2). Часть вектора занимает очередь, часть - свободное пространство. Указателем начала служит индекс первого из поступивших элементов, указателем конца - индекс первой свободной позиции в конце очереди (использование индекса последнего элемента несколько усложнит операции).

а) Индекс начала меньше б) Индекс начала больше

индекса конца индекса конца

Рис. 3.2. Хранение очереди в виде циклического вектора

(показаны два состояния)

Указатель начала увеличивается на одну позицию циклически (за N следует 0) при исключении элемента, указатель конца - при включении. У пустой очереди указатели равны друг другу и могут принимать любое значение от 0 до N. Чтобы отличать максимально заполненную очередь от пустой очереди, оставляют свободным хотя бы один элемент вектора. Поэтому у максимально заполненной очереди указатель конца отстает от указателя начала на одну позицию (рис. 3.3 г).

un=uk=2 un=1 uk=4 un=4 uk=2 un=3 uk=2

а) пустая б) un < uk в) un > uk г) полная

очередь очередь:a,b,c очередь:a,b,c очередь:a,b,c,d

Рис. 3.3. Примеры возможных состояний очереди

(un, uk - указатели начала и конца)

Пример 3.1. Описание данных для представления очереди циклическим вектором:

#define N 100 /* Максимальная длина очереди */

Тип-элемента q[N+1]; /* Отображающий вектор очереди */

int un; /* Указатель начала (индекс первого элемента) */

int uk; /* Указатель конца (индекс первого свободного

элемента в конце очереди) */

Пример 3.2. Инициализация (создание) пустой очереди:

un = uk = 0;

Пример 3.3. Исключение из очереди элемента и присваивание его величине x (обозначим эту операцию Очередь ==> x):

Тип-элемента x; /* Значение исключенного элемента */

...

if (un!= uk) /* В очереди есть элементы */

{ x = q[un]; /* Запоминание значения */

if (un < N) un++; else un=0; /* Исключение элемента */

}

else... /* Пустая очередь */

Пример 3.4. Включение в очередь элемента, равного x

(обозначим эту операцию Очередь<== x):

Тип-элемента x; /* Включаемое значение */

int i;

...

if (uk < N) i=uk+1; else i=0; /* Новое значение uk */

if (i!= un) /* Есть место в очереди */

{ q[uk] = x; /* Включение в очередь значения x */

uk = i;

}

else... /* Переполнение очереди */

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

Дата добавления: 2015-09-27 | Просмотры: 639 | Нарушение авторских прав