数据结构数组ppt课件.ppt

数据结构数组4.1数组的定义4.1数组的定义4.1数组的定义4.2数组的顺序表示和实现5.3数组的压缩存储5.3数组的压缩存储5.3数组的压缩存储若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+I=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：
k=i(i+1)/2+j0≦k<n(n+1)/2
若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：
k=j(j+1)/2+i0≦k<n(n+1)/2
令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为：
k=I(I+1)/2+J0≦k<n(n+1)/2
因此，aij的地址可用下列式计算：
LOC(aij)=LOC(sa[k])
=LOC(sa[0])+k×d=LOC(sa[0])+[I(I+1)/2+J]d
有了上述的下标交换关系，对于任意给定一组下标
(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有
的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，见下图：

k=0123n(n-1)/2n(n-1)/2-1
例如a21和a12均存储在sa[4]中，这是因为
k=I(I+1)/2+J=2(2+1)/2+1=4
5.3数组的压缩存储非零元素仅出现在主对角(aii,0≦i≦n-1上，以及紧邻主对角线上面的那条对角线上(aii+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上(ai+1i,0≦i≦n-2)。显然，当∣i-j∣>1时，元素aij=0。
由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：
若∣i-j∣>(k-1)/2，
则元素aij=0。
对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。

对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。
LOC(i,j)=LOC(0,0)+[3i-1+(j-i+1)]d
=LOC(0,0)+(2i+j)d

上例中，a34对应着

a21对应着

5.3数组的压缩存储5.3数组的压缩存储5.3数组的压缩存储5.3数组的压缩存储5.3数组的压缩存储5.3数组的压缩存储5.3数组的压缩存储