随州网站建设外包公司,物流网站的建设论文,网站备案登录密码找回,wordpress轮翻图参数目录前言【1】stack操作以及应用stack的几个核心接口利用stack完成进制转换【2】priority_queue操作以及应用priority_queue的几个核心接口利用priority_queue完成合并果子问题【3】vector操作以及应用vector的几个核心接口利用vector完成随机排序【4】deuqe(双向队列)操作以及…
目录前言【1】stack操作以及应用stack的几个核心接口利用stack完成进制转换【2】priority_queue操作以及应用priority_queue的几个核心接口利用priority_queue完成合并果子问题【3】vector操作以及应用vector的几个核心接口利用vector完成随机排序【4】deuqe(双向队列)操作以及应用deuqe的特点以及核心接口利用deuqe处理数据【5】list(双向链表)操作以及应用list的特点双向链表实现数据的输入与求和【6】map/multimap操作以及应用map/multimap的几个特点以及功能接口map/multimap应用优惠购物【7】set/multiset(集合/多重集合)操作以及应用set/multiset的几个特点利用set完成随机数的产生以及排序总结前言
前几天回老家没事儿在新华书店乘凉无意翻到《c信息学奥林匹克竞赛入门与提高》拍了几张照片顺便学点c的知识。 现整理如下 关于STL的知识可以先看看百度百科STL(模板库)_百度百科 【1】stack操作以及应用
stack的几个核心接口 向栈中压入一个元素push、 取栈顶元素的值top、 弹出栈顶元素pop、 清空栈empty、 判断栈是否为空isEmpty 利用stack完成进制转换
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
using namespace std;//stack应用
//输入十进制数n,转换成r进制数输出2r16
const string t 0123456789ABCDEF;
int main()
{stackints;int n, r, x;cin n r;while (n ! 0){x n % r;//求余数s.push(x);//将余数压入栈顶n n / r;//缩小r倍}while (!s.empty()){cout t[s.top()]; //转换成r进制数位s.pop(); //弹出栈顶元素即移除元素}
}结果
【2】priority_queue操作以及应用
priority_queue的几个核心接口 push()——根据元素的优先级将元素置入优先队列默认降序排列大值优先 top()——返回优先队列头部最大的元素的引用(不移除 pop()——从优先队列中移除最大元素 empty()——优先队列是否为空 priority_queue 的模板声明带有三个参数: priority_queueType, Container, Functional 其中Type 为数据类型 Container 为保存数据的容器Functional 为元素比较方式。 Container 必须是用数组实现的容器比如 vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator , 所以如果你把后面俩个参数缺省的话 优先队列就是大顶堆队头元素最大。 利用priority_queue完成合并果子问题
问题描述以及分析 在一个果园里多多已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。多多决定把 所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重力之和。 算法分析: 如有3种果子,数目依次为1,92。可以先将1,2堆合并,新堆数目为3,耗费体力为3。接着﹐将新堆 与数量为9的堆合并又得到新的堆数目为12,耗费体力为12。 所以多多总共耗费体力31215。可以证明15为最小的体力耗费值。 类似于堆操作完全二叉树优先级高的优先处理 代码实现
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
using namespace std;
//最小值优先升序处理使用动态数组vector递增参数排序相当于最小值优先
priority_queueint, vectorint, greaterint q;
//从小到大的优先级队列可将greater改为less即为从大到小,
int main()
{int i, n, ans 0, t1 0, t2 0, t3 0, x;cin n;for (i0;in;i){cin x; q.push(x); //进队把一个元素压入队尾}//所有元素压入队列中之后自动排序for (i n;i 1;i--) //合并次数共计n-1次{t1 q.top(); //取最小的元素q.pop(); //此元素出队列t2 q.top(); //取第二小的元素q.pop(); //此元素出队列t3 t1 t2; //合并果子数合并较小的2个ans t3; //求果子数目之和q.push(t3); //入队列//每一次循环都会自动排序}cout ans endl;return 0;
}结果
【3】vector操作以及应用
vector的几个核心接口
常用操作效果vectorc产生一个空的vetcorc.size()返回元素个数front()返回第一个元素的引用不检查元素是否存在back()返回最后一个元素的引用不检查元素是否存在begin()返回一个迭代器指向第一个元素end()返回一个迭代器指向最后一个元素之后c.insert(pos,e)在pos位置插入元素e的副本并返回新元素的位置c.push_back(e)在尾部添加一个元素e的副本c.pop_back(e)移除最后一个元素但不返回最后一个元素c.erase(pos)删除pos位置的元素返回下一个元素的位置c.clear()移除所有元素清空容器
利用vector完成随机排序
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include time.h
using namespace std;
void Swap(int a, int b)
{int c a;a b;b c;
}
void random_arrange(int a[], int len)
{int i;srand(time(NULL));for (i 0; i len; i){Swap(a[i], a[rand() % (i 1)]);}
}void print(int a[], int len)
{for (int i 0; i len; i)cout a[i] ;cout endl;
}int main(void)
{int a[] { 1,2,3,4,5,6,7,8,9 };int len sizeof(a) / sizeof(int);int i 0;cout before arrange endl;print(a, len);//random_arrange(a, len);vectorint se; //这里的vector要是换成set会报错while (se.size() len)se.push_back(a[i]);random_shuffle(se.begin(), se.end());cout after arrange endl;for (i 0; i len; i)cout se[i] ;cout endl;return 0;
}效果
【4】deuqe(双向队列)操作以及应用
deque(双向队列)和vector非常相似操作接口功能模块基本一致。它采用动态数组来管理元素提供随机存取可以在头尾两段快速插入和删除元素。
deuqe的特点以及核心接口 deque支持随机存取可以使用迭代器或[ ]符号 deque支持在头部和尾部存储数据 操作效果c,push_back(e)在尾部添加一个元素e的副本c.push_front(e)在头部添加一个元素e的副本c.pop_back()移除最后一个元素但不返回最后一个元素c.pop_front()移除第一个元素但不返回第一个元素
利用deuqe处理数据
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include time.husing namespace std;int main()
{//deque(int nSize,const T t):创建一个deque,元素个数为nSize,且值均为tdeque intd(10, 1);deque int::iterator it;int x, y;cin x y;d.push_front(y);d.push_back(x);cout d[0] d[0] endl;cout d[11] d[11] endl;cout d.front() d.front() endl;cout d.back() d.back() endl;for (it d.begin();it ! d.end();it){cout *it ;}cout endl;return 0;
}【5】list(双向链表)操作以及应用
list的特点
双向链表将元素按顺序存储在链表中。与动态数组vector相比它允许快速地插入与删除但是随机访问却比较慢。 特点 使用双向链表管理元素数据元素可以使任意类型T list只能通过迭代器遍历数据不支持随机存取不能使用[ ] 在任何位置上执行元素的插入和移除都非常快 双向链表实现数据的输入与求和
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include string
#include cstring
#include list
#includenumericusing namespace std;
listintlist1;
int main()
{listint::iterator iter;//从双向链表list1前面向容器中添加数据list1.push_front(5);list1.push_front(8);//从双向链表list1后面向容器中添加数据list1.push_back(7);list1.push_back(9);//从前向后显示list1中的数据cout list1 data endl;for (iter list1.begin();iter ! list1.end();iter){cout *iter ;}cout endl;//求和int result accumulate(list1.begin(),list1.end(),0);cout Sum result endl;return 0;
} 【6】map/multimap操作以及应用
map是STL关联式容器它提供映射关系第一个关键字第二个关键值的数据处理能力通常用它来快速处理映射相关的数据集map数据结构内部是一棵红黑树平衡二叉树它具有对数据自动排序的功能我们可以快速高效处理容器中的数据时间复杂度为logN。对于访问的迭代器来说仅能修改关键值不能修改key。
map/multimap的几个特点以及功能接口 元素包含两部分(key,value),key和value可以是任意类型 根据元素的key自动对元素排序因此根据元素的key可以进行很快定位 不能直接改变元素的key,可以通过[ ]直接存取元素值 map中不允许key相同的元素multimap允许key相同的元素 操作效果map.c产生空的mapc.size()返回元素个数count(key)返回键值key的元素个数find(key)返回键值key 的第一个元素找不到的话返回endlower_bound(key)返回键值key的第一个元素upper_bound(key)返回键值key的第一个元素equal_range(key)返回键值key的元素区间c.insert(pos,e)在pos位置为起点插入e的副本并返回新元素的位置c.erase(val)移除所有值为val的元素返回移除元素个数
map/multimap应用优惠购物
问题描述 某购物网站平台进行优惠活动每件商品当天第一个订单可以打75折。这天网站先后依次接受到了(N100 000)个订单订单的数据形式是:商品名价格(单价*数量)商品名是长度不超过20请按商品名字典序输出当天的每种商品名和其售出的总价。
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include iomanip //要用到格式控制符
using namespace std;
//声明映射变量m由m[string]映射double类型的数值
mapstring, doublem;
int main()
{string name;double val;int n;cin n;for (int i 1;i n;i){cin name val;//输入订单-商品名和价格if (m.count(name) 0) //如果是第一次出现m[name] val * 0.75; //打折m[name]映射了商品价格的数值elsem[name] val; //不打折}//构建了map类型迭代器指针mapstring, double::iterator it;cout 映射结果统计 endl;for (it m.begin();it ! m.end();it){//输出商品名和价格 2位浮点数cout it-first fixed setprecision(2) it-second endl;}return 0;
}【7】set/multiset(集合/多重集合)操作以及应用
set(集合)是将容器内所有元素都能更具其键值自动排序set元素的键值就是实值。set不允许两个元素有相同的键值multiset可以有相同的键值。
set/multiset的几个特点 set使用平衡二叉树管理元素红黑树 set的每个元素值必须唯一系统会自动将数据排序。他支持插入、删除、查找等操作所有的操作都在logN时间之内完成效率比较高。 set和multiset的区别是set插入的元素不能相同而multiset可以相同 操作指令同map 利用set完成随机数的产生以及排序
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
using namespace std;
//生成n个指定范围a~b中的不重复随机数ab10000
int main()
{setints;int n, a, b,x;cin n a b;while (s.size() n){x rand() % (b - a 2) a; //产生的随机数s.insert(x); //在集合中插入元素自动去重处理 }cout 输出默认升序去重 endl;setint::iterator it1; //正向迭代器for (it1 s.begin();it1 ! s.end();it1)cout *it1 ;cout endl;return 0;
}总结
无
