数据结构与数据库 课号 21050301 2012 秋
第五章数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 2
同理, 一个 n 维数组类型可以定义为其数据元素为 n-1 维数组类型的一维数组类型 数组一旦被定义, 它的维数和维界就不再改变 因此, 除了结构的初始化和销毁之外, 数组只有存取元素和修改元素值的操作 抽象数据类型数组的定义参见教材 p.90
第五章数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 4
5.2 数组的顺序表示和实现 使用一维内存来表示多维数组, 就必须按某种次序将数组元素排成一列序列, 然后将这个线性序列存放在存储器中 此外, 数组一旦建立, 结构中的元素个数和元素间的关系就不再发生变化 因此, 一般都是采用顺序存储的方法来表示数组
以行序为主序 将数组元素按行排列, 第 i+1 个行向量紧接在第 i 个行向量后面 以二维数组为例, 按 行序为主序 方式存储的线性序列为 : a 00,a 01,,a 0, n-1,a 10,a 11, a 1,n- 1,,a m-1,0,a m-1,1,,a m-1,n-1 在 PASCAL C 语言中, 数组就是按行优先顺序存储的
以列序为主序 将数组元素按列向量排列, 第 j+1 个列向量紧接在第 j 个列向量之后 前述二维数组的 m*n 个元素按 列序为主序 方式存储的线性序列为 : a 00,a 10,,a m-1,0,a 01,a 11, a m- 1,1,,a 0,n-1,a 1,n-1,,a m-1,n-1 在 FORTRAN 语言中, 数组就是按列优先顺序存储的
对于数组, 一旦规定了它的维数和各维的长度, 便可为之分配存储空间 反之, 只要给出一组下标便可以求得相应数组元素的存储位置
例如, 二维数组 A mn 按 行序为主序 方式存储在内存中, 假设每个元素占用 L 个存储单元 元素 a ij 的存储地址应是数组的基地址加上排在 a ij 前面的元素所占用的单元数 因为 a ij 位于第 i+1 行 第 j+1 列, 前面 i 行一共有 i n 个元素, 第 i 行上 a ij 前面又有 j 个元素, 故它前面一共有 i n +j 个元素, 因此,a ij 的地址计算函数为 : LOC(a ij )=LOC(a 00 )+(i*n+j)*l
在 C 语言中, 数组各维下标的下界是 0, 因此在 C 语言中, 二维数组的地址计算公式为 : LOC(a ij )=LOC(a 00 )+(i*b 2 +j)*l 其中 b 2 是数组第 2 维的长度 同样, 三维数组 A mnp 按 行序为主序 方式存储, 其地址计算函数为 : LOC(a ijk )=LOC(a 000 )+(i*n*p+j*p+k)*l
推至一般情况, LOC( j n 1 n 1, j2,..., jn) LOC(0,0,...,0) ( j i i 1 k i 1 b k j n )* L n LOC (0,0,...,0) i 1 c i j i 其中,c n =L, c i-1 = b i * c i, 1 < i n 容易看出, 数组元素的存储位置是其下标 (j i ) 的线性函数, 计算各元素存储位置的时间相等 因此, 存取数组中任一元素的时间相等, 我们称具有这一特点的存储结构为随机存储结构 (p93 描述 )
第五章数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 12
5.3 矩阵的压缩存储 在科学与工程计算问题中, 矩阵是一种常用的数学对象 在高级语言编制程序时, 一种简单而又自然的方法就是将一个矩阵描述为一个二维数组 矩阵在这种存储表示之下, 可以对其元素进行随机存取, 各种矩阵运算也非常简单, 并且存储的密度为 1
但是, 在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下, 看起来存储密度仍为 1, 但实际上占用了许多单元去存储重复的非零元素或零元素, 这对高阶矩阵会造成极大的浪费 为了节省存储空间, 我们可以对这类矩阵进行压缩存储 : 即为多个相同的非零元素只分配一个存储空间 ; 对零元素不分配空间
5.3.1 特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵 下面我们讨论几种特殊矩阵的压缩存储 对称矩阵在一个 n 阶方阵 A 中, 若元素满足下述性质 : a ij =a ji 0 i,j n-1 则称 A 为对称矩阵
对称矩阵中的元素关于主对角线对称, 故只要存储矩阵中上三角或下三角中的元素, 让每两个对称的元素共享一个存储空间即可 不失一般性, 我们按 行序为主序 方式存储主对角线 ( 包括对角线 ) 以下的元素, 其存储形式如图所示 : 1 5 1 3 7 a 00 5 0 8 0 0 a 10 a 11 1 8 9 2 6 a 20 a 21 a 22 3 0 2 5 1.. 7 0 6 1 3 a n-1 0 a n-1 1 a n-1 2 a n-1 n-1 图 5.1 对称矩阵
在这个下三角矩阵中, 元素总数为 n(n+1)/2 因此, 我们可以按 由上自下, 由左至右 的次序将这些元素存放在一个向量 sa[0..n(n+1)/2-1] 中 为了便于访问对称矩阵 A 中的元素, 我们必须在矩阵元 a ij 和 sa[k] 之间找一个对应关系 i(i 1) j 2 k j(j 1) i 2 当 i j 当 i<j 称 sa[n(n+1)/2] 为 n 阶对称矩阵 A 的压缩存储
三角矩阵 所谓下 ( 上 ) 三角矩阵是指矩阵的上 ( 下 ) 三角 ( 不包括对角线 ) 中的元均为常数或零的 n 阶矩阵 a 00 a 01 a 0 n-1 a 00 c c c a 11 a 1 n-1 a 10 a 11 c.... c c a n-1 n-1 a n-1 0 a n-1 1 a n-1 n-1 (a) 上三角矩阵 图 5.2 三角矩阵 (b) 下三角矩阵
三角矩阵中的重复元 c 可共享一个存储空间, 其余的元素正好有 n(n+1)/2 个 因此, 三角矩阵可压缩存储到向量 sa[0..n(n+1)/2] 中, 其中 c 存放在向量的最后一个分量中 上三角矩阵中, 如果按 行序为主序 方式存放上三角矩阵中的元素 a ij 时,sa[k] 和 a ij 的对应关系是 : k= i(2n-i+1)/2+j-i 当 i j n(n+1)/2 当 i>j 类似地, 下三角矩阵中,sa[k] 和 a ij 的对应关系是 : k= i(i+1)/2+j 当 i j n(n+1)/2 当 i<j
对角矩阵 对角矩阵中, 所有的非零元集中在以主对角线为中心的带状区域中, 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外, 其余元素皆为零 下图给出了一个三对角矩阵 : a 00 a 01 a 10 a 11 a 12 a 21 a 22 a 23.... 图 5.3 对角矩阵 a n-2 n-3 a n-2 n-2 a n-2 n-1 a n-1 n-2 a n-1 n-1 对角矩阵可按 行序为主序 方式或以对角线的顺序, 将其压缩存储到一个向量中, 并且也能找到每个非零元素和向量下标的对应关系
5.3.2 稀疏矩阵 简单说, 设矩阵 A 中有 s 个非零元素, 若 s 远远小于矩阵元素总数 ( 即 s<<m n), 则称 A 为稀疏矩阵 更精确地, 令 e=s/(m*n), 称 e 为矩阵的稀疏因子 通常认为 e 0.05 时称之为稀疏矩阵
在存储稀疏矩阵时, 为了节省存储单元, 很自然地想到使用压缩存储方法 但由于非零元素的分布一般是没有规律的, 因此在存储非零元素的同时, 还必须同时记下它所在的行和列的位置 (i,j) 反之, 一个三元组 (i, j, a ij ) 唯一确定了矩阵 A 的一个非零元 因此, 稀疏矩阵可由表示非零元的三元组及其行 列数唯一确定
例如, 下列三元组表 ( 注意 i,j 从 1 开始 ) ((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7)) 加上 (6, 7) 这一对行 列值便可作为下列矩阵 M 的另一种描述 而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法 0 12 9 0 0 0 0 0 0-3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0-3 0 0 0 0 14 0 9 0 0 24 0 0 M= T= 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 图 5.4 稀疏矩阵 M 和 T 0 0 0 0 0 0
三元组顺序表 假设以顺序存储结构来表示三元组表, 则可得到稀疏矩阵的一种压缩存储方法 三元组顺序表 #define maxsize 10000 typedef int datatype; typedef struct{ int i, j; datatype v; }triple; typedef struct{ // 非零元的行标和列标 triple data[maxsize]; // 非零元三元组表 int m,n,t; }tripletable; // 矩阵的行数 列数和非零元个数
设 M 为 tripletable 型的结构变量, 图 5.4 中所示的稀疏矩阵的三元组的表示如下 : i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 下面以矩阵的转置为例, 说明在这种压缩存储结构上如何实现矩阵的运算
一个 m n 的矩阵 M, 它的转置 T 是一个 n m 的矩阵, 且 a[i][j]=b[j][i],0 i m,0 j n, 即 M 的行是 T 的列,M 的列是 T 的行 ( 参见 p.98-99) 将 M 转置为 T, 就是将 M 的三元组表 a.data 置换为 T 的三元组表 b.data, 如果只是简单地交换 a.data 中 i 和 j 的内容, 那么得到的 b.data 将是一个按列优先顺序存储的稀疏矩阵 T, 要得到按 行序为主序 方式顺序存储的 b.data, 就必须重新排列三元组的顺序
i j v i j v 1 2 12 2 1 12 1 3 9 3 1 9 3 1-3 1 3-3 调换 i,j 3 6 14 6 3 14 4 3 24 3 4 24 5 2 18 2 5 18 6 1 15 1 6 15 6 4-7 4 6-7 a.data b.data ( 行序为主序 ) ( 列序为主序 )
由于 M 的列是 T 的行, 因此, 按 a.data 的列序转置, 所得到的转置矩阵 T 的三元组表 b.data 必定是按 行序为主序 方式存放的 按这种方法设计的算法, 其基本思想是 : 对 M 中的每一列 col(0 col n-1), 通过从头至尾扫描三元表 a.data, 找出所有列号等于 col 的那些三元组, 将它们的行号和列号互换后依次放入 b.data 中, 即可得到 T 的按 行序为主序 方式的压缩存储表示
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6-7 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 )
三元组顺序表虽然节省了存储空间, 但时间复杂度 (O(n*t)) 比一般矩阵转置的算法 (O(m*n)) 还要复杂, 同时还有可能增加算法的难度 因此, 此算法仅适用于 t m*n 的情况 ( 参见教材 p.99 算法 5.1)
下面给出另外一种称之为快速转置的算法, 其算法思想为 : 按照 a.data 中三元组的次序进行转置, 并将转置后的三元组置入 b 中恰当位置 如果能预先确定矩阵 M 中每一列的第一个非零元在 b.data 中应有的位置, 那么在对 a.data 中的三元组依次作转置时, 可以直接放到 b.data 中恰当位置上去 为了预先确定矩阵 M 中的每一列的第一个非零元素在数组 B 中应有的位置, 需要先求得矩阵 M 中的每一列中非零元素的个数
因为 : 矩阵 M 中第 i 列的第一个非零元素在数组 B 中应有的位置等于第 i-1 列第一个非零元素的位置加上第 i-1 列非零元素的个数 为此, 需要设置两个一维数组 num[0..n] 和 cpot[0..n] num[0..n]: 统计 M 中每列非零元素的个数,num[col] 的值可以由 M 的第二列 ( 即 j 列 ) 求得 cpot[0..n]: 由递推关系得出 M 中的每列第一个非零元素在 T 中的位置
算法通过 cpot 数组建立位置对应关系 : cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2 col a.n 例如 : 图 5.4 中的矩阵 M 和相应的三元组可以求得 num[col] 和 cpot[col] 的值如下 : col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 3 5 7 8 8 9 算法时间复杂度 O(n+t), 参见教材 p.100 算法 5.2
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 a.data ( 行序为主序 ) i j v 2 1 12 b.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 3 5 7 8 8 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 2 1 12 3 1 9 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 4 5 7 8 8 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 2 1 12 3 1 9 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 4 6 7 8 8 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 2 1 12 3 1 9 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 2 4 6 7 8 8 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 2 1 12 3 1 9 3 4 24 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 2 4 6 7 8 9 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 2 1 12 2 5 18 3 1 9 3 4 24 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 2 4 7 7 8 9 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 2 5 7 7 8 9 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6-7 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 3 5 7 7 8 9 9
i j v 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 i j v 1 3-3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6-7 6 3 14 b.data ( 行序为主序 ) a.data ( 行序为主序 ) col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 3 5 7 8 8 9 9
复习题 1. 数组 A[0..5,0..6] 的每个元素占 5 个单元, 将其按列优先次序存储在起始地址为 1000 的连续内存单元中, 则元素 a[5][5] 的地址为 A. 1175 B. 1180 C. 1205 D.1210 2. 对矩阵进行压缩存储是为了 B A. 方便运算 B. 节省存储空间 C. 方便存储 D. 提高运算速度 A 43
复习题 3. 一个 n 阶对称矩阵, 如果采用压缩存储方式, 则容量为 C A. n 2 B. n 2 /2 C. [(n+1)n]/2 D. [(n+1) 2 ]/2 4. 数组 A[1..10,-2..6,2..8] 以行优先顺序存储, 设第一个元素的首地址为 100, 每个数据元素占 3 个单元的存储空间, 则元素 A[5][0][7] 的存储地址为 913 44
复习题 5. 判断以下叙述的正确性 1) 用一维数组表示矩阵, 可以简化对矩阵的存取操作 ( ) 2) 对角矩阵的特点是非零元素只出现在矩阵的两条 ( ) 对角线上 3) 在 n(n>3) 阶三对角矩阵中, 每一行都有 3 个非零的元素 ( ) 4) 稀疏矩阵的特点是矩阵中的元素较少 ( ) 45