数据结构复习：中缀转后缀表达式与链表逆置

"数据结构考前终极复习涵盖了链表逆置、循环队列的操作、中缀表达式转后缀表达式、矩阵计算、以及树和二叉树的基本性质。" 在数据结构的学习中，了解并掌握这些核心概念是至关重要的。 1. **链表逆置**：链表逆置是一种常见的链表操作，它将链表中的元素顺序反转。给出的代码示例展示了如何通过迭代方式实现单链表的逆置。通过设置三个指针p、q和head，逐个处理节点，将节点指向其前一个节点，直至完成逆置。 2. **循环队列**：循环队列是一种线性数据结构，它的特点是队尾超出队列长度时会回到队首，形成环状。在插入和删除操作后，队首和队尾指针的更新遵循模运算，确保它们始终在有效范围内。例如，队首指针加1后取模，队尾指针在插入元素后同样加1取模。 3. **中缀表达式转后缀表达式**：中缀表达式转后缀表达式是编译原理和算法设计中的重要问题。通过使用栈来辅助处理运算符，遵循一定的规则：遇到操作数直接输出，遇到左括号入栈，遇到右括号则连续出栈直到遇到左括号，遇到其他运算符则根据优先级出栈。最终，栈内剩余的元素按顺序输出即为后缀表达式。 4. **矩阵计算**：在二维数组A中，元素的地址计算涉及到行优先和列优先两种方式。题目中提到的元素a[2][3]地址为400，元素a[6][5]的地址可以通过行优先或列优先的公式计算得出。 5. **树的基本性质**：树的结点数与所有结点的度数关系，以及树的层次关系等。例如，度为d的树第i层最多有d^(i-1)个结点，d叉树的最小深度与n个结点的关系等。 6. **二叉树性质**：二叉树的结点数量与层数的关系，以及高度和结点数的关系。比如，二叉树第i层最多有2^(i-1)个结点，高度为k的二叉树最多有2^k-1个结点，n个结点的二叉树高度至少为log2(n+1)，以及二叉树中终端结点和度为2的结点之间的数量关系。 7. **完全二叉树性质**：完全二叉树是特殊的二叉树，它的性质可以推导出结点数量与层次之间的精确关系，以及终端结点的数量与度为2的结点数量之间的关系。 这些知识点是数据结构考试中常见的考点，理解和熟练运用这些概念对于解决实际问题和进行算法设计至关重要。理解并能灵活应用这些基础理论，将有助于提升在数据结构领域的技能。