(5.4.1)-5.4广义表数据结构与算法

广义表1

5.3广义表广义表的定义广义表的存储结构

广义表(Lists，又称列表)广义表是线性表的推广。在第2章中，我们把线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。每个元素可以是一个数或一个结构，但必须保证是元素同型的。若放松对表元素的这种限制，容许它们具有不同的结构，就产生了广义表的概念。广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为广义表的长度。若ai是广义表，则称它为LS的子表。广义表是一种非线性的数据结构，是线性表的一种推广。

在线性表中，表中元素具有原子性，不可分解；如果允许表中的元素嵌套，这就是广义表。广义表被广泛的应用于表处理语言LISP（人工智能语言）中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP语言的程序也表示为一系列的广义表。

广义表是一个多层次的结构，同层的元素间存在线性关系。广义表是一种多层次的结构，此处多层次指的是由于广义表允许“表中有表”，导致不同层次的原子地位是不一样的，形成了一种层次性的结构；而同一层次的元素之间存在线性关系。有A、B、C、D、E五个广义表如下：A=()

//列表A是一个空表,它的长度为零B=(e)//列表B只有一个原子e,B的长度为1.C=(a,(b,c,d))//

列表C的长度为2,两个元素分别为原子a和子表(b,c,d)D=(A,B,C)//列表D的长度为3,三个元素都是列表,显然,

将子表的值代入后,则有D=((),(e),(a,(b,c,d)))E=(a,E)//

这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))[注：]一般用大写字母表示广义表，小写字母表示原子项45广义表的表头与表尾表头，当广义表LS非空时，称第一个元素为LS的表头表头，用符号head[LS]表示表尾，称广义表LS中除去表头后其余元素组成的广义表为LS的表尾，用符号tail[LS]表示采用表头、表尾表示法可以作为广义表的存储结构广义表D的图形化表示6DAeCBabdc广义表本质上是一种非线性的数据结构，它的表元素可以是原子或者广义表。广义表的结构特点:1)广义表中的数据元素有相对次序;2)广义表的长度定义为最外层包含的元素个数;3)广义表的深度定义为所含括弧的重数;

注意:“原子”的深度为“0”;“空表”的深度为14)表头可以是原子或列表;表尾必定是列表。5)广义表可以是一个递归的表;

递归表的深度是无穷值，长度是有限值。76)

任何一个非空广义表

LS=(1,2,…,n)均可分解为两部分

表头

Head[LS]=Head[(1,2,…,n)]=1

表尾Tail[LS]=Tail[(1,2,…,n)]=(2,…,n)

若用圆括号代替方括号需事先声明它是Head或Tail的定界符[例:]Head[(((b,c)))]=((b,c))Tail[(((b,c)))]=()Head[(a,(b,c))]=aTail[(a,(b,c))]=((b,c))Head[((c))]=(c)Tail[((c))]=()[例:]1.广义表((a),((b),c),(((d))))的长度是:3；深度是:42.广义表((a),((b),c),d,e,((I,j),k))的长度是:5；深度是:3

广义表的存储结构广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示，通常用链式结构，每个元素用一个结点表示。1.原子结点：表示原子，为了与表结点，增设标志域valuetag=0标志域

数值域列表的“元素”可以是原子，还可以是列表，所以结点可能有两种形式标志域，数值域tphptag=1

标志域表头指针表尾指针2.表结点：表示列表，若表不空，则可分解为表头和表尾，用3个域表示：标志域，表头指针，表尾指针。指向表头指向表尾11头尾链表存储结构typedefenum{ATOM,LIST}ElemTag;/*ATOM=0，表示原子；LIST=1，表示子表*/typedefstructGLNode{ElemTagtag;/*标志位tag用来区别原子结点和表结点*/union{AtomTypeatom;/*原子结点的值域atom*/struct{structGLNode*hp,*tp;}htp;/*表结点的指针域htp，

包括表头指针域hp和表尾指针域tp*/}atom_htp;/*atom_htp是原子结点的值域atom和表结点的指针域htp的共用体域*/}*GList；①A=()^10e③C=(a,(b,c,d))1^110a0b0d0c1^1例：②B=(e)A=NULLGListA,B,C,D,E;

⑤E=(a,E)④D=(A,B,C)＝((),(e),(a,(b,c,d)))

0a10e1^11^110a0b0d0