广义表 array数组：广义表的介绍和建议（用C实现）

terry 2年前 (2023-09-27) 阅读数 65 #数据结构与算法

1。简介

数组可以存储不可分割的数据元素，例如字符“X”和数字11。当然，它们也可以存储数组，例如二维数组。你可以理解为二维数组每一行的元素都是该列对应元素的组合。

广义表是一个线性表，或者换句话说，它是线性表的泛化。这是一个多级线性表。广义表可以存储不能再分区的元素，也可以存储广义表（子表），所以适用的情况比较灵活。

假设ai是广义表的第i个元素，广义表是n（n≥0）个元素的序列。如果n=0，则称为空列表。，广义表 GL 的一般表达式与线性表相同，即：

GL=(a1,a2,…,ai,…,an)

其中 n 代表广义表的长度，即广义表所含元素个数，n≥0。如果 ai 是单个数据元素，则 ai 是广义表GL 原子；如果 ai 是广义表，那么 ai 是广义表GL 的子表。

一般来说，广义表具有以下重要属性：

(1) 广义表中的数据元素具有相对顺序

(2) 广义表的长度定义为包含的元素数量最外层

(3 ) 广义表的深度定义为括号内的倍数。原子的深度为0，空表的深度为1

(4)广义表可以共享；广义表可以被其他广义表共享；这种共享的广义表表称为重入表

(5) 广义表可以是递归表。广义表可以成为他自己的孩子。这种类型的表称为递归表。递归表的深度无限，长度有限

(6) 任何非空 GL 都可以分解为 head (GL) = a1 和 end (GL) = ( a2,...,an ) 两个部分。

2。广义表的节点设计

从常规的角度来看，广义表是一个大小不确定的数据结构，很难为其分配特定的空间，所以创建方式采用动态链接的方式来动态创建空间。

如图：

对于每个节点来说，都由以上三部分组成。 Tag字段是一个标志字段，只有两个参数，0或1（Tag字段在某些情况下使用int类型，由于只需要简单的求值，因此可以使用较短的类型，例如bool）； Atom/Node字段的内容由标签标志决定。当Tag为0时，表示该节点是原子节点（即存储原子数据）。当Tag为1时，表示该节点是指向下一个广义表的指针（即表节点）。 Link字段存储与该元素同层的另一个元素的节点地址。当该元素是一层的最后一个元素时，Link字段为NULL；

链式方法设计：

#define AtomType inttypedef enum{⓶ OM{‶‶ ag; //ATOM = 0：原子； LIST = 1: 子列表 /*节点设计*/typedef struct

GLNodeGLNode{♿ ag 标签; //枚举类型标志字段只能取定义的枚举值 union{ //Union union，只能使用以下部分之一；要么采用 AtomType；或者采用 ptr 结构体，ptr 包含两个 hp 指针， tp   AtomTypeatom; struct‼'❙‼'❙struct   GLNode * hp, *tp; }ptr;

以下是子表设计：

/*扩展线性表，用于存储线性表=子表方法*/typedefstruct❙♶ 标签ElemTag； 联合{ 原子类型原子； hp； //对于列表，hp指向该列表的第一个元素，tp指向该级别的下一个元素}； ;

首先定义AtomType数据类型，可以是基本的int类型或者其他一些数据类型，包括简单的char或者比较复杂的结构，但不建议创建太复杂的结构

其次，当谈到创建标签数组，我们可以使用枚举来表示原子，或者/Node 的值是多少？对于Atom/Node域，可以创建一个并集来表示。只能将其中一个值分配给联合体的共享内存空间。这也符合广义表的基本需求；作为Field Link表达式可以使用链式存储的方式进行简化，但必须使用子表的方式来表达。