一.什么是优先级队列
可以联想我们现实中排队时,有个军人优先服务.
那么这个就是一个优先级队列.
后面入队的,但是根据优先级,我可以先出.
二.优先级队列的结构
与链队列完全一样,只不过节点多了一个记录优先级的数据.
三.入队
与链队列也完全一样,只不过姚记得设置优先级的值.
四.出队★
优先级队列只影响出队的顺序,当优先级大的我们提前出队,优先级一样的,依次出队.
int deQueue(LinkQueue* LQ,int *data) { if (!LQ)return 0; if (!LQ)return 0; if (isEmpty(LQ)) { cout << "队列为空!无法删除!" << endl; return 0; } //prev=>最高优先级的上一个节点的next指针地址. //prev_node=>最高优先级的上一个节点 LNode** prev = NULL; LNode* prev_node = NULL; LNode* last = NULL;//遍历所用的节点指针 LNode* tmp = NULL;//遍历所用的节点指针 prev = &(LQ->front); last = LQ->front;//假设当前第一个的优先级最大 tmp = last->next; while (tmp) { if (tmp->priority > (*prev)->priority) { prev = &(last->next); prev_node = last; } last = tmp; tmp = tmp->next; } *data = (*prev)->data; LNode* p; p = (*prev); *prev = p->next; delete p; LQ->length--; if (LQ->length == 0) { LQ->rear = NULL; } if (prev_node&& prev_node->next == NULL) { LQ->rear = prev_node; } return 1; }
先假设第一个节点的优先级最大,然后像后面遍历比较,找出最大优先级的节点.
当然我们的目的是删除节点,所以我们指向的是最大优先级节点的前一个,方便我们直接指向要删除节点的下一个位置.直接删除.
当删除完当前节点后,还有两种情况,要改变rear的指向.
如果要删除的位置是只有一个节点的情况.
如果删除的是最后一个节点,那么rear的指向要改变.
五.总结
使用二级指针是为了能够修改一级指针指向的内存地址，从而改变链表节点的指向关系。在这段代码中，通过使用二级指针prev来记录最高优先级节点的上一个节点的next指针地址，可以在删除节点时直接修改链表的指向关系，而不需要再通过一个中间变量来保存上一个节点的地址。同时，二级指针也能够处理特殊情况，例如删除最后一个节点或者删除头节点时需要修改队列的rear指针。因此，使用二级指针能够更方便地操作链表，并且减少了代码的复杂度。
