Динамические структуры данных. Алексеев А.Ю - 40 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

за границу вектора, продолжаясь с его начала (вектор имитирует здесь так на-
зываемый кольцевой буфер). Эта ситуация изображена на рис. 2.5.
Рис. 2.5. Непрерывное представление очередив кольцевом буфере
Двух переменных Начало и Конец недостаточно, чтобы различить в дан-
ном представлении, например, два следующих состояния очереди: 1) Нача-
ло = Конец + 1 и очередь пуста (см.рис.2.6,а); 2) Начало = Конец + 1 и очередь
полна (см.рис.2.6,б). Простым решением этой проблемы является введение
еще одной переменной, идентифицирующей состояние очереди, а именно
переменной Длина, значение которой задает
текущее количество элементов
в очереди (для пустой очереди Длина = 0, для полной очереди Длина = n).
а
б
Рис. 2.6. Два состояния очереди, при которых Начало=Конец+1:
а – очередь пуста, б – очередь полна
Аналогичным образом может быть реализован дек.
2.3. Упражнения
В заданиях 1 – 3 следует использовать очередь и операции над ней; при
этом очередь может быть реализована как на базе вектора, так и в связанной
памяти (ссылочная реализация).
Mem:
n 1
2 3
x x x x x x x x x x x
Начало Конец
Mem:
n 1 2 3
Начало
Конец
Начало Конец
Mem:
n 3 2 1
x x x x x x x x x x x x x x x x x x x x
40
за границу вектора, продолжаясь с его начала (вектор имитирует здесь так на-
зываемый кольцевой буфер). Эта ситуация изображена на рис. 2.5.

             1    2 3                                                                                         n

  Mem:       x x       x       x    x    x                                                  x     x    x   x x


                                        Начало                                            Конец


            Рис. 2.5. Непрерывное представление очередив кольцевом буфере

   Двух переменных Начало и Конец недостаточно, чтобы различить в дан-
ном представлении, например, два следующих состояния очереди: 1) Нача-
ло = Конец + 1 и очередь пуста (см.рис.2.6,а); 2) Начало = Конец + 1 и очередь
полна (см.рис.2.6,б). Простым решением этой проблемы является введение
еще одной переменной, идентифицирующей состояние очереди, а именно
переменной Длина, значение которой задает текущее количество элементов
в очереди (для пустой очереди Длина = 0, для полной очереди Длина = n).


                 1 2       3                                                                                 n
    Mem:


                                        Начало                                   Конец

                                                             а

                 1 2       3                                                                                 n
     Mem:        x x       x       x    x    x   x   x   x       x   x   x   x    x   x    x    x     x    x x


                                                                                 Конец     Начало

                                             б
             Рис. 2.6. Два состояния очереди, при которых Начало=Конец+1:
                            а – очередь пуста, б – очередь полна

      Аналогичным образом может быть реализован дек.


                                                 2.3. Упражнения

   В заданиях 1 – 3 следует использовать очередь и операции над ней; при
этом очередь может быть реализована как на базе вектора, так и в связанной
памяти (ссылочная реализация).

                                                         40

Страницы