[toc]

写在前面

数据结构的实现是多种多样的，在本篇实现多种数据结构的过程中会尽可能的使用动态内存的形式，避免使用宏定义的形式，宏定义的形式是很老旧的版本，在实际运用中很少使用，掌握动态运用内存是必备的技能

对于二叉树的遍历创建方法有多种多样，这里使用的是leetcode等平台力荐的递归形式，递归完成二叉树遍历是较为标准和简单的方式

如果对二叉树的遍历不熟悉，最好优先复习二叉树是如何进行递归遍历和创建的

数据结构---手撕图解二叉树

assert函数仅仅是编写代码时便于调试所加，可以删除，不会造成影响

下载链接

实验三Gitee
实验四Gitee

数制转换

问题描述

将十进制数N和其他d进制数之间进行转换是计算机实现计算的基本问题，解决方案很多，其中最简单的方法是除d取余法。例如，（1348）10=（2504）8，其转化过程如下所示：

          N             N div 8            N mod 8
         1348            168                4
         168             21                 0
         21              2                  5
         2               0                  2

从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的“后进先出”的特性。所以可以用顺序栈来模拟这个过程。

题目解析

很简单的题，写一个栈入余数即可

需要注意的是，超过十进制的数有字母的参与，因此可以提前写一个数组，然后把栈内元素当成下标，再用下标元素访问数组内元素，就可以达到输出数字和字母的效果

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//1. 将十进制数N和其他d进制数之间进行转换是计算机实现计算的基本问题，解决方案很多，其中最简单的方法是除d取余法。
// 例如，（1348）10 = （2504）8，其转化过程如下所示：
//N             N div 8            N mod 8
//1348            168                4
//168             21                 0
//21              2                  5
//2               0                  2
//从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的“后进先出”的特性。所以可以用顺序栈来模拟这个过程。

typedef int STDataType;
typedef struct Stack
{
   
    STDataType* a;
    int capacity;
    int top;
}Stack;

void StackInit(Stack* pst)
{
   
    pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (pst->a == NULL)
    {
   
        perror("malloc fail");
        return;
    }
    pst->capacity = 4;
    pst->top = 0;
}

STDataType StackTop(Stack* pst)
{
   
    assert(pst);
    assert(pst->top);
    return pst->a[pst->top - 1];
}

void StackPop(Stack* pst)
{
   
    assert(pst);
    assert(pst->top);
    pst->top--;
}

void StackPush(Stack* pst, STDataType x)
{
   
    assert(pst);
    if (pst->capacity = pst->top)
    {
   
        STDataType* tmp = NULL;
        int newcapacity = pst->capacity * 2;
        tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
    pst->a[pst->top] = x;
    pst->top++;
}

bool StackEmpty(Stack* pst)
{
   
    if (pst->top == 0)
        return true;
    else
        return false;
}

//被除数 dividend 
//除数   divisor 
//商     result
//余数     remainder

void Calculate(Stack* pst, int dividend, int divisor)
{
   
    int remainder;
    while (dividend)
    {
   
        remainder = dividend % divisor;
        StackPush(pst, remainder);
        dividend = dividend / divisor;
    }
}

void Print(Stack* pst, int dividend, int divisor)
{
   
    char array[16] = {
    '0', '1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
    printf("%d(10)=", dividend);
    while (!StackEmpty(pst))
    {
   
        printf("%c", array[StackTop(pst)]);
        StackPop(pst);
    }
    printf("(8)\n");
}

int main()
{
   
    int dividend = 1348;
    printf("输入十进制数->");
    scanf("%d", &dividend);
    int divisor = 8;
    printf("输入要改变的进制数->");
    scanf("%d", &divisor);
    Stack st;
    StackInit(&st);
    Calculate(&st, dividend, divisor);
    Print(&st, dividend, divisor);
    return 0;
}