Проблема при преобразовании итеративной функции, которая печатает очередь в рекурсивную - PullRequest
Новая
       26

Проблема при преобразовании итеративной функции, которая печатает очередь в рекурсивную

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

У меня есть эта итеративная функция, которая отображает очередь: 

void displayQueue(queue *Q){

     int temp;

     while(!isEmpty(Q)){
         temp = dequeue(Q);
         printf("%d -> ", temp);
         displayQueue(Q);
         enqueue(Q, temp);
     }

     reverse(Q);
}

Я хотел бы сделать ее полностью рекурсивной, удалив while l oop, это то, что я получил до сих пор: 

void displayQueue(queue *Q){

    if(isEmpty(Q)) return;

    int temp = dequeue(Q);
    printf("%d -> ", temp);
    displayQueue(Q);
    enqueue(Q, temp);
}

Проблема заключается в том, когда вызывать функцию «reverse (Q)», которая должна вызываться в конце печати, когда функция возвращается, но в этот момент Q пусто, поэтому ее нельзя будет перевернуть (печать очереди вызывает ее инверсию)

Это моя структура очереди: 

typedef struct queue{
  unsigned capacity;
  int size;
  int front;
  int rear;
  int *array;
}queue;

1 Ответ

0 голосов
/ 25 марта 2020

Кажется, что функция должна выглядеть следующим образом 

void displayQueue( queue *Q )
{
    if ( !isEmpty( Q ) )
    {
        int temp = dequeue( Q );
        printf( "%d -> ", temp );

        displayQueue( Q );

        reverse( Q );
        enqueue( Q, temp );
        reverse( Q );
    }
}

Если вы хотите избежать слишком частого переворота очереди, вы можете написать функцию с переменной stati c, например, такой как 

void displayQueue( queue *Q )
{
    static int state = 0;

    if ( !isEmpty( Q ) )
    {
        int to_reverse = state ^ 1;
        if ( to_reverse ) state = to_reverse;

        int temp = dequeue( Q );
        printf( "%d -> ", temp );

        displayQueue( Q );

        enqueue( Q, temp );

        if ( to_reverse )
        {
            reverse( Q );
            state = 0;
        }
    }
}

Без переменной stati c вы можете написать функцию, разбив ее на две функции. Первый вызывает рекурсивную функцию и полностью изменяет результат. Вторая - это рекурсивная функция, которая отображает очередь.

Например, 

void recursiveDisplayQueue( queue *Q )
{
    if ( !isEmpty( Q ) )
    {
        int temp = dequeue( Q );
        printf( "%d -> ", temp );

        recursiveDisplayQueue( Q );

        enqueue( Q, temp );
    }
}

void displayQueue( queue *Q )
{
    if ( !isEmpty( Q ) )
    {
        recursiveDisplayQueue( Q );

        reverse( Q );
    }
}
...