数据结构—优先队列.docx

priority_queueint,vector,greater优先队列 按照由小到大顺序分类：转载Tech_ACMACM_数据结构2012-07-23 01:24563人阅读评论(0)收藏举报vectorclassn2lesscC+优先队列的基本使用方法#include#include#includeusing namespace std;struct nodefriend bool operator (node n1, node n2)return n1.priority n2.priority;/为从小打到排列int priority;int value;int main()const int len = 5;int i;int alen = 3,5,9,6,2;/示例1priority_queue qi;/普通的优先级队列，按从大到小排序for(i = 0; i len; i+)qi.push(ai);for(i = 0; i len; i+)coutqi.top() ;qi.pop();coutendl;/示例2priority_queueint, vector, greater qi2;/从小到大的优先级队列，可将greater改为less，即为从大到小for(i = 0; i len; i+)qi2.push(ai);for(i = 0; i len; i+)coutqi2.top() ;qi2.pop();coutendl;/示例3priority_queue qn;/必须要重载运算符node blen;b0.priority = 6; b0.value = 1;b1.priority = 9; b1.value = 5;b2.priority = 2; b2.value = 3;b3.priority = 8; b3.value = 2;b4.priority = 1; b4.value = 4;for(i = 0; i len; i+)qn.push(bi);cout优先级t值endl;for(i = 0; i len; i+)coutqn.top().prioritytqn.top().valueendl;qn.pop();return 0;对于队列里元素为一个结构体类型，按照某一个属性排序，就需要对比较函数进行重载小结一下：1、若是定义值类型对象，如：intmain() priority_queue qn; node n1; n1.a = 9; node n2; n2.a = 2; node n3; n3.a = 50; qn.push(n1); qn.push(n2); qn.push(n3); int size = qn.size(); for ( int i = 0; i size; i+) cout qn.top().a endl; qn.pop(); return 0;则定义优先级的时候，直接在类中写个friend 的操作符重载函数即可：class nodepublic : int a; node() node( int x):a(x)friend bool operator ne2.a) return true ; else return false ; ;其中在cprimer第三版 中文版中关于操作符重载有如下描述：程序员只能为类类型或枚举类型的操作数定义重载操作符我们可以这样来实现把重载操作符声明为类的成员或者声明为名字空间成员同时至少有一个类或枚举类型的参数按值传递或按引用传递因此不可用指针类型的参数；2、如果想定义一个指针类型的优先队列，那就不可这么简单的定义了，你需要自定义一个自己的比较函数，在priority_queue的模板函数中，我们可以利用这样一个templateclass _Ty, class _Container = vector, class _Pr = less 模板，在我们的程序代码中，则需要自己定义一个类来定义第三个模板参数，如：class nodePointerComparerpublic : nodePointerComparer() bool operator ()( const node* ne1, const node* ne2) const return ne1-lessthan(ne2); ;当然在这之前我们的类Node要重新书写class nodepublic : int a; node() node( int x):a(x) bool lessthan( const node* pnode) const return a a; ;这样在main函数中就可以定义指针类型的优先队列了：int main() priority_queue node*, vector , nodePointerComparer qn; node *n1 = new node(90); node *n2 = new node(2); node *n3 = new node(50); qn.push(n1); qn.push(n2); /span qn.push(n3); int size = qn.size(); for ( int i = 0; i size; i+) cout a endl; qn.pop(); return 0;2:二分查找 1675#include#includedouble a(double b) return 8*pow(b,4)+2*pow(b,2)+7*pow(b,3)+3*b+6;double search(double m,double n,double y) double mid=(m+n)/2; while(n-m0.00001) if(a(mid)=y) return mid; if(a(mid)y) return search(m,mid,y); if(a(mid)y) return search(mid,n,y); return mid;int main(void) int t; scanf(%d,&t); while(t-) double x,y,m,n