教育部—微软精品课程建设项目 以“行序为主序”的存储映象 例如: 00c01c0.2 00|ao|ao2|a10a1,1a12 a1ola11la 12 维数组A中任一元素a1;的存储位置 LOC(ij)=LOC(0,0)+(b2×i+j)×L 称为基地址或基址。 南京航空航天大学数据结构课题组版权所有
例如： 称为基地址或基址。 以“行序为主序”的存储映象 二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2×i＋j)× a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 L L
教育部—微软精品课程建设项目 推广到一般情况,可得到n维数组数据元 素存储位置的映象关系 LOCG1 323.Jn)=LOC(0,0,,0)+2 ji 其中cn=L,C1=b×C;,1<i≤n 称为n维数组的映象函数。数组元素 的存储位置是其下标的线性函数。 南京航空航天大学数据结构课题组版权所有
推广到一般情况，可得到 n 维数组数据元 素存储位置的映象关系 称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数。 其中 cn = L，ci-1 = bi ×ci , 1 < i n。 LOC(j1 , j2 , ..., jn ) = LOC(0,0,...,0) + ∑ ci j i i =1 n
教育部—微软精品课程建设项目 5.3稀疏矩阵的压缩存储 何谓稀疏矩阵? 假设m行n列的矩阵含t个非零元素, 则称 为稀疏因子。 通常认为δ≤0.05的矩阵为稀疏矩阵。 南京航空航天大学数据结构课题组版权所有
假设 m 行 n 列的矩阵含 t 个非零元素， 则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。 m n t = 5.3 稀疏矩阵的压缩存储 何谓稀疏矩阵？
教育部—微软精品课程建设项目 以常规方法,即以二维数组表示 高阶的稀疏矩阵时产生的问题: 1)零值元素占了很大空间; 2)计算中进行了很多和零值的运算, 遇除法,还需判别除数是否为零。 南京航空航天大学数据结构课题组版权所有
以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零
教育部—微软精品课程建设项目 解决问题的原则 1)尽可能少存或不存零值元素; 2)尽可能减少没有实际意义的运算; 3)操作方便。即 能尽可能快地找到与 下标值(i,j对应的元素 能尽可能快地找到同 行或同一列的非零值元。 南京航空航天大学数据结构课题组版权所有
1) 尽可能少存或不存零值元素； 解决问题的原则: 2) 尽可能减少没有实际意义的运算； 3) 操作方便。 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元