c - 在 C 中创建一个计算 PriorityQueue 中元素数量的函数

Question

任务:我正在为我的结构和算法大学类(class)做作业。任务是使用堆在 C 中实现优先队列并形成 main 以便它可以支持以下操作:插入 (在优先队列中插入字符串 s)删除 (删除优先级最低的元素)号码 (返回优先队列中的元素数)每次在 main 中写入操作时，我们还应该打印出优先队列的预排序。我们可以假设堆是用指针实现的。所以我在结构中实现了它，如下所示:

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)

该函数不应在调用 Number(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;
}

Answer 1

您可以使用不依赖于您列出的函数的递归算法来解决此问题。
代码可能是这样的:

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

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

这是我认为解决此问题的最佳方法。

如果您在递归方面遇到一些麻烦，我会给您留一个有用的链接:

recursion

编辑:

我认为不可能从优先级队列的结构中抽象出来，因为 PrEmpty 的实现, PrInsert , PrDeleteMin , 和 Preorder已经取决于优先级队列的结构。那么为什么要搜索仅依赖于这些函数的实现呢？同样要通用，您可以定义另一个函数来搜索元素而不删除它们并在上述函数的同一级别实现它，或者更好地在优先级队列上使用简单的迭代器。