抽象数据类型广义表的定义如下: ADT GList { 数据对象: D={ | i=1,2,..,n; n≥0; ∈AtomSet 或 ∈GList, AtomSet为某个数据对象 } 数据关系: R1={< , >| , ∈D, 2≤i≤n } |
从数据对象和数据关系的定义可见,广义表是一种"多层次"的"线性结构",通常写作 其中, LS为广义表 的名称,类似于线性表, 是表中第 i 个数据元素,并定义 n (广义表中元素的个数)为广义表的长度,同样,n=0 的广义表被称为空表。但和线性表有很大区别的是,广义表中的每一个数据元素 i 它可以是不可分割的单原子,也可以是一个广义表。也就是说,广义表也是一种"递归"定义的数据结构。 对于任意一个非空广义表 它的第一个数据元素被定义为广义表的"表头",而由其余数据元素构成的广义表 被定义为广义表的"表尾"。 |