一、图的基本概念

1. 图的定义：由顶点(点)和边组成的结构
2. 图的分类：
   • 无向图：边没有方向
   • 有向图：边有方向

     二、顶点与边的关系

     1. 基本关系

• 邻接关系：两个顶点之间有边直接相连
• 关联关系：边与顶点之间的关系

  2. 数学表示

• 无向图：
  • 边记为 (u,v)
  • 顶点度数 = 关联边数
• 有向图：
  • 边记为
  • 出度/入度概念

    三、特殊路径概念

    1. 欧拉路径

• 经过图中每一条边且每边只经过一次的路径
• 条件：
  • 无向图：恰好两个顶点度数为奇数
  • 有向图：一个顶点入度=出度+1，另一个出度=入度+1，其余相等

    2. 欧拉回路

• 起点和终点相同的欧拉路径
• 条件：
  • 无向图：所有顶点度数为偶数
  • 有向图：所有顶点入度=出度

    前辍与后辍表达式

    1. 表达式表示法

• ：运算符位于操作数中间 (如 a + b)
• 前辍表达式：运算符位于操作数前面 (如 + a b)
• 后辍表达式：运算符位于操作数后面 (如 a b +)

  2. 表达式特性对比

  中辍表达式特性：

• 人类最易读的形式
• 需要括号来明确优先级
• 运算符优先级规则复杂
• 计算顺序不明确

  前辍表达式特性：

• 无需括号即可明确运算顺序
• 计算顺序从右向左
• 运算符优先级隐含在结构中
• 适合递归计算
• 计算机处理效率高

  后辍表达式特性：

• 无需括号即可明确运算顺序
• 计算顺序从左向右
• 适合使用栈结构计算
• 运算符优先级隐含在结构中
• 计算机处理效率最高

三、除法运算详解

1. 中辍表达式中的除法

• 明确运算顺序：a / b 表示 a 除以 b
• 带括号的情况：(a + b) / (c - d)
• 除法的优先级高于加减法

  2. 后辍表达式中的除法处理

  计算规则：

1. 从左到右扫描表达式
2. 操作数压入栈
3. 遇到运算符时：
   • 弹出栈顶两个元素
   • 第一个弹出的是右操作数
   • 第二个弹出的是左操作数

     示例：a b /

4. 压入 a
5. 压入 b
6. 遇到 /：
   • 弹出 b (右)
   • 弹出 a (左)
   • 计算 a / b

     3. 前辍表达式中的除法处理

     计算规则： 从右到左扫描表达式 操作数压入栈 遇到运算符时： 弹出栈顶两个元素 第一个弹出的是左操作数 第二个弹出的是右操作数 示例：/ a b 从右到左扫描： 压入 b 压入 a 遇到 /： 弹出 a (左) 弹出 b (右) 计算 a / b 四、记忆技巧 后辍表达式： 运算符”站在”操作数后面 计算顺序：”后进先出，先右后左” 口诀：”先出来的是右边的” 前辍表达式： 运算符”站在”操作数前面 计算顺序：”先进后出，先左后右” 口诀：”先出来的是左边的” 五、综合示例 中辍表达式：(6 + 3) / (4 - 1)
7. 转换为后辍表达式： 步骤：6 3 + 4 1 - / 计算过程： 6, 3 → 遇到 + → 6 + 3 = 9 4, 1 → 遇到 - → 4 - 1 = 3 9, 3 → 遇到 / → 9 / 3 = 3
8. 转换为前辍表达式： 步骤：/ + 6 3 - 4 1 计算过程： 从右到左： 1, 4 → 遇到 - → 4 - 1 = 3 3, 6 → 遇到 + → 6 + 3 = 9 9, 3 → 遇到 / → 9 / 3 = 3 六、课堂练习 将 (8 / 4) + (2 * 3) 转换为：

前辍表达式 后辍表达式 并说明除法运算的处理过程 计算后辍表达式 5 1 2 + 4 * + 3 - 的值