[toc]
写在前面
数据结构的实现是多种多样的,在本篇实现多种数据结构的过程中会尽可能的使用动态内存的形式,避免使用宏定义的形式,宏定义的形式是很老旧的版本,在实际运用中很少使用,掌握动态运用内存是必备的技能
对于二叉树的遍历创建方法有多种多样,这里使用的是leetcode等平台力荐的递归形式,递归完成二叉树遍历是较为标准和简单的方式
如果对二叉树的遍历不熟悉,最好优先复习二叉树是如何进行递归遍历和创建的
assert函数仅仅是编写代码时便于调试所加,可以删除,不会造成影响
下载链接
数制转换
问题描述
将十进制数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", ÷nd);
int divisor = 8;
printf("输入要改变的进制数->");
scanf("%d", &divisor);
Stack st;
StackInit(&st);
Calculate(&st, dividend, divisor);
Print(&st, dividend, divisor);
return 0;
}