chapter6_2.htm

介绍各种数据结构的讲义

            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;Find:=false;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;while 
              (i&lt;&gt;nil)and(not Find) do</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp; 
              begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              k:=Locate(v,i^.Children); {在结点i的儿子表中定位结点v}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              if k&lt;&gt;nil then Find:=true;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              {如果在i的儿子表中找到结点v则Find=true;}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              i:=i^.next;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp; 
              end;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;if 
              (Find)and(k^.next&lt;&gt;nil)</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              {如果找到v在某个结点的儿子表中的位置</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              并且v不是该结点的儿子表的最后一个元素}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
              then return(k^.next^.child) {则返回v的右邻兄弟的指针}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
              else return(nil);{否则返回空指针}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">由于儿子链表只保存各个结点的儿子的信息，没有保存兄弟和父亲的信息，因此在查找v的兄弟时，必须先找到v的父亲结点，然后再找到v在父亲结点的儿子表中的位置，才能得到v的右邻兄弟。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p>假设树有n个结点，在最坏情况下，结点v恰好是树的根结点，则循环要找遍T的所有结点，因此复杂性为<i>O</i>(n)；在最好情况下，第一次循环就可以找到v的兄弟，因此最好情况下复杂性为<i>O</i>(1)；平均情况下复杂性可以证明（证略）为<i>O</i>(n/2)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数 </b>Parent(v,T)</p>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是根结点时，函数值为nil，表示结点v没有父结点。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function 
              Parent(v:TPosition;var T:TreeType):TPosition；</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">var</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">i:TPosition;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">k:^ChildrenNodeType;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Find:Boolean;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;i:=T; 
              {i指向T的第一个结点}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;Find:=false;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;while 
              (i&lt;&gt;nil)and(not Find) do</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp; 
              begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              k:=Locate(v,i^.Children); {在结点i的儿子表中定位结点v}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              if k&lt;&gt;nil then Find:=true else i:=i^.next;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              {如果在i的儿子表中找到结点v则Find=true否则i:=i^.next}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp; 
              end;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;if 
              Find&nbsp; then return(i) {则返回v的父亲的指针}</p>
            <p style="word-spacing: 5; 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; 
              else return(nil);{否则返回空指针}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">由于儿子链表只保存各个结点的儿子的信息，没有保存父亲的信息，因此在查找v的父亲时，必须依次扫描结点表，找到儿子表中含有结点v的结点。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">同Right_Sibling一样，最好情况为<i>O</i>(1)，最坏情况为<i>O</i>(n)，平均情况为<i>O</i>(n/2)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数 </b>Create(i,v,T<sub>1</sub>,T<sub>2</sub>,..,T<sub>i</sub>)</p>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T<sub>1</sub>,T<sub>2</sub>,..,T<sub>i</sub>的根。当i=0时，v既是树根，又是树叶。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Procedure 
              Create(i:integer;var x:LabelType;var T<sub>1</sub>,T<sub>2</sub>,..,T<sub>i</sub>,T:TreeType);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">var</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">k:integer;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">p:TPosition;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">tmp:^ChildrenNodeType;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;new(T);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">T^.Label:=x;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">T^.children:=nil;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">T^.next:=nil;&nbsp;&nbsp;&nbsp;&nbsp; 
              {建立新树的根结点}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">p:=T;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              {p指向链表T的最后一个结点}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">for k:=i 
              downto 1 do&nbsp; {用downto是为了保持子树T<sub>k</sub>从左到右的顺序}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;if 
              T<sub>k</sub>&lt;&gt;nil then&nbsp;&nbsp; {如果子树T<sub>k</sub>不为空}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
              begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              &nbsp;p^.next:=T<sub>k</sub>;{将链表T<sub>k</sub>接在链表T之后}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              while p^.next&lt;&gt;nil do p:=p^.next; {p指向链表T的最后一个结点}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              new(tmp);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              tmp^.child:=T<sub>k</sub>;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              tmp^.next:=T^.children;&nbsp; {建立一个新的儿子表项}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              T^.children:=tmp;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              {将T<sub>k</sub>的根结点在T中的位置插入T的根结点的儿子表的首部}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
              end;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这个过程首先生成新树的根结点，其标号为x；然后对于每一个T<sub>k</sub>，1≤k≤i，如果T<sub>k</sub>不为空则将T<sub>k</sub>的根结点链接到T的后面，为了实现这一步，可以设置一个指针p，p始终指向T的最后一个结点。然后将每个T<sub>k</sub>加入到T的根结点的儿子表中。for循环用的是downto，是因为后面将T<sub>k</sub>的根结点插入到T的根的儿子表的第一个位置上，因此只有从右向左插入T<sub>k</sub>才可以保持子树从左到右的顺序。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">如果∑(T<sub>k</sub>的结点数)=n，即生成的新树的结点总数为n，则复杂性显然为<i>O</i>(n)。</p>
          </blockquote>
          <p>　
        </td>
      </tr>
    </table>
  </center>
</div>
<p>Label,Root和MakeNull比较简单，这里就不一一实现了。</p>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>