数据结构考研重点：栈的应用与递归算法解析

"殷仁昆教授的计算机专业考研辅导资料，重点讲解了栈在数据结构中的应用，以及在中缀和后缀表达式求值中的角色。此外，还强调了递归算法中栈用于存储局部变量、返回地址和实参副本。资料涵盖数据结构考研的各个章节知识点，旨在提升考生对数据结构的理解、分析和应用能力。" 在计算机科学中，数据结构是编程的基础，而栈作为一种特殊的数据结构，具有后进先出（LIFO）的特点，因此在很多场景下有着广泛的应用。在本资料中，殷仁昆教授提到了栈在两个特定计算问题中的运用： 1. **后缀表达式求值**：后缀表达式（也称为逆波兰表示法）是一种不含括号的表达式表示方式，运算符位于操作数之后。在求值过程中，栈用于存放操作数和运算结果。我们依次读取表达式中的元素，遇到数字就压入栈，遇到运算符则弹出栈顶的两个操作数进行运算，结果再压回栈。这样，最后栈顶的元素即为表达式的值。 2. **中缀表达式求值**：在中缀表达式中，运算符位于操作数之间，求值过程更复杂。通常使用两个栈，一个OPND栈存放操作数，另一个OPTR栈存放操作符。读取表达式时，遇到操作数就压入OPND栈，遇到运算符则根据优先级与OPTR栈处理，如果运算符优先级高于栈顶运算符，就将它压入OPTR栈；否则，弹出OPTR栈顶的运算符与OPND栈顶的操作数进行运算，结果再入栈。最后，当表达式读完且OPTR栈为空时，OPND栈顶元素即为结果。 在**递归算法**中，栈同样起到关键作用。每当函数递归调用自身，系统会自动使用栈来保存当前函数的状态，包括局部变量、返回地址和实参副本。这样，每次函数返回时，可以恢复到上一次调用的状态，直到达到基本情况，递归结束。 除了栈的应用，考研要点还包括对各种基本数据结构如顺序表、链表、队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构和散列结构的深入理解和比较。考生需要掌握这些结构的定义、存储表示、操作实现，以及在不同情境下的选择和应用原则。 在复习策略上，殷教授强调了**注重概念**、**抓住特点**和**学会算法**的重要性。理解每个数据结构的定义、传承关系、逻辑和物理结构的层次，以及关注细节对于解题至关重要。同时，理解结构的行为特征、应用背景和声明方式有助于在实际问题中做出正确选择。学会算法不仅涉及基本操作的实现，还包括查找、排序等常用算法的设计与分析，以及迭代、递归、分治和回溯等算法设计方法。 数据结构的学习和掌握是计算机专业考研的核心部分，考生需要通过深入理解概念、把握结构特点、熟练运用算法，提升自己的分析和解决问题的能力。