數(shù)組和矩陣的壓縮存儲

第四章串、數(shù)組和廣義表——數(shù)組與矩陣的存儲方式1/13/2023數(shù)組可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結構其特點是結構中的元素本身可以是具有某種結構的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。4.5數(shù)組1/13/2023數(shù)數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標來標識，因此，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1)取值操作：給定一組下標，讀其對應的數(shù)據(jù)元素(2)賦值操作：給定一組下標，存儲或修改與其相對應的數(shù)據(jù)元素4.5數(shù)組1/13/2023一維數(shù)組一維數(shù)組的示例1/13/2023一維數(shù)組的特點連續(xù)存儲的線性聚集（別名向量）除第一個元素外，其他每一個元素有一個且僅有一個直接前驅。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。1/13/2023二維數(shù)組的定義a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….數(shù)組中的每一個元素由一個值和一組下標來描述二維數(shù)組1/13/2023a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,ai2,……..,ain)(1<=i<=m)——行向量數(shù)組是線性表的推廣二維數(shù)組的表示方法1/13/2023?i=(?1i,

?2i,

……..

,

?mi)(1<=i<=n)——列向量注意：數(shù)組的運算主要是存取元素、修改相應的元素。?1a11a21……am1?2a12a22……am2?na1na2n……amn…………………………二維數(shù)組的表示方法1/13/2023

二維數(shù)組三維數(shù)組行向量下標

i頁向量下標i列向量下標

j行向量下標j

列向量下標

k1/13/2023（1）

按行優(yōu)先順序存放（2）

按列優(yōu)先順序存放數(shù)組的順序存儲結構1/13/2023amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a11

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….loc(aij)=loc(a11)+[(i-1)×n+(j-1)]×SS為每個元素的存儲大小

按行優(yōu)先順序存放1/13/2023amn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22

……..

a2n

am1

am2

……..

amn

….loc(aij)=loc(a11)+[(j-1)×m+(i-1)]×S

S為每個元素的大小

按列優(yōu)先順序存放1/13/20231、給定整型數(shù)組M[3][5],M按行優(yōu)先次序存儲，起始地址M[0][0]的存儲地址為1000，則元素M[2][2]的地址為

。 A）1022 B）1000 C）1024 D）1124CM[0][0]M[0][1]M[0][2]M[0][3]M[0][4]M[1][0]M[1][1]M[1][2]M[1][3]M[1][4]M[2][0]M[2][1]M[2][2]M[2][3]M[2][4]1/13/2023

所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。例如對稱矩陣，三角矩陣，對角線矩陣等特殊矩陣的壓縮存儲1/13/20231、

特殊矩陣（1）

對稱矩陣（2）

三角矩陣（3）

對角線矩陣2、

稀疏矩陣（1）

順序存儲結構——三元組表示法（2）

順序存儲結構稀疏矩陣的轉置運算矩陣的壓縮存儲1/13/2023在一個n階方陣A中，若元素滿足下述性質：aij=aji0≦i,j≦n-1則稱A為對稱矩陣。對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間。這樣，能節(jié)約近一半的存儲空間。不失一般性，我們按“行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示：對稱矩陣1/13/202315137a0050800a10a1118926a20a21a2230251………………..70613an-10an-11an-12…an-1n-1

對稱矩陣第i行恰有i+1個元素，元素總數(shù)為：

n(n+1)/2

因此，我們可以按圖中箭頭所指的次序將這些元素存放在一個向量sa[0..n(n+1)/2-1]中。1/13/2023為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個對應關系。若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的對應關系可統(tǒng)一為：

k=I*(I+1)/2+J0≦k<n(n+1)/2

1/13/2023因此，aij的地址可用下列式計算：

LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*s=LOC(sa[0])+[I*(I+1)/2+J]*s有了上述的下標交換關系，對于任意給定一組下標(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=4a00a10a11a20……an-10……an-1,n-11/13/2023三角矩陣以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣1/13/2023三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中。三角矩陣的存儲1/13/2023

上三角矩陣中，主對角線之上的第p行(0≦p<n)恰有n-p個元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時，aij之前的i行一共有n+n-1+n-2+n-3+…+n-(i-1)=i(2n-i+1)/2個元素，在第i行上，aij前恰好有j-i個元素：aij,aij+1,…aij-1。三角矩陣的存儲1/13/2023因此，sa[k]和aij的對應關系是：i(2n-i+1)/2+j-i當I〈=jn(n+1)/2當i>j下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關系是：i(i+1)/2+ji>=jn(n+1)/2i<j

k=k=1/13/2023

a11

00

……..0

a21a220

……..0

an1an2an3…….ann

…0A=按行優(yōu)先存放{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}

loc(aij)=loc(a11)+[(+(j-1)]×S

i(i-1)2前i-1行非零元素個數(shù)∑R=

i(i-1)2i-1R=1

下三角

ai1ai2ai3

..

aij

...0…01/13/2023

a11

a120

…………..0

a21a22

a23

0

………...00

0

……an-1,n-2an-1,n-1an-1,n………..A=

0

a32a33

a34

0

…..00

0

…………….an,n-1ann.按行優(yōu)先存放{a11,

a12,

a21,

a22,

a23,a32,a34,

…an,n-1,

ann}

loc(aij)=loc(a11)+[2×(i-1)+(j-1)]×S

三對角陣1/13/2023稀疏矩陣什么是稀疏矩陣？簡單說，設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s≦m×n），則稱A為稀疏矩陣。精確點，設在的矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e<=0.05時稱之為稀疏矩陣。1/13/2023

在存儲稀疏矩陣時，為了節(jié)省存儲單元，很自然地想到使用壓縮存儲方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。1/13/2023

7000150

0-40000

-2000021000-100M=2164-214-143-4221551711列行值664稀疏矩陣的壓縮存儲——三元組1/13/2023

7000150

0-40000

-2000021