广义表基础

1.基本定义
（1）基础
①A=() //空表
②B=(e) //只含有一个原子的广义表
③C=(a,(b,c,d)) //含有一个 原子a 和一个 子表(a,b,c) 的广义表
④D=(A,B,C)=((),(e),(a,(b,c,d)))
第一个子表为空表，共含有三个子表()、(e)、(a,(b,c,d))
⑤E=(a,E)
广义表 E 中有两个元素，原子 a 和它本身。
这是一个递归广义表，等同于：E = (a,(a,(a,…)))
注：递归表的深度是无穷值，长度是有限值

（2）广义表的长度和深度
①长度： 最外层包含 元素（=原子+子表） 个数
(a₁,a₂,…,a_n) 的长度为 n
(a,(b,c,d)) 长度为 2，为a和(b,c,d)
((a,b,c)) 长度为 1
空表 () 长度为 0
递归广义表E=(a,E) 长度为2

②深度： 广义表中括号的最大嵌套层数。原子的深度为0，空表的深度为1
(a,(b,c,d)) 深度为2
空表() 深度为1
递归广义表E=(a,E) 深度为无穷

( a, ( a,b ), d, e, ( (i,j) ,k ) ) 深度为3
解：可拆解为
a：0
(a,b)：1
d：0
e：0
( (i,j) , k)：2
加最外层括号的1，最大为3

（3）广义表的表头和表尾
①表头Head： 当广义表不为空表时，第一个元素（可能为子表和原子）称为表头
注：（非空）广义表的表头是原子或广义表
②表尾Tail： 当广义表非空时，除去表头，剩余元素组成的新广义表称为表尾
注：（非空）广义表的表尾总是一个广义表
*非空加括号表示选项中不写非空也是对的，因为空表没有表头和表尾，提到表头或表尾一定是非空广义表

如：
(1,(1,2,3),5) 表头为原子1，表尾为((1,2,3),5)
(1) 表头为原子1，表尾为空表()
( a, (b) ) 的表头为原子a，表尾为((b))
(a,b,c)的表头为原子a，表尾为(b,c)

2.Head与Tail
（1）已知广义表L=(a,(b,(c,(d)), e), f )
L1=Tail(L)=((b,(c,(d)), e), f )
L2=Head(L1)= (b,(c,(d)), e)
L3=Tail(L2)=((c,(d)), e)
L4=Head(L3)=(c,(d))
L5=Head(L4)= c

（2）已知广义表A=(((a)),(b),c,(a),(((d,e))))，写出表的长度与深度，并用求头部、尾部的方式求出e
解：长度5，深度4
Tail(A)=((b),c,(a),(((d,e))))
Tail(Tail(A))=(c,(a),(((d,e))))
Tail(Tail(Tail(A)))=((a),(((d,e))))
Tail(Tail(Tail(Tail(A))))=((((d,e))))
Head(Tail(Tail(Tail(Tail(A)))))=(((d,e)))
Head(Head(Tail(Tail(Tail(Tail(A))))))=((d,e))
Head(Head(Head(Tail(Tail(Tail(Tail(A)))))))=(d,e)
Tail(Head(Head(Head(Tail(Tail(Tail(Tail(A))))))))=(e)
Head(Tail(Head(Head(Head(Tail(Tail(Tail(Tail(A)))))))))=e
或写为：HTHHHTTTT(A)=e

（3）广义表A=(a,b,(c,d),(e,(f,g))),则表达式Head(Tail(head(Tail(Tail(A)))的值为：d

3.广义表的一种存储结构（链式存储）

①tag域为标志字段
②sublist/data由tag决定，为0时表示该节点是原子节点，则第二个域为data，存放原子元素的信息；为1时，表示该节点是表节点，存放sublist，即存放子表第一个元素对应节点的地址。
③link域存放与本元素同一层的下一个元素所在节点的地址，当本元素是所在层的最后一个元素时，link域为NULL。

例：已知广义表A=(((a)),(b),c,(a),(((d,e))))，画出其一种存储结构图