近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對(duì)本書內(nèi)容進(jìn)行連載。

>>>>1.1虛函數(shù)

>>>1.1.1 二叉樹

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

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

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

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

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

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

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

>>>1.1.2 表達(dá)式算術(shù)樹

1. 問題

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

首先將“2*（3+4）+5”拆分為左子樹和右子樹，其中，“+”為根節(jié)點(diǎn)，左子樹的值為2*（3+4），右子樹的值為5；接著將2*(3+4)拆分為左子樹和右子樹，其中，“*”為根節(jié)點(diǎn)，左子樹的值為2，右子樹的值為3+4；然后將3+4拆分為左子樹和右子樹，其中，“+”為根節(jié)點(diǎn)，左子樹的值為3，右子樹的值為4，詳見圖4.6。注意，樹的表示法中不需要任何小括號(hào)或運(yùn)算符優(yōu)先級(jí)的知識(shí)，因?yàn)樗枋龅挠?jì)算過程是唯一的。

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

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

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

● 如果是一個(gè)運(yùn)算符，則計(jì)算左子樹和右子樹的值。

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

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

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

1 #pragma once

2

3 #define NUM_NODE 1

4 #define ADD_NODE 2

5 #define MULT_NODE 3

6

7 typedef struct _Node{

8 int type;

9 double val;

10 struct _Node *pLeft;

11 struct _Node *pRight;

12 }Node;

13

14 double Calc(Node * pNode);

15

16 #define newNumNode(val) {NUM_NODE, (val), NULL, NULL};

17 #define newAddNode(pLeft, pRight) {ADD_NODE, 0, (pLeft), (pRight)};

18 #define newMultNode(pLeft, pRight) {MULT_NODE, 0 , (pLeft), (pRight)};

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

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

1 #include"Node.h"

2

3 double Calc(Node * pNode)

4 {

5 double x = 0;

6 switch (pNode -> type){

7 case NUM_NODE:

8 x = pNode -> val;

9 break;

10 case ADD_NODE:

11 x = Calc(pNode -> pLeft) + Calc(pNode -> pRight);

12 break;

13 case MULT_NODE:

14 x = Calc(pNode -> pLeft) * Calc(pNode -> pRight);

15 break;

16 default:

17 break;

18 }

19 return x;

20 }

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

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

1 #include

2 #include "Node.h"

3

4 void main()

5 {

6 Node node1 = newNumNode(20.0);

7 Node node2 = newNumNode(-10.0);

8 Node node3 = newAddNode(&node1, &node2);

9 Node node4 = newNumNode(0.1);

10 Node node5 = newMultNode(&node3, &node4);

11 printf("Calculating the tree\n");

12 double x = Calc(&node5);

13 printf("Result:%lf\n", x);

14 }

2. 抽象類

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

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

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

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

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

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

Node抽象類的定義如下：

1 typedef struct _Node{

2 double (*nodeCalc)(struct _Node *pThis);

3 }Node;

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

1 typedef struct _NumNode{

2 Node isa;

3 double _num;

4 }NumNode;

5

6 typedef struct _BinNode{

7 Node isa;

8 Node *_pLeft;

9 Node *_pRight;

10 }BinNode;

11

12 typedef struct _AddNode{

13 BinNode isa;

14 }AddNode;

15

16 typedef struct _MultNode{

17 BinNode isa;

18 }MultNode;

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

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

3.建立接口

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

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

1 #pragma once

2 typedef struct _Node Node;

3 typedef double (*node_calc_t)(Node *pThis);

4 typedef void (*node_cleanup_t)(Node *pThis);

5 struct _Node{

6 node_calc_t node_calc;

7 node_cleanup_t node_cleanup;

8 };

9

10 typedef struct _NumNode{

11 Node isa;

12 double _num;

13 }NumNode;

14

15 typedef struct _BinNode{

16 Node isa;

17 Node *_pLeft;

18 Node *_pRight;

19 }BinNode;

20

21 typedef struct _AddNode{

22 BinNode isa;

23 }AddNode;

24

25 typedef struct _MultNode{

26 BinNode isa;

27 }MultNode;

28

29 NumNode * newNumNode(double num);

30 double node_calc(Node *pThis);

31 AddNode * newAddNode(Node *pLeft, Node *pRight);

32 MultNode * newMultNode(Node *pLeft, Node *pRight);

33 void node_cleanup(Node *pThis);

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

NumNode * newNumNode(double num);

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

Node * pNode1 = (Node *)newNumNode(20.0);

Node * pNode2 = (Node *)newNumNode(-10.0);

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

double node_calc(Node *pThis);

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

node_calc(pNode1);

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

AddNode * newAddNode(Node *pLeft, Node *pRight);

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

Node * pNode3 = (Node *)newAddNode(pNode1, pNode2);

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

MultNode * newMultNode(Node *pLeft, Node *pRight);

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

Node * pNode4 = (Node *)newNumNode(0.1);

Node * pNode5 = (Node *)newMultNode(pNode3, pNode4);

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

void node_cleanup(Node *pThis);

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

printf("Calculating the tree\n");

double x = node_calc(pNode5);

printf("Result:%lf\n", x);

node_cleanup(pNode5);

4. 實(shí)現(xiàn)接口

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

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

1 #include

2 #include

3 #include " CalcTree1.h "

4

5 NumNode * newNumNode(double num)

6 {

7 NumNode *pNumNode = malloc(sizeof(NumNode));

8 if(pNumNode != NULL){

9 pNumNode -> isa.node_calc = _numnode_calc;

10 pNumNode -> isa.node_cleanup = _numnode_cleanup;

11 pNumNode -> _num = num;

12 }

13 return pNumNode;

14 }

15

16 static double _numnode_calc(Node *pThis)

17 {

18 printf("numeric node %lf\n", ((NumNode *) pThis) -> _num);

19 return ((NumNode *)pThis) -> _num;

20 }

21

22 static void _numnode_cleanup(Node *pThis)

23 {

24 printf("NumNode cleanup\n");

25 free(pThis);

26 }

27

28 double node_calc(Node *pThis)

29 {

30 return pThis -> node_calc(pThis);

31 }

32

33 AddNode * newAddNode(Node *pLeft, Node *pRight)

34 {

35 AddNode *pAddNode = malloc(sizeof(AddNode));

36 if(pAddNode != NULL){

37 pAddNode -> isa.isa.node_calc =_addnode_calc;

38 pAddNode -> isa.isa.node_cleanup = _binnode_cleanup;

39 pAddNode -> isa._pLeft = pLeft;

40 pAddNode -> isa._pRight = pRight;

41 }

42 return pAddNode;

43 }

44

45 static double _addnode_calc(Node *pThis)

46 {

47 printf("Adding...\n");

48 AddNode * pAddNode = (AddNode*)pThis;

49 return node_calc(pAddNode -> isa._pLeft) + node_calc(pAddNode -> isa._pRight);

50 }

51

52 static double _multnode_calc(Node *pThis)

53 {

54 printf("Multiplying...\n");

55 MultNode * pMultNode = (MultNode*)pThis;

56 return node_calc(pMultNode -> isa._pLeft)*node_calc(pMultNode -> isa._pRight);

57 }

58

59 static void _binnode_cleanup(Node *pThis)

60 {

61 printf("BinNode cleanup\n");

62 BinNode * pBinNode = (BinNode*)pThis;

63 node_cleanup(pBinNode ->_pLeft);

64 node_cleanup(pBinNode ->_pRight);

65 free(pThis);

66 }

67

68 MultNode * newMultNode(Node *pLeft, Node *pRight)

69 {

70 MultNode *pMultNode = malloc(sizeof(MultNode));

71 if(pMultNode != NULL){

72 pMultNode -> isa.isa.node_calc = _multnode_calc;

73 pMultNode -> isa.isa.node_cleanup = _binnode_cleanup;

74 pMultNode -> isa._pLeft = pLeft;

75 pMultNode -> isa._pRight = pRight;

76 }

77 return pMultNode;

78 }

79

80 void node_cleanup(Node *pThis)

81 {

82 pThis -> node_cleanup(pThis);

83 }

>>>1.1.3 虛函數(shù)

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

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

1 //接口（CalcTree2.h）

2 typedef struct _NodeVTable NodeVTable;

3 typedef struct _Node{

4 const NodeVTable * vtable;

5 }Node;

6 //實(shí)現(xiàn)（CalcTree2.c）

7 typedef double (*node_calc_t)(Node *pThis);

8 typedef void (*node_cleanup_t)(Node *pThis);

9 struct _NodeVTable{

10 const node_calc_t node_calc;

11 const node_cleanup_t node_cleanup;

12 };

13 const NodeVTable _addnode_vtable = { _addnode_calc, _binnode_cleanup};

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

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

1 #pragma once

2

3 typedef struct _NodeVTable NodeVTable;

4 typedef struct _Node{

5 const NodeVTable * vtable;

6 }Node;

7

8 typedef struct _NumNode{

9 Node isa;

10 double _num;

11 }NumNode;

12

13 typedef struct _AddNode{

14 Node isa;

15 Node *_pLeft;

16 Node *_pRight;

17 }AddNode;

18

19 typedef struct _MultNode{

20 Node isa;

21 Node *_pLeft;

22 Node *_pRight;

23 }MultNode;

24

25 double node_calc(Node *pThis);

26 void node_cleanup(Node *pThis);

27

28 NumNode * newNumNode(double num);

29 AddNode * newAddNode(Node *pLeft, Node *pRight);

30 MultNode * newMultNode(Node *pLeft, Node *pRight);

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

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

1 #include

2 #include

3 #include " CalcTree2.h "

4

5 typedef double (*node_calc_t)(Node *pThis);

6 typedef void (*node_cleanup_t)(Node *pThis);

7 struct _NodeVTable{

8 const node_calc_t node_calc;

9 const node_cleanup_t node_cleanup;

10 };

11

12 static double _numnode_calc(Node *pThis)

13 {

14 printf("numeric node %lf\n", ((NumNode *)pThis)->_num);

15 return ((NumNode *)pThis) ->_num;

16 }

17

18 static void _numnode_cleanup(Node *pThis)

19 {

20 printf("NumNode cleanup\n");

21 free(pThis);

22 }

23

24 const NodeVTable _numnode_vtable = {_numnode_calc, _numnode_cleanup};

25

26 static void _binnode_cleanup(Node *pThis)

27 {

28 printf("BinNode cleanup\n");

29 BinNode * pBinNode = (BinNode*)pThis;

30 node_cleanup(pBinNode ->_pLeft);

31 node_cleanup(pBinNode ->_pRight);

32 free(pThis);

33 }

34

35 static double _addnode_calc(Node *pThis)

36 {

37 printf("Adding...\n");

38 AddNode * pAddNode = (AddNode*)pThis;

39 return node_calc(pAddNode -> isa._pLeft) + node_calc(pAddNode -> isa._pRight);

40 }

41

42 const NodeVTable _addnode_vtable = { _addnode_calc, _binnode_cleanup };

43

44 static double _multnode_calc(Node *pThis)

45 {

46 printf("Multiplying...\n");

47 MultNode * pMultNode = (MultNode*)pThis;

48 return node_calc(pMultNode -> isa._pLeft)*node_calc(pMultNode -> isa._pRight);

49 }

50

51 const NodeVTable _multnode_vtable = { _multnode_calc, _binnode_cleanup };

52

53 NumNode * newNumNode(double num)

54 {

55 NumNode *pNumNode = malloc(sizeof(NumNode));

56 if(pNumNode != NULL){

57 pNumNode -> isa.vtable = &_numnode_vtable;

58 pNumNode -> _num = num;

59 }

60 return pNumNode;60 return pNumNode;

61 }

62

63 AddNode * newAddNode(Node *pLeft, Node *pRight)

64 {

65 AddNode *pAddNode = malloc(sizeof(AddNode));

66 if(pAddNode != NULL){

67 pAddNode -> isa.isa.vtable = &_addnode_vtable;

68 pAddNode -> isa._pLeft = pLeft;

69 pAddNode -> isa._pRight = pRight;

70 }

71 return pAddNode;

72 }

73

74 MultNode * newMultNode(Node *pLeft, Node *pRight)

75 {

76 MultNode *pMultNode = malloc(sizeof(MultNode));

77 if(pMultNode != NULL){

78 pMultNode -> isa.isa.vtable = &_multnode_vtable;

79 pMultNode -> isa._pLeft = pLeft;

80 pMultNode -> isa._pRight = pRight;

81 }

82 return pMultNode;

83 }

84

85 double node_calc(Node *pThis)

86 {

87 return pThis -> vtable -> node_calc(pThis);

88 }

89

90 void node_cleanup(Node *pThis)

92 pThis -> vtable -> node_cleanup(pThis);

93 }