数据结构-栈之二进制转十进制和八进制

柔情只为你懂 2022-05-04 00:28 55阅读 0赞

栈满则后进先出原则，我们可以利用此特性实现二进制转十进制、二进制转八进制、二进制转十六进制等相关操作，废话不多说，直接上代码。

二进制转十进制：

//
    // Created by Administrator on 2018/5/28.
    //
    
    //二进制转十进制
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    
    #define ElementType int
    #define MaxSize 10
    
    定义栈的结构体
    typedef struct {
        ElementType *top;//栈顶指针（这里定义为指向栈顶元素的下一个位置，即为空）
        ElementType *base;//栈底指针
        int stackSize;//栈的容量
    } Stack;
    
    /**
     *  初始化栈
     * @param s
     */
    void InitStack(Stack *s) {
        //初始化分配栈的总空间
        s->base = (ElementType *) malloc(MaxSize * sizeof(ElementType));
        if (!s->base) {
            //分配失败
            exit(0);
        }
        s->top = s->base;
        s->stackSize = MaxSize;
    }
    
    /**
     * 入栈
     * @param s 栈
     * @param e 入栈元素
     */
    void Push(Stack *s, ElementType e) {
        //判断栈是否已满
        if (s->top - s->base >= s->stackSize) {
            //栈已满
            //处理方式1.递增空间 2.退出
            printf("栈已满~\n");
            exit(0);
        }
        *(s->top) = e; //赋值
        s->top++;
    }
    
    /**
     * 出栈
     * @param s 栈
     * @return
     */
    ElementType Pop(Stack *s) {
        //判断栈是否为空
        if (s->base == s->top) {
            //栈为空
            printf("不好意思，栈目前为空~\n");
            exit(0);
        }
        s->top--;
        ElementType e = *(s->top);//取值，并不是取地址
        return e;
    }
    
    /**
     * 释放栈
     * @param s
     */
    void FreeStack(Stack *s) {
        if (!s) {
            printf("栈空，不需要释放\n");
        } else {
            free(s->base);
            free(s);
            printf("栈释放完成~\n");
        }
    }
    
    /**
     * 栈当前容量
     * @param s
     * @return
     */
    ElementType GetLen(Stack s) {
        int len = (s.top - s.base);
        return len;
    }
    
    int main() {
        printf("二进制转十进制!\n");
        Stack stack;
        InitStack(&stack);
        int data[] = {1, 0, 1, 1, 0, 1};
        int length = sizeof(data) / sizeof(data[0]);  //数组占内存总空间，除以单个元素占内存空间大小
        int sum = 0;
        printf("二进制数据入栈\n");
        for (int i = 0; i < length; i++) {
            Push(&stack, data[i]);
            int e = Pop(&stack);
            printf("%d", e);
            sum = sum + e * pow(2, i);
        }
        printf("\n十进制结果=%d", sum);
        return 0;
    }

![70][]

二进制转八进制：

//
    // Created by Administrator on 2018/5/28.
    //
    
    //二进制转八进制
    //注：二进制转八进制是通过获取二进制中每三位数据计算一个八进制值，如果高位不足三位则通过补0的方式凑齐
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define ElementType int
    #define MaxSize 10
    
    //定义栈的结构体
    typedef struct {
        ElementType *top;//栈顶指针（这里定义为指向栈顶元素的下一个位置，即为空）
        ElementType *base;//栈底指针
        int stackSize;//栈的容量
    } Stack;
    
    /**
     *  初始化栈
     * @param s
     */
    void InitStack(Stack *s) {
        //初始化分配栈的总空间
        s->base = (ElementType *) malloc(MaxSize * sizeof(ElementType));
        if (!s->base) {
            //分配失败
            exit(0);
        }
        s->top = s->base;
        s->stackSize = MaxSize;
    }
    
    /**
     * 入栈
     * @param s 栈
     * @param e 入栈元素
     */
    void Push(Stack *s, ElementType e) {
        //判断栈是否已满
        if (s->top - s->base >= s->stackSize) {
            //栈已满
            //处理方式1.递增空间 2.退出
            printf("栈已满~\n");
            exit(0);
        }
        *(s->top) = e; //赋值
        s->top++;
    }
    
    /**
     * 出栈
     * @param s 栈
     * @return
     */
    ElementType Pop(Stack *s) {
        //判断栈是否为空
        if (s->base == s->top) {
            //栈为空
            //printf("\n不好意思，栈目前为空~\n");
            return -1;
        }
        s->top--;
        ElementType e = *(s->top);//取值，并不是取地址
        return e;
    }
    
    /**
     * 释放栈
     * @param s
     */
    void FreeStack(Stack *s) {
        if (!s) {
            printf("栈空，不需要释放\n");
        } else {
            free(s->base);
            free(s);
            printf("栈释放完成~\n");
        }
    }
    
    /**
     * 栈当前容量
     * @param s
     * @return
     */
    ElementType GetLen(Stack s) {
        int len = (s.top - s.base);
        return len;
    }
    
    int main() {
        printf("二进制转八进制!\n");
        Stack stack, stack1;
        InitStack(&stack);
        InitStack(&stack1);
        int data[] = {1, 0, 1, 1, 0,1,0};
        int length = sizeof(data) / sizeof(data[0]);  //数组占内存总空间，除以单个元素占内存空间大小
        printf("二进制数据入栈~\n");
        for (int i = 0; i < length; i++) {
            printf("%d", data[i]);
            Push(&stack, data[i]);
        }
        //获取栈当前的长度
        int currentLen = GetLen(stack);
        int sum = 0;
        int k = 1;
        if (currentLen < 3) {
            //如果栈当前容量不足3位则补足3位
            currentLen = 3;
        } else {
            //如果当前栈容量为基数即不是3的倍数，则凑为3的倍数（方便接下来便利计算）
            int mod = currentLen % 3;
            if (mod != 0) {
                currentLen = currentLen + (3 - mod);
            }
        }
        for (int j = 0; j < currentLen; j++) {
            ElementType e = Pop(&stack);
            if (e == -1) {
                //如果二进制中不存在数据（说明该栈不是3的倍数），通过高位补0的方式处理
                e = 0;
                if (k % 3 != 0) {
                    k++;
                } else{
                    sum = sum + e * pow(2, k - 1);
                    Push(&stack1, sum);
                }
            } else {
                //二进制栈中存在数据，按取3位计算一次，然后入八进制栈
                sum = sum + e * pow(2, k - 1);
                if (k % 3 == 0) {
                    Push(&stack1, sum);
                    sum = 0;
                    k = 1;
                    continue;
                }
                k++;
            }
        }
        int s2Len = GetLen(stack1);
        printf("\n八进制结果数据出栈：\n");
        for (int l = 0; l < s2Len; l++) {
            ElementType e = Pop(&stack1);
            printf("%d", e);
        }
        return 0;
    }

![70 1][]

注：以上代码为个人的拙见，存在不足之处，还请大家多多海涵！

[70]: /images/20220504/b46c87753f1244a38303cfebe64d313f.png
[70 1]: /images/20220504/4d4d17b1bc0a4dd2b8ee92201d159ea2.png