Рубрики

Структуры данных | Связанный список | Вопрос 12

Циркулярно связанный список используется для представления очереди. Одна переменная p используется для доступа к очереди. На какой узел следует указать p так, чтобы операции enQueue и deQueue могли выполняться за постоянное время? (GATE 2004)

(A) задний узел
(B) передний узел
(C) невозможно с одним указателем
(D) узел рядом с фронтом

Ответ: (А)
Объяснение: Ответ не «(b) передний узел», так как мы не можем получить заднюю часть спереди в O (1), но если p задняя, мы можем реализовать и enQueue, и deQueue в O (1), потому что сзади мы можем получить фронт в O (1). Ниже приведены примеры функций. Обратите внимание, что эти функции просто пример не работают. Код для обработки базовых случаев отсутствует.

/ * p указатель на адрес тыльной стороны (двойной указатель). Эта функция добавляет новые

   узел за тылом и обновляет тыл, который является * p, чтобы указать на новый узел * /

void  enQueue(struct node **p, struct node *new_node)

{

    / * Отсутствует код для обработки базовых случаев, например * p равен NULL * /

       

     new_node->next = (*p)->next;

     (*p)->next = new_node;

     (*p) = new_node / * Новое теперь сзади * /

     / * Обратите внимание, что p снова впереди, а p-> next сзади * /

 }

  
/ * p указатель на тыл. Эта функция удаляет передний элемент и

    возвращает новый фронт * /

struct node *deQueue(struct node *p)

{

    / * Отсутствует код для обработки базовых случаев, таких как p - NULL,

        p-> следующий равен NULL, ... и т. д. * /

  

    struct node *temp = p->next->next;

    p->next = p->next->next;

    return temp;

    / * Обратите внимание, что p снова впереди, а p-> next сзади * /

}

Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Связанный список | Вопрос 12

0.00 (0%) 0 votes