POueueNode( Type& ralue, int data( value ) priority( nonpriority ) link( next) ∥构造函数 virtual Type GetData(f return data; 3 ∥取得结点数据 virtual int GetPriority (i 取得结点优先级 virtual PQueueNode<type> * GetLink ()i return link; j ∥取得下一结点地址 virtual void SetData( Type& value )i data= value; 3 ∥修改结点数据 virtual void SetPriorin( Int neprioriry){ priority= new priori;}∥修改结点优先级 virtual void Setlink( PQueuenode<Iype>·nex){lmk=nex;}∥修改指向下一结点的指针 ListNode<type> ∥链指针 }; template <class Type> class PQueue ∥优先级队列的类定义 public PQueue(: front( NULL), rear (NULL) 造函数 virtual -PQueue(i MakeEmpry (:3 ∥析构函数 virtual void Insert( Type& value, int newprioriry )i 插入新元素wae到队尾 virtual Type Remove (; 删除队头元素并返回 virtual Type Get ( ∥读取队头元素的值 virtual void Make Empty(; ∥置空队列 irtual int IsEmpry(i return front== NULL; /判队列空否 PQueueNode<type> front, rear; 队头指针,队尾指针 }; template<class Type> void PQueue<Type>: MakeEmpy (i ∥将优先级队列置空 while (front I= NULL ∥链不空时,删去链中所有结点 (q=front front =front->link: delete 4: j ∥循链逐个删除 队尾指针置空 template<class Type> void PQueue<Type> Insert( Type& int newprioriry )i 质插入函数 PQueueNode<Type> *g= new PQueueNode ralue, newpriorir, NULL ) if( lsEmpry ()front rear=q: 队列空时新结点为第一个结点 ∥寻找q的插入位置 hie(P=NULL&&p> prioriry> newprioriry)W队列中按优先级从大到小链接public: PQueueNode ( Type& value, int newpriority, PQueue<Type> * next ) : data ( value ), priority ( newpriority ), link ( next ) { } //构造函数 virtual Type GetData ( ) { return data; } //取得结点数据 virtual int GetPriority ( ) { return priority; } //取得结点优先级 virtual PQueueNode<Type> * GetLink ( ) { return link; } //取得下一结点地址 virtual void SetData ( Type& value ) { data = value; } //修改结点数据 virtual void SetPriority ( int newpriority ) { priority = newpriority; } //修改结点优先级 virtual void SetLink ( PQueueNode<Type> * next ) { link = next; } //修改指向下一结点的指针 private: Type data; //数据 int priority; //优先级 ListNode<Type> *link; //链指针 }; template <class Type> class PQueue { //优先级队列的类定义 public: PQueue ( ) : front ( NULL ), rear ( NULL ) { } //构造函数 virtual ~PQueue ( ) { MakeEmpty ( ); } //析构函数 virtual void Insert ( Type& value, int newpriority ); //插入新元素 value 到队尾 virtual Type Remove ( ); //删除队头元素并返回 virtual Type Get ( ); //读取队头元素的值 virtual void MakeEmpty ( ); //置空队列 virtual int IsEmpty ( ) { return front == NULL; } //判队列空否 private: PQueueNode<Type> *front, *rear; //队头指针, 队尾指针 }; template<class Type> void PQueue<Type> :: MakeEmpty ( ) { //将优先级队列置空 PQueueNode<Type> *q; while ( front != NULL ) //链不空时, 删去链中所有结点 { q = front; front = front->link; delete q; } //循链逐个删除 rear = NULL; //队尾指针置空 } template<class Type> void PQueue<Type> :: Insert ( Type& value, int newpriority ) { //插入函数 PQueueNode<Type> *q = new PQueueNode ( value, newpriority, NULL ); if ( IsEmpty ( ) ) front = rear = q; //队列空时新结点为第一个结点 else { PQueueNode<Type> *p = front, *pr = NULL; //寻找 q 的插入位置 while ( p != NULL && p->priority >= newpriority ) //队列中按优先级从大到小链接 { pr = p; p = p->link; }