编写优先队列数据priorityqueueWord文档格式.docx
- 文档编号:4773698
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:11
- 大小:80.99KB
编写优先队列数据priorityqueueWord文档格式.docx
《编写优先队列数据priorityqueueWord文档格式.docx》由会员分享,可在线阅读,更多相关《编写优先队列数据priorityqueueWord文档格式.docx(11页珍藏版)》请在冰点文库上搜索。
intSize(){returnCurrentSize;
}//求当前堆的元素大小
TMax(){if(CurrentSize==0)throwOutOfBounds();
returnheap[1];
}//求最大的元素
voidLoadHeap()//遍历整个堆元素
cout<
<
"
输出数据为"
endl;
for(inti=1;
i<
=CurrentSize;
i++)
{
cout<
heap[i]<
}
}
MaxHeap<
T>
&
Insert(Tx);
//插入
DeleteMax(T&
x);
//删除
voidInitialize(Ta[],intsize);
//初始化
voidheapAdjust();
//调整
private:
intCurrentSize,MaxSize;
//当前长度和最大长度
T*heap;
//元素数组,用堆来存取
};
:
MaxHeap(intMaxHeapSize)
{//构造函数
MaxSize=MaxHeapSize;
heap=newT[MaxSize+1];
CurrentSize=0;
voidMaxHeap<
Initialize(Ta[],intsize)//初始化
{//把最大堆初始化为数组a.
heap=a;
CurrentSize=size;
heapAdjust()//调整
for(inti=CurrentSize/2;
i>
=1;
i--){
Ty=heap[i];
//子树的根
//寻找放置y的位置
intc=2*i;
//c的父节点是y的目标位置
while(c<
=CurrentSize){
//heap[c]应是较大的同胞节点
if(c<
CurrentSize&
heap[c]<
heap[c+1])c++;
//能把y放入heap[c/2]吗?
if(y>
=heap[c])break;
//能
//不能
heap[c/2]=heap[c];
//将孩子上移
c*=2;
//下移一层
heap[c/2]=y;
MaxHeap<
Insert(Tx)//插入
{//把x插入到最大堆中
if(CurrentSize==MaxSize)
throwNoMem();
//没有足够空间
//为x寻找应插入位置
//i从新的叶节点开始,并沿着树上升
inti=++CurrentSize;
while(i!
=1&
x>
heap[i/2])
//不能够把x放入heap[i]
heap[i]=heap[i/2];
//将元素下移
i/=2;
//移向父节点
heap[i]=x;
return*this;
DeleteMax(T&
x)//删除
{//将最大元素放入x,并从堆中删除最大元素
//检查堆是否为空
if(CurrentSize==0)
throwOutOfBounds();
//队列空
x=heap[1];
//最大元素
//重构堆
Ty=heap[CurrentSize--];
//最后一个元素
//从根开始,为y寻找合适的位置
inti=1,//堆的当前节点
ci=2;
//i的孩子
while(ci<
//heap[ci]应是i的较大的孩子
if(ci<
heap[ci]<
heap[ci+1])ci++;
//能把y放入heap[i]吗?
=heap[ci])break;
heap[i]=heap[ci];
//
i=ci;
//下移一层
ci*=2;
heap[i]=y;
voidInitArray(Array&
A)//初始化元素数组
A.array=(T*)malloc(MAX*sizeof(T));
A.length=0;
A.MaxSize=MAX;
voidGetArrayKey(Array&
A)//输入元素数组的值
请输入您数组集合的大小个数"
intn;
cin>
>
n;
intkey;
请输入数据"
=n;
cin>
key;
if(A.length>
=A.MaxSize)
A.array=(T*)realloc(A.array,(A.length+MAX)*sizeof(T));
A.array[++A.length]=key;
classOutOfBounds//异常抛出,太麻烦不写
public:
OutOfBounds()
{}
~OutOfBounds()
};
classNoMem
NoMem()
virtual~NoMem()
//异常抛出,太麻烦不写
intmain()
H(MAX);
Tx;
ArrayA;
InitArray(A);
H.LoadHeap();
intchoose;
//控制选择
while(choose)//菜单选择
1.初始化输入数据"
2.插入数据"
3.查找数据"
4.删除数据"
5.遍历数据"
0.退出"
choose;
switch(choose)
case1:
GetArrayKey(A);
//初始化数据
H.Initialize(A.array,A.length);
H.heapAdjust();
break;
case2:
//插入元素
请输入您想要插入的元素的值"
x;
H.Insert(x);
插入成功"
break;
case3:
x=H.Max();
//求最大元素
当前查找最大的元素为:
x<
break;
case4:
H.DeleteMax(x);
//删除最大元素
删除的最大元素为:
"
case5:
//遍历整个数组元素
case0:
return0;
return0;
数据结构选择:
定义T为INT类型,权值为INT类型,定义一个class,里面一个privateT*heap,
采用大顶堆的方法实现函数功能,函数实现都是在class里面的public函数;
算法实现:
在class里面实现全部函数,函数定义为public
一个初始化initialize(Ta[],intsize),把一个数组直接覆盖掉原来的T*heap,并执行相应的长度变化操作.
一个插入Insert(Tx):
在数组的最尾部插入,插入之后进行大顶堆调整,保证第一个数组元素为最大权值
一个删除DeleteMax(T&
x):
返回第一个数组元素,然后进行大顶堆调整,重新建堆
一个查找最大元素TMax():
返回第一个数组元素
一个遍历voidLoadHeap():
采用从头到尾遍历整个数组元素
一个求元素数组的长度intSize():
返回当前长度
总结:
由于编写优先队列数据(priority_queue)类型可以用很多种方法实现,而且难度不大,所以在《数据结构》和C语音的基础上自学了C++,代码才用C++语言描写,函数在class内完成,大顶堆代码在《数据结构》中稍微调整了一下,整个元素集合封装只可以调用函数访问.
测试数据:
第一组:
第二组:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编写 优先 队列 数据 priorityqueue