ds9.3.3.htm

这是清华大学所用的数据结构的电子版教材

<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" size="5"><b>&nbsp;<o:p>
</o:p>  
</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" size="5"><b>Result<span style="mso-spacerun: yes">&nbsp; 
</span>SearchBTree(BTree T,KeyType k)</b></font></span></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><b><span lang="EN-US">{<span style="mso-tab-count:1"> 
</span></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">//在</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">m</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">阶</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">B</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">t</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">上查找关键码</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">k</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，反回</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">(pt,i,tag)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">。若查找成</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">&nbsp;//功，则特征值</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">tag=1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span></b></font><font color="#FFFFFF" size="5"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">指针</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">pt</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所指结点中第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">个关键码等于</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">&nbsp;//</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">key</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">；否则，特征值</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">tag=0,</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">等于</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">k</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的关键码记录</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0" align="left"><font color="#FFFFFF" size="5"><b><span style="mso-bidi-font-size: 10.0pt" lang="EN-US">&nbsp;//</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">应插入在指针</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">pt</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所指结点中第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">个和第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">i+1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">个关键码之间</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-tab-count:1"><font size="5"><b><font color="#FFFFFF">&nbsp;</font></b></font></span><font size="5"><b><font color="#FFFFFF">p=T;q=NULL;found=FALSE;i=0;<span style="mso-tab-count:1">&nbsp;&nbsp; 
</span></font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" size="5"><b><span style="mso-tab-count: 1">&nbsp;&nbsp; 
</span></b></font></span><font size="5"><b><font color="#FFFFFF"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">初始化，</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">p</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">指向待查结点，</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">q</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">指向</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">p</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的双亲</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-tab-count:1"><font size="5"><b><font color="#FFFFFF">&nbsp;</font></b></font></span><font size="5"><b><font color="#FFFFFF">while(p&amp;&amp;!found)</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-tab-count:1"><font size="5"><b><font color="#FFFFFF">&nbsp;   
</font></b></font></span><font size="5"><b><font color="#FFFFFF">{<span style="mso-tab-count:1"> 
</span>n=p-&gt;keynum;i=Search(p,k); <span style="mso-tab-count:1">&nbsp;&nbsp; </span></font></b></font></span></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" size="5"><b><span style="mso-tab-count: 1">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</span></b></font><font size="5"><b><font color="#FFFFFF"><span style="mso-tab-count:1"> 
</span></font></b></font></span><font size="5"><b><font color="#FFFFFF"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">p--&gt;key[1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">…</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">keynum]</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">中查找</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-tab-count:2"><font size="5"><b><font color="#FFFFFF">&nbsp;&nbsp;&nbsp;   
</font></b></font></span><font size="5"><b><font color="#FFFFFF">if(i&gt;0&amp;&amp;p-&gt;key[i]=   
=k) found=TRUE;<span style="mso-spacerun: yes">&nbsp; </span></font></b></font></span><font size="5"><b><font color="#FFFFFF"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">找到</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-tab-count:2"><font size="5"><b><font color="#FFFFFF">&nbsp;&nbsp;&nbsp;   
</font></b></font></span><font size="5"><b><font color="#FFFFFF">else<span style="mso-tab-count:1">&nbsp; 
</span>{q=p;p=p-&gt;ptr[i];}</font></b></font></span></p>