用栈之前首先你要想明白你需要使用“后进先出”干什么，然后才可编写算法，使用中往往是先把数据都压入栈中，然后使用使取出便可，
像表达式求解就是典型的运用栈的例子，可以去看看，会对栈的理解印象深刻些
# include <stdio.h>
# define origial 100
# define add 10
typedef struct
{
int *base
int *top
int stack
}opno
typedef struct
{
char *base
char *top
int stack
}optr
void initstacka(opno *a)
{
a->base=(int *)malloc(sizeof(int)*origial)
a->top=a->base
a->stack=origial
}
void initstackb(optr *b)
{
b->base=(char *)malloc(sizeof(char)*origial)
b->top=b->base
b->stack=origial
*b->top++='#'
}
void pusha(opno *a,int b)
{
if(a->top-a->base>=a->stack)
{
a->base=(int *)realloc(a->base,sizeof(int)*(a->stack+add))
a->top=a->base+a->stack
a->stack+=add
}
*a->top++=b
}
void pushb(optr *b,char c)
{
if(b->top-b->base>=b->stack)
{
b->base=(char *)realloc(b->base,sizeof(char)*(b->stack+add))
b->top=b->base+b->stack
b->stack+=add
}
*b->top++=c
}
int determine(char c)
{
if(c>='0'&&c<='9')
return(1)
else
return(0)
}
char gettopb(optr *b)
{
char a
a=*(b->top-1)
return(a)
}
char shuzu(int i,int j)
{
char a[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','0'},{'>','>','>','>','0','>','>'},{'<','<','<','<','<','0','='}}
return(a[i][j])
}
char precede(char b,char a)
{
int i,j
char s
switch(b)
{
case '+':i=0
break
case '-':i=1
break
case '*':i=2
break
case '/':i=3
break
case '(':i=4
break
case ')':i=5
break
case '#':i=6
break
}
switch(a)
{
case '+':j=0
break
case '-':j=1
break
case '*':j=2
break
case '/':j=3
break
case '(':j=4
break
case ')':j=5
break
case '#':j=6
break
}
s=shuzu(i,j)
return(s)
}
void popb(optr *a,char *b)
{
*b=*--a->top
}
void popa(opno *a,int *b)
{
*b=*--a->top
}
int count(int a,int b,char c)
{
int sum=0
switch(c)
{
case '+':sum=a+b
break
case '-':sum=a-b
break
case '*':sum=a*b
break
case '/':sum=a/b
break
}
return(sum)
}
int empty(optr *a)
{
if(a->top==a->base)
return(1)
else
return(0)
}
void main()
{
opno *a
optr *b
char c
char d[50]
int i=0,j=0,k,sum=0,p,o,r,w
int y[3]
a=(opno *)malloc(sizeof(opno))
b=(optr *)malloc(sizeof(optr))
initstacka(a)
initstackb(b)
printf("请输入表达式！\n")
scanf("%s",d)
while(d[i]!='#'&&d[i]!='\0')
if(determine(d[i]))
{
sum=0
y[j]=d[i]-'0'
while(determine(d[i+1]))
{
i=i+1
y[++j]=d[i]-'0'
}
for(k=0k<=jk++)
sum=sum*10+y[k]
if(sum!=0)
pusha(a,sum)
else
pusha(a,y[0])
j=0
for(k=0k<3k++)
y[k]=0
i=i+1
}
else
{
switch(precede(gettopb(b),d[i]))
{
case '>':popb(b,&c)
popa(a,&p)
popa(a,&o)
r=count(o,p,c)
pusha(a,r)
break
case '=':popb(b,&c)
i++
break
case '<':pushb(b,d[i])
i++
break
}
}
popb(b,&c)
while(c!='#')
{
popa(a,&o)
popa(a,&p)
r=count(o,p,c)
pusha(a,r)
popb(b,&c)
}
popa(a,&w)
printf("%d",w)
}
这就是运用栈写得表达式求值
递归可以用栈实现吗？栈是如何实现递归的在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，毎个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i <2的，这样就可以执行return i的语句而不用继续递归了。
对比了两种实现斐波那契的代码。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。
递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。
迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同 情况选择不同的代码实现方式。
那么我们讲了这么多递归的内容，和栈有什么关系呢？这得从计算机系统的内部说起。
前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。
这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。
简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被d出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。
递归调用其实就是栈，栈有先进后出的特点，递归调用的实质也就是循环调用，我写一个简单的例子吧：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）