七、蛤蟆的数据结构笔记之七栈的应用之数制转换
7、蛤蟆的数据结构笔记之七栈的应用之数制转换
本篇名言：“人生意义的大小，不在乎外界的变迁，而在乎内心的经验。”
上面两篇中我们实现了链栈和链队列，接下去哦我们看看实际中栈的应用场景。本次来看下栈在数制转换的作用。
欢迎转载，转载请标明出处：
1. 原理介绍
十进制N和其他进制数的转换时计算机实现计算的基本问题。简单算法如下：
N=（N div d ）x d + N modd
2. 实现
2.1 定义结构体
定义堆栈的结构体
typedef struct
{
int*base;
intstacksize;
int*top;
}sqstack;
2.2 初始化堆栈
传入的参数是堆栈结构体的指针。分配10个整型的节点。
void initstack(sqstack *S)
{
//创建一个空栈
(*S).base=(int*)malloc(sizeof(int)*10);
if(!(*S).base)exit(0);
(*S).stacksize=10;
(*S).top=(*S).base;
}
2.3 Pop函数
Pop是从堆中弹出一个元素
int pop(sqstack *S)
{
//输出堆栈的元素
inte;
if((*S).base==(*S).top)exit(0);
e=*(--(*S).top);
returne;
}
2.4 Push函数
Push 函数想堆中压入一个元素。当超过堆本身拥有的最大上限时候，需要重新分配堆，每次扩大4个int字节。
void push(sqstack *S,int e)
{
if((*S).top-(*S).base>=(*S).stacksize) //当初始化的空间被用完了之后，重新分配新的内存给堆栈
{
S->base=(int*)realloc((*S).base,sizeof(int)*(S->stacksize+4));
if(!(*S).base)exit(0);
(*S).top=(*S).base+(*S).stacksize;
S->stacksize=S->stacksize+4;
printf("afterrealloc %d\n",(*S).stacksize);
}
*(*S).top++=e;
}
3. Main
最后注意释放malloc得到的内存空间，最后得到如下图1：
void main()
{
intn,m;
chare;
sqstackS;
initstack(&S);
printf("输入要转换的十进制数和要转换成什么进制：");
scanf("%d%d",&n,&m);
while(n)
{
push(&S,n%m);//调用入栈函数，具体的函数自己写
n=n/m;
}
while(StackEmpty(&S))//判断堆栈是否为空
{
e=pop(&S);//出栈
printf("%d",e);
}
free(S.base);
}
4. 源码
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int*base;
intstacksize;
int*top;
}sqstack;
void initstack(sqstack *S)
{
//创建一个空栈
(*S).base=(int*)malloc(sizeof(int)*4);
if(!(*S).base)exit(0);
(*S).stacksize=4;
(*S).top=(*S).base;
}
int pop(sqstack *S)
{
//输出堆栈的元素
inte;
if((*S).base==(*S).top)exit(0);
e=*(--(*S).top);
returne;
}
void push(sqstack *S,int e)
{
if((*S).top-(*S).base>=(*S).stacksize) //当初始化的空间被用完了之后，重新分配新的内存给堆栈
{
S->base=(int*)realloc((*S).base,sizeof(int)*(S->stacksize+4));
if(!(*S).base)exit(0);
(*S).top=(*S).base+(*S).stacksize;
S->stacksize=S->stacksize+4;
printf("afterrealloc %d\n",(*S).stacksize);
}
*(*S).top++=e;
}
int StackEmpty(sqstack *S)
{
if((*S).top==(*S).base)
return0;
else
return1;
}
void main()
{
intn,m;
chare;
sqstackS;
initstack(&S);
printf("输入要转换的十进制数和要转换成什么进制：");
scanf("%d%d",&n,&m);
while(n)
{
push(&S,n%m);//调用入栈函数，具体的函数自己写
n=n/m;
}
while(StackEmpty(&S))//判断堆栈是否为空
{
e=pop(&S);//出栈
printf("%d",e);
}
free(S.base);
}