栈--利用栈实现进制转换

利用栈实现进制转换

一、二进制转十进制

利用栈的数据结构特点,将二进制转换为十进制数。

二进制数是计算机数据的存储形式,它是由一串0和1组成的,每个二进制数转换成相应的十进制数方法如下:
(XnXn-1……X3X2X1)2 = X1*2^0+X2*2^1+…+Xn*2^(n-1)

一个二进制数要转换为相应的十进制数,就是从最低位起用每一位去乘以对应位的积,也就是说用第n位去乘以2^(n-1),然后全部加起来。

二进制转十进制.png

由于栈具有后进先出的特性,
例如输入11001001这样的二进制数,
如图:

栈中的二进制数.png

代码实现:

#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) = e;
    s->top++;
}

void Pop(sqStack *s, ElemType *e)
{
    if( s->top == s->base )
    {
        return;
    }
    *e = *--(s->top);
}

int StackLen(sqStack s)
{
    return (s.top - s.base);
}

int main()
{
    ElemType c;
    sqStack s;
    int len, i, sum = 0;

    InitStack(&s);

    printf("请输入二进制数,输入#符号表示结束!\n");
    scanf("%c", &c);
    while( c != '#' )
    {
        Push(&s, c);
        scanf("%c", &c);
    }

    getchar();  // 把'\n'(回车)从缓冲区去掉

    len = StackLen(s);
    printf("栈的当前容量是: %d\n", len);

    for( i=0; i < len; i++ )
    {
        Pop(&s, &c);
        sum = sum + (c-48) * pow(2, i);
    }

    printf("转化为十进制数是: %d\n", sum);

    return 0;
}

二、二进制转八进制

二进制是计算机唯一认识的,十进制是人们通常使用的。

观察二进制跟十六进制的对应关系:

二进制与十六进制的对应关系.png

可见一个字节(8bit)刚好用两个十六进制数可以表示完整,也大大的节省了显示空间。

八进制:因为早期的计算机系统都是三的倍数,所以用八进制比较方便。

在进行二进制到八进制的转换时,要将二进制数的每三位转换成一个八进制数来表示,然后按顺序输出即可。

1.png

2.png

3.png

代码实现:

/**  二进制/八进制转换器   **/

#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;

// 函数功能:初始化栈
// 参数*s:栈的地址
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;
}

// 函数功能:入栈操作
// 参数*s:栈的地址
// 参数e:待压入栈的元素
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++;
}

// 函数功能:弹栈操作
// 参数*s:栈的地址
// 参数e:存放从栈里弹出的数据
void Pop(sqStack *s, ElemType *e)
{
    if( s->top == s->base )
    {
        return;
    }
    *e = *--(s->top);
}

// 函数功能:计算栈s的当前长度
// 参数s:栈
int StackLen(sqStack s)
{
    return (s.top - s.base);
}

int main()
{
    ElemType c;
    sqStack s1;
    sqStack s2;
    int len, i, j, sum = 0;

    InitStack(&s1); // 初始化栈s1,用来存放二进制输入

    printf("请输入二进制数,输入‘#’号表示结束!\n\n");
    scanf("%c", &c);
    while( c != '#' )
    {
        if( c=='0' || c=='1' )  // 检查输入是否二进制
            Push(&s1, c);
        scanf("%c", &c);
    }
    getchar();      // 把'\n'从缓冲区去掉
    len = StackLen(s1);

    InitStack(&s2); // 初始化栈s2,用来存放转换的八进制

    for( i=0; i < len; i+=3 )
    {
        for( j=0; j < 3; j++ )
        {
            Pop( &s1, &c ); // 取出栈顶元素
            sum = sum + (c-48) * pow(2, j);

            if( s1.base == s1.top )
            {
                break;
            }
        }

        Push( &s2, sum+48 );
        sum = 0;
    }

    printf("\n转化为八进制数是: ");
    while( s2.base != s2.top )
    {
        Pop( &s2, &c );
        printf("%c", c);
    }
    printf("(O)\n");

    return 0;
}

三、二进制转十六进制

代码实现:

/** 二进制/十六进制转换器  **/

#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;

// 函数功能:初始化栈
// 参数*s:栈的地址
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;
}

// 函数功能:入栈操作
// 参数*s:栈的地址
// 参数e:待压入栈的元素
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++;
}

// 函数功能:弹栈操作
// 参数*s:栈的地址
// 参数e:存放从栈里弹出的数据
void Pop(sqStack *s, ElemType *e)
{
    if( s->top == s->base )
    {
        return;
    }
    *e = *--(s->top);
}

// 函数功能:计算栈s的当前长度
// 参数s:栈
int StackLen(sqStack s)
{
    return (s.top - s.base);
}

int main()
{
    ElemType c;
    sqStack s1;
    sqStack s2;
    int len, i, j, sum = 0;

    InitStack(&s1); // 初始化栈s1,用来存放二进制输入

    printf("请输入二进制数,输入‘#’号表示结束!\n\n");
    scanf("%c", &c);
    while( c != '#' )
    {
        if( c=='0' || c=='1' )  // 检查输入是否二进制
            Push(&s1, c);
        scanf("%c", &c);
    }
    getchar();      // 把'\n'从缓冲区去掉
    len = StackLen(s1);

    InitStack(&s2); // 初始化栈s2,用来存放转换的八进制

    for( i=0; i < len; i+=4 )
    {
        for( j=0; j < 4; j++ )
        {
            Pop( &s1, &c ); // 取出栈顶元素
            sum = sum + (c-48) * pow(2, j);

            if( s1.base == s1.top )
            {
                break;
            }
        }

        switch( sum )
        {
            case 10: sum = 'A'; break;
            case 11: sum = 'B'; break;
            case 12: sum = 'C'; break;
            case 13: sum = 'D'; break;
            case 14: sum = 'E'; break;
            case 15: sum = 'F'; break;
            default: sum += 48;
        }

        Push( &s2, sum );
        sum = 0;
    }

    printf("\n转化为十六进制数是: ");
    while( s2.base != s2.top )
    {
        Pop( &s2, &c );
        printf("%c", c);
    }
    printf("(H)\n");

    return 0;
}
版权声明:本文为CSDN_GIA原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/CSDN_GIA/article/details/79758493

智能推荐

Qt 之 Query Model Example 解析

总体概括 Query Model Example主要演示了怎么使用QSqlQueryModel这个数据库查询模型类。其中包括创建普通的数据库查询模型、可编辑的数据库查询模型和自定义的数据库查询模型。普通(默认)的数据库查询模型是只读的(不可再模型中编辑数据,模型只通过视图展示数据);可编辑的数据库查询模型重写了QSqlQueryModel的flags()方法和setData()方法;自定义的数据库...

Flutter:Scaffold.of() called with a context that does not contain a Scaffold.

Flutter:Scaffold.of() called with a context that does not contain a Scaffold. 当我第一次点击按钮想要弹出底部消息时出现了如下错误 当BuildContext在Scaffold之前时,调用Scaffold.of(context)会报错。这时可以通过Builder Widget来解决,代码如下:...

【机器学习基础】线性回归

                                                        &nbs...

08-Vue实现书籍购物车案例

书籍购物车案例 index.html main.js style.css 1.内容讲解 写一个table和thead,tbody中每一个tr都用来遍历data变量中的books列表。 结果如下: 在thead中加上购买数量和操作,并在对应的tbody中加入对应的按钮。结果如下: 为每个+和-按钮添加事件,将index作为参数传入,并判断当数量为1时,按钮-不可点击。 结果如下: 为每个移除按钮添加...

堆排序

堆排序就是利用堆进行排序的方法,基本思想是,将代排序列构造成一个大根堆,此时整个序列的最大值就是堆顶的根节点。将它与堆数组的末尾元素交换,此时末尾元素就是最大值,移除末尾元素,然后将剩余n-1个元素重新构造成一个大根堆,堆顶元素为次大元素,再次与末尾元素交换,再移除,如此反复进行,便得到一个有序序列。 (大根堆为每一个父节点都大于两个子节点的堆) 上面思想的实现还要解决两个问题: 1.如何由一个无...

猜你喜欢

基础知识(变量类型和计算)

一、值类型 常见的有:number、string、Boolean、undefined、Symbol 二、引用类型 常用的有:object、Array、null(指针指向为空)、function 两者的区别: 值类型暂用空间小,所以存放在栈中,赋值时互不干扰,所以b还是100 引用类型暂用空间大,所以存放在堆中,赋值的时候b是引用了和a一样的内存地址,所以a改变了b也跟着改变,b和a相等 如图: 值...

Codeforces 1342 C. Yet Another Counting Problem(找规律)

题意: [l,r][l,r][l,r] 范围内多少个数满足 (x%b)%a!=(x%a)%b(x \% b) \% a != (x \% a) \% b(x%b)%a!=(x%a)%b。 一般这种题没什么思路就打表找一下规律。 7 8 9 10 11 12 13 14 15 16 17 18 19 20 28 29 30 31 32 33 34 35 36 37 38 39 40 41 49 50...

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3)

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3) (Credit: https://gitee.com/paddlepaddle/Paddle/raw/develop/doc/imgs/logo.png) MNIST数据集 MNIST数据集可以认为是学习机器学习的“hello world”。最早出现在1998年LeC...

哈希数据结构和代码实现

主要结构体: 实现插入、删除、查找、扩容、冲突解决等接口,用于理解哈希这种数据结构 完整代码参见github: https://github.com/jinxiang1224/cpp/tree/master/DataStruct_Algorithm/hash...