数据结构 中数制转换(栈的应用)

1. 什么是数制转换？

数制转换是从一种数字表示方式（即一种进位制，如二进制、八进制、十进制、十六进制等）转化为另一种数字表示方式的过程。在数制转换中，可以使用栈这种数据结构来进行转换的具体实现。

2. 根据位值权重的转换方法

2.1. 十进制转换为其他进制

2.1.1. 除余法

将十进制数不断除以目标进制的基数，比如2（表示二进制）或8（表示八进制）或16（表示十六进制），直到除数为0为止，在每次除法中，将余数记录下来，倒序排列起来即为转换后的数。
例如，将十进制的18转换成二进制：
- 先将18除以2得到商9余0；
- 将9除以2得到商4余1；
- 将4除以2得到商2余0；
- 将2除以2得到商1余0；
- 最后将1除以2得到商0余1。
将这些余数从下到上连接起来，就成了18的二进制数：10010。

2.1.2. 相减法

将十进制数按照多项式展开形式来表示，例如，18可以表示为1*10^1+8*10^0，而将十转换成16进制时，将上述式子中的10换成16即可，即：1*16^1+2*16^0。这样，就将十进制数转化为了其他进制，可以根据需要将数字或字母赋予对应的十进制值。

2.2. 其他进制转换为十进制

将其他进制各位的数字乘以对应权重（以该位所在的位权值为底的幂），然后将结果相加即可得到十进制数。
例如，将二进制数10010转换成十进制：
- 首先分解该数的位权值为权重1、2、4、8、16（从右往左数依次加倍），对应数字为0、1、0、0、1；
- 将各位数字乘以对应的权重，得到18（1*2^4+0*2^3+0*2^2+1*2^1+0*2^0）。
因此，二进制数10010表示的十进制数是18。

3. 有关进制的记数法

3.1. 二进制数的表示法

二进制数字左侧通常用0b或者B来表示，例如，0b101表示二进制数101；

3.2. 八进制数的表示法

八进制数字左侧通常用0或者O来表示，例如，011表示八进制数11；

3.3. 十六进制数的表示法

十六进制数字左侧通常用0x或者X来表示，例如，0xAC表示十六进制数AC。

4. 栈的应用

栈是一种特殊的数据结构，它只允许在栈顶进行操作，并具有"先进后出"的特点，因此非常适合用来实现进制转换。

4.1. 十进制转换为其他进制

以十进制转换为二进制为例，具体步骤如下：

• 创建一个空栈，用来存放余数；
• 将十进制数不断除以2，将得到的余数存入栈中，直到除数为0为止；
• 将栈中存储的余数取出，并按照出栈的顺序拼接成一个数字即可。

下面的示例将十进制数18转换为二进制数：

def decimal_to_binary(decimal_num):
    """
    将十进制数转换为二进制数
    """
    s = []   # 创建一个空栈
    while True:
        decimal_num, remainder = divmod(decimal_num, 2)
        s.append(remainder)
        if decimal_num == 0:
            break
    # 将栈中剩余的元素一起弹出，按顺序拼接成字符串
    binary_num = ''
    while s:
        binary_num += str(s.pop())
    return binary_num

print(decimal_to_binary(18))   # 输出：10010

4.2. 其他进制转换为十进制

以二进制转换为十进制为例，具体步骤如下：

• 创建一个空栈，用来存放各位数字；
• 从右往左遍历二进制数的每一位数字，并将其存入栈中；
• 将栈中的数字按位权值相加得到十进制数。

下面的示例将二进制数10010转换为十进制数：

def binary_to_decimal(binary_num):
    """
    将二进制数转换为十进制数
    """
    s = []   # 创建一个空栈
    for i in binary_num:
        s.append(int(i))
    # 将栈中的数字按位权值相加
    decimal_num = sum([s[i] * 2 ** i for i in range(len(s))])
    return decimal_num

print(binary_to_decimal('10010'))   # 输出：18

5. 总结

以上，介绍了在数据结构中利用栈实现数制转换的方法和步骤。无论是十进制转换为其他进制，还是其他进制转换为十进制，都可以用栈简单、快捷地实现。