📄 ds5.4.1.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><font lang="ZH-CN" size="6" color="#FFFF00"><b><font face="oúì?,SimHei">5.4.1
</font><font face="??ì?,SimSun">广义表的定义和基本运算</font></b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN"> </font></b></font><font FACE="oúì?,SimHei" LANG="ZH-CN"><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">
我们知道，线性表是由</font>n<font FACE="??ì?,SimSun" LANG="ZH-CN">个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：</font></b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>（俄罗斯，巴西，（国家，河北，四川），古巴，美国，（），日本）</b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>
在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。</b></font></p>
<p ALIGN="JUSTIFY"><b><font FACE="??ì?,SimSun" LANG="ZH-CN" color="#FFFF00" size="5">
广义表（</font><font size="5" color="#FFFFFF">Generalized Lists<font FACE="??ì?,SimSun" LANG="ZH-CN">）是</font>n<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>n<font FACE="??ì?,SimSun" LANG="ZH-CN">≥</font>0<font FACE="??ì?,SimSun" LANG="ZH-CN">）个数据元素</font>a<sub>1</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>a<sub>2</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，…，</font>a<sub>i</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，…，</font>a<sub>n</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">的有序序列，一般记作：</font></font></b></p>
<p ALIGN="CENTER"><font size="5" color="#FFFFFF"><b>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">＝（</font>a<sub>1</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>a<sub>2</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，…，</font>a<sub>i</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，…，</font>a<sub>n</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">）</font></b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">其中：</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">是广义表的名称，</font>n<font FACE="??ì?,SimSun" LANG="ZH-CN">是它的长度。每个</font>a<sub>i</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">≤</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">≤</font>n<font FACE="??ì?,SimSun" LANG="ZH-CN">）是</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">的单元素和子表。当广义表</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">非空时，称第一个元素</font>a<sub>1</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">为</font>ls<font FACE="??ì?,SimSun" LANG="ZH-CN">的表头（</font>head<font FACE="??ì?,SimSun" LANG="ZH-CN">），称其余元素组成的表（</font>a<sub>2</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，…，</font>a<sub>i</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">，…，</font>a<sub>n</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">）为</font>ls<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>显然，广义表的定义是递归的。</b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>
为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>A
<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>B
<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>C
<font FACE="??ì?,SimSun" LANG="ZH-CN">＝（</font>a<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>D
<font FACE="??ì?,SimSun" LANG="ZH-CN">＝（</font>A<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>E
<font FACE="??ì?,SimSun" LANG="ZH-CN">＝（</font>a<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>F
<font FACE="??ì?,SimSun" LANG="ZH-CN">＝（（））</font></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 FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>
从上述广义表的定义和例子可以得到广义表的下列重要性质：</b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表</font>E<font FACE="??ì?,SimSun" LANG="ZH-CN">就是一个递归的表。</font></b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">⑶广义表可以为其他表所共享。例如，表</font>A<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>D<font FACE="??ì?,SimSun" LANG="ZH-CN">中可以不必列出子表的值，而用子表的名称来引用。</font></b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>
广义表的上述特性对于它的使用价值和应用效果起到了很大的作用。</b></font></p>
<!--msimagelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -