【数据结构】第3章 栈和队列 数制的转换(栈)
用栈实现【10->非10】进制的数制转换
·
【算法分析】
将一个十进制整数N转换为八进制数时,在计算过程中,把 N 与 8求余得到的八进制数的各位依次进栈,计算完毕后将栈中的八进制数依次出栈输出,输出结果就是待求得的八进制数。
例如:(1348)10 = (2504)8, 其运算过程如下:
//数制的转换_10->8 O(log8n)
void conversion(int N)
{//对于任意一个非负十进制数,输出与其等值的八进制数
if(N == 0)
{
cout<<0;
return;
}
InitStack(S);
while(N)
{
Push(S, N % 8);
N = N / 8;
}
while(!StackEmpty(S))
{
SElemType e;
Pop(S, e);
cout<<e;
}
}
【完整代码】
#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int SElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1
//------顺序栈的存储结构-----
#define MAXSIZE 100
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;
SqStack S;
//1、顺序栈初始化
Status InitStack(SqStack &S)
{//构造一个空栈S
S.base = new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base)
exit(OVERFLOW); //储存分配失败
S.top = S.base; //top初始为base,空栈
S.stacksize = MAXSIZE;
return OK;
}
//4、顺序栈判空
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return OK;
else
return ERROR;
}
//7、顺序栈入栈
Status Push(SqStack &S, SElemType e)
{//插入元素e为新的栈顶元素
if(S.top - S.base == S.stacksize)
return ERROR; //栈满
*S.top++ = e; //先将元素e压入栈顶,再栈顶指针+1
return OK;
}
//8、顺序栈出栈
Status Pop(SqStack &S, SElemType &e)
{//删除S的栈顶元素,用e返回其值
if(S.top == S.base)
return ERROR; //栈空
e = *--S.top; //先栈顶指针-1,再将栈顶元素赋给e
return OK;
}
//数制的转换_10->8 O(log8n)
void conversion(int N)
{//对于任意一个非负十进制数,输出与其等值的八进制数
if(N == 0)
{
cout<<0;
return;
}
InitStack(S);
while(N)
{
Push(S, N % 8);
N = N / 8;
}
while(!StackEmpty(S))
{
SElemType e;
Pop(S, e);
cout<<e;
}
}
int main()
{
int n;
while(cin>>n)
{
conversion(n);
cout<<ends;
}
return 0;
}

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。
更多推荐
所有评论(0)