chapter3_1.htm

介绍各种数据结构的讲义

          <p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Enqueue(x,Q)</p>
          <p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            
        <p style="margin-top: 5; margin-bottom: 5">将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。也可用<a href="../list/chapter2.htm">一般的表运算</a>将Enqueue(x,Q)表示为Insert(x,End(Q),Q)。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">Procedure Enqueue(x:ElementType;var 
              Q:QueueType);</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;if Full(Q) then Error('The 
              queue is full!')</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              else</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              Q.rear:=Q.rear mod MaxLength+1;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              Q.Elements[Q.rear]:=x;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              end;</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">Full是一个函数，若队列Q已满，则函数值为true，否则为false。</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">Function Full(var Q:QueueType):Boolean;</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;Return((Q.front+MaxLength-Q.rear=2)or(Q.front-Q.rear=2));</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">注意在计算队尾的位置时，如果用Q.rear:=(Q.rear+1) 
              mod MaxLength，当Q.rear=MaxLength-1时就会出错，因此应该用Q.rear:=Q.rear mod MaxLength+1。</p>
            <p style="margin-top: 5; margin-bottom: 5">如图7(a)所示，队列满有两种情况，一种是Q.front&gt;Q.rear且Q.front-Q.rear=2，一种是Q.front&lt;Q.rear且Q.front+MaxLength-Q.rear=2，根据这点可以实现Full函数。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Dequeue(Q)</p>
          <p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            
        <p style="margin-top: 5; margin-bottom: 5">将Q的队头元素删除，简称为出队。用<a href="../list/chapter2.htm">一般的表运算</a>可将Dequeue(Q)表示为Delete(First(Q),Q)。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">Procedure Dequeue(var Q:QueueType);</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;if Empty(Q) then 
              Error('The queue is empty!')</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              else Q.front:=Q.front mod MaxLength +1;</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">显然。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Empty(Q)</p>
          <p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">这是一个函数，若Q是一个空队列，则函数值为true，否则为false。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">Function Empty(var Q:QueueType):Boolean;</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;return((Q.front-Q.rear=1)or(Q.front+MaxLength-Q.rear=1));</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">根据图6(a)知，队列空有两种情况，一种是Q.front&gt;Q.rear且Q.front-Q.rear=1，一种是Q.front&lt;Q.rear且Q.front+MaxLength-Q.rear=1。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="margin-top: 5; margin-bottom: 5"><b>函数</b> MakeNull(Q)</p>
          <p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">使队列Q成为空队列。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">Procedure MakeNull(Q);</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;Q.front:=2;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;Q.rear:=1;</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">用这种循环数组实现队列，不需要回收内存空间，因此MakeNull实现起来很简单，只要利用队列空的条件，使Q.front-Q.rear=1即可。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
    </table>
  </center>
</div>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>