在 C 中制作一个计算 PriorityQueue 中元素数量的函数

Question

任务：

我正在为我的结构与算法学院做作业class。任务是使用堆在 C 中实现 Priority Queue 并形成 main，因此它可以支持诸如以下的操作：

INSERT s (inserts string s in a Priority Queue)
DELETE (删除优先级最低的元素)
NUMBER (returns Priority 中的元素数量 Queue)

我们还应该在每次写入时打印出 Priority Queue 的预序主要是一个操作。我们可以假设堆是用指针实现的。所以我在看起来像这样的结构中实现它：

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)

问题：
我应该像这样用 header 实现 "number function"：

int Number(PriorityQueue P)

函数在调用 Number(A) 后不应更改优先级 Queue A。此外，该功能应独立于 Priority Queue 实现。（我认为这意味着我应该只使用 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);
}

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

如果你在递归上遇到了一些问题，我会给你一个有用的 link:

recursion

编辑：

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

Answer 2

int Number(PriorityQueue A) {
    if(PrEmpty(A)) return 0;
    elementType val = PrDeleteMin(&A);
    int num = 1 + Number(A);
    PrInsert(val, &A);
    return num;

}

在 C 中制作一个计算 PriorityQueue 中元素数量的函数

Making a function that counts number of elements in PriorityQueue in C

c

priority-queue