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

📄 2_1 栈 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.htm

📁 主要介绍了多任务下面的一些数据结构和算法,比如树和图的一些遍历
💻 HTM
📖 第 1 页 / 共 3 页
字号:
🔍
123 
          {    
            szType=  document.getElementById("listSearchType").options(document.getElementById("listSearchType").selectedIndex).value;  
          }
          else
          {
              szType= document.getElementById("listSearchType").value;
          }
          if(szType==1)
            loc="http://book.csdn.net/book/morelz.aspx?key="+escape(document.getElementById("txtTopKey").value);
          else
             loc="http://club.book.csdn.net/book/s.aspx?key="+escape(document.getElementById("txtTopKey").value);
          
          self.location=loc;
        
      } 
    }
  </SCRIPT>

<DIV id=booknavbottom2>
<DIV class=hotleft><A href="http://book.csdn.net/subject/allbook.htm" 
target=_blank>全部图书</A> <FONT color=red>推荐</FONT>:<A 
href="http://club.book.csdn.net/book/s.aspx?key=asp.net">ASP.NET</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=ajax">Ajax</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=spring">Spring</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=Hibernate">Hibernate</A> <A 
href="http://club.book.csdn.net/book/s.aspx?key=Java">Java</A></DIV>
<DIV class=hotright><SELECT id=listSearchType name=aa> <OPTION value=2 
  selected>书友会</OPTION> <OPTION value=1>连载</OPTION></SELECT><INPUT 
onkeypress=if(event.keyCode==13){SearchBook_Top();} id=txtTopKey maxLength=25><INPUT onclick=SearchBook_Top(); type=button value=搜索 name=提交></DIV></DIV></DIV>
<DIV class=area>
<SCRIPT 
src="2_1 栈 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/BookDetailAd.js" 
type=text/javascript></SCRIPT>

<DIV class=col1>
<DIV class=lineBlue></DIV><!-- title -->
<DIV class=arcTitle>
<H1><A href="http://book.csdn.net/bookfiles/65">多任务下的数据结构与算法 </A></H1>
<DIV style="FONT-SIZE: 15px; TEXT-ALIGN: center"><A 
href="http://book.csdn.net/bookfiles/65/100651877.shtml">2.1 栈 </A></DIV>
<DIV style="FONT-SIZE: 15px; TEXT-ALIGN: center"><A class=url 
href="http://book.csdn.net/">http://book.csdn.net/</A> 2006-7-14 18:04:00 </DIV>
<DIV class=clear></DIV>
<DIV 
style="BORDER-RIGHT: #0b5f98 1px solid; BORDER-TOP: #0b5f98 1px solid; MARGIN: 0px auto; BORDER-LEFT: #0b5f98 1px solid; WIDTH: 700px; BORDER-BOTTOM: #0b5f98 1px solid">
<DIV 
style="PADDING-RIGHT: 1px; PADDING-LEFT: 1px; FLOAT: left; PADDING-BOTTOM: 1px; WIDTH: 16px; COLOR: white; PADDING-TOP: 1px; BACKGROUND-COLOR: #0b5f98">图书导读 
</DIV>
<DIV 
style="PADDING-LEFT: 2px; FLOAT: right; WIDTH: 670px; LINE-HEIGHT: 16pt; TEXT-ALIGN: left"><!--导读-->
<H1 id=divCurrentNode 
style="PADDING-LEFT: 2px; FONT-SIZE: 12px; WIDTH: 100%; COLOR: #b83507; TEXT-ALIGN: left">当前章节:<A 
href="http://book.csdn.net/bookfiles/65/100651877.shtml"><FONT color=red>2.1 栈 
</FONT></A></H1>
<DIV id=divRelateNode style="PADDING-LEFT: 2px">
<DIV style="FLOAT: left; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651874.shtml">1.3 任意数据类型处理</A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651875.shtml">1.4 多任务介绍 </A></DIV>
<DIV style="FLOAT: left; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651876.shtml">1.5 软件设计简介</A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651878.shtml">2.2 队列 </A></DIV>
<DIV style="FLOAT: left; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651879.shtml">2.3 排序表 </A></DIV>
<DIV style="FLOAT: right; WIDTH: 49%">·<A 
href="http://book.csdn.net/bookfiles/65/100651880.shtml">2.4 实例：HOOK管理功能的实现 
</A></DIV></DIV></DIV></DIV>
<DIV class=clear></DIV></DIV><!-- main -->
<DIV id=main>
<DIV id=text>
<DIV id=csdn_zhaig_ad_yahoo_2></DIV>
<H2><A name=_Toc122884709></A><A name=_Toc116222470><FONT size=5>2.1 
</FONT></A>栈</H2>
<H3><A name=_Toc122884710></A>2.1.1 栈的基本概念</H3>
<P>栈是一种最常用的操作，采用后进先出的方式，当栈为空时执行弹出操作会操作失败；当栈满时压入数据会失败。</P>
<P>本节使用数组来实现一个栈的操作，通常栈的操作主要有以下几个方面。</P>
<P>① 创建栈；</P>
<P>② 将数据压入栈中；</P>
<P>③ 从栈中弹出数据；</P>
<P>④ 释放栈。</P>
<P>栈的操作如图2-1所示。</P>
<P>图2-1中显示的是栈未满时的操作情况，当数据全部弹出时，栈为空；当栈满时，无法再压入数据，可以通过将数组大小增加一倍的方式来增加栈中的最大元素个数，以便于插入新的数据，如图2-2所示。</P>
<P></P>
<P align=center><IMG 
src="2_1 栈 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/image2.1.jpg"> </P>
<P align=center>图2-1 栈的操作</P>
<P align=center><IMG 
src="2_1 栈 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.files/image2.2.jpg"> <BR>图2-2 
通过扩大数组来调整栈的大小</P>
<P>要实现数据类型的任意性，可用void指针来实现，所以栈中用一个void 
指针数组来记录栈中的数据。由于用指针来表示数组时，可以动态决定数组的大小，有很好的灵活性，因此应该用一个void双指针来记录栈中的数据。另外，要知道栈顶位置，还要知道栈的最大尺寸，栈的最大尺寸也就是数组的大小，因此，可以用以下结构体来描述栈。</P>
<P style="LINE-HEIGHT: 14pt">typedef struct STACK_st {</P>
<P style="LINE-HEIGHT: 14pt">void **ppBase；</P>
<P style="LINE-HEIGHT: 14pt">/* 用来记录任意类型数据的数组 */</P>
<P style="LINE-HEIGHT: 14pt">UINT uTop；</P>
<P style="LINE-HEIGHT: 14pt">/* 栈顶位置 */</P>
<P style="LINE-HEIGHT: 14pt">unsigned uStackSize；</P>
<P style="LINE-HEIGHT: 14pt">/* 栈的最大尺寸，也就是数组的大小 */</P>
<P style="LINE-HEIGHT: 14pt">} STACK；</P>
<H3><A name=_Toc122884711></A>2.1.2 栈的编码实现</H3>
<P>在进行栈的操作时，是从一头进并从同一头出的，从数组的尾部进出数据，不会移动前面的数据，所以压入操作和弹出操作都在数组的尾部也就是在数组的uTop位置进行，这样实现起来可以充分利用数组操作的高效性，避免移动数据。</P>
<P>栈操作的主要代码如下。</P>
<P style="LINE-HEIGHT: 14pt">/** 创建一个栈</P>
<P style="LINE-HEIGHT: 14pt">@param UINT uStackSize——栈的大小 </P>
<P style="LINE-HEIGHT: 14pt">@return STACK *——成功返回栈指针；失败返回NULL</P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>STACK *Stack_Create(UINT uStackSize)</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">STACK *pStack；</P>
<P style="LINE-HEIGHT: 14pt">if ( uStackSize == 0 )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">return NULL；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">pStack = (STACK *)malloc( sizeof(struct STACK_st) 
)；</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack != NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">pStack-&gt;ppBase = (void **)malloc( uStackSize 
*sizeof(void *) )；</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack-&gt;ppBase == NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">free( pStack )；</P>
<P style="LINE-HEIGHT: 14pt">pStack = NULL；</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">pStack-&gt;ppBase[0] = NULL；</P>
<P style="LINE-HEIGHT: 14pt">pStack-&gt;uTop = 0；</P>
<P style="LINE-HEIGHT: 14pt">pStack-&gt;uStackSize = uStackSize；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">return pStack；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/** 栈的释放函数，它会将栈中剩余的未弹出数据释放</P>
<P style="LINE-HEIGHT: 14pt">@param STACK *pStack——栈指针 </P>
<P style="LINE-HEIGHT: 14pt">@param DESTROYFUNC DestroyFunc——数据释放回调函数</P>
<P style="LINE-HEIGHT: 14pt">@return void——无 </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>void Stack_Destroy(STACK 
*pStack</B><B>，</B><B>DESTROYFUNC DestroyFunc)</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack != NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack-&gt;ppBase != NULL &amp;&amp; 
DestroyFunc != NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">UINT i；</P>
<P style="LINE-HEIGHT: 14pt">for ( i = 0； i &lt; pStack-&gt;uTop； i++ )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack-&gt;ppBase[i] != NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">(*DestroyFunc)(pStack-&gt;ppBase[i])；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">free( pStack-&gt;ppBase )；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">free( pStack )；</P>
<P style="LINE-HEIGHT: 14pt">pStack = NULL；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/** 栈的弹出函数，弹出栈顶数据，弹出的数据需要调用者自行释放</P>
<P style="LINE-HEIGHT: 14pt">@param STACK *pStack——栈指针 </P>
<P style="LINE-HEIGHT: 14pt">@return void *——成功返回栈顶数据；栈为空则返回NULL </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>void *Stack_Pop( STACK *pStack )</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">void *pData；</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack == NULL || pStack-&gt;uTop == 0 )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">return NULL；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">pStack-&gt;uTop－= 1；</P>
<P style="LINE-HEIGHT: 14pt">pData = pStack-&gt;ppBase[pStack-&gt;uTop]；</P>
<P style="LINE-HEIGHT: 14pt">return pData；</P>
<P style="LINE-HEIGHT: 14pt">}</P>
<P style="LINE-HEIGHT: 14pt">/** 压栈函数，将数据压入栈顶，数据可以为空</P>
<P style="LINE-HEIGHT: 14pt">@param STACK *pStack——栈指针 </P>
<P style="LINE-HEIGHT: 14pt">@param void *pData——要压入的数据，可以为空 </P>
<P style="LINE-HEIGHT: 14pt">@return INT——成功返回CAPI_SUCCESS；失败返回CAPI_FAILED </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>INT Stack_Push( STACK *pStack</B><B>，</B><B>void 
*pData )</B></P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14pt">if ( pStack == NULL )</P>
<P style="LINE-HEIGHT: 14pt">{</P>
<P style="LINE-HEIGHT: 14.4pt">return CAPI_FAILED；</P>
<P style="LINE-HEIGHT: 14.4pt">}</P>
<P style="LINE-HEIGHT: 14.4pt">/* 判断栈是否为满，如果满了则将栈空间增大一倍 */</P>
<P style="LINE-HEIGHT: 14.4pt">if ( pStack-&gt;uTop &gt;= 
pStack-&gt;uStackSize－1 )</P>
<P style="LINE-HEIGHT: 14.4pt">{</P>
<P style="LINE-HEIGHT: 14.4pt">pStack-&gt;ppBase = (void **)realloc( 
pStack-&gt;ppBase，</P>
<P style="LINE-HEIGHT: 14.4pt">( pStack-&gt;uStackSize *2 ) *sizeof( void *) 
)；</P>
<P style="LINE-HEIGHT: 14.4pt">if ( pStack-&gt;ppBase == NULL )</P>
<P style="LINE-HEIGHT: 14.4pt">{</P>
<P style="LINE-HEIGHT: 14.4pt">return CAPI_FAILED；</P>
<P style="LINE-HEIGHT: 14.4pt">}</P>
<P style="LINE-HEIGHT: 14.4pt">pStack-&gt;uStackSize *= 2；</P>
<P style="LINE-HEIGHT: 14.4pt">}</P>
<P style="LINE-HEIGHT: 14.4pt">pStack-&gt;ppBase[pStack-&gt;uTop] = pData；</P>
<P style="LINE-HEIGHT: 14.4pt">pStack-&gt;uTop += 1；</P>
<P style="LINE-HEIGHT: 14.4pt">return CAPI_SUCCESS；</P>
<P style="LINE-HEIGHT: 14.4pt">}</P>
<P style="LINE-HEIGHT: 14.4pt">/** 判断栈是否为空</P>
<P style="LINE-HEIGHT: 14.4pt">@param STACK *pStack——栈指针 </P>
<P style="LINE-HEIGHT: 14.4pt">@return INT——0表示为空；非零表示非空 </P>
<P style="LINE-HEIGHT: 14.4pt">*/</P>
<P style="LINE-HEIGHT: 14.4pt"><B>INT Stack_IsEmpty( STACK *pStack )</B></P>
<P style="LINE-HEIGHT: 14.4pt">{</P>
<P style="LINE-HEIGHT: 14.4pt">return pStack-&gt; uTop；</P>
<P style="LINE-HEIGHT: 14.4pt">}</P>
<P>本节用数组实现了栈的操作，当栈中元素超过数组的大小时，通过将数组扩大一倍的方式来消除数组大小固定的限制，当然也可以用后面讲到的链表方式来实现栈的操作。用数组实现栈的操作比较简单，效率也很高，缺点是当栈中元素较多并超过数组大小时，将数组扩大一倍需要消耗比较长的时间，分时性能不如链表。</P>
<H3><A name=_Toc122884712></A>2.1.3 多任务栈的实现</H3>
<P>前面讲的栈的实现是单任务情况下的实现，即只有一个任务对栈进行操作，如果有多个任务要同时进行栈操作，必须要给栈加上锁保护才能避免重入问题。</P>
<P>很多人在编多任务程序时，喜欢在调用的地方先上锁，调用完后再解锁。采用这种方法编的程序很难维护，正确的方法是在这个函数里直接进行上锁及解锁操作，或者另外写一个单独函数，在这个函数里进行上锁，调用对应函数后再解锁，其他模块只要调用这个具有上锁和解锁操作的函数就可以了。</P>
<P>如对本节的栈操作函数，欲将其变成支持多任务，可以做如下设计。</P>
<P style="LINE-HEIGHT: 14pt">typedef struct MSTACK_st {</P>
<P style="LINE-HEIGHT: 14pt">STACK *pStack；</P>
<P style="LINE-HEIGHT: 14pt">LOCK pLock；</P>
<P style="LINE-HEIGHT: 14pt">} MSTACK；</P>
<P>对栈的操作只需对要进行读写的数据进行上锁保护就可以实现多任务下的操作，为了方便，可以复用栈的代码，栈的各种操作实现编码如下。</P>
<P style="LINE-HEIGHT: 14pt">/** 多任务栈的创建函数</P>
<P style="LINE-HEIGHT: 14pt">@param UINT uStackSize——栈的大小 </P>
<P style="LINE-HEIGHT: 14pt">@return MSTACK *——成功返回栈指针；失败返回NULL </P>
<P style="LINE-HEIGHT: 14pt">*/</P>
<P style="LINE-HEIGHT: 14pt"><B>MSTACK *MStack_Create(UINT uStackSize)</B></P>
123

⌨️ 快捷键说明

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