广义表的一些概念

本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/02/generalized-list.html　　作者: Suixin

基本概念

广义表（Lists，又称列表）是线性表的推广。广义表是个元素的有限序列，其中或者是原子项，或者是一个广义表。

• 元素：广义表的元素可以是原子，也可以是广义表，也可以为空。
• 表头：若广义表非空，则是LS的表头。表头可以是单元素值，也可以是表。空的广义表不能求表头。
• 表尾：若广义表非空，则除去表头后剩下的元素组成的表是LS的表尾。表尾一定是表。空的广义表不能求表尾。

例子

1. ——A是一个空表，其长度为零。
2. ——表B只有一个原子，其长度为1。
3. ——表C的长度为2，两个元素分别为原子和子表，其表尾为。
4. ——表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有。
5. ——这是一个递归的表，它的长度为2，E相当于一个无限的广义表.

考点

1. 广义表是0个或多个单因素或子表组成的有限序列，广义表可以是自身的子表，广义表的长度，所以可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系。
2. 广义表的表头为空，并不代表该广义表为空表。广义表和不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为1的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表。
3. 已知广义表,运用和函数取出LS中原子的运算是。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是说，广义表的操作，取出的元素是什么，那么结果就是什么。但是操作取出的元素外必须加一个表——““。；；；。
4. 二维以上的数组其实是一种特殊的广义表。
5. 在（非空）广义表中：1、表头可以是原子或者一个表；2、表尾一定是一个表；3.广义表难以用顺序存储结构；4.广义表可以是一个多层次的结构。

参考

数据结构：广义表