编写优先队列数据(priority-queue).doc

《编写优先队列数据(priority-queue).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include"iostream"#include"stdlib.h"typedefintT;#defineERROR0#defineOK1#defineMAX50typedefstruct{T*array;intlength;intMaxSize;}Array;//定义一个数组，用来存放第一次录入的数据。对应有两个函数操作usingnamespacestd;template//定义一种格式，当T改变时，class类型改变,采用class才完成，用最大堆来存取classMaxHeap{public:

2、MaxHeap(intMaxSize);intSize(){returnCurrentSize;}//求当前堆的元素大小TMax(){if(CurrentSize==0)throwOutOfBounds();returnheap[1];}//求最大的元素voidLoadHeap()//遍历整个堆元素{cout<<"输出数据为"<&Insert(Tx);//插入MaxHeap&

3、DeleteMax(T&x);//删除voidInitialize(Ta[],intsize);//初始化voidheapAdjust();//调整private:intCurrentSize,MaxSize;//当前长度和最大长度T*heap;//元素数组，用堆来存取};templateMaxHeap::MaxHeap(intMaxHeapSize){//构造函数MaxSize=MaxHeapSize;heap=newT[MaxSize+1];CurrentSize=0;}template

4、lassT>voidMaxHeap::Initialize(Ta[],intsize)//初始化{//把最大堆初始化为数组a.heap=a;CurrentSize=size;}voidMaxHeap::heapAdjust()//调整{for(inti=CurrentSize/2;i>=1;i--){Ty=heap[i];//子树的根//寻找放置y的位置intc=2*i;//c的父节点是y的目标位置while(c<=CurrentSize){//heap[c]应是较大的同胞节点if(c

5、ze&&heap[c]=heap[c])break;//能//不能heap[c/2]=heap[c];//将孩子上移c*=2;//下移一层}heap[c/2]=y;}}templateMaxHeap&MaxHeap::Insert(Tx)//插入{//把x插入到最大堆中if(CurrentSize==MaxSize)throwNoMem();//没有足够空间//为x寻找应插入位置//i从新的叶节点开始，并沿着树上升

6、inti=++CurrentSize;while(i!=1&&x>heap[i/2]){//不能够把x放入heap[i]heap[i]=heap[i/2];//将元素下移i/=2;//移向父节点}heap[i]=x;return*this;}templateMaxHeap&MaxHeap::DeleteMax(T&x)//删除{//将最大元素放入x，并从堆中删除最大元素//检查堆是否为空if(CurrentSize==0)throwOutOfBounds();//队列空x=heap[1];

7、//最大元素//重构堆Ty=heap[CurrentSize--];//最后一个元素//从根开始，为y寻找合适的位置inti=1,//堆的当前节点ci=2;//i的孩子while(ci<=CurrentSize){//heap[ci]应是i的较大的孩子if(ci=heap[ci])break;//能//不能heap[i]=heap[ci];//i=ci;//下移一层ci*=2;}heap[i]=y;

8、return*this;}voidInitArray(Array&A)//初始化元素数组{A.array=(T*)malloc(MAX*sizeof(T));A.length=0;A.MaxSize=MAX;}voidGetArrayKey(Array&A)//输入元素数组的值{cout<<"请输入您数组集合的大小个数"<