周立功教授數(shù)年之心血之作《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》以及《面向AMetal框架與接口的編程（上）》，電子版已無償性分享到電子工程師與高校群體，書本內(nèi)容公開后，在電子行業(yè)掀起一片學(xué)習(xí)熱潮。經(jīng)周立功教授授權(quán)，本公眾號特對《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》一書內(nèi)容進行連載，愿共勉之。

第四章為面向?qū)ο缶幊?/span>，本文為 4.4虛函數(shù)。

>>> 4.4.1 二叉樹

樹的應(yīng)用非常廣泛，比如，數(shù)據(jù)庫就是由樹構(gòu)造而成的，C編譯器的詞法分析器也是經(jīng)過語法分析生成的樹。

樹是一種管理象樹干、樹枝、樹葉一樣關(guān)系的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，通常一棵樹由根部長出一個樹干，接著從樹干長出一些樹枝，然后樹枝上又長出更小的樹枝，而葉子則長在最細(xì)的樹枝上，樹這種數(shù)據(jù)結(jié)構(gòu)正是象一棵樹倒過來的樹木。

樹是由結(jié)點（頂點）和枝構(gòu)成的，由一個結(jié)點作為起點，這個起點稱為樹的根結(jié)點。從根結(jié)點上可以連出幾條枝，每條枝都和一個結(jié)點相連，延伸出來的這些結(jié)點又可以繼續(xù)通過枝延伸出新的結(jié)點。這個過程中的舊結(jié)點稱作父結(jié)點，而延伸出來的新結(jié)點稱作子結(jié)點，一個子結(jié)點都沒有的結(jié)點就叫做葉子結(jié)點。另外，從根結(jié)點出發(fā)到達某個結(jié)點所要經(jīng)過的枝的個數(shù)叫做這個結(jié)點的深度。

從家譜樹血緣關(guān)系來看，家譜樹使得介紹計算機科學(xué)中用于描述樹結(jié)構(gòu)的術(shù)語變得更簡單了。樹中的每一個結(jié)點都可以有幾個孩子，但是只有一個雙親。在樹中祖先和孫子的意義與日常語言中的意義完全相同。

與根形成對比的是沒有孩子的結(jié)點，這些結(jié)點稱為葉，而既不是根又不是葉的結(jié)點稱為內(nèi)部結(jié)點，樹的長度定義為從根到葉的最長路徑的長度（或深度）。在一顆樹里，如果從根到葉的每條路徑的長度都大致相等，那么這顆樹被稱為平衡樹。實際上，要實現(xiàn)某種永遠(yuǎn)能夠保證平衡的樹是很復(fù)雜的，這也是為什么存在多種不同種類的樹的原因。

實際上，在樹的每一層次都是分叉形式，如果任意選取樹中的一個結(jié)點和它的子樹，所得到的部分都符合樹的定義。樹中的每個結(jié)點都可以看成是以它自己為根的子樹的根，這就是樹結(jié)構(gòu)的遞歸特性。如果以遞歸的觀點考察樹，那么樹只是一個結(jié)點和一個附著其上的子樹的集合——在葉結(jié)點的情景下該集合為空，因此樹的遞歸特性是其底層表示和大部分針對樹操作的算法的基礎(chǔ)。

樹的一個重要的子類是二叉樹，二叉樹是一種常用的樹形數(shù)據(jù)結(jié)構(gòu)。二叉樹的每個結(jié)點最多只有兩個子結(jié)點（left和right），且除了根以外的其它結(jié)點，要么是雙親結(jié)點的左孩子，要么是右孩子。

>>> 4.4.2 表達式算術(shù)樹

1、問題

求解算術(shù)表達式就是一種二叉樹，它的結(jié)點包含兩種類型的對象：操作符和終值。操作符是擁有操作數(shù)的對象，終值是沒有操作數(shù)的對象。表達式樹背后的思想——存儲在父結(jié)點中的是操作符，其操作數(shù)是由子結(jié)點延伸的子樹組成的。操作數(shù)有可能是終值，或它們本身也可能是其它的表達式。表達式在子樹中展開，終值駐留在葉子結(jié)點中，這種組織形式的好處是可以通過表達式將一個表達式轉(zhuǎn)換為3種常見的表示形式：前綴、中綴和后綴，但中綴表達式是在數(shù)學(xué)中學(xué)到的最為熟悉的表達方式。在這里，將以2*（3+4）+5中綴表達式算術(shù)樹結(jié)構(gòu)為例。

首先將“2*（3+4）+5”拆分為左子樹和右子樹，其中，“+” 為根節(jié)點，左子樹的值為2*（3+4），右子樹的值為5；接著將2*(3+4)拆分為左子樹和右子樹，其中，“*”為根節(jié)點，左子樹的值為2，右子樹的值為3+4；然后將3+4拆分為左子樹和右子樹，其中，“+”為根節(jié)點，左子樹的值為3，右子樹的值為4，詳見圖 4.6。注意，樹的表示法中不需要任何小括號或運算符優(yōu)先級的知識，因為它描述的計算過程是唯一的。

圖 4.6 表達式算術(shù)樹

由此可見，從根結(jié)點（Node）到葉進行分析，該表達式算術(shù)樹的結(jié)點是算術(shù)運算符“+（Additive）”和“*（Multiplicative）”，它的樹葉是操作數(shù)（Number）。由于這里所有的操作都是二元（Binary）的，即每個結(jié)點最多只有兩個孩子，這顆特定的樹正好是二叉樹。因此可以用以下方式計算（calculate，簡寫為calc）每個結(jié)點：

• 如果是一個數(shù)字，則返回它的值；

• 如果是一個運算符，則計算左子樹和右子樹的值。

其計算過程是先分別輸入3和4，接著計算3+4；然后輸入2，再接著計算2*(3+4)；接著輸入5，最后計算2*(3+4)+5。

傳統(tǒng)的做法是定義一個struct _Node，包含二元運算符和數(shù)字結(jié)點，詳見程序清單 4.12。

程序清單 4.12 表達式算術(shù)樹接口（calctree.h）

其中，使用了名為newNumNode、newAddNode和newMultNode的宏將結(jié)構(gòu)體初始化，表達式算術(shù)樹接口的實現(xiàn)詳見程序清單 4.13。

程序清單 4.13 表達式算術(shù)樹接口的實現(xiàn)（cacltree.c）

表達式算術(shù)樹的使用范例詳見程序清單 4.14。

程序清單 4.14 表達式算術(shù)樹使用范例

如果此方案應(yīng)用于包括上百個結(jié)點的樹時，其消耗的內(nèi)存太大了。

2、抽象類

根據(jù)問題的描述，需求詞匯表中有一組這樣的概念，比如，根結(jié)點和左右葉子結(jié)點的操作數(shù)，且加法和乘法都是二元操作。雖然詞匯表對應(yīng)的詞匯為Node、_pLeft、_pRight、Number、Binary、Additive和Multiplicative，但用Node、_pLeft、_pRight、NumNode、BinNode、AddNode和MultNode描述表達式算術(shù)樹的各個結(jié)點更準(zhǔn)確。

由于AddNode和MultNode都是二元操作，其共性是兩個數(shù)（_pLeft和_pRight）的計算，其可變性分別為加法和乘法，因此可以將它們的共性包含在BinNode中，可變性分別包含在AddNode和MultNode中。

其實輸入操作數(shù)同樣可以視為計算，因此NumNode和BinNode的共性也是計算，不妨將它們的共性上移到Node抽象類中。

顯然，基于面向?qū)ο蟮腃編程，則表達式算術(shù)樹的所有結(jié)點都是從類Node繼承的子類，Node的直系后代為NumNode和BinNode，NumNode表示一個數(shù)，BinNode表示一個二元運算，然后再從BinNode派生兩個類：AddNode和MultNode。

圖 4.7 結(jié)點的類層次

如圖 4.7所示展示了類的層次性，它們是一種“is-a”的抽象層次結(jié)構(gòu)，子類AddNode和MultNode重新定義了BinNode和Node基類的結(jié)構(gòu)和行為。基類代表了一般化的抽象，子類代表了特殊的抽象。雖然抽象類Node或BinNode不能實例化，只能作為其它類的父類，但NumNode、AddNode和MultNode子類是可以實例化的。Node抽象類的定義如下：

除了Node之外，每個子類都要實現(xiàn)自己的nodeCalc計算方法，并返回一個作為計算結(jié)點值的雙精度數(shù)。即：

其中的NumNode結(jié)點是從Node分出來的，_num表示數(shù)值。BinNode也是從Node分出來的，_pLeft和_pRight分別為指向左子樹和右子樹的指針，而AddNode和MultNode又是從BinNode分出來的。

此前，針對繼承和多態(tài)框架，使用了一種稱為靜態(tài)的初始化范型。在這里，將使用動態(tài)內(nèi)存分配初始化范型處理繼承和多態(tài)框架。

3、建立接口

由于對象不同，因此動態(tài)分配內(nèi)存的方式不一樣，但其共性是——不再使用某個對象時，釋放動態(tài)內(nèi)存的方法是一樣，因此還需要添加一個node_cleanup()函數(shù)，這是通過free()實現(xiàn)的，詳見程序清單 4.15。

程序清單 4.15 表達式算術(shù)樹的接口（CalcTree1.h）

實現(xiàn)表達式算術(shù)樹的第一步是輸入數(shù)據(jù)和初始化NumNode結(jié)構(gòu)體的變量isa和_num，newNumNode()函數(shù)原型如下：

其調(diào)用形式如下：

接下來開始為計算做準(zhǔn)備，node_calc()函數(shù)原型如下：

其調(diào)用形式如下：

然后開始進行加法運算，newAddNode()函數(shù)原型如下：

其調(diào)用形式如下：

當(dāng)然，也可以開始進行乘法運算了，newMultNode()函數(shù)原型如下：

其調(diào)用形式如下：

一切準(zhǔn)備就緒，則計算最終結(jié)果并釋放不再使用的資源，node_cleanup()函數(shù)原型如下：

其調(diào)用形式如下：

4、實現(xiàn)接口

顯然，為每個結(jié)點創(chuàng)建了相應(yīng)的類后，就可以為每個結(jié)點創(chuàng)建一個動態(tài)變量，即可在運行時根據(jù)需要使用malloc()分配內(nèi)存并使用指針存儲該地址，并使用指針初始化結(jié)構(gòu)體的各個成員，CalcTree1.c接口的實現(xiàn)詳見程序清單 4.16。

程序清單 4.16表達式算術(shù)樹接口的實現(xiàn)（CalcTree1.c）

>>> 4.4.3 虛函數(shù)

雖然可以使用繼承實現(xiàn)表達式算術(shù)樹，但實現(xiàn)代碼中的每個對象都有函數(shù)指針。如果結(jié)構(gòu)體內(nèi)有很多函數(shù)指針，或必須生成更多的對象時，將會出現(xiàn)多個對象具有相同的行為、需要較多的函數(shù)指針和需要生成較多數(shù)量的對象，將會浪費很多的內(nèi)存。

不妨將Node中的成員轉(zhuǎn)移到另一個結(jié)構(gòu)體中實現(xiàn)一個虛函數(shù)表，然后在接口中創(chuàng)建一個抽象數(shù)據(jù)類型NodeVTable，在此基礎(chǔ)上定義一個指向該表的指針vtable。比如：

表達式算術(shù)樹的接口詳見程序清單 4.17，其中的NumNode派生于Node，_num表示數(shù)值；BinNode也是派生于Node，pLeft和pRight分別表示指向左子樹和右子樹的指針；而AddNode和MultNode又派生于BinNode。雖然抽象類包含一個或多個純虛函數(shù)類，但不能實例化（此類沒有對象可創(chuàng)建），只有從一個抽象類派生的類和為所有純虛函數(shù)提供了實現(xiàn)代碼的類才能實例化，它們都必須提供自己的計算方法node_calc和node_cleanup。

程序清單 4.17 表達式算術(shù)樹接口（CalcTree2.h）

顯然，為每個結(jié)點創(chuàng)建了相應(yīng)的類后，就可以為每個結(jié)點創(chuàng)建一個動態(tài)變量，即可在運行時根據(jù)需要使用malloc()分配內(nèi)存并使用指針存儲該地址，并使用指針初始化結(jié)構(gòu)體的各個成員，表達式算術(shù)樹接口的實現(xiàn)詳見程序清單 4.18。

程序清單 4.18 表達式算術(shù)樹接口的實現(xiàn)（CalcTree2.c）