📄 c_digr.html

📁 C ++ in action
💻 HTML
字号:
<html>
<head>
	<title>C-language Digression</title>
    <meta  name="description" content="Implementation of virtual functions in C">
    <meta name="keywords" content="virtual function, polymorphism, implementation, pointer, function pointer">
	<link rel="stylesheet" href="../../rs.css">
</head>

<body background="../../images/margin.gif" bgcolor="#FFFFDC">

<!-- Main Table -->
<table cellpadding="6">
    <tr>
    <td width="78">
	&nbsp;
    
	<td>

<h3>C Digression</h3>


<p>How would the same problem be solved in C, where there are no virtual functions? A good way would actually be to try to implement a virtual table by hand, and make calls through function pointers. You抎 be surprised how often it is done. It is called object oriented programming in C. The more traditional approach would be to define <var>struct</var> <var>Node</var> that has enough fields to accommodate the needs of binary operators as well as numeric nodes. The identity of the node would be stored in a separate field.
<tr>
<td class=margin valign=top>

<br>
<a href="source/ctree.zip">
<img src="Images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
<td>

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>#define NUM_NODE 1
#define ADD_NODE 2
#define MULT_NODE 3

struct Node
{
    /* Node type */
    int type;
    /* Used only in numeric nodes */
    double val;
    /* Used only in binary nodes */
    Node * pLeft;
    Node * pRight;
};</pre>
</table><!-- End Code -->

<p>Virtual functions in C++ would be turned into multi-way conditionals, like this switch statement below.

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>

<pre>double Calc (Node * pNode)
{
    switch (pNode-&gt;type)
    {
    case NUM_NODE:
        return pNode-&gt;val;
    case ADD_NODE:
        return Calc (pNode-&gt;pLeft) + Calc (pNode-&gt;pRight);
    case MULT_NODE:
        return Calc (pNode-&gt;pLeft) * Calc (pNode-&gt;pRight);
    }
    return 0;
}</pre>
</table><!-- End Code -->

<p>Obviously, this solution would be too expensive when applied to trees with hundreds of nodes. This is when a C programmer would fetch     his or her powerful secret weapon. When the going gets tough, type safety is the first to go梪se casts (I am being sarcastic here). Instead of packing everything into a single <var>struct</var>, the programmer creates a variety of <var>structs</var>:

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>

<pre>struct Node
{
    int type;
};

struct NumNode
{
    int type;
    double val;
};

struct BinNode
{
    int type;
    Node * pLeft;
    Node * pRight;
};</pre>
</table><!-- End Code -->

<p>Some would even use a byte to store type梩rading speed for size (on many processors fetching a word aligned value is faster than fetching a byte aligned value). The function <var>Calc</var> takes a pointer to <var>Node</var> and, based on its type field, casts it to the appropriate pointer. (In fact, one could even get rid of the last pretense of type safety and pass <var>Calc</var> a void pointer.)

<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>

<pre>double Calc (Node * pNode)
{
    switch (pNode-&gt;type)
    {
        case NUM_NODE:
            return ((NumNode *)pNode)-&gt;val;
        case ADD_NODE:
        {
            BinNode * pN = (BinNode *) pNode;
            return Calc (pN-&gt;pLeft) + Calc (pN-&gt;pRight);
        }
        case MULT_NODE:
        {
            BinNode * pN = (BinNode *) pNode;
            return Calc (pN-&gt;pLeft) * Calc (pN-&gt;pRight);
        }
        default:
            printf ("Bad node type\n");
    }
    return 0;
}</pre>
</table><!-- End Code -->

<!-- Sidebar -->
<table width="100%" border=0 cellpadding=5><tr>
<td width=10>
<td bgcolor="#cccccc" class=sidebar>

I haven't explained casting yet, and I'm very reluctant to do it at this stage. Casting means cheating the compiler. You have an object that is declared as a pointer to Node and you are telling the compiler to treat is as a pointer to BinNode. This way, you are bypassing the compiler's elaborate mechanism of type checking. Now it's up to you, the programmer, to make sure that the pointer in question actually points to a BinNode and not something else.
<td width=10>
</table>
<!-- End Sidebar -->



<p>Notice that even the &quot;constructor&quot;
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -