第5章數(shù)組

數(shù)組是一種特殊的線性表，表中的數(shù)據(jù)元素本身也是一個數(shù)據(jù)結(jié)構(gòu)。5.1數(shù)組的類型定義5.3稀疏矩陣的壓縮存儲5.2數(shù)組的順序表示和實現(xiàn)5.1數(shù)組的定義由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是向量的推廣。例如，二維數(shù)組：()()()()()()()()()可以看成是由一個行向量組成的向量，也可以看成是由一個列向量組成的向量。數(shù)組的類型定義ADTArray{

數(shù)據(jù)對象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

數(shù)據(jù)關(guān)系：

R＝{R1,R2,...,Rn}Ri＝{<aj1,...

ji,...jn

,aj1,...ji+1,...jn

>|0jkbk-1,1kn且ki,0ji

bi-2,i=2,...,n}

}ADTArray/n維數(shù)組。Bi：第i維的長度基本操作:二維數(shù)組的定義:數(shù)據(jù)對象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}數(shù)據(jù)關(guān)系:

R={ROW,COL}

ROW={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}

COL={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-2}//b1為行數(shù)；b2為列數(shù)基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作結(jié)果：若維數(shù)n和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A)

操作結(jié)果：銷毀數(shù)組A。Value(A,&e,index1,...,indexn)初始條件：

A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。操作結(jié)果：若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)

初始條件：

A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。5.2數(shù)組的順序表示和實現(xiàn)1.類型特點:1)只有引用型操作，沒有加工型操作；2)數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。2.有兩種順序映象的方式:1)以行序為主序(低下標(biāo)優(yōu)先)；2)以列序為主序(高下標(biāo)優(yōu)先)。由于計算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。(1)以行序為主序(2)以列序為主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序為主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序為主序存放01m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

例如：

稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j

的存儲位置：

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

3.計算二維數(shù)組元素地址的通式

二維數(shù)組列優(yōu)先存儲的通式為：

LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij

…

ad1,c2…ad1,d2

Amn=單個元素長度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長度aij本行前面的元素個數(shù)則行優(yōu)先存儲時的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。例1〖軟考題〗：一個二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是

個字節(jié)。答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例2：設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。∵LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L∴LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2

＝8950

假設(shè)m行n列的矩陣含t個非零元素，則稱為稀疏因子。5.3稀疏矩陣的壓縮存儲1.何謂稀疏矩陣？

通常認(rèn)為

0.05的矩陣為稀疏矩陣。

簡單說，設(shè)矩陣A中有t個非零元素，若t遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即t<<m×n），則稱A為稀疏矩陣。1)特殊矩陣

非零元在矩陣中的分布有一定規(guī)則。例如:三角矩陣矩陣的上（下）三角中的元素均為常數(shù)或0

對角矩陣所有的非0元素都分布在以對角線為中心的帶狀區(qū)域?qū)ΨQ矩陣aij＝aji2)隨機(jī)稀疏矩陣非零元在矩陣中隨機(jī)出現(xiàn)2.稀疏矩陣a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

上三角矩陣下三角矩陣

a00a01a10a11a12a21a22a23….…..….an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1

對角矩陣151375080018926302510613

對稱矩陣

以常規(guī)方法，即以二維數(shù)組表示高階的稀疏或特殊矩陣時產(chǎn)生的問題:1)零值元素占了很大空間;2)計算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。3.稀疏矩陣的壓縮存儲方法1)三元組順序表2)行邏輯聯(lián)接的順序表3)

十字鏈表

#defineMAXSIZE12500

typedefstruct{

inti,j;//該非零元的行下標(biāo)和列下標(biāo)

ElemTypev;//該非零元的值

}Triple;//三元組類型1)三元組順序表typedefunion{

Tripledata[MAXSIZE+1];//data[0]未使用

intmu,nu,tu;//當(dāng)ElemType為int時可放在data[0]}TSMatrix;//稀疏矩陣類型如何表示稀疏矩陣M的第i個非零元素所在的列？2)三元組表示例6

7

8

121213931-3361443245218611564-7ijv01234567M6

7

8

31-3611512125218139432464-73614ijv01234567M三元組表默認(rèn)行序1.了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法。小結(jié)2.掌握對特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式。3.了解稀疏矩陣的兩類壓縮存儲方法的特點和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行矩陣運(yùn)算采用的處理方法。1.假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為

。（無第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．A,B,C均不對

鞏固練習(xí)2.設(shè)矩陣A是一個對稱矩陣(第一個元素為a1,1)，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對下三角部分中任一元素ai,j,在一維數(shù)組B中下標(biāo)k的值為

。

Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j1.假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以行序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為

。（無第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．A,B,C均不對

強(qiáng)化練習(xí)2.設(shè)矩陣A是一個對稱矩陣(第一個元素為a1,1)，為了節(jié)省存儲，將其下三角部分按列序存放在一維數(shù)組B[1,n(n-1)/2]中，對下三角部分中任一元素ai,j,在一維數(shù)組B中下標(biāo)k的值為

。

A.(i+(i-j+1))×j/2B.無解

選擇：（程序員2005）設(shè)數(shù)組a[1..10,5..15]的元素以行為主序存放，每個元素占用4個存儲單元，則數(shù)組元素a[i,j](1≤i≤10,5≤j≤15)的地址計算公式為（）A.a-204+2i+jB.a-204+40i+4jC.a-84+i+jD.a-64+44i+4j選擇：（程序員2004）對于二維數(shù)組A[1..4,3..6]，設(shè)每個元素占兩個存儲單元，若分別以行和列為主序存儲，則元素A[3,4]相對于數(shù)組空間起始地址的偏移量分別是（）和（）A.12B.14C.16D.18－D－A選擇：（北京郵電1998）將一個A[1..100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1..298]中，A中元素A66,65（即元素下標(biāo)）在B中的位置K為（）A.198 B.195 C.197選擇：（武漢理工2002）三對角線矩陣A[1..n][1..n]以行序為主順序存儲，其存儲始址是B，每個元素占一個存儲單元，則元素A[i][j]的存儲起始地址為（）(1≤i,j≤n)A.b+2*j+i-2B.b+2*i+j-2C.b+2*j+i-3D.b+2*i+j-32006年11月試題55對于二維數(shù)組a[0…4,1…5]，設(shè)每個元素占1個存儲單元，且以列為主序存儲，則元素a[2,2]，相對于數(shù)組空間起始地址的偏移量是_(55)_A.5 B.7 C.10 D.15軟件設(shè)計師2010.5設(shè)有如下所示的下三角矩陣A[0..8,0..8]，將該三角矩陣的非零元素（即行下標(biāo)不小于列下標(biāo)的所有元素）按行優(yōu)先壓縮存儲在數(shù)組M[1..m]中，則元素A