logo
i囡漫笔
NEWS LETTER

STL 线性结构

  • Home
  • STL-linear-structure.html
Scroll down

问题引入

如何输出6的二进制数？

分析问题

问题->解决方案->实现方案->编写

即

从问题得到解决方案（解决方案（具体步骤（过程可以问专业专家）））

实现方案有哪几种方法，并进行优化

编写代码

解决方案

整数

十进制整数转换为二进制整数采用”除2取余，逆序排列”法。

具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

实现方案

一、使用stack【栈】输出

因为 将得到的余数作为二进制数的高位有效位依次排列起来 的过程需要后进先出，所以我们使用栈进行输出

老师给出代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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型）

1
2
3
4
5
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();

1
2
3
4
while(!r.empty()){	// empty()只返回真假值，栈空返回1，否则返回0 
	printf("%d",r.top());//top有返回值，而pop没有返回值 ，//用stack倒叙输出 
	r.pop();		
}

优化

我们发现，在输出时候，我们并没有输出双向链表std::list<int> q;，

所以我们可以判断，双向链表是多余的，需要优化（但是思考实现方案的时候不能不考虑到双向链表）

我们把list相关代码删除（或注释）

得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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函数，具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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)

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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具有数组特性，我们可以使用数组的方法进行输出 （不建议）

即使用

1
2
for(int i=r.size();i>0;--i)
		printf("%d",r[i]) ;

得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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 两端添加或删除元素的开销很小，它不需要重新分配空间。

具体模型见下图：

image-20220522141449464

他能支持上述所有方式：

1）使用r.push_back(n%2);加上reverse

2）使用r.push_back(n%2);利用属性改为rbigin，rend

3）使用r.push_front(n%2);

4）具有数组特性，可以使用数组的方法进行输出 （不建议）

推荐文章
站内
推荐 (5.0%)
6分钟

Hexo博客EJS主题的相关文章智能推荐插件hexo-article-recommender进阶配置（DIY）

DIY客制化文章底部“文章推荐模块”，本篇文章介绍EJS模板的hexo主题如何实现。hexo-article-recommender为Hexo博客提供本地化智能

1
i囡漫笔
随心漫笔写文章
站内
推荐 (5.0%)
6分钟

Hexo博客NJK主题的相关文章智能推荐插件hexo-article-recommender进阶配置（DIY）

DIY客制化文章底部“文章推荐模块”，本篇文章介绍Nunjucks（NJK）模板的hexo主题（如NexT主题）如何实现。hexo-article-recomm

2
i囡漫笔
随心漫笔写文章
站内
推荐 (5.0%)
6分钟

Hexo博客文章底部添加推荐相关文章：使用hexo-article-recommender插件实现

hexo-article-recommender为Hexo博客提供本地化智能文章推荐：融合语义、标题、标签、分类与发布时间五维特征，支持三种策略切换，自动生成带

3
i囡漫笔
随心漫笔写文章
站内
推荐 (4.2%)
14分钟

Java 数组—JAVA语言基础

数组是最为常见的一种数据结构，是相同类型的用一个标识符封装到一起的基本类型数据序列或对象序列。
（本文章参考《Java从入门到精通 第5版 明日科技》。

4
本站作者
原创文章

--- over ---

其他文章
目录导航 置顶
  1. 1. 问题引入
  2. 2. 分析问题
  3. 3. 解决方案
    1. 3.1. 整数
  4. 4. 实现方案
    1. 4.1. 一、使用stack【栈】输出
    2. 4.2. 二、使用list【链式存储】输出
    3. 4.3. 三、vector【顺序存储，数组】输出
    4. 4.4. 四、双端队列deque【deque 是 double-ended queue 的缩写，又称双端队列容器。】
请输入关键词进行搜索
  • to close