摘要：本文介绍栈的工作原理，以及一步一步手把手教做一个进制转换的题目，主要面向学数据结构的新同学
有那么一道题目，从键盘接收需要转换的十进制数以及要转换成的数制（如将1000转换为八进制，则接收1000和8两个整数；将1250转换为二进制，则接收1250和2两个整数），要求使用栈来写。
当我们拿道这个题目的时候，首先我们先直接按照我们的常规思维来做一下，代码是这样的
常规思维：
将源数据求以所求进制数的余，然后再除以进制数，循环多次直到源数据得零，即算完成。
代码1：
#include<bits/stdc++.h>
using namespace std;
const int Max=1e6+5;
int main(){
int orign,n,i=0; //orign原数，n需要转换的进制数,i循环控制
char change[Max];
memset(change,0,Max);
cin>>orign>>n;
while(orign>0) {
change[i]=orign%n+'0';
orign=orign/n;
i++;
}
for(i=i-1; i>=0; i--)
cout<<change[i];
return 0;
}但是我们会发现一个问题，就是，这样来写显示上面会发现只能输出十进制转换为低于十进制的数字，无法转换为高于十进制的数，如图：
（10进制转换为8进制转换正常↑）
（10进制转换为8进制转换异常↑）
这是由于我们使用char来储存转换过后的代码的原因，利用字符串/字符数组的方式可以很方便的表示位数，同时这也是大数加法，乘法等大数据处理的方式，相当的方便，但由于字符是使用ASCII码来存储表示的，我们存进去的数字其实只是表示一个值，而真正在char字符中显示的是根据这个值对应的ASCII表显示的字符，比如输入33对应的字符就是！
根据ASCII码表，高于10之后会出现一些奇怪的字符，不能很方便的表示十六进制，以及32进制等高进制的数，这也是这行代码change[i]=orign%n+'0';为什么要+'0'的原因，如果不加'0'，字符数组里面的数就是一堆表情了。
（附上一个ASCII码表，图源自百度百科）
有什么办法可以解决这个办法呢？
当然有，最为简单直白且粗暴的方式之一就是【打表】，建立一个表，使我们输入的每一个数字都有一一对应的进制数表示，比如说我们呢输入11，直接对应一个A就是表示32/16进制中的11。
我们可以建立一个字符数组来储存这些东西，然后取下标直接输出即可，但是这里我介绍一个新的东西，C++中的STL库：
STL是Standard Template Library的简称，中文名标准模板库。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用安装额外的库文件。
STL的版本很多，常见的有HP STL、PJ STL、 SGI STL等。
在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。
可以见的，STL库基本包囊了所有的我们常用的数据结构的功能，在这里我介绍一个叫做字典（map）的数据结构，
map 是一种容器，用来存储若干元素，这些元素都是由关键值 (Key Value，以下称为 Key 值) 和映射值 (Mapped Value，以下依旧称为映射值) 配对组成的，具体说明如下：
在一个 map 中， Key 值通常用来排序或特指元素，映射值用来存储与该 Key 值绑定的内容。 Key 值与映射值的数据类型可以不同，而且可以一起被放进成员类型 value_type 中，value_type 是一种配对类型，定义如下：
typedef pair<const Key, T> value_type;
其自带包含了很多常用的功能函数，其中常用的有
clear
清除 map 中所有元素；
erase
删除 map 中指定位置的元素；
insert
在 map 指定位置添加 pair 类型的元素；
find
获取 map 中元素的迭代器；
begin, end
map 的正向迭代器的起始位置与终点位置；
rbegin, rend
map 的反向迭代器的起始位置与终点位置；
我们利用insert的方法进行插入，废话不多说，直接把现成的代码上上来！
代码2：
#include<bits/stdc++.h>
using namespace std;
const int Max=1e6+5;
map<int,char> map32f; //使用map结构创建32进制搜索表
map<int,char>::iterator iter; //用于便利，本题也可以去掉
void loading_map() { //当然是打表万岁啦
map32f.insert(pair<int,char>(0,'0'));//插入0，'0'，也就是说输入0，将会返回'0'
map32f.insert(pair<int,char>(1,'1'));
map32f.insert(pair<int,char>(2,'2'));
map32f.insert(pair<int,char>(3,'3'));
map32f.insert(pair<int,char>(4,'4'));
map32f.insert(pair<int,char>(5,'5'));
map32f.insert(pair<int,char>(6,'6'));
map32f.insert(pair<int,char>(7,'7'));
map32f.insert(pair<int,char>(8,'8'));
map32f.insert(pair<int,char>(9,'9'));
//十进制内
map32f.insert(pair<int,char>(10,'A'));
map32f.insert(pair<int,char>(11,'B'));
map32f.insert(pair<int,char>(12,'C'));
map32f.insert(pair<int,char>(13,'D'));
map32f.insert(pair<int,char>(14,'E'));
map32f.insert(pair<int,char>(15,'F'));
//十六进制区
map32f.insert(pair<int,char>(16,'G'));
map32f.insert(pair<int,char>(17,'H'));
map32f.insert(pair<int,char>(18,'J'));
map32f.insert(pair<int,char>(19,'K'));
map32f.insert(pair<int,char>(20,'L'));
map32f.insert(pair<int,char>(21,'M'));
map32f.insert(pair<int,char>(22,'N'));
map32f.insert(pair<int,char>(23,'P'));
map32f.insert(pair<int,char>(24,'Q'));
map32f.insert(pair<int,char>(25,'R'));
map32f.insert(pair<int,char>(26,'T'));
map32f.insert(pair<int,char>(27,'U'));
map32f.insert(pair<int,char>(28,'V'));
map32f.insert(pair<int,char>(29,'W'));
map32f.insert(pair<int,char>(30,'X'));
map32f.insert(pair<int,char>(31,'Y'));
//三十二进制区
}
int main() {
loading_map();
int orign,n,i=0; //orign原数，n需要转换的进制数,i循环控制
char change[Max];
memset(change,0,Max);
cin>>orign>>n;
while(orign>0) {
change[i]=map32f[orign%n];
orign=orign/n;
i++;
}
for(i=i-1; i>=0; i--)
cout<<change[i];
return 0;
}
/*
32进制表
0-9，
A-10/B-11/C-12/D-13/E-14/F-15
G-16/H-17/J-18/K-19/L-20/M-21
N-22/P-23/Q-24/R-25/T-26/U-27
V-28/W-29/X-30/Y-31
注：
① 26个字母中去除【I、O、S、Z】
② 32进制可作为日期的表示
*/
/*
16进制表
0~9，
A-10/B-11/C-12/D-13/E-14/F-15
*/注明一下：32进制表示方法有一些异议，有些地方的表示方法使超过9使用A~U的表示法，而有一些则采用24个字母去除“IOSZ”这4个字母的方法，这里我查阅资料，个人选择还是用后者。
可以见的，其实本题中没有什么大的变化，除了而外建立一个表，可以表示32进制数字了而已。
接下来讲讲栈，透过本题，我们发现如果我们输出已经进行好了进制转换的数字之后需要逆序输出存进去的数字，这样的思维无疑（当然强行）和’栈‘这一数据结构非常相似，栈的输出也是只能自顶向下的进行（逆序）。
拿出栈的概念来看看
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
（栈的操作——入栈push和出栈pop，图来自百度百科）
就着这一概念，我们试着建立一个关于栈的数据结构：
代码3：
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node {
char data; //用字符型表示进制数更好表示高进制的
struct node *next;
} Node;
typedef struct stack {
Node *top;
int count;
} Link_Stack;
//创建栈
Link_Stack *Creat_stack() {
Link_Stack *p;
p= new Link_Stack;
p->count=0;
p->top=NULL;
return p;
}
//入栈 push
Link_Stack *Push_stack(Link_Stack *p,char elem) {
if(p==NULL)
return NULL;
Node *temp;
temp = new Node;
temp->data=elem;
temp->next=p->top;
p->top=temp;
p->count++;
return p;
}
//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p) {
Node *temp;
temp = p->top;
if(p->top==NULL) {
cout<<"Error:The stack is empty."<<endl;
return p;
} else {
p->top=p->top->next;
delete temp;
p->count--;
return p;
}
}
//遍历栈：输出栈中所有元素
int show_stack(Link_Stack *p){
Node *temp;
temp=p->top;
if(p->top==NULL){
cout<<"Error: The stack is empty."<<endl;
return 0;
}
while(temp!=NULL){
cout<<temp->data;
temp=temp->next;
}
cout<<endl;
return 0;
}
int main(){ //用主函数测试一下功能
Link_Stack *p;
p=Creat_stack();
int n=5;
char input[6]="ABCDE";
while(n--){
Push_stack(p,input[n]);
}
show_stack(p);
Pop_stack(p);
show_stack(p);
return 0;
}用主函数进行测试，创建一个栈，进行测试性的调用，顺序输入EDCBA，同时去除栈顶元素"A",输出栈，结果输出BCDE，正符合预期。
创建栈基本完成，我们就该详细的来写出这一个功能了，还是老规矩，先打表让32进制得以表示，再把栈和需求结合.
突然发现字数到上线了，开两个帖子好了。
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复