"实习二栈及队列的应用.ppt" 是一份教学课件,主要讲解了栈和队列在实际问题中的应用。
【栈的应用】
在这个实习项目中,栈被用于解决“火烧连营”的问题。这是一个典型的深度优先搜索(DFS)问题,通过模拟火势蔓延的过程来标记被燃烧的营帐。具体步骤如下:
1. 首先,读取40行70列的文本文件,其中每个字符代表一个营帐,用特定字符表示可燃的营帐,其他字符表示不可燃的区域。
2. 用户通过MFC界面输入起火点的坐标(x, y),满足0 < x < 70, 0 < y < 40。
3. 创建一个栈,将起火点压入栈中,然后进入循环过程。
4. 在循环中,每次从栈顶取出一个点,将其标记为'X',表示已被烧毁。
5. 搜索栈顶点的四个相邻方向(上、下、左、右),如果找到可燃的营帐,则将其压入栈中,继续进行标记。
6. 这一过程持续到栈为空,即所有与起火点相连的可燃营帐都被标记完毕。
7. 最后,将更新后的整个布局写回文件,展示被烧毁的营帐情况。
【队列的应用】
虽然题目中没有明确提到队列,但队列同样适用于此类问题,采用广度优先搜索(BFS)策略。在火烧连营问题中,可以使用队列来存储待检查的营帐,按照先进先出(FIFO)的原则,依次处理队列中的点,达到相同的效果。
【算术表达式求值】
该实习项目还涵盖了计算合法表达式的值,这涉及到运算符的优先级和结合性。对于给定的表达式,如3.5*(7+2)/(-6),遵循以下规则:
1. 支持四种基本运算:加法(+)、减法(-)、乘法(*)、除法(/)以及扩展的模运算(%)。
2. 运算符优先级:乘法和除法优先于加法和减法;同一优先级的运算符从左到右顺序计算。
3. 括号用于改变运算顺序,括号内的表达式优先计算。
4. 提供函数运算,如平方根函数sqrt()。
实现这个功能需要一个解析器来分析表达式,可能使用到逆波兰表示法(Reverse Polish Notation, RPN)或递归下降解析等方法。首先,将表达式转化为中缀表达式,然后根据运算符优先级和括号规则进行计算,最后输出计算结果。在这个例子中,计算结果为-2.1666666666666665。