面向对象编程——虚函数

和newMultNode的宏将结构体初始化，表达式算术树接口的实现详见程序清单 4.13。

程序清单 4.13 表达式算术树接口的实现（cacltree.c）

表达式算术树的使用范例详见程序清单 4.14。

程序清单 4.14 表达式算术树使用范例

如果此方案应用于包括上百个结点的树时，其消耗的内存太大了。

2、抽象类

根据问题的描述，需求词汇表中有一组这样的概念，比如，根结点和左右叶子结点的操作数，且加法和乘法都是二元操作。虽然词汇表对应的词汇为Node、_pLeft、_pRight、Number、Binary、Additive和Multiplicative，但用Node、_pLeft、_pRight、NumNode、BinNode、AddNode和MultNode描述表达式算术树的各个结点更准确。

由于AddNode和MultNode都是二元操作，其共性是两个数（_pLeft和_pRight）的计算，其可变性分别为加法和乘法，因此可以将它们的共性包含在BinNode中，可变性分别包含在AddNode和MultNode中。

其实输入操作数同样可以视为计算，因此NumNode和BinNode的共性也是计算，不妨将它们的共性上移到Node抽象类中。

显然，基于面向对象的C编程，则表达式算术树的所有结点都是从类Node继承的子类，Node的直系后代为NumNode和BinNode，NumNode表示一个数，BinNode表示一个二元运算，然后再从BinNode派生两个类：AddNode和MultNode。

图 4.7 结点的类层次

如图 4.7所示展示了类的层次性，它们是一种"is-a"的抽象层次结构，子类AddNode和MultNode重新定义了BinNode和Node基类的结构和行为。基类代表了一般化的抽象，子类代表了特殊的抽象。虽然抽象类Node或BinNode不能实例化，只能作为其它类的父类，但NumNode、AddNode和MultNode子类是可以实例化的。Node抽象类的定义如下：

除了Node之外，每个子类都要实现自己的nodeCalc计算方法，并返回一个作为计算结点值的双精度数。即：

其中的NumNode结点是从Node分出来的，_num表示数值。BinNode也是从Node分出来的，_pLeft和_pRight分别为指向左子树和右子树的指针，而AddNode和MultNode又是从BinNode分出来的。

此前，针对继承和多态框架，使用了一种称为静态的初始化范型。在这里，将使用动态内存分配初始化范型处理继承和多态框架。

3、建立接口

由于对象不同，因此动态分配内存的方式不一样，但其共性是——不再使用某个对象时，释放动态内存的方法是一样，因此还需要添加一个node_cleanup()函数，这是通过free()实现的，详见程序清单 4.15。

程序清单 4.15 表达式算术树的接口（CalcTree1.h）

实现表达式算术树的第一步是输入数据和初始化NumNode结构体的变量isa和_num，newNumNode()函数原型如下：

其调用形式如下：

接下来开始为计算做准备，node_calc()函数原型如下：

其调用形式如下：

然后开始进行加法运算，newAddNode()函数原型如下：

其调用形式如下：

当然，也可以开始进行乘法运算了，newMultNode()函数原型如下：

其调用形式如下：

一切准备就绪，则计算最终结果并释放不再使用的资源，node_cleanup()函数原型如下：

其调用形式如下：

4、实现接口

显然，为每个结点创建了相应的类后，就可以为每个结点创建一个动态变量，即可在运行时根据需要使用malloc()分配内存并使用指针存储该地址，并使用指针初始化结构体的各个成员，CalcTree1.c接口的实现详见程序清单 4.16。

程序清单 4.16表达式算术树接口的实现（CalcTree1.c）

>>>   4.4.3 虚函数

虽然可以使用继承实现表达式算术树，但实现代码中的每个对象都有函数指针。如果结构体内有很多函数指针，或必须生成更多的对象时，将会出现多个对象具有相同的行为、需要较多的函数指针和需要生成较多数量的对象，将会浪费很多的内存。

不妨将Node中的成员转移到另一个结构体中实现一个虚函数表，然后在接口中创建一个抽象数据类型NodeVTable，在此基础上定义一个指向该表的指针vtable。比如：

表达式算术树的接口详见程序清单 4.17，其中的NumNode派生于Node，_num表示数值；BinNode也是派生于Node，pLeft和pRight分别表示指向左子树和右子树的指针；而AddNode和MultNode又派生于BinNode。虽然抽象类包含一个或多个纯虚函数类，但不能实例化（此类没有对象可创建），只有从一个抽象类派生的类和为所有纯虚函数提供了实现代码的类才能实例化，它们都必须提供自己的计算方法node_calc和node_cleanup。

程序清单 4.17 表