chapter3_2.htm

介绍各种数据结构的讲义

      <p align="center" style="text-autospace: none"><img border="0" src="images/img5.gif" width="489" height="170"></p>
          <p align="center" style="text-autospace: none">(b)</p>
          <blockquote> 
            <p align="center" style="text-autospace: none">&nbsp;图2 Insert过程的指针修改示意图</p>
            <p align="left" style="text-align:left;text-autospace:none">图2(a)是执行Insert运算之前的情况。我们要在指针p所指的单元之后插入一个新元素x。图2(b)是执行Insert运算以后的结果，其中的虚线表示新的指针。</p>
            <p align="left" style="text-align:left;text-autospace:none">在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性容易判定。</p>
          </blockquote>
          <p><b>复杂性</b></p>
          <blockquote> 
            <p align="left" style="text-align:left;text-autospace:none">Insert运算所需的时间显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
    </center>
    <tr>
      <td width="100%" bgcolor="#E0E0E0"> 
        <center>
          <p align="left" style="text-align:left;text-autospace:none"><b>函数</b> 
            Delete(p)</p>
          <p align="left" style="text-align:left;text-autospace:none"><b>功能</b></p>
          <blockquote> 
            <p align="left" style="text-align:left;text-autospace:none"><font size="2">从表L中删除位置p处的元素。例如，当L为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>时，执行Delete(p)后，L变为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>p-1</sub>,a<sub>p+1</sub>,…,a<sub>n</sub> 
              。当L中没有位置p或p=End(L)时，该运算无定义。</font></p>
          </blockquote>
          <p align="left" style="text-align:left;text-autospace:none"><b>实现</b></p>
          <blockquote> 
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"><b>Procedure</b> 
              Delete(p:TPosition);</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">var</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp; 
              q:TPosition;</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">begin</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              q:=p^.next;</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              p^.next:=p^.next^.next;</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              dispose(p);</p>
            <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p align="left" style="text-align:left;text-autospace:none"><b>说明</b></p>
          <blockquote> 
            <p align="left" style="text-align:left;text-autospace:none">这个过程很简单，其指针的修改如图3所示。</p>
          </blockquote>
          
      <p align="center" style="text-autospace: none"><img border="0" src="images/img6.gif" width="435" height="126"></p>
        </center>
        <p style="text-autospace: none" align="center">&nbsp;图3&nbsp; Delete过程的指针修改示意图</p>
        <blockquote> 
          <center>
            <p align="left" style="text-align:left;text-autospace:none">若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。</p>
          </center>
        </blockquote>
        <center>
          <p align="left" style="text-align:left;text-autospace:none"><b>复杂性</b></p>
          <blockquote> 
            <p align="left" style="text-align:left;text-autospace:none">Delete过程所需的时间显然也为<i>O</i>(1)。</p>
          </blockquote>
        </center>
      </td>
    </tr>
    <tr> 
      <td width="100%" bgcolor="#E0E0E0"><b>函数</b> <font size="2">Locate(x,L)</font> 
        <p><b>功能</b></p>
        <blockquote> 
          <p><font size="2">这是一个函数，函数值为元素x在L中的位置。若x在L中重复出现多次，则函数值为x第一次出现的位置。当x不在L中时，函数值为End(L)。</font></p>
        </blockquote>
        <p><b>实现</b></p>
        <blockquote> 
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5"><b>Function</b>&nbsp; 
            Locate(x:TElement;L:TList):TPosition;</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">Var</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
            p:TPosition;</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">begin</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
            p:=L;</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
            while p^.next&lt;&gt;nil do</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
            if p^.next^.element = x then return(p)</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else 
            p:=p^.next;</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
            return(p);</p>
          <p align="left" style="text-align: left; text-autospace: none; margin-top: 5; margin-bottom: 5">end;</p>
        </blockquote>
        <p><b>说明</b></p>
        <blockquote> 
          <p>在单链表中实现LOCATE的过程与用数组实现表时的LOCATE过程是类似的。</p>
        </blockquote>
        <p><b>复杂性</b></p>
        <blockquote> 
          <p>容易看出，在最坏情况下和平均情况下，LOCATE所需的时间均为O(n)。</p>
        </blockquote>
      </td>
    </tr>
  </table>
</div>
<p align="left" style="text-align:left;text-autospace:none">&nbsp;&nbsp;&nbsp; 
  对于其他基本的表运算实现起来都比较简单，这里从略。至于时间复杂性，在最坏情况下，PrintList显然需要<i>O</i>(n)，而Previous由于单链表没有设置指向前驱的指针，得从头到尾扫描，因此也需要<i>O</i>(n)。</p>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>