【数据结构】栈和队列之练习题(用栈实现进制转换)

1.利用栈的数据结构特点，将二进制转换为十进制数

分析

由于栈具有先进后出的特性，我们输入11001001的二进制数，出栈的顺序就相反，将每个出栈的数带入进制转换公式得到的结果就是转换之后的十进制数

完整代码

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

#define STACK_INIT_SIZE 20
#define STACKINCREMENT  10

typedef char ElemType;
typedef struct {

    ElemType * base;
    ElemType * top;
    int stackSize;
}sqStack;

/**
 * 初始化
 */
void InitStack(sqStack * s){

    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base)
        exit(0);
    
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

/**
 * 进栈
 */
void Push(sqStack * s, ElemType e){
    
    if (s->top - s->base >= s->stackSize) {  // 栈满，扩大空间
        
        s->base = (ElemType *)realloc(s->base, (s->stackSize * STACKINCREMENT) * sizeof(ElemType));
        
        if (!s->base)
            exit(0);
        s->top = s->base + s->stackSize;  // 设置栈顶
        s->stackSize = s->stackSize + STACKINCREMENT;  // 设置栈的最大容量
    }
    
    *(s->top) = e;
    s->top++;
    
}

/**
 * 出栈
 */
void Pop(sqStack * s, ElemType *e){
    
    if (s->top == s->base)  // 栈空
        return;
    s->top--;        // 栈顶指针减1
    *e = *(s->top);  // 将要删除的栈顶元素赋值给e
//    *e = *--(s->top);
    
}

/**
 * 获取栈的当前容量
 */
int StackLen(sqStack s){
    
    return (int)(s.top - s.base);
}



int main(int argc, const char * argv[]) {
    
    ElemType e;
    sqStack s;
    
    int len,i,sum = 0;
    
    // 初始化栈
    InitStack(&s);
    
    printf("请输入二进制数，输入#号表示结束！\n");
    scanf("%c",&e);
    
    while (e != '#') {
        Push(&s, e);
        scanf("%c", &e);
    }
    
    getchar(); // 把‘\n’从缓冲区去掉
    
    len  = StackLen(s);
    printf("栈的当前容量是：%d\n", len);
    
    for (i = 0; i < len; i++) {
        
        Pop(&s, &e);
        sum = sum + (e-48) * pow(2, i); // 这里是ASCII码，所以要减去48
    }
    
    printf("转化为十进制数是：%d\n", sum);
    return 0;
}

输出结果

二进制转换为十进制