【数据结构】第3章栈和队列数制的转换（栈）

浅浅的花香味﹌ 2022-11-27 12:18 161阅读 0赞

【算法分析】  
将一个十进制整数N转换为八进制数时，在计算过程中，把 N 与 8求余得到的八进制数的各位依次进栈，计算完毕后将栈中的八进制数依次出栈输出，输出结果就是待求得的八进制数。  
例如：(1348)10 = (2504)8, 其运算过程如下：  
![在这里插入图片描述][20200815161556331.png_pic_center]

//数制的转换_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;
    }

![在这里插入图片描述][2020081516302339.png_pic_center]

[20200815161556331.png_pic_center]: /images/20221124/f2cb4faae892471ea0e0ed835b4d1e9a.png
[2020081516302339.png_pic_center]: /images/20221124/9e0c1c203dce4a7b9430ccc84ee1d5bc.png