广义表

广义表(Generalized Lists)是n(n≥0)个数据元素a1,a2,…,ai,…,an 的有序序列,一般记作:

ls=(a1,a2,…,ai,…,an)

其中:ls 是广义表的名称,n 是它的长度。每个ai(1≤i≤n)是ls 的成员,它可以是单个元素,也可以是一个广义表,分别称为广义表ls 的单元素和子表。当广义表ls 非空时,称第一个元素a1 为ls 的表头(head),称其余元素组成的表(a2,…,ai,…,an)为ls 的表尾(tail)。

从上述广义表的定义和例子可以得到广义表的下列重要性质:

⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素,也可以是子表,而子表的元素还可以是子表,…。

⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归,即广义表也可以是其自身的子表。例如表E 就是一个递归的表。

⑶广义表可以为其他表所共享。例如,表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值,而用子表的名称来引用

广义表有两个重要的基本操作,即取头操作(Head)和取尾操作(Tail)。根据广义表的表头、表尾的定义可知,对于任意一个非空的列表,其表头可能是单元素也可能是列表,而表尾必为列表。

对于广义表的head和tail的理解了,head是第一个元素,tail是除了第一个元素的余下的。如果只有一个那么尾部是空!

区别长度无穷大无限列表,由于计算机资源的限制,长度无穷大的广义表不能在计算机中实现。

但是如果考虑这样一个广义表 E = (a, E) ——这是一个递归的表,它的长度是 2 。E相当于一个无限的列表 E = (a, (a, (a, …))),这个广义表是可以在计算机中实现的。

例题:已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()

解析:tail(LS)=((d,e,f))                //这一步,不是(d,e,f),切记!
        head(tail(LS))=(d,e,f)
        tail(head(tail(LS) )) = (e,f)
        head(tail( head(tail(LS) ) )) = e
态度决定行为,行为决定习惯,习惯决定性格,性格决定命运
原文地址:https://www.cnblogs.com/neversayno/p/5087808.html