线性链表2.4 数组.ppt

2).按列优先顺序存储结构 按列优先顺序存放是将数组看作若干个列向量。 例如，二维数组Amxn，可以看作n个列向量，每个列向量m个元素。数组中的每个元素由元素的两个下标表达式唯一确定。 地址计算公式： LOC（aij）=LOC（a11）+（（j-1）*m+（i-1））*L 其中，L 是每个元素所占的存储单元。 二维数组按列优先存储举例 LOC（a23）= LOC（a11）+（3-1）* 4+（2-1）= 10 LOC（a34）= 1 + （4-1）* 4 + （3-1） = 15 LOC（a14）= 1 + （4-1）* 4 + （1-1） = 13 有二维数组如下： 2.4.2 规则矩阵的压缩 实际工程问题中推导出的数组常常是高阶、含大量零元素的矩阵，或者是一些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储。 压缩的含义是： 相同值的多个元素占用一个存储单元； 零元素不分配存储单元。 能够采用压缩存储的矩阵 对称矩阵:存储主对角线以上（下）的元素； 上（下）三角矩阵:只存储三角阵元素； 带状矩阵:只存储带状元素； 稀疏矩阵:只存储非零元素； 1 下三角矩阵的压缩存储 开辟一个长度为n（n+1）/2的一维数组B，然后一行接一行地依次存放A中下三角部分的元素。 以行为主压缩存储 以列为主压缩存储 2 对称矩阵的压缩存储 对称矩阵的元素满足：aij = aji 1 ≤ i ，j ≤ n 因此将n*n 个元素压缩存放到 n（n+1）/2 个单元的一维数组S（（n+1）*n/2）中。 （按行存放）aij的地址为： 对称矩阵的压缩存储举例 存于一维数组S[6] S[6]=( a11, a21, a22, a31, a32, a33 ) 1 2 3 4 5 6 LOC(a31)=3(3-1)/2+1= 4 LOC(a22)=2(2-1)/2+2= 3 LOC(a21)=2(2-1)/2+1= 2 设有A3x3矩阵: 3 三对角矩阵的压缩存储 在三对角矩阵中，三条对角线以外的元素均为零，并且，除了第一行与最后一行外，其他每一行均只有三个元素为非零，因此，n阶三对角矩阵共有3n-2个非零元素。 对角矩阵的压缩存储 以行为主存放 ： 以列为主存放 ： 2.4.3 一般稀疏矩阵的表示 如果一个矩阵中绝大多数的元素值为零，只有很少的元素值非零，则称该矩阵为稀疏矩阵 。 1 三列二维数组表示 （1）非零元素所在的行号i； （2）非零元素所在的列号j； （3）非零元素的值V。 即每一个非零元素可以用下列三元组表示： （i，j，V） 例如，上述稀疏矩阵A中的8个非零元素可以用以下8个二元组表示（以行为主的顺序排列）： （1，3，3） （1，8，1）（3，1，9）（4，5，7） （5，7，6） （6，4，2）（6，6，3） (7，3，5） 为了表示的唯一性，除了每一个非零元素用一个三元组表示外，在所有表示非零元素的三元组之前再添加一个三元组：（I，J，t） 其中I表示稀疏矩阵的总行数，J表示稀疏矩阵的总列数，t表示稀疏矩阵中非零元素的个数。 上述稀疏矩阵A可以用以下9个三元组表示： （7，8，8）（3，1，9）（5，7，6） （6，6，3）（1，3，3）（4，5，7） （6，4，2）（7，3，5）（1，8，1） 其中第一个三元组表示了稀疏矩阵的总体信息（总行数，总列数、非零元素个数）， 其后的8个三元组依次（以行为主排列）表示稀疏矩阵中每一个非零元素的信息（所在的行号、列号以及非零元素值）。 为了使各三元组的结构更紧凑，通常将这些三元组组织成三列二维表格的形式，一般又表示成三列二维数组的形式，并简称为三列二维数组。 为了便于在三列二维数组B中访问稀疏矩阵A中的各元素，通常还附设两个长度与稀疏矩阵A的行数相同的向量POS与NUM， POS（k）表示稀疏矩阵A中第k行的第一个非零元素（如果有的话）在三列二维数组B中的行号， NUM（k）表示稀疏矩阵A中第k行中非零元素的个数， 这两个向量之间存在以下关系： POS(1)＝2 POS(k)＝POS(k-1)十NUM(k-1)，2 ≤ k ≤ m 2 线性链表表示 稀疏矩阵运算后非零元素个数变化时，采用三列二维数组表示不方便； 可采用链表的方式来表示 结点定义： 行域 列域 值域 指针域 3、十字链表 每个结点有五个域：行域、列域、值域、 向下域与向右域。 row col val 行域 列域 值域 向下域 向右域 down