@fuheimao
2014-11-29T10:44:30.000000Z
字数 3868
阅读 663
Stack(栈),是 LIFO (last-in first-out) 的一种数据结构。
使用 stack 需要
#include <stack>
声明
stack<int> s;
stack<TJJ> T;
函数
s.push(); //在栈中压入一个元素
s.top(); //取出栈顶元素(不删除)
s.pop(); //弹出栈顶元素
s.empty(); //是否为空
s.size(); //元素个数
例子 十进制转二进制
#include <iostream>
#include <stack>
using namespace std;
stack<int> result;
int main() {
int n;
cin>>n;
while (n) {
result.push(n%2);
n/=2;
}
cout<<"转换后的二进制共有"<<result.size()<<"位"<<endl<<"转换后的二进制为:";
while (!result.empty()) {
cout<<result.top();
result.pop();
}
return 0;
}
Queue(队列),一个FIFO(先入先出)的数据结构。
使用 queue 需要
#include <queue>
声明
#queue<int> q;
#queue<TJJ> T;
函数
q.empty(); //判断队列空,当队列空时,返回true。
q.size(); //返回队列中的元素个数。
q.push(); //将一个元素置入queue中。
q.front(); //返回queue内的第一个元素(也就是第一个被置入的元素)。
q.back(); //返回queue中最后一个元素(也就是最后被置入的元素)。
q.pop(); //移除队列头部的一个元素。
例子 SPFA
#include "iostream"
#include "vector"
#include "queue"
using namespace std;
struct node{
int num,value;
};
vector<node> v[101];
queue<int> q;
bool used[101];
int dis[101];
int main(){
ios::sync_with_stdio(false);
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
int n,m;
cin>>n>>m;
for (int i=1;i<=m;++i){
int t1,t2,t3;
cin>>t1>>t2>>t3;
v[t1].push_back((node){t2,t3});
}
q.push(1);
used[1]=true;
while (!q.empty()){
int now=q.front();
q.pop();
for (vector<node>::iterator i = v[now].begin(); i != v[now].end(); ++i){
if (dis[i->num]>dis[now]+i->value) {
dis[i->num]=dis[now]+i->value;
}
if (!used[i->num]){
used[i->num]=true;
q.push(i->num);
}
}
}
cout<<dis[n];
return 0;
}
Deque(double-ended queue)即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。
使用 deque 需要
#include <deque>
函数
函数还是那么些,反正这玩意儿我们基本上用不着所以就不说了吧~(逃)
priority_queue(优先队列),调用了 STL 中的 make_heap(),pop_heap(),push_heap(),也相当于一个堆。
使用 priority_queue 需要
#include <queue>
声明
priority_queue <int> q //默认是大根堆。
priority_queue <int, vector<int>, greater<int> > q
//第二个参数是容器,可以是 vector,deque 但不能为 list
//第三个参数是比较,greater<int> 就是小根堆了,注意> >不能写在一起,否则会变成右移
例子 合并果子
#include<iostream>
#include<queue>
using namespace std;
int main () {
int minh=0,min1,min2;
priority_queue<int, vector<int>,greater<int> > q;
cin>>n;
for (int i=1;i<=n;i++){
int value;
cin>>value;
q.push(value);
}
for (int i=n+1;i<=2*n-1;i++){
min1=q.top();
q.pop();
min2=q.top();
q.pop();
q.push(min1+min2);
minh+=min1+min2;
}
cout<<minh;
return 0;
}
Set(集合),set 中不会有重复的元素,所有的操作都会在 logn 的时间内完成。
使用 set 需要
#include <set>
声明
set<int> s;
函数
//函数什么的大都差不多啦
s.insert();
例子 明明的随机数
#include <iostream>
#include <set>
using namespace std;
set<int> s;
int main() {
int n;
cin>>n;
while (n--) {
int temp;
cin>>temp;
s.insert(temp);
}
cout<<s.size()<<endl;
for (set<int>::iterator i=s.begin();i!=s.end();++i){
cout<<*i<<" ";
}
return 0;
}
algorithm意为"演算法",是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模版函数。
常用函数
swap(a[1],a[2]);//交换两个变量的值
sort(begin,end);//排序
stable_sort(begin,end);//稳定排序
max(a,b);//二者中的最大值
max_element();//给定范围内的最大值
min(a,b);
min_element();//给定范围内的最小值
next_permutation();//下一个排列
prev_permutation();//上一个排列
lower_bound();//返回给定范围内的第一个大于等于给定元素的迭代器。
upper_bound();//返回给定范围内的第一个大于给定元素的迭代器。
例子
//全排列
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main (){
int n;
scanf("%d",&n);
vector<int> q;
for (int i=1;i<=n;i++){
q.push_back(i);
}
do{
for (vector<int>::iterator i=q.begin();i!=q.end();++i){
printf("%d ",*i);
}
printf("\n");
}while(next_permutation(q.begin(),q.end()));
return 0;
}
//自定义结构体的排序 #1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct tjj{
int height;
int length_of_neck;
bool operator < (const tjj& b) const {
if (height>b.height) return true;
if (height==b.height&&length_of_neck>b.length_of_neck) return true;
return false;
}
};
vector<tjj> TJJ;
int main() {
int n;
cin>>n;
while (n--) {
int h,t;
cin>>h>>t;
TJJ.push_back((tjj){h,t});
}
sort(TJJ.begin(),TJJ.end());
return 0;
}
//自定义结构体的排序 #2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct tjj{
int height;
int length_of_neck;
};
bool cmp(const tjj& a,const tjj& b){
if (a.height>b.height) return true;
if (a.height==b.height&&a.length_of_neck>b.length_of_neck) return true;
return false;
}
vector<tjj> TJJ;
int main() {
int n;
cin>>n;
while (n--) {
int h,t;
cin>>h>>t;
TJJ.push_back((tjj){h,t});
}
sort(TJJ.begin(),TJJ.end(),cmp);
return 0;
}
其实还有很多没有说到的东西,就靠大家自己查资料了。
腹黑猫
2014.11.29