相关概念(续) 层:我们将元素的深度值称做该元素的层号,层号相同者称为同层 结点 系列广义表:由于广义表的元素往往也是广义表,所以需要一同考 虑。我们称可追塑到同属于某一广义表的所有广义表为一个广义表 系列(或系列广义表) 递归表:若表Ls中某成员含有自己(即Ls,则称Ls为递归表。 下面的叙述中,我们用大写字母表示具体的广义表,用小写字母代 表数据对象的成员(单元素)。在同一个广义表系列中,相同字母 表示同一对象
6 相关概念(续) •层：我们将元素的深度值称做该元素的层号，层号相同者称为同层 结点。 •系列广义表：由于广义表的元素往往也是广义表，所以需要一同考 虑。我们称可追塑到同属于某一广义表的所有广义表为一个广义表 系列（或系列广义表）。 •递归表:若表Ls中某成员含有自己(即Ls)，则称Ls为递归表。 •下面的叙述中，我们用大写字母表示具体的广义表，用小写字母代 表数据对象的成员（单元素）。在同一个广义表系列中，相同字母 表示同一对象
广义表例子 ①A=():空表,无头,尾为空表,长度为0,深度为1 ②B=(a,b,c):单元素表,头为a,尾为(bc),长度为3,深度为1 ③C=(a,(b,c,d)):非单元素表,头为a,尾为(b,c,d),长度为2, 深度为2 ④D=(B,(a,b),c)):非单元素表,头为B,尾为((a.b),c),长度为 2,深度为3 ⑤E=(a,E):非单元素,头为a,尾为(E),长度为2,深度为∞ 事实上,E=(a,E)=(a,(a(,…))是个递归表。 有时,为了强调广义表名称,可将表名写在表的左括号前面,如上 例中的D可写为: D(B(a, b, c), F(G(a, b),c))
7 广义表例子 ① A=( )：空表，无头，尾为空表，长度为0，深度为1. ② B=(a,b,c)：单元素表，头为a，尾为(b,c)，长度为3，深度为1. ③ C=(a, (b, c, d) )：非单元素表，头为a，尾为 ((b,c,d))，长度为2， 深度为2. ④ D=(B, ((a,b), c ) )：非单元素表，头为B，尾为( ((a,b),c)) )，长度为 2，深度为3. ⑤ E=(a, E)：非单元素，头为a，尾为(E)，长度为2，深度为∞ •事实上，E=(a,E) = (a, (a (,… ) ) )是个递归表。 •有时，为了强调广义表名称，可将表名写在表的左括号前面，如上 例中的D 可写为： D( B(a, b, c), F( G(a, b), c) )
§712基本特性 宏观线性性:对任意广义表,若不考虑它的元素的内部结构,则它 是一个线性表,即它的直接元素之间是线性关系 元素递归性:广义表的任一元素,又可以是一个广义表(其它广义 表或自身)。这种递归性使得广义表具有强有力的表达能力,这是 广义表最重要的特性 元素共享性:在同一广义表系列中,任一元素(单元素或表)均可 以出现多次,同一元素的多次出现都代表的是同一个目标,可以认 为它们是共享同一目标,具有该特性的表也称再入表
8 §7.1.2 基本特性 •宏观线性性：对任意广义表，若不考虑它的元素的内部结构，则它 是一个线性表，即它的直接元素之间是线性关系。 •元素递归性：广义表的任一元素，又可以是一个广义表（其它广义 表或自身）。这种递归性使得广义表具有强有力的表达能力，这是 广义表最重要的特性。 •元素共享性：在同一广义表系列中，任一元素（单元素或表）均可 以出现多次，同一元素的多次出现都代表的是同一个目标，可以认 为它们是共享同一目标，具有该特性的表也称再入表
§713基本操作 线性表的基本运算 求深度 求表头 求表尾 求成员 串行化
9 §7.1.3 基本操作 • 线性表的基本运算 • 求深度 • 求表头 • 求表尾 • 求成员 • 串行化
§72广义表的存贮结构 §721基本存储方法 ·具有较高的复杂性,因此一般只采用链式存贮 结构 ·分枝单链表法—一种通用的存贮结构
10 §7.2 广义表的存贮结构 • 具有较高的复杂性，因此一般只采用链式存贮 结构 • 分枝单链表法── 一种通用的存贮结构 §7.2.1 基本存储方法