广义表

data structure

广义表定义

广义表又称列表(List)，是 n≥0 个元素 (a1,a2,a3,...,an) 的优先序列，其中ai是原子数据类型或者是一个广义表，记

LS=(a1,a2,a3,...,an)

• LS : 表示表名
• ai : 表示元素，通常小写字母表示元素是原子数据类型，大写字母表示元素是广义表

广义表表头

广义表的第一个元素(a1),可以是一个原子类型也可以是一个广义表

广义表表尾

广义表中除了第一个元素之外的其他元素组成的广义表 --> 表尾是一个表

广义表可以使用 "()" 表示，其中()的最深层数表示表的深度， 表的次序 ：一个直接前驱，一个直接后继

例如

LS = (a1) : LS中有一个元素 表头为 a1，表尾为 () LS = (a1, a2) ：LS中有两个元素 表头为 a1，表尾为 (a2) LS = (a1, ()) ：LS中有两个元素 表头为 a1，表尾为 (()) LS = (a1, a2,()) ：LS中有三个元素 表头为 a1，表尾为 (a2,())

表的共享

两个广义表 A，B, 其中A和 B 的关系 B = (A)

表的递归

有一个广义表 A，其中 A = (A)