数据结构之图（有向无环图结构表达式）

概念

第一个图没有环
第二个图v0到v4到v3再到v0是一个环所以第二个图不是有向无环图

我们学过用树存储表达式
但是可能会有重复
比如红色的和绿色的

我们把绿色的干掉
指向一个红的
也是这样的结果，不过这种数据结构就编程图了

同样的包括单独一个字母也可以这样


变成一个

真题奥

1.

所以选A

因为单纯的查找太容易漏了
所以我们总结出了

把对应表达式转换成有向无环图的方法

一种方法


就是按照运算顺序一个个添加运算符（按照前序）
如果
要用到(c+d)比如说第三步
那他就得比第二层高一个层次
就是你这个运算符一共用到几个操作数
就放在对应的i-1层
c+d 中的+用两个操作数放在第一层

做完第三步

第四步合运算符
注意奥，对应一层一层看，不同层次间的运算符是不可能合并的
因为包含的运算数都不一样

看第二层
看三个绿色+号运算数都是c和d
可以合并

再看第三层对应的最右边乘（×）号和靠着右边的乘（×）

两个操作数都是e 和（c+d）可以合并

再往上的三层每一层一个运算符不需要合并

完毕

练习