• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C++优先级队列表基本算法实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

C++优先级队列表基本算法实现

主要采用链式结构,进行数据存储,然后定义一个最后结点指针数组,将所有优先级最后一个元素的地址保存到这个指针数组中。

#ifndef PriorityQueue_h
#define PriorityQueue_h
#include <iostream>
template <class T>
struct PriorityNode{
    short priority;                 //优先级
    T data;                         //数据域
    struct PriorityNode<T> * next; //指针域
};
#define PRIORITY_NUMBER 10
template < class T>
class PriorityQueue{
public:
    PriorityQueue();
    ~PriorityQueue();
    void Push(T x, short pri);
    T Pop();
    bool Empty();
    void PushAdjustLastNodeArray(short pri, PriorityNode<T> *p);//入队时调整数组
    void PopAdjustLastNodeArray(PriorityNode<T> *p);//出队时调整数组
private:
    PriorityNode <T> * front;                          //头结点
    PriorityNode <T> * lastNodeArray[PRIORITY_NUMBER]; //最后结点指针数组
};
template <class T>
PriorityQueue<T>::PriorityQueue(){
    front = new PriorityNode <T>;
    front->next = NULL;
    for(int i = 0; i< PRIORITY_NUMBER;i++){
        lastNodeArray[i] = front;
    }
}
template <class T>
PriorityQueue<T>::~PriorityQueue(){   //析构函数
    PriorityNode <T> * p = front;
    while(p){
        p = p->next;
        delete front;
        front = p;
    }
}
template <class T>
bool PriorityQueue<T>::Empty(){
    if(!front->next)
        return true;
    else
        return false;
}
template <class T>
void PriorityQueue<T>::Push(T x, short pri){
    if(pri>=PRIORITY_NUMBER) throw "Priority too great!";
    PriorityNode<T> *s = new PriorityNode<T>;
    s->data = x;
    s->priority = pri;
    //新结点加入到链中
    s->next = lastNodeArray[pri] -> next;
    lastNodeArray[pri]->next = s;
    PushAdjustLastNodeArray(pri,s);
}
template <class T>
T PriorityQueue<T>::Pop(){
    if(!front->next) throw "Queue is NULL";
    PriorityNode<T>*p = front->next;        //保存队头结点
    front->next = p->next;
    T x = p->data;
    PopAdjustLastNodeArray(p);
    delete p;
    return x;
}
template <class T>
void PriorityQueue<T>::PushAdjustLastNodeArray(short pri,PriorityNode<T> *p){
    short i= pri-1;
    while (i>=0 && lastNodeArray[i] == lastNodeArray[pri]){
        lastNodeArray[i] = p;
        i--;
    }
    lastNodeArray[pri] = p;
}
template <class T>
void PriorityQueue<T>::PopAdjustLastNodeArray(PriorityNode<T> *p){
    short pri = p->priority;
    if(lastNodeArray[pri] == p){  //只有当出队元素为该优先级最后一个元素时,才需要调整
        PriorityNode<T> * newLastNode = (pri==PRIORITY_NUMBER-1)?front:lastNodeArray[pri+1];
        short i = pri - 1;
        while(i>=0 && lastNodeArray[i] == lastNodeArray[pri]){
            lastNodeArray[i] = newLastNode;
        }
        lastNodeArray[pri] = newLastNode;
    }
    
}
#endif /* PriorityQueue_h */

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
radhat6.6上安装oracle12cRAC(一)发布时间:2022-07-13
下一篇:
最简单的http服务器(C#)发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap