~344特殊矩阵的压缩存储

本节内容特殊矩阵压缩存储研/CSKAOYAN知识总览研/CSKAOYAN一维数组的存储结构C语言定义一维数组内存a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]起始各数组元素大小相同，且物理上连续存放。数组元素a[i]

的存放地址

=LOC+i*sizeof(ElemType)

(0≤i<10)注：除非题目特别说明，否则数组下标默认从0开始

注意审题！！研/CSKAOYAN二维数组的存储结构C语言定义二维数组内逻辑视角行优先存存储内列优先存存储b[0][0]b[0][1]b[0][2]b[0][3]b[1][0]b[1][1]b[1][2]b[1][3]b[0][0]b[1][0]b[0][1]b[1][1]b[0][2]b[1][2]b[0][3]b[1][3]b[0][0]b[0][1]b[0][2]b[0][3]b[1][0]b[1][1]b[1][2]b[1][3]研/CSKAOYAN二维数组的存储结构C语言定义二维数组内逻辑视角行优先存存储b[0][0]b[0][1]b[0][2]b[0][3]b[1][0]b[1][1]b[1][2]b[1][3]b[0][0]b[0][1]b[0][2]b[0][3]b[1][0]b[1][1]b[1][2]b[1][3]M行N列的二维数组

b[M][N]

中，若按行优先存储，则起始b[i][j]

的存储地址

=LOC+(i*N+j)*sizeof(ElemType)研/CSKAOYAN二维数组的存储结构C语言定义二维数组内逻辑视角列优先存存储b[0][0]b[1][0]b[0][1]b[1][1]b[0][2]b[1][2]b[0][3]b[1][3]b[0][0]b[0][1]b[0][2]b[0][3]b[1][0]b[1][1]b[1][2]b[1][3]M行N列的二维数组

b[M][N]

中，若按列优先存储，则起始b[i][j]

的存储地址

=LOC+(j*M+i)*sizeof(ElemType)研/CSKAOYAN普通矩阵的存储a1,1a1,2a1,3······a1,n-1a1,na2,1a2,2a2,3······a2,n-1a2,n某些特殊矩阵可以压缩存储空间a3,1a3,2a3,3······a3,n-1a3,n······························am,1am,2am,3······am,n-1am,n可用二维数组存储注意：描述矩阵元素时，行、列号通常从

1

开始；而描述数组时通常下标从0开始（具体看题目给的条件，注意审题！）研/CSKAOYAN对称矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,n若

n

阶方阵中任意一个元素

ai,j

都有

ai,j

=aj,i则该矩阵为对称矩阵a2,1a2,2a2,3······a2,n-1a2,n普通存储：n*n

二维数组a3,1a3,2a3,3······a3,n-1a3,n压缩存储策略：只存储主对角线+下三角区······························（或主对角线+上三角区）an-1,1an-1,2an-1,3······an-1,n-1

an-1,n上三角区：i<jan,1an,2an,3······an,n-1an,n主对角线：i=j下三角区：i>j研/CSKAOYAN对称矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,n策略：只存储主对角线+下三角区按行优先原则将各元素存入一维数组中。a2,1a2,2a2,3······a2,n-1a2,nB[0]B[1]B[2]B[3]….B[?]a3,1a3,2a3,3······a3,n-1a3,n······························思考：an-1,1an-1,2an-1,3······an-1,n-1

an-1,n①数组大小应为多少?②站在程序员的角度，对称矩阵压an,1an,2an,3······an,n-1an,n缩存储后怎样才能方便使用？①

(1+n)*n/2a1,1a2,1a2,2a3,1……an,n-1an,n②可以实现一个“映射”函数矩阵下标à一维数组下标研/CSKAOYAN对称矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,n策略：只存储主对角线+下三角区按行优先原则将各元素存入一维数组中。a2,1a2,2a2,3······a2,n-1a2,nB[0]B[1]B[2]B[3]….𝒏(𝒏#𝟏)B[𝟐-1]a3,1a3,2a3,3······a3,n-1a3,n······························矩阵下标à

一维数组下标an-1,1an-1,2an-1,3······an-1,n-1

an-1,nai,j

（i≥j）àB[k]an,1an,2an,3······an,n-1an,nKey：按行优先的原则，ai,j

是第几个元素？[1+2+···+(i-1)]+jà

第'('())+j

个元素i≥j*'('())à

k=*+j−1a1,1a2,1a2,2a3,1……an,n-1an,n研/CSKAOYAN对称矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,n策略：只存储主对角线+下三角区按行优先原则将各元素存入一维数组中。a2,1a2,2a2,3······a2,n-1a2,ni<jB[0]B[1]B[2]B[3]….𝒏(𝒏#𝟏)B[𝟐-1]a3,1a3,2a3,3······a3,n-1a3,na1,1a2,1a2,2a3,1……an,n-1an,n····································矩阵下标à

一维数组下标an-1,1an-1,2an-1,3an-1,n-1

an-1,nai,j

（i<j）àB[k]an,1an,2an,3······an,n-1an,nai,j

=aj,i

（对称矩阵性质）à

k=+(+())+𝑖−1i≥j*研/CSKAOYAN对称矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,n策略：只存储主对角线+下三角区按行优先原则将各元素存入一维数组中。a2,1a2,2a2,3······a2,n-1a2,ni<jkB[0]B[1]B[2]B[3]….𝒏(𝒏#𝟏)B[𝟐-1]a3,1a3,2a3,3······a3,n-1a3,na1,1a2,1a2,2a3,1……an,n-1an,n····································矩阵下标à

一维数组下标an-1,1an-1,2an-1,3an-1,n-1

an-1,nai,jàB[k]ai,j

=aj,i

（对称矩阵性质）an,1an,2an,3······an,n-1an,nìïï=

íïïîii(-1)+j-1,i≥

(下三角区和主对角线元素)j2i≥jjj(-1)+

-i1,i<j(上三角区元素aij=aji)2研/CSKAOYAN对称矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,n策略：只存储主对角线+下三角区按列优先原则将各元素存入一维数组中。a2,1a2,2a2,3······a2,n-1a2,nB[0]B[1]B[2]B[3]….𝒏(𝒏#𝟏)B[𝟐-1]a3,1a3,2a3,3······a3,n-1a3,n····································矩阵下标à

一维数组下标ai,jàB[k]an-1,1an-1,2an-1,3an-1,n-1

an-1,nai,j

=aj,i

（对称矩阵性质）an,1an,2an,3······an,n-1an,na1,1a2,1a3,1a4,1……an,n-1an,n研/CSKAOYAN三角矩阵的压缩存储a1,1cc······cca1,1a1,2a1,3······a1,n-1a1,na2,1a2,2c······ccca2,2a2,3······a2,n-1a2,na3,1a3,2a3,3······cccca3,3······a3,n-1a3,n····························································an-1,1an-1,2an-1,3······an-1,n-1cccc······an-1,n-1

an-1,nan,1an,2an,3······an,n-1an,nccc······can,n下三角矩阵：除了主对角线和下三角区，其余的上三角矩阵：除了主对角线和上三角区，其余的元素都相同元素都相同研/CSKAOYAN三角矩阵的压缩存储a1,1cc······cck压缩存储策略：按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量ca2,1a2,2c······ccB[0]B[1]B[2]B[3]𝒏(𝒏#𝟏)….

B[𝟐𝒏(𝒏#𝟏)-1]

B[𝟐]a3,1a3,2a3,3······cc······························矩阵下标à

一维数组下标an-1,1an-1,2an-1,3······an-1,n-1cai,j

（i≥j）àB[k]Key：按行优先的原则，ai,j

是第几个元素？an,1an,2an,3······an,n-1an,nìïï=

íïïîii(-1)+j-1,i≥

(下三角区和主对角线元素)j2下三角矩阵：除了主对角线和下三角区，其余的nn(+1),i<j(上三角区元素)2元素都相同a1,1a2,1a2,2a3,1……an,nc研/CSKAOYAN三角矩阵的压缩存储a1,1a1,2a1,3······a1,n-1a1,nk压缩存储策略：按行优先原则将绿色区元素存入一维数组中。并在最后一个位置存储常量cca2,2a2,3······a2,n-1a2,nB[0]B[1]B[2]B[3]𝒏(𝒏#𝟏)….

B[𝟐𝒏(𝒏#𝟏)-1]

B[𝟐]cca3,3······a3,n-1a3,n······························矩阵下标à

一维数组下标ai,j

（i≤j）àB[k]ccc······an-1,n-1

an-1,nKey：按行优先的原则，ai,j

是第几个元素？ccc······can,nìïï=

íïïî(i-1)(2n-

+i2)+(j-i),i≤

(上三角区和主对角线元素)j2上三角矩阵：除了主对角线和上三角区，其余的nn(+1),i>j(下三角区元素)2元素都相同a1,1a1,2a1,3a1,4……an,nc研/CSKAOYAN三对角矩阵的压缩存储三对角矩阵，又称带状矩阵：a1,1a1,20······00当

|i-j|>1

时，有

ai,j

=0

（1≤i,j≤n）压缩存储策略：a2,1a2,2a2,3······00按行优先（或列优先）原则，只存储带状部分B[0]B[1]B[2]B[3]….B[3n-3]0a3,2a3,3······00······························矩阵下标à

一维数组下标000······an-1,n-1

an-1,nai,j

（|i-j|≤1）

àB[k]000······an,n-1an,nKey：按行优先的原则，ai,j

是第几个元素？前i-1行共

3(i-1)-1

个元素ai,j是

i

行第

j-i+2

个元素数组下标从0开始ai,j是第

2i+j-2

个元素à

k=2i+j-3a1,1a1,2a2,1a2,2……an,n-1an,n研/CSKAOYAN三对角矩阵的压缩存储a1,1a1,20······00若已知数组下标k，如何得到

i,j

？B[k]à

ai,ja2,1a2,2a2,3······00第

k+1

个元素，在第几行？第几列？0a3,2a3,3······00前i-1行共

3(i-1)-1

个元素前i行共

3i-1

个元素显然，

3(i-1)-1<k+1

≤

3i-1······························i

≥

(k+2)/3可以理解为“刚好”大于等于000······an-1,n-1

an-1,ni

=

(k+2)/3向上取整即可满足“刚好”大于等于000······an,n-1an,n的计算逻辑：

3(i-1)-1

≤

k<3i-1i

≤

(k+1)/3+1可以理解为“刚好”小于等于i

=

(k+1)/3+1向下取整即可满足“刚好”小于等于研/CSKAOYAN三对角矩阵的压缩存储a1,1a1,20······00若已知数组下标k，如何得到

i,j

？B[k]à

ai,ja2,1a2,2a2,3······00第

k+1

个元素，在第几行？第几列？0a3,2a3,3······00i

=

(k+2)/3或

i

=

(k+1)/3+1····································由k=2i+j-3，得j=k–2i+3000an-1,n-1

an-1,n000······an,n-1an,n研/CSKAOYAN三角矩阵的压缩存储a1,1cc······cck压缩存储策略：按行优先原则将绿色区元素存入一维数组中。并在最后一个位置存储常量ca2,1a2,2c······ccB[0]B[1]B[2]B[3]𝒏(𝒏#𝟏)….

B[𝟐𝒏(𝒏#𝟏)-1]

B[𝟐]a3,1a3,2a3,3······cc······························矩阵下标à

一维数组下标an-1,1an-1,2an-1,3····