第5章數組

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

數據對象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,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維數組。Bi：第i維的長度基本操作:二維數組的定義:數據對象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}數據關系:

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為行數；b2為列數基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作結果：若維數n和各維長度合法，則構造相應的數組A，并返回OK。DestroyArray(&A)

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

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

初始條件：

A是n維數組，e為元素變量，隨后是n個下標值。

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

例如：

稱為基地址或基址。以“行序為主序”的存儲映象二維數組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.計算二維數組元素地址的通式

二維數組列優先存儲的通式為：

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

…

ad1,c2…ad1,d2

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

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

個字節。答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例2：設數組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

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

通常認為

0.05的矩陣為稀疏矩陣。

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

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

對角矩陣所有的非0元素都分布在以對角線為中心的帶狀區域對稱矩陣aij＝aji2)隨機稀疏矩陣非零元在矩陣中隨機出現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

對稱矩陣

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

十字鏈表

#defineMAXSIZE12500

typedefstruct{

inti,j;//該非零元的行下標和列下標

ElemTypev;//該非零元的值

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

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

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

7

8

121213931-3361443245218611564-7ijv01234567M6

7

8

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

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

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

。

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

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

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

。

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

選擇：（程序員2005）設數組a[1..10,5..15]的元素以行為主序存放，每個元素占用4個存儲單元，則數組元素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）對于二維數組A[1..4,3..6]，設每個元素占兩個存儲單元，若分別以行和列為主序存儲，則元素A[3,4]相對于數組空間起始地址的偏移量分別是（）和（）A.12B.14C.16D.18－D－A選擇：（北京郵電1998）將一個A[1..100,1..100]的三對角矩陣，按行優先存入一維數組B[1..298]中，A中元素A66,65（即元素下標）在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對于二維數組a[0…4,1…5]，設每個元素占1個存儲單元，且以列為主序存儲，則元素a[2,2]，相對于數組空間起始地址的偏移量是_(55)_A.5 B.7 C.10 D.15軟件設計師2010.5設有如下所示的下三角矩陣A[0..8,0..8]，將該三角矩陣的非零元素（即行下標不小于列下標的所有元素）按行優先壓縮存儲在數組M[1..m]中，則元素A