描述

广义表(General liat),一般写为下列形式:

((1, 2, (3, 4), ()), (5, 6))

表头为 (1, 2, (3, 4), ()) , 表尾为 (5, 6)。当表不为空时,第一个元素称为表头,其余元素组成的表为表尾,表头可以为广义表或者原子,比如

((5), 6)

的表头为 (5),表尾为 (6)。而

(())

的表头表尾都是空表 ()。

存储结构

可以将广义表分为表头和表尾存储。以

(1, 2, (3, 4), 5)

为例:

[["1"][+]]
       |
    [["2"][+]]
           |
         [[+]---------------[+]]
           |                 |
        [["3"][+]]        [["5"][NIL]]
               |
            [["4"][NIL]]

’+’ 表示这是一个指针,指向另一个广义表,”” 表示这个表头存储的数据是一个原子。也就是不断向后分出表尾,直到表尾为空表,记为 NIL。

实现

广义表的一个简单 C 语言实现