广义表

广义表名词解释
广义表（英语：Generalized List）是一种非线性的数据结构。

但如果广义表的每个元素都是原子，它就变成了线性表。

广义表广泛地用于人工智能等领域的LISP语言。

广义表一般记作LS = (a1, a2, ···, an), n是它的长度，ai可以是单个元素(原子)，也可以是广义表(子表)，当广义表非空时，称第一个元素a1为LS的表头，称其余元素组成的表为LS 的表尾。

注意：表头是元素(可以是原子，也可以是广表)，表尾一定是广义表。

E=(a, E)是一个递归的表。

D=(( ),(e),(a,(b,c,d)))是多层次的广义表，长度为3，深度为3。

例：((a),a)的表头是(a)，表尾是(a)，((a))的表头是(a)，表尾是( )。

5.4 广义表的类型定义ADT Glist {数据对象：D＝{e i | i=1,2,..,n; n≥0;e i∈AtomSet 或e i∈GList,AtomSet为某个数据对象} 数据关系：LR＝{<e i-1, e i >| e i-1 ,e i∈D, 2≤i≤n }广义表是递归定义的线性结构，LS = ( α1, α2, ⋅⋅⋅, αn )其中：αi 或为原子或为广义表换句话说，广义表是一个多层次的线性结构。

例如:D = (E, F)E = (a, (b, c))F = (d, (e))A = ( )B = (a, B) = (a, (a, (a, ⋅⋅⋅ , ) ) )C = (A, D, F)广义表的结构特点:1) 广义表中的数据元素有相对次序;2) 广义表的长度定义为最外层包含的元素个数;3) 广义表的深度定义为所含括弧的重数;注意: “原子”的深度为“0”;“空表”的深度为14) 广义表可以共享;5) 广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。

6) 任何一个非空广义表LS = ( α1, α2, …, αn)均可分解为表头Head(LS) = α1 和表尾Tail(LS) = ( α2, …, αn)两部分例如：LS = ( A, D )Head(LS) = A Tail(LS) = ( D )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )基本操作：∙结构的创建和销毁InitGList(&L); DestroyGList(&L);CreateGList(&L, S); CopyGList(&T, L);∙状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L); ∙插入和删除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);∙遍历Traverse_GL(L, Visit());} ADT GList5.5 广义表的表示方法头、尾指针的链表结构表结点: tag=1 hp tp原子结点：tag=0 data构造存储结构的分析方法:1)空表ls= NIL2)空表ls = NIL•••α1α2αn 若子表为原子5.6 递归函数的设计方法递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件:1) 在每一次调用自己时，必须是(在某种意义上)更接近于解;2) 必须有一个终止处理或计算的准则。

广义表中原子的深度什么是广义表广义表（Generalized List），简称GList，是一种拓展了线性表的数据结构。

与线性表只能存储单一类型元素不同，广义表可以存储原子和子表两种类型的元素。

在广义表中，原子是不可再分的最小单位，可以是数字、字符、布尔值等。

而子表则是由多个元素组成的序列，可以是空表或者由原子和/或其他子表组成。

举个例子，下面是一个简单的广义表示例：L = [1, 2, [3, 4], [5, [6, 7]]]在这个示例中，数字1和2是广义表L的原子；[3, 4]和[5, [6, 7]]则是L的两个子表。

广义表中原子的深度在广义表中，一个原子所处的层次称为它的深度。

深度为0表示该原子直接位于广义表最外层；深度为1表示该原子位于第一层子表内；以此类推。

对于上述示例L来说： - 数字1和2的深度为0； - 子列表[3, 4]的深度为1；- 子列表[5, [6, 7]]中数字5的深度为1，子列表[6, 7]的深度为2。

计算广义表中原子的深度计算广义表中原子的深度可以使用递归的方法。

首先，我们需要定义一个函数来计算广义表中原子的深度。

假设我们将这个函数命名为calculate_depth，它接受一个广义表作为参数，并返回该广义表中所有原子的深度。

def calculate_depth(glist):depth = 0if isinstance(glist, list):for item in glist:if isinstance(item, list):depth = max(depth, calculate_depth(item) + 1)else:depth = max(depth, 0)return depth在上述代码中，我们首先初始化深度为0。

然后，判断传入的参数是否是列表类型。

如果是列表类型，则遍历列表中的每个元素。

对于每个元素，如果它仍然是一个列表，则递归调用calculate_depth函数来计算该元素内部原子的深度，并将结果加1。

第6章广义表z6.1 广义表的基本概念z6.2 广义表的存储结构z6.3 广义表的操作算法16.1 广义表的基本概念广义表（列表）的概念-n( ≥0 )个表元素组成的有限序列，记作LS= ( a1, a1, a2, …, a n)LS是表名，a i是表元素，它可以是单个元素(称为原子) ，可以是表(称为子表) 。

n为表的长度。

n= 0 的广义表为空表。

n> 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。

2广义表举例：（1）A=（）（2）B=（e）（3）C=（a, (b, c, d) )（4）D=（A，B，C）（5）E= (a , E）9任意一个非空广义表，均可分解为表头和表尾。

9对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。

3广义表的基本操作：•结构的创建和销毁InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);•状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L);•插入和删除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);•遍历Traverse_GL(L, Visit());66. 2 广义表的存储结构z由于广义表中的元素不是同一类型，因此难以用顺序结构表示，通常采用链接存储方法存储广义表，并称之为广义链表。

z由于广义表中有两种数据元素，原子或子表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。

z下面介绍一种广义表的链式存储结构。

78扩展的线性链表表示法：-子表结点由三个域组成：标志域、表头指针域和指向下一个元素的指针域；-原子结点的三个域为：标志域、值域和指向下一个元素的指针域。

数据结构5.3_⼴义表的定义和存储结构⼴义表定义：⼴义表(Lists，⼜称列表)是⼀种⾮线性的数据结构，是线性表的⼀种推⼴。

即⼴义表中放松对表元素的原⼦限制，容许它们具有其⾃⾝结构。

⼀个⼴义表是n（n≥0）个元素的⼀个序列，若n=0时则称为空表。

GL=(a1,a2,…,ai,…,an)其中n表⽰⼴义表的长度，即⼴义表中所含元素的个数，n≥0。

如果ai是单个数据元素，则ai是⼴义表GL的原⼦；如果ai是⼀个⼴义表，则ai是⼴义表GL的⼦表。

习惯上⽤⼤写表⽰⼴义表的名称；⽤⼩写字母表⽰原⼦。

当⼴义表⾮空时，称第⼀个元素a1为GL的表头（Head），称其余元素组成的表（a2,a3,...an）是GL的表尾（Tail）。

可以发现上述⼴义表的定义描述时，⼜⽤到了⼴义表的概念；⼴义表的存储结构：⼴义表中的数据元素可以具有不同的结构（或是原⼦，或是列表）。

因此难以⽤顺序存储结构表⽰，通常采⽤链式存储结构。

每个数据元素可⽤⼀个结点表⽰。

如何设定结点的结构？由于列表中的数据元素可能为原⼦或列表。

因此需要两种结构的结点：⼀种是表结点⽤于表⽰列表，⼀种是原⼦结点⽤于表⽰原⼦；若列表不空，则可以分解成表头和表尾；⼀个表结点可以由3个域组成：标志域（标识是表还是原⼦）、指⽰表头的指针域、指⽰表尾的指针域；对于原⼦结点只需要2个域：标志域、值域；--------⼴义表的头尾链表存储表⽰--------typedef enum {ATOM, LIST} ElemTag; //ATOM==0 原⼦； LIST==1 ⼦表typedef struct GLNode{ ElemTag tag; //公共部分，⽤于区分原⼦结点和表结点 union{ //原⼦结点和表结点的联合部分 AtomType atom; //atom是原⼦结点的值域， struct{ struct GLNode *hp *tp}ptr; //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾 };} *GList; //⼴义表类型--------⼴义表的扩展线性链表存储表⽰--------typedef enum {ATOM, LIST}ElemTag;typedef struct GLNode{ ElemTag tag; union{ AtomType atom; struct GLNode *hp; } struct GLNode *tp;} *GList;相关链接：。

以下关于广义表的叙述中，正确的(A)
A.广义表是0个或多个单因素或子表组成的有限序列
B.广义表至少有一个元素是子表
C.广义表不可以是自身的子表
D.广义表不能为空表
广义表(Lists，又称列表)是一种非连续性的数据结构，是线性表的一种推广。

即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

它被广泛的应用于人工智能等领域的表处理语言LISP语言中。

在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。

广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。

其中：
1.ai--或者是原子或者是一个广义表。

2.广义表通常记作：
Ls=( a1，a2，…，ai，…，an)。

3.Ls是广义表的名字，n为它的长度。

4.若ai是广义表，则称它为Ls的子表。

注意：
1.广义表通常用圆括号括起来，用逗号分隔其中的元素。

2.为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。

3.若广义表Ls非空(n≥1)，则al是Ls的表头，其余元素组成的表(a2，a3，…，an)称为Ls的表尾。

4.广义表是递归定义的.
由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。

在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。

根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。

⼴义表1.定义：⼴义表是⼀种复杂的数据结构，是线性表的扩展，能够表⽰树结构和图结构。

2.细分定义：⼴义表是n个数据元素a0，a1，...，an-1组成的有限序列，记为GList=（a0，a1，...，an-1）其中，（1）ai或为不可分的数据元素（称为原⼦），或为可再分的⼴义表（称为⼦表）。

（2）⼴义表的元素个数n称为⼴义表长度（特殊：当n=0时，为空表。

）（3）⼴义表的深度是指表格中所含括号的层数（特殊：原⼦的深度为0，空表的深度为1.）注意：如果⼴义表作为⾃⾝的⼀个元素，则称该⼴义表为递归表。

递归的深度是⽆穷指，其长度是有限值。

（4）为了区分原⼦和表，约定⼤写字母表⽰表，⼩写字母表⽰原⼦。

（5）另⼀种⼴义表表⽰称为⼜名表，约定每个表都要有名称，将名称写在表组成的括号前。

（6）⼴义表的语法：其中“（）”作为⼴义表开始和结束的标记，“，”作为原⼦或⼦表的分隔符。

3.⼴义表的特性。

（1）线性结构。

（⼴义表是⼀种线性结构，数据元素之间是线性关系，只不过元素不⼀定都是原⼦了，如果元素都是原⼦，那么这个⼴义表就是线性表，所以说线性表是⼴义表的特例）（2）多层次结构，有深度。

（注意：⼴义表是树的扩展。

当限制表中成分不能共享和递归时，该⼴义树就是树，树中的叶⼦结点对应⼴义表中的原⼦，⾮叶结点对应⼦表）（3）可共享（⼀个⼴义表可作为其他⼴义表的⼦表，多个⼴义表可共享⼀些⼴义表。

（4）可递归（⼴义表是⼀个递归表，当⼴义表中有共享或递归成分的⼦表时构成图结构，与有根，有序，有向图对应。

4.⼴义表的图形表⽰a.说明：（1）当⼴义表L（a，b）的数据元素全部都是原⼦时，L为线性结构的线性表。

（2）当⼴义表L（c，L）的数据元素中有⼦表，但没有共享和递归成分时，T为树结构的纯表。

（3）当⼴义表L（d，L，T）的数据元素中有⼦表，并且有共享成分时，G为结构的再⼊表。

（4）当⼴义表L（e，Z）的数据元素中有⼦表且有递归成分时，Z为图结构的递归表。

广义表是一种数据结构，它可以被广泛应用于各种实际应用场景。

以下是一些广义表应用场景的例子：1. 存储传感器数据：在物联网系统中，传感器收集各种数据并将其发送到数据处理中心。

这些数据可以被表示为广义表，其中每个元素表示一个传感器的读数。

通过这种方式，可以将多个传感器读数合并在一起以进行比较和关联，从而实现高级数据分析。

2. 文本处理：在自然语言处理中，广义表可以被用来表示文本数据。

例如，可以将文本分解为单词、短语和句子等元素，并将它们存储在广义表中。

这样，可以对文本进行各种操作，如分词、句法分析、语义分析等。

3. 图像处理：在图像处理中，广义表可以被用来表示图像的各个部分。

例如，可以将图像分解为像素、颜色和形状等元素，并将它们存储在广义表中。

这样，可以对图像进行各种操作，如滤波、分割、特征提取等。

4. 社交网络分析：在社交网络分析中，广义表可以被用来表示社交网络中的节点和关系。

例如，可以将每个节点表示为一个广义表，其中包含节点的属性（如用户名、性别、年龄等）和与该节点相关的关系（如好友、关注者等）。

通过这种方式，可以对社交网络进行各种操作和分析，如寻找关键节点、社区检测、网络流量分析等。

5. 用户行为分析：在电子商务或社交媒体平台上，用户行为数据可以被表示为广义表。

例如，可以将每个用户的行为（如浏览、购买、评论等）表示为一个广义表，其中包含时间、地点、商品等元素。

通过这种方式，可以对用户行为进行分析和预测，以优化平台功能和提供更好的用户体验。

6. 数据库管理系统：在数据库管理系统中，广义表可以被用来表示各种数据结构。

例如，可以将数据库中的表表示为广义表，其中每个元素表示一个记录的各个字段。

通过这种方式，可以对数据库进行各种操作和分析，如查询优化、数据挖掘等。

综上所述，广义表可以广泛应用于各种实际应用场景，包括传感器数据处理、文本处理、图像处理、社交网络分析、用户行为分析和数据库管理系统等。

通过使用广义表，可以方便地进行数据处理和分析，提高数据处理效率和准确性，从而为各种应用场景提供更好的支持和服务。

广义表的长度和深度怎么看
广义表的长度
广义表的长度，指的是广义表中所包含的数据元素的个数。

由于广义表中可以同时存储原子和子表两种类型的数据，因此在计算广义表的长度时规定，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。

例如，在广义表{a,{b,c,d}} 中，它包含一个原子和一个子表，因此该广义表的长度为2。

再比如，广义表{{a,b,c}} 中只有一个子表{a,b,c}，因此它的长度为1。

前面我们用LS={a1,a2,...,an} 来表示一个广义表，其中每个ai 都可用来表示一个原子或子表，其实它还可以表示广义表LS 的长度为n。

广义表的值
广义表是由原子和广义表构成的有序排列，是一种具有递归性质的数据结构。

广义表可以理解为是一种可以存储不同类型数据元素的表。

广义表中的元素可以分为两类，即原子和子表。

其中，原子是广义表中最基本的元素，它可以是数字、字母或其他的基本数据类型。

而子表则是由一组元素组成的序列，也可以是另外一个广义表。

因为子表本身也是一种广义表，所以广义表具有递归性质。

广义表的值可以用递归的方式进行定义和计算。

通过递归算法，可以将一个广义表不断地拆分成原子和子表，直到最终计算出表达式的结果。

在计算广义表的值时，需要注意运算符的优先级，以及处理子表时需要递归计算子表中的元素。

广义表的值在编程语言中具有广泛的应用，例如在Lisp语言中广义表被广泛地应用于函数调用和递归算法的实现中。

在Python语言中，广义表是通过原生类型列表来实现的，可以用列表来表示子表，通过递归遍历列表实现对广义表的处理。

总之，广义表是一种具有广泛应用的数据结构，通过递归算法可以计
算广义表的值，具有较强的表达和计算能力。

在编程语言中，广义表也被广泛地应用于函数调用、递归算法和数据结构的实现中。