顺序栈实现十进制转成R进制

不念不忘少年蓝@ 2022-07-16 13:29 228阅读 0赞

2016年7月31日13:53:37
        利用顺序栈实现十进制整数转换转换成r进制
        1、算法思想
        将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下：
        N         N / 8 （整除）        N  % 8（求余）
        3456          432                    0                  低
        432           54                     0
        54            6                      6
        6            0                       6                  高
        所以：（3456）10  =（6600）8
        我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。
        算法思想如下：当N>0时重复1，2
        ①若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。
        ②用N / r 代替 N

#include<stdio.h>
    #define MAXSIZE 100
    #define X 2
    
    //顺序栈的结构体类类型
    typedef struct  
    {
        int data[MAXSIZE];
        int top;
    }SeqStack;
    
    //函数前置声明
    void initSeqStack(SeqStack * S);
    int  isEmpty(SeqStack * S);
    void pushStack(SeqStack * S,int element);
    int  popStack(SeqStack * S,int element);
    void conversion(SeqStack * S,int N);
    void traverseStack(SeqStack * S);
    
    //初始化顺序栈
    void initSeqStack(SeqStack * S)
    {
        S->top = -1;
        return ;
    }
    
    //判断栈是否为空
    int isEmpty(SeqStack * S)
    {
        if(-1 == S->top)
            return 1;
        else
            return 0;
    }
    
    //判断栈是否为满
    int  isFull(SeqStack * S)
    {
        if(MAXSIZE == S->top)
            return 1;
        else
            return 0;
    }
    
    //顺序栈的压栈操作
    void pushStack(SeqStack * S,int element)
    {
        if( isFull(S) )
        {
            printf("栈已满,无法继续压栈!\n");
            return ;
        }
        else
        {
            S->top++;
            S->data[S->top] = element;
            /* S->data[++S->top] = element; */
            return;
        }
    }
    
    //顺序栈的出栈操作
    void popStack(SeqStack * S,int * element)
    {
        if( isEmpty(S) )
        {
            printf("栈已空,无法继续出栈!\n");
            return ;
        }
        else
        {
            *element = S->data[S->top];
            S->top--;
            return ;
        }
    }
    
    //进制转换
    void conversion(SeqStack * S,int number)
    {
        int restNumber;
        /* while(restNumber) { restNumber = number%X; pushStack(S,restNumber); restNumber = restNumber/X; } */
        do 
        {
            restNumber = number%X;
            pushStack(S,restNumber);
            number = number/X;
        } while (number);
        return;
    }
    
    //顺序栈的遍历操作
    void traverseStack(SeqStack * S)
    {
        int i;
        int j = 0;
        if(isEmpty(S))
        {
            printf("栈为空!\n");
            return;
        }
        for(i = S->top;i>=0;i--)
        {
            if(!(j%4))
                printf(" ");
            printf("%d",S->data[i]);
            j++;
        }
        return ;    
    }
    
    //主函数
    int main(void)
    {
        SeqStack S; 
        int number;
    
        initSeqStack(&S);
        printf("请输入一个十进制整数:\n");
        scanf("%d",&number);
        conversion(&S,number);
        printf("它的%d进制值为:",X);
        traverseStack(&S);
        printf("\n");
        return 0;
    }