数据结构与算法设计PPT (14).pdf

《数据结构与算法设计PPT (14).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (14).pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 字符串和数组3.4 特殊矩阵矩阵:一个m行n列的矩阵是一平面阵列,有mn个元素操作：可以对矩阵作加、减、乘等运算。存在的问题：矩阵中存在大量零元或者值相同的元素，节约存储空间压缩的方法：零元不存储，多个值相同的只存一个压缩存储的对象：稀疏矩阵特殊矩阵矩阵值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例:对称矩阵、上（下）三角矩阵都是特殊矩阵a00 a01 a02 a0n1a10 a11 a12 a1n1an-10an-11an-1n-1a00 a01 a0n-10 a11 a1n-10 0 0 an-1n-1特殊矩阵对称矩阵是满足下面条件的n 阶矩阵:aij=aji1 i,j n

2、a00 a10 an-10a10 a11 an-11an-10an-11an-1n-1对称矩阵元素可以只存储下三角部分，共需 n(n+1)/2 个单元的空间(三角矩阵的存储方式类似）a00 a10 a11 a20 a21 a22 an-10an-11an-1n-1a00a10a11a20a21 a22an-10 an-11an-1n-1k=0 1 2 3 4 5 6 n(n+1)/2-1 对称矩阵的存储压缩k=i(i+1)/2 +j 当 i jj(j+1)/2 +i当 i j以一维数组sa0.n(n+1)/2-1作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sak之间关系：a0

3、0a10a11a20a21 a22an10 an11an1n1k=0 1 2 3 4 5 6 n(n+1)/2-1例如：a42 在 sa 中的存储位置是：k=4*(4+1)/2+2=12sa12=a42aij前面有i行，i（i+1）/2本行前面有j个元素对称矩阵是满足下面条件的n 阶矩阵:aij=01 ij na00 a10 a11 Can-10an-11an-1n-1对称矩阵元素可以只存储下三角部分，共需 n(n+1)/2 个单元的空间(三角矩阵的存储方式类似）a00 a10 a11 0 a20 a21 a22 an-10an-11an-1n-1a00a10a11a20a21 a22an-1

4、0 an-11an-1n-1k=0 1 2 3 4 5 6 n(n+1)/2-1 下三角矩阵存储压缩k=i(i+1)/2 +j 当 i j返回0 当 i j以一维数组sa0.n(n+1)/2-1作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sak之间关系：a00a10a11a20a21 a22an10 an11an1n1k=0 1 2 3 4 5 6 n(n+1)/2-1aij前面有i行，i（i+1）/2本行前面有j个元素对称矩阵是满足下面条件的n 阶矩阵:aij=01 i j以一维数组sa0.n(n+1)/2-1作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置s

5、ak之间关系：例如：一个5*5的矩阵a24 在 sa 中的存储位置是：k=(2*5-2+1)*2/2+4-2=11sa11=a24aij前面有i行，前i行元素个数!#%=(+)()/本行前面有j-i个元素带状矩阵带状矩阵所有非所有非0元素都集元素都集中在以主对角线为中在以主对角线为中心的带状区域，中心的带状区域，半带宽为半带宽为d时时,非非0元素有元素有(2d+1)*n-(1+d)*d个个a00 a11 a02000 0 00 0 0 0a10 a11 a12 a13000 0 00 0 0a20 a21 a22 a23 a240 0 00 0 0 00 a31 a32 a33 a34 a35

6、0 00 0 0 000 a42 a43 a43 a45 a4600 0 0 000 0 a53 a54 a55 a56 a570 0 0 000 0 0a64 a65 a66 a67 a680 0 0 0 0 000 a75 a76 a77 a78 a790 00 0 000 0 a86 a87 a88 a89 a81000 00 00 00 a97a98 a99 a910 a9110 00 00 000 a108 a109 a1010 a10110 00 00 0000 a119 a1110 a1111d0 a00a01a10a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 0K=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14a00 a01 000a10 a11 a12 0 00a21 a22 a23 000 a32 a33 a34000 a43 a44为计算方便，认为每一行都有2d+1个非0元素，若少则用0补足存放矩阵的数组sa 有:n(2d+1)个元素数组元素sak与矩阵元素aij之间有关系:k=i*(2d+1)+d+(j-i)a00前为何放一个0？d=2,n=6的带状矩阵如何存储呢？本例：d=1