Изменение размера кольцевой очереди с использованием динамического массива - PullRequest
Новая
       14

Изменение размера кольцевой очереди с использованием динамического массива

2 голосов
/ 25 марта 2019

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

void ResizeQueue(struct DynArrayQueue* q) {

    int size = q->capacity;
    q->capactiy = q->capacity*2;
    q->array = realloc(q->array,q->capacity);
    if(!q->array) {
        printf("Memory error");
        return;
    }
    """(the doubt lines):

        if(q->front > q->rear) {
        for(int i = 0; i<q->front; i++) {
            q->array[i+size] = q->array[i];
        }
        q->rear = q->rear + size; """
   }
   }

Я сомневаюсь в этом коде выше, чтов какой момент в реализации динамического массива с круговой очередью фронт становится больше, чем задний?

Ответы [ 2 ]

1 голос
/ 25 марта 2019

Причина в том, что это кольцевой буфер. Предположим, что буфер имеет длину 8, вот две сцены A и B, где 4 элемента данных находятся в буфере, используя - для обозначения несущественных данных и d для обозначения буферизованных данных: 

index   0   1   2   3   4   5   6   7

A data  -   d   d   d   d   -   -   -
          begin        end

B data  d   d   -   -   -   -   d   d
           end                begin

Так как, по определению кольцевого буфера, данные переносятся, голова может быть ниже хвоста, или хвост может быть ниже головы.

Посмотрите, что происходит с буфером B, когда его длина удваивается 

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  d   d   -   -   -   -   d   d   -   -   -   -   -   -   -   -
           end                begin

Теперь должно быть понятно, почему данные нужно перемещать, поэтому это так: 

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  d   d   -   -   -   -   -   -   -   -   -   -   -   -   d   d
           end                                                begin

с соответствующим указателем или указателем.

В качестве альтернативы данные могут быть скорректированы так: 

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  -   -   -   -   -   -   d   d   d   d   -   -   -   -   -   -
                              begin        end
0 голосов
/ 25 марта 2019

Таким образом, "front" - это указатель чтения, следующая вещь, которую нужно прочитать. «Задняя часть» - это указатель записи, вставленный последним.

Каждый раз, когда в круговую очередь вставляется более capacity элементов, rear переносится в начало, и front > rear становится истинным. Именно этот механизм делает этот кольцевой буфер.

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

(Я думаю, было бы также правильно, если бы он копировал только элементы до rear. Как написано, он копирует устаревшие элементы.)

...