数据结构：广义表

广义表

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、广义表的定义

广义表（Generalized List）是线性表的扩展，是由零个或多个原子（Atom）或子表（SubList）组成的有序序列，记为：
LS=(a1,a2,...,an) LS = (a_1, a_2, ..., a_n)LS=(a1​,a2​,...,an​)
其中：

• nnn为广义表的长度，n=0n=0n=0时称为空表；
• aia_iai​既可以是原子（不可再分的基本元素，如数字、字符），也可以是子表（另一个广义表）；
• 广义表的深度：指表中嵌套的最大层数，原子的深度为 0，空表的深度为 1，例如((1,2), (3,(4)))的深度为 3。

广义表的核心特征：

1. 层次性：支持嵌套结构，子表可继续包含原子或子表；
2. 共享性：多个广义表可共享同一个子表（避免重复存储）；
3. 递归性：广义表可以是自身的子表（如LS = (LS, 1)）。

二、广义表的核心概念

1. 基本术语

2. 特殊广义表

• 空表：()，长度为 0，深度为 1；
• 纯原子表：无嵌套的广义表，等价于普通线性表，如(1, 2, 3)；
• 递归表：包含自身的广义表，如LS = (LS, 5)；
• 共享表：子表被多个父表引用，如A=(1,2), B=(A, 3)（A 是 B 的共享子表）。

3. 表头/表尾特性

• 任何非空广义表的表头可以是原子或子表，表尾一定是广义表（即使只剩一个元素，表尾也是空表）；
• 示例：
  • 对(1,2,3)，表头是1，表尾是(2,3)；
  • 对((1),2)，表头是(1)，表尾是(2)；
  • 对(a)，表头是a，表尾是()。

三、广义表的存储结构

广义表的嵌套特性决定了其无法用普通数组存储，通常采用链式存储，核心思路是：用两种节点（原子节点、表节点）表示不同元素，通过指针连接。

1. 节点结构设计

# 通用节点结构（Python 类表示） class GLNode: def __init__(self, tag): self.tag = tag # 标记：0 表示原子节点，1 表示表节点 if tag == 0: self.data = None # 原子节点：存储原子值 else: self.head = None # 表节点：指向子表的表头 self.tail = None # 所有节点：指向当前元素的下一个元素（表尾）

• 原子节点（tag=0）：data存储原子值（如 1、‘a’），tail指向同一层的下一个元素；
• 表节点（tag=1）：head指向子表的第一个节点，tail指向同一层的下一个元素。

2. 存储示例

以广义表LS = (a, (b, c), d)为例，链式存储结构如下：

表节点(1) → 原子节点(0, a) → 表节点(1) → 原子节点(0, d) → None ↓ (tail) ↓ (tail) ↓ (tail) 原子节点(0, b) → 原子节点(0, c) → None ↓ (head) ↓ (tail) ↓ (tail)

四、广义表的核心操作

1. 基本操作列表

2. 实现示例（Python）

classGLNode:"""广义表节点类"""def__init__(self,tag):self.tag=tag# 0: 原子节点，1: 表节点self.data=None# 原子节点的数据self.head=None# 表节点的表头指针self.tail=None# 指向下一个元素的指针classGeneralizedList:"""广义表类"""def__init__(self):self.head=None# 广义表的头节点（表节点）def_parse(self,s,idx):"""递归解析字符串，返回当前节点和更新后的索引"""# 跳过空格whileidx<len(s)ands[idx]==' ':idx+=1ifidx>=len(s)ors[idx]==')':returnNone,idx+1# 空表或表结束ifs[idx]=='(':# 创建表节点node=GLNode(tag=1)idx+=1# 跳过 '('# 解析表头node.head,idx=self._parse(s,idx)# 解析表尾（递归处理后续元素）current=node.headwhilecurrentisnotNoneandidx<len(s)ands[idx]!=')':# 跳过逗号whileidx<len(s)ands[idx]==',':idx+=1# 解析下一个元素next_node,idx=self._parse(s,idx)ifnext_nodeisnotNone:current.tail=next_node current=next_nodereturnnode,idxelse:# 创建原子节点（提取连续的原子字符）atom=[]whileidx<len(s)ands[idx]notin',() ':atom.append(s[idx])idx+=1node=GLNode(tag=0)node.data=''.join(atom)returnnode,idxdefbuild_from_string(self,s):"""从字符串构建广义表（如 "(a,(b,c),d)"）"""ifs.strip()=='()':self.head=GLNode(tag=1)returnself.head,_=self._parse(s,0)def_get_length(self,node):"""递归求长度（辅助函数）"""ifnodeisNone:return0return1+self._get_length(node.tail)defget_length(self):"""求广义表的长度（最外层元素个数）"""ifself.headisNoneorself.head.tag!=1:return0returnself._get_length(self.head.head)def_get_depth(self,node):"""递归求深度（辅助函数）"""ifnodeisNone:return1# 空表深度为1ifnode.tag==0:return0# 原子深度为0# 表节点：深度 = 子表深度 + 1，取最大值max_depth=0current=node.headwhilecurrentisnotNone:current_depth=self._get_depth(current)ifcurrent_depth>max_depth:max_depth=current_depth current=current.tailreturnmax_depth+1defget_depth(self):"""求广义表的深度"""ifself.headisNone:return0returnself._get_depth(self.head)def_traverse(self,node,result):"""递归遍历（辅助函数）"""ifnodeisNone:returnifnode.tag==0:# 原子节点，添加值result.append(node.data)else:# 表节点，递归遍历子表result.append('(')self._traverse(node.head,result)result.append(')')# 遍历下一个元素ifnode.tailisnotNone:result.append(',')self._traverse(node.tail,result)deftraverse(self):"""遍历广义表，返回字符串形式"""result=[]ifself.headisNone:return"()"self._traverse(self.head,result)return''.join(result)# 使用示例if__name__=="__main__":# 构建广义表gl=GeneralizedList()gl.build_from_string("(a, (b, c), d)")# 输出基本信息print("广义表结构:",gl.traverse())# 输出 (a,(b,c),d)print("长度:",gl.get_length())# 输出 3print("深度:",gl.get_depth())# 输出 2# 测试空表gl_empty=GeneralizedList()gl_empty.build_from_string("()")print("空表深度:",gl_empty.get_depth())# 输出 1print("空表长度:",gl_empty.get_length())# 输出 0# 测试嵌套表gl_nested=GeneralizedList()gl_nested.build_from_string("((1, 2), (3, (4)), 5)")print("嵌套表结构:",gl_nested.traverse())# 输出 ((1,2),(3,(4)),5)print("嵌套表深度:",gl_nested.get_depth())# 输出 3

五、广义表的典型应用

1. 数据结构表示：用于表示复杂的嵌套数据，如 XML/JSON 数据的底层解析（JSON 的数组/对象嵌套本质是广义表）；
2. 表达式解析：表示算术表达式的嵌套结构，如(1 + (2 × 3))可表示为广义表(+, 1, (×, 2, 3))；
3. 树结构的存储：树的嵌套结构可直接映射为广义表，如二叉树1(2(3),4)可表示为(1, (2, 3), (4))；
4. 编译器语法分析：用于表示程序的语法树（嵌套的语法单元）；
5. 图形学：表示复杂的几何形状（嵌套的点、线、面结构）。

六、广义表与线性表的对比

广义表是线性表的泛化，弥补了线性表仅能存储原子的不足，是处理嵌套、层次化数据的核心数据结构，但由于递归和嵌套特性，实现和操作复杂度远高于普通线性表。