"该实验报告来自山东大学计算机科学与技术学院的数据结构与算法课程,学生李港在2019年10月25日进行了关于栈的实验,使用了Visual Studio 2019作为开发工具。实验目标是理解和掌握栈的定义与实现,并能运用栈解决实际问题,如计算数学表达式和解决迷宫问题。实验内容包括创建栈类,用数组实现,以及应用栈解决两个具体问题:计算包含加减乘除括号的数学表达式和寻找迷宫中的路径。实验采用了动态调整大小的数组作为数据结构,并通过栈来处理计算过程和路径搜索。"
实验详细内容与知识点:
1. **栈的基本概念**:栈是一种具有“后进先出”(LIFO)特性的数据结构,常用于临时存储和处理数据。在这个实验中,栈被用来处理数学表达式和迷宫问题。
2. **数组实现栈**:在实验中,栈通过原生数组来实现,这是最基础的实现方式,数组的索引可以对应栈的深度,通过数组下标实现元素的压入和弹出。
3. **动态扩容与缩容**:为了节省内存资源,栈的容量不是固定的,而是动态调整的。当栈满时,容量会扩展到原来的两倍;当栈长度小于缓冲区的四分之一时,容量会收缩到原来的一半。这种策略平衡了空间效率和插入删除的效率。
4. **表达式计算**:使用栈计算数学表达式的值,通常涉及中缀表达式到后缀表达式的转换。中缀表达式(如2+3*(4+5)-6/4)需要转换成后缀表达式(如2 3 4 5 + * 6 4 / -),然后通过栈处理后缀表达式得到结果。这个过程中,符号栈用于处理运算符的优先级和结合性。
5. **中缀转后缀算法**:遍历中缀表达式,遇到数字直接添加到后缀表达式,遇到运算符则根据优先级将其压入符号栈,遇到括号进行特殊处理。当遇到右括号时,将栈顶运算符弹出直到遇到左括号,将这对括号内的运算符都加入到后缀表达式。
6. **后缀表达式计算**:从左到右读取后缀表达式,遇到数字直接压栈,遇到运算符则弹出栈顶的两个数进行运算,结果再压回栈。最后栈中只剩下一个元素,即为表达式的结果。
7. **走迷宫算法**:利用栈来存储可能的路径,每次从当前点出发,尝试向上下左右四个方向移动,如果遇到通路则将坐标压栈,同时记录路径信息。当找到出口或遍历所有可能的路径但未找到出口时,算法结束。通过字符数组显示迷宫和路径,方便可视化。
8. **数据结构选择**:原生数组作为数据结构简单直观,但在动态扩容时可能导致效率降低,因为需要复制整个数组。然而,实验中采取的动态调整策略能够有效缓解这一问题。
9. **算法设计**:实验中的算法设计体现了数据结构的运用和问题解决的策略,不仅展示了栈在计算和路径查找中的应用,还涉及到算法的时间和空间复杂度优化。
通过这个实验,学生不仅掌握了栈的基本操作,也学会了如何将栈应用于实际问题的解决,深化了对数据结构和算法的理解。