数据结构——串、数组和广义表.ppt

行向量的一维数组 列向量的一维数组 二维数组 以行序为主序 C, PASCAL 4.2.2 数组的顺序存储 以列序为主序 FORTRAN 4.2.2 数组的顺序存储  a[n][m] 设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k 二维数组的行序优先表示 4.2.2 数组的顺序存储 设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中 ∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692. 练习 设有二维数组A[10,20]，其每个元素占两个字节， A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优先顺序存储，元素A[6,6]的存储地址为 。 352 232 (6*20+6)*2+100=352 (6*10+6)*2+100=232 练习 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。 2. 什么样的矩阵能够压缩？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。 3. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%） 4.2.3 特殊矩阵的压缩存储 对称矩阵: aij = aji (1=i,j=n) 下三角矩阵: 当ij时, aij = 0或常数c, (1=i,j=n) 对角矩阵: 当|i-j| 1时, aij = 0, (1=i,j=n) a11 a12 a13 ... a1n a21 a22 a23 ... a2n a31 a32 a33 ... a3n ...... an1 an2 an3 ... ann Anxn = 特殊矩阵 存储元素数: 1+2+...+n = n(n+1)/2 一维数组Sa[0..n(n+1)/2-1]作为数组A下三角元素的 存储结构: Sa[k] = [a11, a21, a22, a31, ... , an1, ... , ann] k = 0 1 2 3 n(n-1)/2 n(n+1)/2-1 Sa[k]和A[i, j]的一一对应关系: i(i-1)/2 + j -1 当 i = j k = j(j-1)/2 + i -1 当 i j 对称矩阵 n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15 一维数组Sa[0..14]作为数组A的存储结构: Sa=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5) 如: a[5,3] = a[3,5] = 7 k = 5(5-1)/2 + 3-1 = 12 故:Sa[12] = 7 4 5 3 2 1 5 2 1 5 6 3 1 3 2 7 2 5 2 8 9 1 6 7 9 5 A = 4 5 2 0 3 1 3 2 5 2 8 1 6 7 9 5 A = 对称矩阵 当ij时, aij = 0或常数c, (1=i, j=n) 同样，用一维数组Sa[0..n(n+1)/2-1]作为数组A非零元素的存储结构: sa[k]和a[i, j]的一一对应关系: Sa[k], k = i(i-1)/2 + j-1 (当 i = j) a[i, j] = n(n+1)/2 (当 i j) 下三角矩阵 4 0 0 0 0 5 2 0 0 0 A =