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

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

<H4 style="LINE-HEIGHT: 15.8pt">4. 环形队列的动态增长</H4>
<P 
style="LINE-HEIGHT: 15.8pt">可能读者会问，如果队列已满，想要队列自动增长来插入新的元素，用这种环形队列是否可以实现呢？其实可以采用一种简单的技术来实现环形队列的动态增长，其方法如下。</P>
<P 
style="LINE-HEIGHT: 15.8pt">在插入操作中如果发现队列已满，可以再分配一个是原来队列双倍的空间，将原队列中的数据复制到新分配的空间中，再将新分配的空间作为队列，将原来的队列释放掉。复制时有两种情况，如图2-4所示。</P>
<P style="LINE-HEIGHT: 15.8pt"></P>
<P align=center><IMG 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/image2.4.jpg"></P>
<P style="LINE-HEIGHT: 15.8pt" align=center>图2-4 环形队列动态增长示意图</P>
<P 
style="LINE-HEIGHT: 15.8pt">图2-4(a)所示的是last大于first的情况，这时只要简单地按顺序将队列中的元素复制到新分配的空间中即可。如图2-4(b)所示，先将1～6复制过去，再插入7。</P>
<P 
style="LINE-HEIGHT: 15.8pt">图2-4(c)所示的是last小于first的情况，这种情况要分两次复制，先将first和队列空间最尾部间的元素复制到新空间中，再将队列空间头部和last之间的元素复制到刚才复制的元素的后面即可。如图2-4(d)所示，先将4～7复制过去，再将8，9复制到7的后面，然后再在9的后面插入10。</P>
<P>采用上述方法实现动态环形队列比较简单，且整个队列空间在物理上是连续的，使用了确定的内存空间。但其缺点是需要复制数据，当队列中元素很多时，如果遇上队列满，这时插入数据很费时间。有没有其他办法实现既可以将队列动态扩大，又不需要复制数据呢？</P>
<P>做一个简单的推导。由于队列是FIFO的，因此可以将队列看成是一个连续的序列，存储队列元素的空间在物理上或逻辑上也必须是连续的。首先，要想不复制数据，原来的队列空间必须继续使用，否则必然要将原来存在队列中的数据移动到新分配的空间。由于队列空间的前后内存可能已经被使用了，显然无法做到在物理上将队列空间扩大成为连续的空间，因此必须另外分配一块空间，把新分配的空间和原来的队列空间在逻辑上连起来，成为一个在逻辑上是连续的空间。</P>
<H4>5. 环形队列的C语言结构体描述</H4>
<P style="LINE-HEIGHT: 14pt">typedef struct QUEUE_st {</P>
<P style="LINE-HEIGHT: 14pt">void **ppData； /* 存放数据指针的指针数组 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uMaxCount； /* 队列中的最大数据数量 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uHead； /* 队列头部位置 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uTail； /* 队列尾部位置 */</P>
<P style="LINE-HEIGHT: 14pt">} QUEUE；</P>
<H4>6. 环形队列的插入尾部和弹出头部编码实现</H4>
<P style="LINE-HEIGHT: 14pt">/** 插入数据到队列的尾部的函数，如果队列已满会自动将队列空间扩大一倍再插入</P>
<P style="LINE-HEIGHT: 14pt">@param QUEUE *pQueue——队列指针 </P>
<P style="LINE-HEIGHT: 14pt">@param void *pData——要插入的数据指针 </P>
<P style="LINE-HEIGHT: 14pt">@return INT—— 
返回CAPI_FAILED表示队列已满，申请不到内存将队列再扩大，插入失</P>
<P style="LINE-HEIGHT: 14pt">败；返回CAPI_SUCCESS表示插入成功</P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>INT Queue_InsertTail( QUEUE 
*pQueue</B><B>，</B><B>void *pData )</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">UINT uTailNext；</P>
<P style="LINE-HEIGHT: 14pt">/* 求出尾部位置的下一个位置 */</P>
<P style="LINE-HEIGHT: 14pt">if ( pQueue-&gt;uTail == pQueue-&gt;uMaxCount－1 ) 
{</P>
<P style="LINE-HEIGHT: 14pt">/* 当到了数组的最尾部时，下一个要从数组头部重新计算 */</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 = pQueue-&gt;uTail + 1；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">if ( uTailNext != pQueue-&gt;uHead ) { /* 队列未满的情况 
*/</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;ppData[pQueue-&gt;uTail] = pData；</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;uTail = uTailNext；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else { /* 队列为满的情况 */</P>
<P style="LINE-HEIGHT: 14pt">/* 将队列空间扩大一倍 */ </P>
<P style="LINE-HEIGHT: 14pt">void **ppData = (void 
**)malloc(pQueue-&gt;uMaxCount *2 *sizeof(void *))； </P>
<P style="LINE-HEIGHT: 14pt">if ( ppData == NULL ) {</P>
<P style="LINE-HEIGHT: 14pt">return CAPI_FAILED；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">if ( pQueue-&gt;uHead &gt; pQueue-&gt;uTail ) {</P>
<P style="LINE-HEIGHT: 14pt">UINT i；</P>
<P style="LINE-HEIGHT: 14pt">/* 复制从uHead到队列最尾部间的数据 */</P>
<P style="LINE-HEIGHT: 14pt">for ( i = pQueue-&gt;uHead； i &lt; 
pQueue-&gt;uMaxCount； i++) {</P>
<P style="LINE-HEIGHT: 14pt">ppData[i] = pQueue-&gt;ppData[i]；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/* 复制从0到uTail间的数据 */</P>
<P style="LINE-HEIGHT: 14pt">for ( i = 0； i &lt; pQueue-&gt;uTail； i++) {</P>
<P style="LINE-HEIGHT: 14pt">ppData[i + pQueue-&gt;uMaxCount] = 
pQueue-&gt;ppData[i]；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;uTail += pQueue-&gt;uMaxCount；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else {</P>
<P style="LINE-HEIGHT: 14pt">UINT i；</P>
<P style="LINE-HEIGHT: 14pt">/* 复制从uHead到uTail间的数据 */</P>
<P style="LINE-HEIGHT: 14pt">for ( i = pQueue-&gt;uHead； i &lt; 
pQueue-&gt;uTail； i++) {</P>
<P style="LINE-HEIGHT: 14pt">ppData[i] = pQueue-&gt;ppData[i]；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/* 将数据插入新分配的队列空间中 */</P>
<P style="LINE-HEIGHT: 14pt">ppData[pQueue-&gt;uTail] = pData；</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;uTail += 1；</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;uMaxCount *= 2；</P>
<P style="LINE-HEIGHT: 14pt">free(pQueue-&gt;ppData)；</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;ppData = ppData；</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">/** 队列的弹出头部数据函数</P>
<P style="LINE-HEIGHT: 14pt">@param QUEUE *pQueue——队列指针 </P>
<P style="LINE-HEIGHT: 14pt">@return void *——返回NULL表示队列为空，否则返回弹出的头部数据指针 </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>void *Queue_PopHead(QUEUE *pQueue)</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">UINT uHead；</P>
<P style="LINE-HEIGHT: 14pt">uHead = pQueue-&gt;uHead；</P>
<P style="LINE-HEIGHT: 14pt">if ( uHead != pQueue-&gt;uTail ) {</P>
<P style="LINE-HEIGHT: 14pt">/* 头部和尾部没有重合表示队列不为空的情况 */</P>
<P style="LINE-HEIGHT: 14pt">if ( uHead == pQueue-&gt;uMaxCount－1 ) {</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;uHead = 0；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">else {</P>
<P style="LINE-HEIGHT: 14pt">pQueue-&gt;uHead += 1；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">return pQueue-&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>
<P>上面只列出了主要的插入尾部和弹出头部的函数，实际上环形队列也可以插入在头部，弹出尾部数据，这样环形队列就可以变成一个双向队列了。这部分内容留给读者作为练习。另外，队列的创建和释放操作代码没有在上面列出来，本书附带的光盘中有完整的代码可供参考。</P>
<H3><A name=_Toc122884716></A><A name=_Toc116222474></A>2.2.3 
STL中的动态队列(STL∷deque)</H3>
<P>了解STL的人都知道STL中有一个双向动态队列，HP是采用多个数组来实现一个动态队列，多个数组用一个map来管理。map其实也是一个数组，通过map将多个数组连成一个逻辑上连续的空间，这样便实现了一个在队列满时不需要复制元素的动态队列。下面简单介绍HP的STL中的动态队列实现，如图2-5所示。详情参考STL相关的书籍。</P>
<P></P>
<P align=center><IMG 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/image2.5.jpg"></P>
<P align=center>图2-5 STL中的动态队列示意图</P>
<P>假设map的大小为5，每块的大小为7，初始时，map的第1个元素指向第1块空间，插入7个元素到队列后，由于队列满，需重新分配一块空间，即图中的第2块空间，将map的第2个元素指向这块空间，此时要插入的元素8，9都是在第2块空间中依次插入。如果要从队列中弹出数据，则从first指向的元素弹出，比如要弹出1～7这几个元素，当弹出7后，第一块空间已经没有了元素，此时需要释放掉第1块空间。</P>
<P>HP的STL中的这种实现，随着插入和弹出操作的不断进行会不断地分配新的块和释放空的块。比如块的大小为10，如果插入了1 
000个元素又全部弹出，会重新分配99个块及释放99个块，如果map设得很小，还要进行复杂的map管理操作。</P>
<H3><A name=_Toc122884717></A><A name=_Toc116222475></A>2.2.4 动态环形队列</H3>
<H4>1. 动态环形队列概念的产生</H4>
<P>通常队列的插入和弹出操作都是交替进行的，插入1 000个元素和弹出1 
000个元素交替进行时，可能队列中的元素最多只有几十个。如有50个元素，采用STL的动态队列要进行19次块的分配和释放操作，但如果采用一个有50个元素的环形队列，则不需要重新分配和拷贝数据就可以满足要求。能不能实现一个既可以动态增长又不需要拷贝数据，同时还尽量减少块的分配和释放的操作呢？</P>
<P>要减少块的分配和释放操作，必须提高每个块的利用率，HP的STL中的动态队列，每个块中的元素被弹出后，空间并没有被重复使用，这是导致当数据不断地插入和弹出时，块也不断地分配和释放的原因。在环形队列中，弹出的空间可以重复使用，如果将每个块都设计成环形队列，那么每个块的利用率就大大提高了，就可以减少块的分配和释放操作。</P>
<H4>2. 动态环形队列图解</H4>
<P>多个环形队列组成的一个动态环形队列如图2-6所示。</P>
<P>如图2-6所示，初始时将map大小设为6，环形队列大小设为7，有两个指针first和last分别指向map中的第一个环形队列和最后一个环形队列，先插入1，2，3，4，5，再删除1，2，再插入7，8，9，此时第一个环形队列就满了，因此再插入10时就必须新建一个环形队列了，一直插入到20。由图上看出，共有三个环形队列，每个队列最大可以存储7个元素。还可以看出与STL的动态队列相比，每个环形队列需要一个head、一个tail和一个空的空间，STL的动态队列的每个块不需要任何辅助空间。是不是这种设计比STL的动态队列多浪费很多辅助空间呢？其实不然，如果环形队列的大小设成比正常情况下队列的元素稍多的话，整个队列中大部分情况下只有一个环形队列，消耗的空间并不比STL的动态队列多，当队列元素达到高峰时，需要很多个环形队列，这时消耗的空间会比STL的动态队列大，但如果将环形队列大小设成超过一定值时，多出的辅助空间占整个队列空间的比值很小，比如将环形队列大小设成1 
024，则比值为0.5％左右，几乎可以忽略不计，所以在空间利用率上与STL的动态队列差别不是很大，但是动态环形队列的优势在于不会像STL的动态队列那样频繁地分配和释放内存。</P>
<P style="LINE-HEIGHT: 15.6pt"></P>
<P align=center><IMG 
src="2_2 队列 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/image2.6.jpg"></P>
<P style="LINE-HEIGHT: 15.6pt" align=center>图2-6 动态环形队列示意图</P>
<P 
style="LINE-HEIGHT: 15.6pt">在多任务环境下，特别是服务器软件，由于是长时间运行，通常对内存的使用有很高的要求，频繁分配、释放内存容易产生内存碎片，必然会影响软件长期运行的稳定性，因此，在这种情况下使用像动态环形队列这种内存性能比较好的数据结构就非常合适。</P>
<H4 style="LINE-HEIGHT: 15.6pt">3. 动态环形队列的map管理</H4>
<P 
style="LINE-HEIGHT: 15.6pt">动态环形队列中的map管理也和STL的动态队列一样，当map大小不够时，分配一个大一倍的map，然后将原map中的数据复制到新的map中，释放原map，使用新的map作为队列的map就可以了。复制时，也是将数据复制到新的map中，以便在整个队列的前后都可以插入数据。详细的实现可以参阅以下代码。</P>
<H4 style="LINE-HEIGHT: 15.6pt">4. 动态环形队列的C语言结构体定义</H4>
<P style="LINE-HEIGHT: 14pt">/* DeQue中的环形队列结构体定义 */</P>
<P style="LINE-HEIGHT: 14pt">typedef struct DEQUEBLOCK_st {</P>
<P style="LINE-HEIGHT: 14pt">UINT uHead； /* 环形队列的头部 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uTail； /* 环形队列的尾部 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uMapPos； /* 所对应map中的位置 */</P>
<P style="LINE-HEIGHT: 14pt">void **ppData； /* 数据指针数组 */</P>
<P style="LINE-HEIGHT: 14pt">} DEQUEBLOCK；</P>
<P style="LINE-HEIGHT: 14pt">/* DeQue的结构体定义 */</P>
<P style="LINE-HEIGHT: 14pt">typedef struct DEQUE_st {</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK **ppMap； /* 管理环形队列的map数组指针 */</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK *pFirst； /* 第一个环形队列指针 */</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK *pLast； /* 最后一个环形队列指针 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uMapSize； /* map大小 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uBlockSize； /* 环形队列大小 */</P>
<P style="LINE-HEIGHT: 14pt">} DEQUE；</P>
<H4 style="LINE-HEIGHT: 16.5pt">5. 动态环形队列的插入和弹出头部操作代码</H4>
<P style="LINE-HEIGHT: 14pt">/** DeQue中的环形队列创建函数，其中使用两次malloc()函数可以优化成调用</P>
<P style="LINE-HEIGHT: 14pt">一次malloc()</P>
<P style="LINE-HEIGHT: 14pt">@param UINT uBlockSize——环形队列大小 </P>
<P style="LINE-HEIGHT: 14pt">@return DEQUEBLOCK *——环形队列指针 </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>DEQUEBLOCK *DeQueBlock_Create(UINT 
uBlockSize)</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">DEQUEBLOCK *pBlock；</P>
<P style="LINE-HEIGHT: 14pt">pBlock = (DEQUEBLOCK 
*)malloc(sizeof(DEQUEBLOCK))；</P>
<P style="LINE-HEIGHT: 14pt">if ( pBlock != NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">pBlock-&gt;ppData = malloc(uBlockSize *sizeof(void