4.多维数组和广义表
当数组维数为 1 时, 它是一种元素个数固定的线性表. 当是多维数组时, 它可以看成是线性表的推广. 以二维数组为例:
a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
- 除了边界元素外, 每个元素都有分别位于行向量上和列向量上的两个直接前趋和两个直接后继. 如
b2的两个直接前趋为b1和a2, 两个直接后继为b3和c2. - 开始结点 (
a1) 没有前趋, 终端结点 (c4) 没有后继. - 边界上的结点只有行或列上的一个直接前趋或一个直接后继. 如
b1只有一个前趋结点a1,b4只有一个后继结点c4.
矩阵一般用数组来存储.
特殊矩阵指的是相同值的元素或者零元素在矩阵的分布有一定规律的矩阵. 可以对这类矩阵采取压缩存储.
对称矩阵的元素关于主对角线对称分布, 只需要存储矩阵上三角或下三角元素. 如下面的矩阵:
00
10 11
20 21 22
...
假设行数为 n, 可以看出, 如果把上面的矩阵存储到一维数组中, 则总共需要 n(n+1)/2 个空间.
而且矩阵中元素 ij 对应到以为数组位置 k 有如下关系:
- 如果 i >= j, 则
ij位于下三角:k = i * (i + 1) / 2 + j. - 如果 i < j, 则
ij位于上三角:k = j * (j + 1) / 2 + i.
三角矩阵指矩阵的对角线上方或下方均为常数或零的方阵. 分别称为下三角矩阵或上三角矩阵.
下三角矩阵 (其中 C 指代常数):
00 C C C C
10 11 C C C
20 21 22 C C
30 31 32 33 C
40 41 42 43 44
上三角矩阵 (其中 C 指代常数):
00 01 02 03 04
C 11 12 13 14
C C 22 23 24
C C C 33 34
C C C C 44
比之对称矩阵, 三角矩阵需额外存储重复的元素, 故需要 n (n + 1) / 2 + 1 个空间.
对于上三角矩阵, 矩阵元素 ij 对应到数组位置 k 的关系为:
- 如果 i <= j, 则
ij位于上三角:k = i * (2n - i + 1) / 2 + j - i. - 如果 i > j, 则存储于最后一项:
k = n (n + 1) / 2.
对于下三角矩阵, 矩阵元素 ij 对应到数组位置 k 的关系为:
- 如果 i >= j, 则
ij位于下三角, 类似对称矩阵:k = i * (i + 1) / 2 + j. - 如果 i > j, 则存储于最后一项:
k = n (n + 1) / 2.
稀疏矩阵是非零元素的分布没有规律的矩阵, 因此在存储非零元素值时, 还需同时存储该元素的行列位置, 所以可用一个称为三元组 (i, j, a[i] [j]) 来唯一确定一个非零元素. 对稀疏矩阵的压缩存储通常有顺序存储和链式存储两种方法:
- 链式存储: 一般用十字链表法, 比较复杂, 不做介绍.
- 顺序存储: 将三元组按行优先的顺序排列, 可得到一个其结点均为三元组的线性表, 称为三元组表.
为了便于随机存取任一行的非零元素, 可以在三元组表表示的系数矩阵中额外存储每一行的第一个非零元素在三元组表中位置的数组. 这样的表示叫做带行表的三元组表, 又称为行逻辑连接的顺序表.
广义表是线性表的推广, 又称列表. 线性表中的元素仅限于原子项, 如果放松这种限制, 允许它们自身具有结构, 就产生了广义表的概念.
广义表是 n 个元素的有限序列, 其中的元素或者是原子项, 或者是一个广义表. n 为它的长度, 内层的广义表称作子表.
嵌套的层数称为它的深度. 称第一个元素为表头, 称其余元素组成的表为表尾. 显然, 广义表是一个递归定义,
它是一种多层次的非线性结构. 它不仅是线性表的推广, 也是树结构的推广.
广义表通常记为 LS=(a1, a2, ..., an).
注意, () 和 (()) 是不同的. 前者是空表, 长度为 0, 后者是由空表做元素的广义表, 长度为 1.
通常采用链式存储结构表示广义表. 结点由三个域构成:
tag 是标志位. tag 为 1 表示该结点是原子结点, 此时第二个域为 data, 存放结点值; tag 为 0 表示该结点是子表, 此时第二个域为 slink, 存放子表地址. 第三个域 link 存放同一层的下一个元素地址.
由此, 广义表 D=((), (a), (a, (b, c))) 的表示为:
