数组矩阵广义表：广义表的介绍及设计（C语言实现）

1.    简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

数组可以存储不允许再分割的数据元素，如字符’X’，数字11，当然他也可以存储数组，二维数组就是一个例子，你可以理解二维数组的每一行的元素是一列中的对应元素的组合。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

广义表是一种线性表，或者说，广义表是一种线性表的推广，它属于多层次的线性表，广义表中可以存储不可以再分割的元素，同时也可以存储一张广义表（子表），因此适用情况相对灵活。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

设ai为广义表的第i个元素，广义表是n（n≥0）个元素的一个序列，若n=0时则称为空表。,广义表GL的一般表示与线性表相同，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

GL=(a1,a2,…,ai,…,an)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

其中n表示广义表的长度，即广义表中所含元素的个数，n≥0。如果ai是单个数据元素，则ai是广义表GL的原子；如果ai是一个广义表，则ai是广义表GL的子表。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

一般来说，广义表具有如下重要的特性：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

（1）广义表中的数据元素有相对次序文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

（2）广义表的长度定义为最外层包含元素个数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

（3）广义表的深度定义为所含括弧的重数。其中原子的深度为0，空表的深度为1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

（4）广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

（5）广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

（6）任何一个非空广义表GL均可分解为表头head(GL) = a1和表尾tail(GL) = ( a2,…,an) 两部分。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

2.    广义表的结点设计文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

我们以常规方法来看，广义表是一种不定规模的数据结构，很难为之分配具体的空间，因此创建的方法采用动态的链式方法，动态的创建空间。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

如图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

对于每一个结点而言由如上三大部分组成，其中Tag域为标志字段，其只有两个参数，0或者1（Tag域使用int类型，在某些情况下因为只需要简单判断也可以使用更短的类型，如bool）；Atom/Node域的内容由tag标志决定，当Tag为0时表示该节点是原子结点（即存放原子数据），当Tag为1时表示该节点为指向下一个广义表的指针（即表结点），Link域存放与本元素同一层的下一个元素所在的结点地址，当本元素时所在层的最后一个元素时，Link域为NULL；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

链式法设计：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

下面是子表法设计：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

首先定义AtomType的数据类型，可以为基本的int型，也可以为一些其他的数据类型，包括简单的char或者是复杂一些的结构体，不过这里不建议创建过于复杂的结构体。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html

其次，关于tag域的建立，我们可以使用一个枚举建立，分别表示Atom/Node到底取何种值，而关于Atom/Node域，则可以建立一个union（共用体）来表示，共用体公用内存空间，只能取其一赋值，这也符合广义表的基本需求；而关于表达的Link域，我们使用链式的存储方法可以化简，而使用子表的方式则必须表达。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25146.html