⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 lib0037.html

📁 Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag
💻 HTML
📖 第 1 页 / 共 5 页
字号:
🔍
12345 
   <span style="background-color:d9d9d9">else if( val &lt; (*(*link)).value)</span>
   <span style="background-color:d9d9d9">{</span>
       <span style="background-color:d9d9d9">PRINT("insertNode(): moving left\n",val);</span>
       <span style="background-color:d9d9d9">insertNode(&amp;((*(*link)).left),val);</span>
   <span style="background-color:d9d9d9">}</span>
   <span style="background-color:d9d9d9">else</span>
   <span style="background-color:d9d9d9">{</span>
       <span style="background-color:d9d9d9">PRINT("insertNode(): moving right\n",val);</span>
       <span style="background-color:d9d9d9">insertNode(&amp;((*(*link)).right),val);</span>
   <span style="background-color:d9d9d9">}</span>
   <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end insertNode---------------------------------------------*/</span>

<span style="background-color:d9d9d9">void BinarySearchTree::insertNode(struct BiNode **link, struct</span>
                                  <span style="background-color:d9d9d9">BiNode *ptr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if( *link==NULL )</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">(*link) = (struct BiNode*)malloc(sizeof(struct BiNode));</span>

        <span style="background-color:d9d9d9">(*(*link)).value = (*ptr).value;</span>
        <span style="background-color:d9d9d9">(*(*link)).index = (*ptr).index;</span>
        <span style="background-color:d9d9d9">(*(*link)).nreserved = (*ptr).nreserved;</span>

        <span style="background-color:d9d9d9">(*(*link)).left = NULL;</span>
        <span style="background-color:d9d9d9">(*(*link)).right = NULL;</span>
        <span style="background-color:d9d9d9">PRINT("insertNode(): inserting %d\n",(*ptr).value);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if( (*ptr).value &lt; (*(*link)).value)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">PRINT("insertNode(): moving left\n",(*ptr).value);</span>
        <span style="background-color:d9d9d9">insertNode(&amp;((*(*link)).left),ptr);</span>
    <span style="background-color:d9d9d9">}</span><a name="460"></a><a name="IDX-229"></a>
    <span style="background-color:d9d9d9">else</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">PRINT("insertNode(): moving right\n", (*ptr).value);</span>
        <span style="background-color:d9d9d9">insertNode(&amp;((*(*link)).right),ptr);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end insertNode---------------------------------------------*/</span>

<span style="background-color:d9d9d9">struct BiNode* BinarySearchTree::findNode</span>
<span style="background-color:d9d9d9">(</span>
    <span style="background-color:d9d9d9">struct BiNode *link,</span>
    <span style="background-color:d9d9d9">unsigned long val )</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if(link==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return(NULL);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((*link).value == val)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return(link);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if(val &gt;= (*link).value)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return(findNode((*link).right,val));</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return(findNode((*link).left,val));</span>
    <span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">}/*end findNode---------------------------------------------*/</span>

<span style="background-color:d9d9d9">struct BiNode* BinarySearchTree::deleteSmallestNode(struct</span>
               <span style="background-color:d9d9d9">BiNode **link)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if((*(*link)).left != NULL)</span>
    <span style="background-color:d9d9d9">{</span>
         <span style="background-color:d9d9d9">return(deleteSmallestNode(&amp;((*(*link)).left)));</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else</span>
    <span style="background-color:d9d9d9">{</span>
         <span style="background-color:d9d9d9">struct BiNode *temp;</span>
         <span style="background-color:d9d9d9">temp = *link;</span>
         <span style="background-color:d9d9d9">(*link) = (*(*link)).right;</span>
         <span style="background-color:d9d9d9">return(temp);</span>
     <span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">}/*end deleteSmallestNode------------------------------------*/</span><a name="461"></a><a name="IDX-230"></a>
<span style="background-color:d9d9d9">void BinarySearchTree::deleteNode</span>
<span style="background-color:d9d9d9">(</span>
    <span style="background-color:d9d9d9">struct BiNode **link,</span>
    <span style="background-color:d9d9d9">unsigned long val )</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if( (*link)==NULL )</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">PRINT("deleteNode(): %d does not exist\n",val);</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">if(val &lt; (*(*link)).value)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">deleteNode(&amp;((*(*link)).left),val);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if(val &gt; (*(*link)).value)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">deleteNode(&amp;((*(*link)).right),val);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">/*</span>
        <span style="background-color:d9d9d9">have equality</span>
        <span style="background-color:d9d9d9">3 cases</span>
            <span style="background-color:d9d9d9">i)  node has no children (just delete it)</span>
            <span style="background-color:d9d9d9">ii) node has one child</span>
            <span style="background-color:d9d9d9">(set parent of current node</span>
              <span style="background-color:d9d9d9">to child of current node, delete current node)</span>
            <span style="background-color:d9d9d9">iii) node has two children/subtrees</span>

            <span style="background-color:d9d9d9">In the third case, get smallest/leftmost node in</span>
            <span style="background-color:d9d9d9">right subtree of current node. Then delete the</span>
            <span style="background-color:d9d9d9">leftmost node and place its value in the current</span>
            <span style="background-color:d9d9d9">node (retain binary tree properties)</span>
        <span style="background-color:d9d9d9">*/</span>

        <span style="background-color:d9d9d9">struct BiNode *temp;</span>
        <span style="background-color:d9d9d9">temp = *link;</span>

        <span style="background-color:d9d9d9">if((*(*link)).right==NULL)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">(*link) = (*(*link)).left;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">else if((*(*link)).left==NULL)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">(*link) = (*(*link)).right;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">else</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">temp = deleteSmallestNode(&amp;((*(*link)).right));</span><a name="462"></a><a name="IDX-231"></a>
             <span style="background-color:d9d9d9">(*(*link)).value = (*temp).value;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">PRINT("deleteNode(): freeing %d\n",val);</span>
        <span style="background-color:d9d9d9">free(temp);</span>


    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end deleteNode ---------------------------------------------------*/</span>

<span style="background-color:d9d9d9">void BinarySearchTree::deleteAll(struct BiNode **link)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if((*link)==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">deleteAll(&amp;((*(*link)).left));</span>
    <span style="background-color:d9d9d9">deleteAll(&amp;((*(*link)).right));</span>

    <span style="background-color:d9d9d9">PRINT("deleteAll(): freeing %d\n",(*(*link)).value);</span>
    <span style="background-color:d9d9d9">free((*link));</span>
    <span style="background-color:d9d9d9">*link=NULL;</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end deleteAll-------------------------------------------*/</span>

<span style="background-color:d9d9d9">void BinarySearchTree::printTree(struct BiNode *link, int level)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">int i;</span>
    <span style="background-color:d9d9d9">if(link==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">printTree((*link).right,level+1);</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;level;i++){ printf ("-");}</span>
    <span style="background-color:d9d9d9">printf("(%d)\n",(*link).value);</span>

    <span style="background-color:d9d9d9">printTree((*link).left,level+1);</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end printTree-----------------------------------------------------------------*/</span>

<span style="background-color:d9d9d9">unsigned long BinarySearchTree::getHeight(struct BiNode *link)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long u;</span>
    <span style="background-color:d9d9d9">unsigned long v;</span>

    <span style="background-color:d9d9d9">if(link==NULL) { return(-1); }</span><a name="463"></a><a name="IDX-232"></a>
    <span style="background-color:d9d9d9">u = getHeight((*link).left);</span>
    <span style="background-color:d9d9d9">v = getHeight((*link).right);</span>

    <span style="background-color:d9d9d9">if(u &gt; v){ return(u+1); }</span>
    <span style="background-color:d9d9d9">else{ return(v+1); }</span>

<span style="background-color:d9d9d9">}/*end getHeight----------------------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">bitmap.cpp</h4>
<p class="first-para">The <span class="fixed">BitMap</span> class is also fairly straightforward in its implementation and could be reused for something else:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">1 bitmap bit = 16-byte block of memory</span>
<span style="background-color:d9d9d9">1 bitmap byte (i.e., block) = 128-byte block of memory</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">#define BYTES_PER_BITMAP_BIT    16</span>
<span style="background-color:d9d9d9">#define BYTES_PER_BITMAP_BYTE    128</span>

<span style="background-color:d9d9d9">/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span style="background-color:d9d9d9">+ declarations</span>
<span style="background-color:d9d9d9">+</span>
<span style="background-color:d9d9d9">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/</span>

<span style="background-color:d9d9d9">class BitMap</span>
<span style="background-color:d9d9d9">{</span>
   <span style="background-color:d9d9d9">private:</span>
   <span style="background-color:d9d9d9">unsigned char *map;</span>
   <span style="background-color:d9d9d9">unsigned long nbytes;</span>
   <span style="background-color:d9d9d9">unsigned long nbits;</span>

   <span style="background-color:d9d9d9">public:</span>
   <span style="background-color:d9d9d9">BitMap(unsigned long nblocks);</span>
   <span style="background-color:d9d9d9">~BitMap();</span>
   <span style="background-color:d9d9d9">unsigned long getByteSize();</span>
   <span style="background-color:d9d9d9">void setBits(int val,unsigned long nbits,unsigned long</span>
                <span style="background-color:d9d9d9">index);</span>
   <span style="background-color:d9d9d9">int getBit(unsigned long index);</span>
   <span style="background-color:d9d9d9">long getBitRun(unsigned long size);</span>
   <span style="background-color:d9d9d9">void printMap();</span>
<span style="background-color:d9d9d9">};</span>


<span style="background-color:d9d9d9">/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span style="background-color:d9d9d9">+ definitions</span>
<span style="background-color:d9d9d9">+</span>
<span style="background-color:d9d9d9">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/</span><a name="464"></a><a name="IDX-233"></a>
12345

⌨️ 快捷键说明

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