Object-Oriented Programming - Virtual Functions

Professor Zhou Ligong's years of hard work "Programming and Data Structure" and "Programming for AMetal Framework and Interface (I)", the electronic version has been distributed to electronic engineers and college groups for free, after the content of the book is published, in electronic The industry has set off a learning boom. Authorized by Professor Zhou Ligong, this public number has serialized the contents of the book "Programming and Data Structure" and is willing to share it.

The fourth chapter is object-oriented programming , this article is 4.4 virtual function .

> > >    4.4.1 Binary Tree

The application of the tree is very extensive. For example, the database is constructed from a tree, and the lexical analyzer of the C compiler is also a tree generated by parsing.

A tree is a data structure that manages data like the relationship between a tree trunk, a tree branch, and a leaf. Usually, a tree has a trunk from the root, and then some branches grow from the trunk, and then a smaller branch grows on the branch. The leaves grow on the thinnest branches, and the data structure of the tree is like a tree that is inverted by a tree.

A tree is made up of nodes (vertices) and branches, with a node as the starting point. This starting point is called the root node of the tree. A few branches can be connected from the root node, each branch is connected to a node, and the extended nodes can continue to extend new nodes through the branches. The old nodes in this process are called parent nodes, and the new nodes that are extended are called child nodes, and the nodes that are not in one child node are called leaf nodes. In addition, the number of branches that pass through the root node to reach a node is called the depth of the node.

From the family relationship of genealogy trees, the genealogical tree makes it easier to introduce the terminology used to describe tree structure in computer science. Every node in the tree can have several children, but only one parent. The meaning of ancestors and grandchildren in the tree is exactly the same as in everyday language.

In contrast to the roots are nodes without children, these nodes are called leaves, and nodes that are neither roots nor leaves are called internal nodes, and the length of the tree is defined as the length of the longest path from root to leaf. (or depth). In a tree, if the length of each path from root to leaf is roughly equal, then the tree is called a balanced tree. In fact, it is very complicated to achieve a tree that can always guarantee a balance, which is why there are many different kinds of trees.

In fact, each level of the tree is a bifurcation form. If a node in the tree and its subtree are arbitrarily selected, the obtained part conforms to the definition of the tree. Each node in the tree can be seen as the root of the subtree rooted at itself, which is the recursive nature of the tree structure. If the tree is examined from a recursive point of view, then the tree is just a collection of nodes and a subtree attached to it - in the context of a leaf node the set is empty, so the recursive nature of the tree is its underlying representation and most The basis of the algorithm for tree operations.

An important subclass of the tree is the binary tree, which is a commonly used tree data structure. Each node of the binary tree has at most two child nodes (left and right), and the nodes other than the root are either the left child of the parent node or the right child.

> > >    4.4.2 Expression Math Tree

1, the problem

Solving an arithmetic expression is a binary tree whose nodes contain two types of objects: operators and final values. An operator is an object that has an operand, and the final value is an object that has no operands. The idea behind the expression tree—stored in the parent node is the operator whose operand is composed of subtrees that extend from the child nodes. The operands may be final values, or they may themselves be other expressions. The expression is expanded in the subtree, and the final value resides in the leaf node. The advantage of this organization is that an expression can be converted into three common representations by expression: prefix, infix, and suffix, but The infix expression is the most familiar expression learned in mathematics. Here, the 2*(3+4)+5 infix expression arithmetic tree structure will be taken as an example.

First, split "2*(3+4)+5" into the left subtree and the right subtree, where "+" is the root node and the value of the left subtree is 2*(3+4), right subtree The value is 5; then 2*(3+4) is split into a left subtree and a right subtree, where "*" is the root node, the value of the left subtree is 2, and the value of the right subtree is 3+. 4; then split 3+4 into a left subtree and a right subtree, where "+" is the root node, the value of the left subtree is 3, and the value of the right subtree is 4, as shown in Figure 4.6. Note that no knowledge of parentheses or operator precedence is required in the representation of the tree because the computational process it describes is unique.

Figure 4.6 Expression Math Tree

It can be seen that from the root node to the leaf analysis, the nodes of the expression arithmetic tree are the arithmetic operators "+(Additive)" and "*(Multiplicative)", and its leaves are operands (Number ). Since all operations here are Binary, that is, there are at most two children per node, this particular tree happens to be a binary tree. So you can calculate (calculate, abbreviated as calc) each node in the following way:

If it is a number, return its value;

If it is an operator, the values ​​of the left and right subtrees are calculated.

The calculation process is to input 3 and 4 respectively, then calculate 3+4; then input 2, then calculate 2*(3+4); then input 5, and finally calculate 2*(3+4)+5.

The traditional approach is to define a struct _Node that contains binary operators and numeric nodes. See Listing 4.12 for details.

Listing 4.12 Expression Arithmetic Tree Interface (calctree.h)

The structure is initialized using macros named newNumNode, newAddNode, and newMultNode. The implementation of the expression arithmetic tree interface is shown in Listing 4.13.

Listing 4.13 Implementation of the Expression Arithmetic Tree Interface (cacltree.c)

An example of the use of an expression arithmetic tree is shown in Listing 4.14.

Listing 4.14 Example of Expression Math Tree Usage

If this scheme is applied to a tree that includes hundreds of nodes, it consumes too much memory.

2, abstract class

According to the description of the problem, there is a set of such concepts in the demand vocabulary, such as the root node and the operands of the left and right leaf nodes, and the addition and multiplication are binary operations. Although the vocabulary corresponds to Node, _pLeft, _pRight, Number, Binary, Additive, and Multiplicative, it is more accurate to describe the nodes of the expression arithmetic tree with Node, _pLeft, _pRight, NumNode, BinNode, AddNode, and MultNode.

Since both AddNode and MultNode are binary operations, the commonality is the calculation of two numbers (_pLeft and _pRight) whose variability is addition and multiplication, respectively, so their commonality can be included in BinNode, and the variability is included in AddNode and MultNode.

In fact, the input operand can also be regarded as a calculation. Therefore, the commonality between NumNode and BinNode is also computation. It is possible to move their commonality up to the Node abstract class.

Obviously, based on object-oriented C programming, all nodes of the expression arithmetic tree are subclasses inherited from the class Node. The immediate descendants of Node are NumNode and BinNode, NumNode represents a number, BinNode represents a binary operation, and then Then derive two classes from BinNode: AddNode and MultNode.

Figure 4.7 Class hierarchy of nodes

The hierarchy of classes is shown in Figure 4.7. They are an abstract hierarchy of "is-a". The subclasses AddNode and MultNode redefine the structure and behavior of the BinNode and Node base classes. The base class represents a generalized abstraction, and the subclass represents a special abstraction. Although the abstract class Node or BinNode cannot be instantiated and can only be used as a parent class of other classes, the NumNode, AddNode, and MultNode subclasses can be instantiated. The Node abstract class is defined as follows:

In addition to Node, each subclass implements its own nodeCalc calculation method and returns a double precision as a computed node value. which is:

The NumNode node is separated from Node, and _num represents the value. BinNode is also separated from Node. _pLeft and _pRight are pointers to the left and right subtrees respectively, and AddNode and MultNode are separated from BinNode.

Previously, for inheritance and polymorphic frameworks, an initialization paradigm called static was used. Here, the dynamic memory allocation initialization paradigm will be used to handle inheritance and polymorphic frameworks.

3, establish an interface

Because the objects are different, the way to dynamically allocate memory is different, but the commonality is that when you no longer use an object, the method of releasing dynamic memory is the same, so you need to add a node_cleanup() function, which is through free( For implementation, see Listing 4.15.

Listing 4.15 The interface to the expression arithmetic tree (CalcTree1.h)

The first step in implementing the expression arithmetic tree is to enter the data and initialize the variables isa and _num of the NumNode structure. The prototype of the newNumNode() function is as follows:

The form of its call is as follows:

The next step is to prepare for the calculation. The prototype of the node_calc() function is as follows:

The form of its call is as follows:

Then start the addition, the newAddNode() function prototype is as follows:

The form of its call is as follows:

Of course, you can also start multiplication. The newMultNode() function prototype is as follows:

The form of its call is as follows:

When everything is ready, the final result is calculated and the resources that are no longer used are released. The prototype of the node_cleanup() function is as follows:

The form of its call is as follows:

4, implement the interface

Obviously, after creating the corresponding class for each node, you can create a dynamic variable for each node. You can use malloc() to allocate memory at runtime and store the address with a pointer, and initialize it with a pointer. The implementation of the CalcTree1.c interface for each member of the structure is detailed in Listing 4.16.

Listing 4.16 Implementation of the Expression Math Tree Interface (CalcTree1.c)

> > >    4.4.3 virtual function

Although you can use inheritance to implement an expression arithmetic tree, each object in the implementation code has a function pointer. If there are many function pointers in the structure, or more objects must be generated, multiple objects will have the same behavior, require more function pointers, and need to generate a larger number of objects, which will waste a lot of memory.

You can transfer a member of Node to another struct to implement a virtual function table, and then create an abstract data type NodeVTable in the interface, on this basis, define a pointer vtable pointing to the table. such as:

The interface of the expression arithmetic tree is shown in Listing 4.17, where NumNode is derived from Node, _num represents a value, BinNode is also derived from Node, pLeft and pRight represent pointers to the left and right subtrees, respectively, and AddNode and MultNode are Derived from BinNode. Although an abstract class contains one or more pure virtual function classes, it cannot be instantiated (such objects have no objects to create), only classes derived from an abstract class and classes that provide implementation code for all pure virtual functions can be instantiated, They must all provide their own calculation methods node_calc and node_cleanup.

Listing 4.17 Expression Arithmetic Tree Interface (CalcTree2.h)

Obviously, after creating the corresponding class for each node, you can create a dynamic variable for each node. You can use malloc() to allocate memory at runtime and store the address with a pointer, and initialize it with a pointer. The implementation of the expression arithmetic tree interface for each member of the structure is detailed in Listing 4.18.

Listing 4.18 Implementation of the Expression Arithmetic Tree Interface (CalcTree2.c)