栈的应用之数制转换

栈的应用之数制转换
16年2月29日19:46:56
/*
 *==============================================================================
 *
 * Filename: 3.2.c
 *
 * Description: 数制转换
 *
 * Version: 1.0
 * Created: 2016年02月29日 19时07分33秒
 * Revision: none
 * Compiler: gcc
 *
 * Author: ZER0 (ybx), [e-mail]
 * Organization: TJPU
 *
 *==============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define STACK_INIT_SIZE 10
#define STACK_INCREMENT 2

typedef struct {
    int *top;
    int *base;
    int stacksize;
}Stack;

int * InitStack(Stack *S)
{
    S->base = (int *)malloc(sizeof(int) * STACK_INIT_SIZE);
    if (!S->base)
    {
        printf("Can not malloc memory for Stack.\n");
        exit(-1);
    }

    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;

    return S->base;
}

void Push(Stack *S, int val)
{
    if ((S->top - S->base) > S->stacksize)
    {
        S->base = (int *)realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(int));
        if (!S->base)
        {
            printf("Can not realloc memory for Stack.\n");
            exit(-1);
        }

        S->top = S->base + S->stacksize;
        S->stacksize += STACK_INCREMENT;
    }

    *(S->top) = val;
    S->top++;
}

int Pop(Stack *S, int *val)
{
    if (S->top == S->base)
    {
        printf("The stack is empty.\n");
        exit(-1);
    }

    *val = *(--S->top);
    return 1;
}

void TraverseStack(Stack S)
{
    while (S.top > S.base)
    {
        printf("%d ", *--S.top);
    }

    printf("\n");
}

int main(int argc, char const *argv[])
{
    Stack S;
    int n, N;
    int val;

    InitStack(&S);

    printf("Please input the number you want to change: \n");
    scanf("%u", &n);

    printf("Please input the decimal you want change to : (2/8/10/16)\n");
    scanf("%u", &N);

    while(n)
    {
        Push(&S, n % N);
        n = n / N;
    }

    printf("The answer is :\n");

    while(!(S.top == S.base))
    {
        Pop(&S, &val);
        if (val <= 9)
        {
            printf("%d", val);
        }
        else
        {
            printf("%c", val + 55);
        }
    }

    printf("\n");

    return 0;
}

关于数制转换的问题，最好的解决方法就是通过栈的方式，因为仔细思考数学上面是怎么计算数值之间的进制转换的？？比如说想要到十进制的123转换成二进制，怎么求这个二进制呢？？用123不断地除以2，直到0为止，然后从后往前输出每一个得数。这样的方式正好符合栈的性质：先进后出。以上就是源程序，对于16进制，我们把大于10的数用字母来表示。