priority_queue优先队列.doc

#include#include#include#include#include#include /用于做种子#include using namespace std;struct mytype /自定义的一个类，要在类中重载小于符号int value;int index;bool operator(const mytype b) return valueb.value;int ForInstance(priority_queuemytype,vector,cmp &q)/重构一个priority_queue的构造方法， srand(time(NULL);/使用这个就可以每次不同for(int i=0;i10;i+) int k=rand(); mytype t; t.value=k; t.index=i; q.push(t); coutindex=i value= kendl;coutendl;while(!q.empty() mytype t=q.top(); q.pop(); coutindex=t.index value= t.valueendl;return 0;int GetKey(priority_queuemytype,vector,cmp &q)mytype t;int n;cout请输入要数据个数n;int k;cout请输入n个数据endl;for(int i=0;ik;t.value=k; t.index=i;q.push(t);cout value= kendl;return 1;int main()priority_queuemytype,vector,cmpq;/创建优先队列，采用重构了一个比较的方法，优先队列为小顶堆int choose;/控制选择mytype t;while(choose)/菜单选择cout1.举例输入输出endl;cout2.初始化输入数据endl;cout3.插入数据endl;cout4.查找优先值最大的数据endl;cout5.删除优先值最大的数据endl;cout6.输出数据endl;cout0.退出choose;switch(choose)case 1:ForInstance(q);/举例说明cout例子如上endl;break;case 2:if(GetKey(q)/2.初始化输入数据cout成功输入数据t.value;/插入数据q.push(t);cout成功插入数据endl; break;case 4:t=q.top();/4.查找优先值最大的数据cout最小value= t.valueendl;break;case 5:t=q.top();/5.删除优先值最大的数据cout最小value= t.valueendl;q.pop();cout成功删除最小元素endl;break;case 6:/6.输出优先值最大的数据while(!q.empty() mytype t=q.top(); q.pop(); cout value= t.valueendl;break;case 0:return 0;return 0;数据结构：priority_queue mytype,vector,cmpq;创建优先队列，采用重构了一个比较的方法，优先队列为小顶堆，类型为mytypestruct mytype /自定义的一个结构体，要在结构体中重载小于符号int value;int index;算法实现：struct cmp用于实现优先级的比较函数，就是重载小括号，赋值运算符重载的问题priority_queue mytype,vector,cmpq:重构了一个构造函数，对象类型为mytype，比较方法重构为mytype.value最小值比较bool empty() const; /判断优先级队列是否为空，为空返回true，否则返回falsesize_type size() const; /返回优先级队列中的元素个数const value_type& top() const(); /返回优先级队列中第一个元素的参考值。void push(const value_type& x); /把元素x插入到优先级队列的尾部，队列的长度加1void pop(); /删除优先级队列的第一个值，前提是队列非空，删除后队列长度减1总结：这次写优先队列，是对第一题的完善和改进，同时更重要的是学会STL类库模板优先队列priority_queue的使用。总的来说收获很大，第一方面是在阅读STL源码解析，让以前模糊的知识点更加清晰。其二是知道了对于STL类库模板，我们更重要的是学会如何运用的问题，其三在一些代码上的不解上，我通过上网查询，知道了更加详细和全面的优先队列priority_queue的使用方法，知道了如何创建不同类型的优先队列priority_queue，以及赋值运算符重载的问题，还有更加详细的优先队列priority_queue函数使用方法。同时和第一题比较下，知道了优先队列priority_queue的使用方法是如何的简洁，只要学会如何STL类库模板，我们随时可以改变我们想要建立的优