前言

????????多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前趋和直接后继。

????????多维数组可以看成是线性表的推广。因为一旦确定数组是按行或按列优先顺序存储之后，每个数组元素之间的关系就同一维数组一样变成线性的了。因此，只要弄清楚多维数组按行优先顺序存储结构之后，它的运算就同线性表的运算类似。

一、多维数组

1.多维数组定义及顺序存储

1.1 多维数组的定义

????????数组是我们比较熟悉的一种数据类型。由于数组中各元素具有相同的数据类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其他复杂的结构较为简单。当数组维数为1时，数组是一种元素个数固定的线性表，而维数大于1时，称为多维数组，它可以看成是线性表的推广。这里仅讨论多维数组。
????????由于对数组一般不做插入和删除操作，因此数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。所以，一般都是采用顺序存储的方法来表示数组。

????????多维数组是一种复杂的数据结构。以二维数组为例，数组元素之间的关系除了边界元素外，每个元素 $a_{ij}$ 都恰好有两个直接前趋和两个直接后继：行向量上的直接前趋是 $a_{ij-1}$ 和 $a_{ij+1}$ ，列向量上的直接前趋是 $a_{i-1j}$ 和直接后继 $a_{i+1j}$ 。并且二维数组也只有一个开始结点 $a_{00}$ ，它没有前趋；仅有一个终端结点 $a_{m-1n-1}$ ，它没有后继。此外，边界上的结点(开始结点和终端结点除外)只有一个直接前趋或者只有一个直接后继。

1.2 数组的顺序存储

（1）按行优先顺序存储，即将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。A的m x n个元素按行优先顺序存储的线性序列为：
???????? $a_{00},a_{01},...,a_{0n-1},a_{10},a_{11},...,a_{1n-1},...,a_{m-10},a_{m-11},...,a_{m-1n-1}$
（2）按列优先顺序存储，即将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后， A的m x n个元素按列优先顺序存储的线性序列为：
???????? $a_{00},a_{10},...,a_{m-10},a_{01},a_{11},...,a_{m-11},...,a_{0n-1},a_{1n-1},...,a_{m-1n-1}$
????????如果按上述两种方式顺序存储数组，只要知道开始结点的存储地址(即基地址)，维数和每维的上、下界，以及每个元素所占用的单元数，就可以将每个数组元素的存储地址表示为其下标的线性函数。
????????在C语言中的数组元素 $a_{ij}$ 的地址计算函数为： $LOC(a_{ij})=LOC(a_{00})+(i*n+j)*d$

2.矩阵的压缩存储

2.1 特殊矩阵

????????所谓特殊矩阵，指的是相同值的元素或者零元素在矩阵中的分布有一定规律的矩阵。

2.1.1 对称矩阵

????????若n阶方阵A中的元素满足下述性质： $a_{ij}=a_{ji}(0\leqslant i,j\leqslant n-1)$

则称A为n阶的对称矩阵。对称矩阵中的元素是关于主对角线对称的，所以只需要存储矩阵上三角或下三角的元素即可，让两个对称的元素共享一个存储空间。

2.1.2 三角矩阵

????????以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指矩阵的下三角(不包括对角线)中的元素均为常数c或是零的n阶方阵，如图4.3(b)所示；下三角矩阵正好相反，它的主对角线上方均为常数c或零，如图4.3(a)所示。一般情况下，三角矩阵的常数c均为零。

2.2 稀疏矩阵

????????由于特殊矩阵中非零元素的分布是有规律的，因此总可以找到矩阵元素与一维数组的下标的对应关系。但还有一种矩阵，其中有s个非零元素，而s远远小于矩阵元素的总数，通常把这种矩阵称为稀疏矩阵，为了节省存储单元，也可用压缩存储方法只存储非零元素。由于稀疏矩阵非零元素的分布一般是没有规律的，因此在存储非零元素时，除了存储非零元素的值之外，还必须同时存储该元素的行、列位置(即下标)，所以可用一个称为三元组(i，j， $a_{ij}$ )来唯一确定一个非零元素。

三元组表：

????????如果将表示稀疏矩阵非零元素的三元组按行优先的顺序排列，则可得到一个其结点均为三元组的线性表，将这种线性表的顺序存储结构称为三元组表。

二、广义表

1.广义表基础

????????广义表是线性表的推广，又称列表。线性表的元素仅限于原子项，即每个数据元素只能是一个数或一个记录，如果放松对线性表元素的这种限制，允许它们自身具有结构，由此就产生广义表的概念。

1.1 广义表的定义

????????广义表是n(n≥0)个元素 $a_{1}$ ， $a_{2}$ ，...， $a_{n}$ 的有限序列，其中 $a_{i}$ 或者是原子项，或者是一个广义表，通常记作LS=( $a_{1}$ ， $a_{2}$ ，...， $a_{n}$ )。LS是广义表的名字，n为它的长度。若 $a_{i}$ 又是广义表，则称它为LS的子表。为了区分原子和广义表，在书写时习惯上用大写字母表示广义表，用小写字母表示原子。通常用圆括号将广义表括起来，用逗号分隔其中的元素。当广义表LS非空时，称第一个元素 $a_{1}$ 是LS的表头(head) ，其余元素组成的表( $a_{2}$ ，...， $a_{n}$ ) 称为LS的表尾(tail) 。