2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.htm

主要介绍了多任务下面的一些数据结构和算法,比如树和图的一些遍历

*))；</P>
<P style="LINE-HEIGHT: 14pt">if ( pBlock-&gt;ppData == NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">free(pBlock)；</P>
<P style="LINE-HEIGHT: 14pt">return NULL；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;uHead = 0；</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;uTail = 0；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">return pBlock；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/** DeQue的插入尾部函数</P>
<P style="LINE-HEIGHT: 14pt">@param DEQUE *pQue——DeQue指针 </P>
<P style="LINE-HEIGHT: 14pt">@param void *pData——要插入的数据指针 </P>
<P style="LINE-HEIGHT: 14pt">@return INT (by default)<SUB> </SUB>—— 
返回CAPI_SUCCESS表示成功；返回CAPI_FAILED </P>
<P style="LINE-HEIGHT: 14pt">表示失败</P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>INT DeQue_InsertTail( DEQUE 
*pQue</B><B>，</B><B>void *pData )</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK *pBlock；</P>
<P style="LINE-HEIGHT: 14pt">UINT uTailNext；</P>
<P style="LINE-HEIGHT: 14pt">pBlock= pQue-&gt;pLast；</P>
<P style="LINE-HEIGHT: 14pt">if ( pBlock-&gt;uTail == pQue-&gt;uBlockSize－1 ) 
{</P>
<P style="LINE-HEIGHT: 14pt">uTailNext = 0；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else {</P>
<P style="LINE-HEIGHT: 14pt">uTailNext = pBlock-&gt;uTail + 1；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">if ( pBlock-&gt;uHead != uTailNext ) { /* 队列未满的情况 
*/</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;ppData[pBlock-&gt;uTail] = pData；</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;uTail = uTailNext；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else {</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK *pNewBlock = 
DeQueBlock_Create(pQue-&gt;uBlockSize)；</P>
<P style="LINE-HEIGHT: 14pt">if ( pNewBlock == NULL ) {</P>
<P style="LINE-HEIGHT: 14pt">return CAPI_FAILED；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">if ( pBlock-&gt;uMapPos &gt;= pQue-&gt;uMapSize－1 ) 
{</P>
<P style="LINE-HEIGHT: 14pt">/* 重新分配map */</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK **ppMap = malloc(pQue-&gt;uMapSize *2 
*</P>
<P style="LINE-HEIGHT: 14pt">sizeof(DEQUEBLOCK *))；</P>
<P style="LINE-HEIGHT: 14pt">if ( ppMap == NULL ) {</P>
<P style="LINE-HEIGHT: 14pt">return CAPI_FAILED；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">memcpy(ppMap，pQue-&gt;ppMap，</P>
<P style="LINE-HEIGHT: 14pt">pQue-&gt;uMapSize *sizeof(DEQUEBLOCK *) )；</P>
<P style="LINE-HEIGHT: 14pt">pQue-&gt;uMapSize *= 2；</P>
<P style="LINE-HEIGHT: 14pt">free(pQue-&gt;ppMap)；</P>
<P style="LINE-HEIGHT: 14pt">pQue-&gt;ppMap = ppMap；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">pNewBlock-&gt;uMapPos = pBlock-&gt;uMapPos + 1；</P>
<P style="LINE-HEIGHT: 14pt">pNewBlock-&gt;ppData[0] = pData；</P>
<P style="LINE-HEIGHT: 14pt">pNewBlock-&gt;uTail += 1；</P>
<P style="LINE-HEIGHT: 14pt">pQue-&gt;ppMap[pNewBlock-&gt;uMapPos] = 
pNewBlock；</P>
<P style="LINE-HEIGHT: 14pt">pQue-&gt;pLast = pNewBlock；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">return CAPI_SUCCESS；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/** DeQue的弹出头部节点数据函数</P>
<P style="LINE-HEIGHT: 14pt">@param DEQUE *pQue——DeQue指针 </P>
<P style="LINE-HEIGHT: 14pt">@return void *——弹出的头部数据指针 </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>void *DeQue_PopHead(DEQUE *pQue)</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK *pBlock；</P>
<P style="LINE-HEIGHT: 14pt">UINT uHead；</P>
<P style="LINE-HEIGHT: 14pt">pBlock = pQue-&gt;pFirst；</P>
<P style="LINE-HEIGHT: 14pt">uHead = pBlock-&gt;uHead；</P>
<P style="LINE-HEIGHT: 14pt">if ( uHead != pBlock-&gt;uTail ) {</P>
<P style="LINE-HEIGHT: 14pt">/* 头部和尾部没有重合表示队列不为空的情况 */</P>
<P style="LINE-HEIGHT: 14pt">if ( uHead == pQue-&gt;uBlockSize－1 ) {</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;uHead = 0；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else {</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;uHead += 1；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">if ( pBlock-&gt;uHead == pBlock-&gt;uTail ) {</P>
<P style="LINE-HEIGHT: 14pt">/* 队列中只有一个元素的情况，如果存在下一块则需要指向下一个块 */</P>
<P style="LINE-HEIGHT: 14pt">if ( pQue-&gt;pLast != pQue-&gt;pFirst ) {</P>
<P style="LINE-HEIGHT: 14pt">UINT uMapPos = pBlock-&gt;uMapPos；</P>
<P style="LINE-HEIGHT: 14pt">DeQueBlock_Destroy(pQue，pBlock，NULL)；</P>
<P style="LINE-HEIGHT: 14pt">pBlock = pQue-&gt;ppMap[uMapPos + 1]；</P>
<P style="LINE-HEIGHT: 14pt">pQue-&gt;pFirst = pBlock；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">return pBlock-&gt;ppData[uHead]；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else {</P>
<P style="LINE-HEIGHT: 14pt">return NULL；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<H3><A name=_Toc122884718></A><A name=_Toc116222476></A>2.2.5 
各种队列的时间效率测试及分析</H3>
<P 
style="LINE-HEIGHT: 16.5pt">下面对普通环形队列(Queue)，STL的动态队列(STL∷deque)和动态环形队列(DeQue)之间的效率差别进行比较。</P>
<H4 style="LINE-HEIGHT: 16.5pt">1. 测试环境</H4>
<P style="LINE-HEIGHT: 14pt">CPU： Celeron 2.4G</P>
<P style="LINE-HEIGHT: 14pt">Memory： 256M</P>
<P style="LINE-HEIGHT: 14pt">OS： Windows</P>
<H4 style="LINE-HEIGHT: 16.5pt">2. 测试结果</H4>
<P style="LINE-HEIGHT: 16.5pt">测试结果如表2-1所示。</P>
<P>表2-1 各种队列的效率测试结果</P>
<DIV align=center>
<TABLE 
style="BORDER-RIGHT: medium none; BORDER-TOP: medium none; BORDER-LEFT: medium none; BORDER-BOTTOM: medium none; BORDER-COLLAPSE: collapse" 
cellSpacing=0 cellPadding=0 border=1>
  <TBODY>
  <TR style="HEIGHT: 19.5pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center></P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center>初始条件</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center>执行的操作</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" 
    align=center>花费时间(ms)</P></TD></TR>
  <TR style="HEIGHT: 19.5pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">Queue</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">队列大小设为128</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">插入2 000 000个整数再全部弹出</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center>93</P></TD></TR>
  <TR style="HEIGHT: 19.5pt">
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 62.9pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=84>
      <P style="LINE-HEIGHT: 14pt">Queue</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 112.1pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=149>
      <P style="LINE-HEIGHT: 14pt">队列大小设为2 000 000</P></TD>
    <TD 
    style="BORDER-RIGHT: windowtext 1pt solid; PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 148.85pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent" 
    width=198>
      <P style="LINE-HEIGHT: 14pt">插入2 000 000个整数再全部弹出</P></TD>
    <TD 
    style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; BORDER-LEFT-COLOR: #ebe9ed; PADDING-BOTTOM: 0cm; WIDTH: 71.4pt; BORDER-TOP-COLOR: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 19.5pt; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #ebe9ed" 
    width=95>
      <P style="LINE-HEIGHT: 14pt; TEXT-ALIGN: center" align=center>47</P></TD></TR>
  <TR style="HEIGHT: 33.75pt">