任务：
我正在为我的结构与算法大学班的家庭作业。任务是使用堆在C中实现优先级队列并形成主体，以便它可以支持以下操作：
INSERT（在优先级队列中插入字符串）
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)
该函数在调用Number（A）之后不应更改Priority QueueA。同样，该功能应独立于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;
}
您可以使用不依赖于您列出的函数的递归算法来解决此问题。代码可能像这样：
int Number(PriorityQueue A)
{
if(!A) return 0;
return 1 + Number(A->left) + Number(A->right);
}
我认为这是解决此问题的最佳方法。
如果您在递归方面遇到麻烦，请给我一个有用的链接：
编辑：
我不认为这是一个可以从抽象的优先级队列这个结构，因为实施PrEmpty，PrInsert，PrDeleteMin，和Preorder已经依赖于优先级队列的结构。那么，为什么要搜索仅依赖于这些功能的实现呢？同样，您可以定义另一个函数，该函数搜索元素而不删除它们，并在与上述函数相同的级别上实现它，或者最好是在优先级队列上使用简单的迭代器。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句