引入

我们学习了栈的基本操作，今天我们就看看，栈能为我们做哪些服务，以及如何灵活的使用栈的这些特性。我们就从二进制数转换为十进制数的例子说起。

方法

首先，我们先说明一下二进制转十进制的公式

公式 $n\times 2^{n-1}$

N 表示二进制的从右向左的位数，然后把所有位的和相加，就是十进制结果。

演示
二进制数：$100101$
第 1 位：$1 \times 2^{1-1}=1 \times 1=1$
第 2 位：$0 \times 2^{2-1}=0 \times 2=0$
第 3 位：$1 \times 2^{3-1}=1 \times 4=4$
第 4 位：$0 \times 2^{4-1}=0 \times 8=0$
第 5 位：$0 \times 2^{5-1}=0 \times 16=0$
第 6 位：$1 \times 2^{6-1}=1 \times 32=32$
结果是：$1+0+4+0+0+32=37$
其实就是计算非零数相加。

代码实现

清楚了计算方法之后，我们就通过代码来看看如何实现这个功能

初始化栈

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LEN sizeof(int)
#define SLEN sizeof(struct Stack)
#define MAXSIZE 100
#define INCREMENT 10

struct Stack{
    int *top;
    int *base;
    int num;
};

struct Stack *init(struct Stack *s){
    s->base=(int *)malloc(MAXSIZE*LEN);
    s->top=s->base;
    s->num=MAXSIZE;
    return s;
}

压栈、出栈、栈长

然后我们写三个函数，能够压栈、出栈、栈长

void push(struct Stack *s , char data){
    if(s->top-s->base>=s->num){
        s->base=(int *)realloc(s->base,(s->num+INCREMENT)*LEN);
        s->top=s->base+s->num;
        s->num=s->num+INCREMENT;
    }
    *(s->top)=data;
    s->top++;
}

int pop(struct Stack *s){
    if(s->top-s->base==0){
        return 0;
    }
    return *--(s->top);
}

int length(struct Stack *s){
    return s->top-s->base;
}

二进制转换

然后是二进制转换

  • 根据栈长判断要转换多少位
  • 从右向左转换，正好是栈后入先出的顺序
  • 因为 push 压入的是 char 类型，所以要减去48，转换成数字
  • 然后利用 pwo 函数，计算指数
int translate(struct Stack *s){
    if(s->top-s->base==0){
        return 0;
    }
    int sum=0,n=0,len=length(s);
    for(int i=0;i<len;i++){
        n=pop(s);
        sum = sum+(n-48)*pow(2,i);
    }
    return sum;
}

main 函数主调

int main(){
    struct Stack *s;
    char n;
    s=(struct Stack *)malloc(SLEN);
    s=init(s);    //初始化栈
    printf("请输入二进制数：\n");
    scanf("%c",&n);
    //利用 while 循环批量输入数值
    while(n!='#'){
        push(s,n);  //压栈
        scanf("%c",&n);  //再次要求输入
    }
    getchar();  //这里的 getchar 是为了接收回车符的
    
    printf("栈的容量是：%d\n",length(s));
    printf("十进制数为：%d\n",translate(s));
    return 0;
}

全部代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LEN sizeof(int)
#define SLEN sizeof(struct Stack)
#define MAXSIZE 100
#define INCREMENT 10

struct Stack{
    int *top;
    int *base;
    int num;
};

struct Stack *init(struct Stack *s){
    s->base=(int *)malloc(MAXSIZE*LEN);
    s->top=s->base;
    s->num=MAXSIZE;
    return s;
}

void push(struct Stack *s , char data){
    if(s->top-s->base>=s->num){
        s->base=(int *)realloc(s->base,(s->num+INCREMENT)*LEN);
        s->top=s->base+s->num;
        s->num=s->num+INCREMENT;
    }
    *(s->top)=data;
    s->top++;
}

int pop(struct Stack *s){
    if(s->top-s->base==0){
        return 0;
    }
    return *--(s->top);
}

int length(struct Stack *s){
    return s->top-s->base;
}

int translate(struct Stack *s){
    if(s->top-s->base==0){
        return 0;
    }
    int sum=0,n=0,len=length(s);
    for(int i=0;i<len;i++){
        n=pop(s);
        sum = sum+(n-48)*pow(2,i);
    }
    return sum;
}

int main(){
    struct Stack *s;
    char n;
    s=(struct Stack *)malloc(SLEN);
    s=init(s);
    
    printf("请输入二进制数：\n");
    scanf("%c",&n);
    while(n!='#'){
        push(s,n);
        scanf("%c",&n);
    }
    getchar();
    printf("栈的容量是：%d\n",length(s));
    printf("十进制数为：%d\n",translate(s));
    return 0;
}

输出结果
请输入二进制数：
10010#
栈的容量是：5
十进制数为：18

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。