栈的应用

数据结构 › C
,
·本篇:1.1k字 大约需要: 4分钟

栈的应用——递归

斐波那契数列实现

  • 斐波那契数列的特点就是：前面相邻两项之和，构成了后一项

  • 数学函数定义

    $$ F(n)=\begin{cases} 0, & \text{当$ n=0 $} \\ 1, & \text{当$ n=1 $} \\ F(n-1)+ F(n-2), & \text{当$ n>1 $} \end{cases} $$

  • 假设需要打印出前40位的斐波那契数列数

代码如下

迭代方法

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    int i, a[40];
    a[0] = 0, a[1] = 1;
    printf("%d ", a[0]);
    printf("%d ", a[1]);
    for(i = 2; i < 40; i++)
    {
        a[i] = a[i - 1] + a[i -2];
        printf("%d ", a[i]);
    }
    return 0;
}

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
int Fbi(int i)
{
    if(i < 2)
        return i == 0 ? 0 : 1;
    return Fbi(i - 1) + Fbi(i - 2);
}
int main()
{
    int i;
    for(int i = 0; i < 40; i++)
        printf("%d ", Fbi[i]);
    return 0;
}

递归定义

  • 把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数

  • 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出

两种方法对比

迭代和递归的区别：

  • 迭代使用的是循环结构，递归使用的是选择结构
  • 递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间
  • 但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存
  • 迭代则不需要反复调用函数和占用额外的内存

栈和递归的关系

  • 递归过程退回的顺序是它前行顺序的逆序，在退回过程中，可能要执行某些动作，包括恢复在前行过程存储起来的某些数据
  • 这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构
  • 简单来说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中，在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态

栈的应用——四则运算表达式求值

后缀（逆波兰）表示法定义

  • 一种不需要括号的后缀表达法，我们也把它称为逆波兰表示

  • 对于”9 + (3 - 1) ✖ 3 + 8 ➗ 2”，用后缀表示法就为”9 3 1 - 3 ✖ + 8 2 ➗ +”

  • 所有的符号都是在要运算数字的后面出现

后缀表达式计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int Operations(SqStack *S)
{
    SqStack *a = S;
    int temp;
    char ptr[20] = {'9', '3', '1', '-', '3', '*', '+', '8', '2', '/', '+'};
    for(int i = 0; ptr[i] != '\0'; i++)
    {
        if(ptr[i] <= '9' && ptr[i] >= '0')
            Push(a, (int) ptr[i] - 48);
        else if(ptr[i] == '-')
        {
            temp = a->data[a->top - 1] - a->data[a->top];
            a->data[--a->top] = temp;
        }
        else if(ptr[i] == '+')
        {
            temp = a->data[a->top - 1] + a->data[a->top];
            a->data[--a->top] = temp;
        }
        else if(ptr[i] == '*')
        {
            temp = a->data[a->top - 1] * a->data[a->top];
            a->data[--a->top] = temp;
        }
        else if(ptr[i] == '/')
        {
            temp = a->data[a->top - 1] / a->data[a->top];
            a->data[--a->top] = temp;
        }
    }
    return temp;
}

结果为19

中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式，称为中缀表达式

规则：

  • 从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分
  • 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈
  • 一直到最终输出后缀表达式为止

总结

要想让计算机具有处理我们通常的标准表达式的能力，最重要的就是两步：

  • 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
  • 将后缀表达式进行运算得出结果（栈用来进出运算的数字）