STL 线性结构
如果写c++程序那么STL容器是不可避免要使用的，而正确合理地使用这些容器才能够简化我们的程序、提高运行的效率，所以本篇根据2022-05-22《数据结构课程设计》来记录 STL线性结构 笔记
问题引入
如何输出6的二进制数？
分析问题
问题->解决方案->实现方案->编写
即
从问题得到解决方案（解决方案（具体步骤（过程可以问专业专家）））
实现方案有哪几种方法，并进行优化
编写代码
解决方案
整数
十进制整数转换为二进制整数采用”除2取余，逆序排列”法。
具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。
实现方案
一、使用stack【栈】输出
因为 将得到的余数作为二进制数的高位有效位依次排列起来 的过程需要后进先出，所以我们使用栈进行输出
老师给出代码如下
#include<cstdio>
#include<list>
#include<stack>
main(){
std::list<int> q; //定义（双向）链表（被除数q） #include<list>
std::stack<int> r;//定义栈（余数r） #include<stack>
int n;
scanf("%d",&n);
while(n!=0){
q.push_back(n/2); //push_back链表的后面插入
r.push(n%2); //push余数压入栈
n=n/2;
}
while(!r.empty()){ // empty()只返回真假值，栈空返回1，否则返回0
printf("%d",r.top());//top有返回值，而pop没有返回值 ，//用stack倒叙输出
r.pop();
}
return 0;
}
其中std::list<int> q; 定义（双向）链表 来记录商q；std::stack<int> r 定义 栈 来记录余数r，定义n来表示操作数（要变为2进制的数）
利用循环1来“压进”处理的数据：将商压进 链表的后面（q.push_back(n/2)）；将余数 压入栈 r.push(n%2); ；随后将n/2向下取整（int型）
while(n!=0){
q.push_back(n/2); //push_back链表的后面插入
r.push(n%2); //push余数压入栈
n=n/2;
}
利用循环2来输出：将 压入栈 r.push(n%2); 的元素从栈顶输出printf("%d",r.top());随后销毁栈顶元素[目的是为了让下一个元素输出]r.pop();
while(!r.empty()){ // empty()只返回真假值，栈空返回1，否则返回0
printf("%d",r.top());//top有返回值，而pop没有返回值 ，//用stack倒叙输出
r.pop();
}
优化
我们发现，在输出时候，我们并没有输出双向链表std::list<int> q;，
所以我们可以判断，双向链表是多余的，需要优化（但是思考实现方案的时候不能不考虑到双向链表）
我们把list相关代码删除（或注释）
得到
#include<cstdio>
//#include<list>
#include<stack>
main(){
// std::list<int> q; //定义（双向）链表（被除数q） #include<list>
std::stack<int> r;//定义栈（余数r） #include<stack>
int n;
scanf("%d",&n);
while(n!=0){
// q.push_back(n/2);商（不用输出） //push_back链表的后面插入
r.push(n%2); //push余数压入栈
n=n/2;
}
while(!r.empty()){ // empty()只返回真假值，栈空返回1，否则返回0
printf("%d",r.top());//top有返回值，而pop没有返回值 ，//用stack倒叙输出
r.pop();
}
return 0;
}
二、使用list【链式存储】输出
具有三种实现list输出方案：
1）使用r.push_back(n%2);加上reverse
因为 将得到的余数作为二进制数的高位有效位依次排列起来 的过程需要后进先出，若我们需要使用list【链式存储】输出，要先将链式存储的顺序进行交换
那么我们需要用到的是reverse函数，具体代码如下
#include<cstdio>
#include<list>
main(){
std::list<int> r;
int n;
scanf("%d",&n);
while(n!=0){
r.push_back(n%2);
n=n/2;
}
reverse(r.begin(),r.end());//【或者】r.reverse;
//auto *i;auto:自动类型推倒//std::list<int>::iterator ;
for(auto i=r.begin();i!=r.end();++i)
printf("%d",*i) ;
return 0;
}
其中reverse(r.begin(),r.end());为交换顺序函数，将链表排序颠倒（1,2,3->3,2,1）
在输出时，我们要用到类似指针的i，但是它的类型我们并不知道（或者不想写），那么我们使用auto i，让编译器自动识别
不过在使用时需要如下配置
2）使用r.push_back(n%2);利用属性改为rbigin，rend
利用双向链表的属性，我们可以重后往前输出
注意：双向链表不是数列，不能将上述for(auto i=r.begin();i!=r.end();++i)用for(auto i=r.end();i!=r.begin();i--)，而是要将r.begin()改为r.rbegin，r.end改为r.rend,即改为for(auto i=r.rbegin();i!=r.rend();++i)
具体代码如下
#include<cstdio>
#include<list>
main(){
std::list<int> r;
int n;
scanf("%d",&n);
while(n!=0){
r.push_back(n%2);
n=n/2;
}
//auto *i;auto:自动类型推倒//std::list<int>::iterator ;
for(auto i=r.rbegin();i!=r.rend();++i)// begin变成rbegin， end改为rend，双向链表从后向前读取
printf("%d",*i) ;
return 0;
}
3）使用r.push_front(n%2);
将得到的余数作为二进制数的高位有效位依次排列起来 的过程需要后进先出，我们还可以在插入时从链表头插入r.push_front(n%2)
#include<cstdio>
#include<list>
main(){
std::list<int> r;
int n;
scanf("%d",&n);
while(n!=0){
push_front(n%2); // push_front(n%2)（从前插入）顺序等于reverse(r.begin(),r.end())【或者】;数序颠倒，1,2,3->3,2,1 ,
n=n/2;
}
for(auto i=r.begin();i!=r.end();++i)
printf("%d",*i) ;
return 0;
}
三、vector【顺序存储，数组】输出
同使用list【链式存储】输出一样，我们可以
1）使用r.push_back(n%2);加上reverse
方法同list，只不过将list替换为vector
2）使用r.push_back(n%2);利用属性改为rbigin，rend
方法同list，只不过将list替换为vector
但是我们不能使用r.push_front(n%2); ，因为vector作为顺序存储（数组），不能从头输入，只能从尾输入。即没有r.push_front()
vector具有数组特性，我们可以使用数组的方法进行输出 （不建议）
即使用
for(int i=r.size();i>0;--i)
printf("%d",r[i]) ;
得到：
#include<cstdio>
#include<vector>
main(){
std::vector<int> r;
int n;
scanf("%d",&n);
while(n!=0){
r.push_back(n%2);
n=n/2;
}
for(int i=r.size();i>0;--i)
printf("%d",r[i]) ; //数组从r[max]输出到r[1](r[0]为空)
return 0;
}
四、双端队列deque【deque 是 double-ended queue 的缩写，又称双端队列容器。】
和 vector 不同的是，deque 还擅长在序列头部添加或删除元素
deque的内存模型相比于vector与list要复杂许多，它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小，它不需要重新分配空间。
具体模型见下图：
他能支持上述所有方式：
1）使用r.push_back(n%2);加上reverse
2）使用r.push_back(n%2);利用属性改为rbigin，rend
3）使用r.push_front(n%2);
4）具有数组特性，可以使用数组的方法进行输出 （不建议）
本文作者：i囡漫笔
版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
本文链接：https://kcsj.i-nmb.cn/STL-linear-structure.html