第五章 数组和广义表

特殊矩阵的分类

  • 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
  • 我们要研究的特殊矩阵包括：对称矩阵、三角矩阵，对角矩阵。

对称矩阵的压缩存储

  • 我们可以按从上到下、从左到右将这些元素存放在一个向量sa[0…n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。

  • 若 i ≥ j，则 aij 在下三角形中。
    aij 之前的 i-1 行共有 1 + 2 + … + i-1 = i (i-1) / 2个元素;
    在第i行上,aij 之前共有 j-1 个元素（即 ai1, ai2, ai3, … , aij-1），因此有：

k = i * (i-1) / 2 + j – 1 当 i ≥ j
k = j * (j-1) / 2 + i - 1 当 i < j

三角矩阵的压缩存储

  • 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n (n+1) / 2个，因此，三角矩阵可压缩存储到向量sa[0…n(n+1) / 2]中，其中c存放在向量的最后一个分量中。
  • 上三角矩阵中，主对角线之上的第i行(0≤i < n)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有i(2n-i+1)/2 个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,…aij-1。因此，sa[k]和aij的对应关系是：
    上三角矩阵:
    i ( 2n - i + 1) / 2 + j - i 当 i ≤ j
    n (n + 1) / 2 当 i > j
    下三角矩阵:
    i (i + 1) / 2 + j 当i ≧ j
    n (n + 1) /2 当 i < j

对角矩阵的压缩存储

  • 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。
  • 数组sa中的元素sa[k]不三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：

LOC(i,j) = LOC(0,0) + [3 * i - 1 + (j - i + 1)] * d = LOC(0,0) + (2 i + j) * d

稀疏矩阵的三元组表示

广义表

  • 广义表（Lists）又称列表，是线性表的推广。广义表是n(n≥0)个元素的有限序列，LS=（a1,a2,…an）
  • 其中LS是广义表的名字，n为它的长度，ai是原子戒者是一个广义表。若ai是广义表，则称它为LS的子表。
  • 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
  • 若广义表LS非空（n≥1），则a1是LS的表头，其余元素组成的表（a2,a3,…an）称为LS的表尾。
  • 广义表是递归定义的，广义表中可以包含广义表。
  • 一个表的“深度（Depth）”是指表展开后所含括号的层数。

广义表是一种递归的线性结构，广义表的长度指广义表中元素的个数。
广义表的深度指广义表中括弧的重数

  1. 列表的元素可以是子表，而子表的元素还可以是子表。
  2. 列表可以为其它列表所共享。
  3. 列表可以是一个递归的表，也就是说列表也可以是它自身的一个子表。