广义表

ゝ一纸荒年。 2022-08-22 13:17 247阅读 0赞

**广义表的定义：**

![20160528163216384][]

**在广义表中约定：**

① 第一个元素是表头，而其余元素组成的表称为表尾；

② 用小写字母表示原子类型，用大写字母表示广义表。

**广义表与线性表的区别和联系？**

广义表中元素既可以是原子类型，也可以是广义表； 当每个元素都为原子且类型相同时，就是线性表。

**特点：**

![20160528163241514][]

特别提示：任何一个非空表，表头可能是原子，也可能是广义表；但表尾一定是广义表。

![20160528163318588][]

![20160528163336891][]

**两种特殊的基本操作：**

GetHead( L) ——取表头(可能是原子或列表);

GetTail(L ) ——取表尾(一定是列表) 。

例如：

![20160528163407063][]

广义表可以采用顺序存储结构吗？

由于广义表中的数据元素的类型不统一，因此难以采用顺序存储结构来存储。

如何采用链接存储结构存储广义表？

若广义表不空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。

**广义表的存储结构——头尾表示法**

![20160528163439588][]

![20160528163505010][]

![20160528163523151][]

![20160528163545886][]

![20160528163603238][]

[20160528163216384]: /images/20220722/e23c5b0755044461a7e314c7766eee4d.png
[20160528163241514]: /images/20220722/25acf59435ba48b0a3aad39e0a97f979.png
[20160528163318588]: /images/20220722/fcd022edeb204717a8a7075eb3a85fdb.png
[20160528163336891]: /images/20220722/fc42144f9fe04103a27ff761ac21c4f3.png
[20160528163407063]: /images/20220722/58bcb32bfaef4e40b3810bd34472df15.png
[20160528163439588]: /images/20220722/55071570098344b481d8d90f113f9d23.png
[20160528163505010]: /images/20220722/b19c3a15452043a688d5eaa22892282a.png
[20160528163523151]: /images/20220722/8d16f361c524450ea829f362a46630c4.png
[20160528163545886]: /images/20220722/b93885450dd54f70acaff8264de735f7.png
[20160528163603238]: /images/20220722/90786dd3bae14d849b1588c39f31eb42.png