数据结构——有向无环图描述表达式

作者：Cpp五条 | 2024-03-17 21:59:20

踩

有向无环图描述表达式

——本节内容为Bilibili王道考研《数据结构》P65视频内容笔记。

一、定义

一、定义

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph），如下图所示；

1.之前学习过用树的形式来表示一个表达式，比如下面这棵树：

2.不难发现上面这棵树其中有很多部分可以合并，合并完后变为：

3.一般会给出一个算术表达式，让我们来求出所需要的最少的顶点个数，下面给出解答步骤；

1.例如题目给出：

2.第一步：把各个操作数不重复地排成一排，如下图：

3.第二步：标出各个运算符的生效顺序（先后顺序有点出入无所谓），如下图：

4.第三步：按顺序加入运算符，注意“分层”，如下图：

5.第四步：从底向上逐层检查同层的运算符是否可以合体，如下图：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/258240