ds5.4.1.htm

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

  <!--msimagelist--><tr>
    <!--msimagelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。</b></font><!--msimagelist--></td>
  </tr>
  <!--msimagelist--><tr>
    <!--msimagelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。</b></font><!--msimagelist--></td>
  </tr>
  <!--msimagelist--><tr>
    <!--msimagelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>树和有向图也可以用广义表来表示。</b></font><!--msimagelist--></td>
  </tr>
<!--msimagelist--></table>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp;  
由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。</b></font></p>
<font FACE="oúì?,SimHei" LANG="ZH-CN">
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>⒊广义表基本运算</b></font></p>
</font>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp;  
广义表有两个重要的基本操作，即取头操作（</font>Head<font FACE="??ì?,SimSun" LANG="ZH-CN">）和取尾操作（</font>Tail<font FACE="??ì?,SimSun" LANG="ZH-CN">）。</font></b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp;  
根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Head<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>B<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝</font> 
e Tail<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>B<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝（）</font></b></font></p> 
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Head<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>C<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝</font> 
a Tail<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>C<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝（（</font>b<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>c<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>d<font FACE="??ì?,SimSun" LANG="ZH-CN">））</font></b></font></p> 
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Head<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>D<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝</font> 
A Tail<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>D<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝（</font>B<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>C<font FACE="??ì?,SimSun" LANG="ZH-CN">）</font></b></font></p> 
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Head<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>E<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝</font> 
a Tail<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>E<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝（</font>E<font FACE="??ì?,SimSun" LANG="ZH-CN">）</font></b></font></p> 
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Head<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>F<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝（）</font> 
Tail<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>F<font FACE="??ì?,SimSun" LANG="ZH-CN">）＝（）</font></b></font></p> 
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp;  
此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">CreateLists(ls)<font FACE="??ì?,SimSun" LANG="ZH-CN">：</font></font><font face="??ì?,SimSun" lang="ZH-CN" color="#FFFFFF" size="4">根据广义表的书写形式创建一个广义表</font><font size="5" color="#FFFFFF">ls<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">IsEmpty(ls)<font FACE="??ì?,SimSun" LANG="ZH-CN">：</font></font><font color="#FFFFFF" size="4"><font FACE="??ì?,SimSun" LANG="ZH-CN">若广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">空，则返回</font>True<font FACE="??ì?,SimSun" LANG="ZH-CN">；否则返回</font></font><font size="5" color="#FFFFFF">False<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Length(ls)<font FACE="??ì?,SimSun" LANG="ZH-CN">：求广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">的长度。</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Depth(ls)<font FACE="??ì?,SimSun" LANG="ZH-CN">：求广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">的深度。</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Locate(ls<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>x)<font FACE="??ì?,SimSun" LANG="ZH-CN">：在广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">中查找数据元素</font>x<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Merge(ls1<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>ls2)<font FACE="??ì?,SimSun" LANG="ZH-CN">：以</font>ls1<font FACE="??ì?,SimSun" LANG="ZH-CN">为头、</font>ls2<font FACE="??ì?,SimSun" LANG="ZH-CN">为尾建立广义表。</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">CopyGList(ls1<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>ls2)<font FACE="??ì?,SimSun" LANG="ZH-CN">：</font></font><font color="#FFFFFF" size="4"><font FACE="??ì?,SimSun" LANG="ZH-CN">复制广义表，即按</font>ls1<font FACE="??ì?,SimSun" LANG="ZH-CN">建立广义表</font></font><font size="5" color="#FFFFFF">ls2<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Head(ls)<font FACE="??ì?,SimSun" LANG="ZH-CN">：返回广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">的头部。</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Tail(ls)<font FACE="??ì?,SimSun" LANG="ZH-CN">：返回广义表的尾部。</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>……</b></font></p>
<p ALIGN="center"><b><a href="ds5.4.HTM"><font face="??ì?,SimSun" lang="ZH-CN" size="5" color="#FFFF00">返回</font></a></b></p>

</body>

</html>