Создание функции, которая считает количество элементов в PriorityQueue в C - PullRequest
Новая
       29

Создание функции, которая считает количество элементов в PriorityQueue в C

2 голосов
/ 21 января 2020

ЗАДАЧА: Я работаю над домашней работой для своего класса колледжа структуры и алгоритмов. Задача состоит в том, чтобы реализовать приоритетную очередь в C с использованием кучи и сформировать основную, чтобы она могла поддерживать такие операции, как: INSERT s (вставляет строку s в приоритетную очередь) DELETE (удаляет элемент с самым низким приоритетом) NUMBER (возвращает количество элементов в приоритетной очереди) Мы также должны распечатывать предзаказ очереди приоритетов каждый раз, когда пишем операцию в основном. Можно предположить, что куча реализована с помощью указателей. Поэтому я реализовал его в структуре, которая выглядит следующим образом: 

typedef char* elementtype;

typedef struct celltag {
    elementtype zapis;
    struct celltag *left, *right, *parent;
}   celltype;

typedef celltype* node;
typedef celltype* PriorityQueue;

Я также реализовал следующие функции: 

void PrMakeNull(PriorityQueue *Ap)
int PrEmpty(PriorityQueue A)
void PrInsert(elementtype x, PriorityQueue *Ap)
elementtype PrDeleteMin(PriorityQueue *Ap)
void Preorder(PriorityQueue A)

ВОПРОС: Я должен реализовать «функцию нумерации» с таким заголовком: 

int Number(PriorityQueue P)

Функция не должна изменять приоритетную очередь A после вызова номера (A). Кроме того, функция должна быть независимой от реализации Приоритетной очереди. (Я думаю, это означает, что я должен использовать только PrMakeNull, PrEmpty, PrInsert, PrDeleteMin). Это вообще возможно? Как я мог это сделать? Как это должно выглядеть? ЧТО Я ПОПРОБОВАЛ: 1) 

//This one is independent on Priority Queue implementation but destroys the Priority Queue. 
int Number(PriorityQueue P){
    PriorityQueue S;
    PrMakeNull(&S);
    int counter=0;
    while(!PrEmpty(P))
    {
        PrInsert(PrDeleteMin(&P), &S);
        counter++;
    }
    while(!PrEmpty(S))
    {
        PrInsert(PrDeleteMin(&S), &P);
    }
    return counter;
}

2) 

//This one is dependent on Priority Queue implementation but doesn't destroy the Priority Queue. 
int Number(PriorityQueue A){
    int returning_number=1;
    if (A == NULL)
        return 0;
    if(A->left!=NULL)
        returning_number+=Number(A->left);
    if(A->right!=NULL)
        returning_number+=Number(A->right);
    return returning_number;
}

Ответы [ 2 ]

2 голосов
/ 21 января 2020

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

int Number(PriorityQueue A)
{
    if(!A) return 0;

    return 1 + Number(A->left) + Number(A->right);
}

На мой взгляд, это лучший способ решить эту проблему.

Если у вас возникли проблемы с рекурсией, я оставлю вам полезную ссылку:

рекурсия

Редактировать:

Я не думаю, что есть возможность абстрагироваться от структуры очереди приоритетов, потому что реализация PrEmpty PrInsert, PrDeleteMin и Preorder уже зависят от структуры очереди приоритетов. Так зачем искать реализацию, которая зависит только от этих функций? Также, чтобы быть обобщенным c, вы можете определить другую функцию, которая ищет элемент, не удаляя их, и реализует его на том же уровне вышеупомянутой функции, или, что лучше, простой итератор в очереди приоритетов.

0 голосов
/ 21 января 2020 
int Number(PriorityQueue A) {
    if(PrEmpty(A)) return 0;
    elementType val = PrDeleteMin(&A);
    int num = 1 + Number(A);
    PrInsert(val, &A);
    return num;

}
...