數(shù)據(jù)結(jié)構(gòu)課件-第5章 數(shù)組

第5章數(shù)組

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

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

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維的長(zhǎng)度基本操作:二維數(shù)組的定義:數(shù)據(jù)對(duì)象:

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和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A)

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

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

初始條件：

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

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

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序?yàn)橹餍虼娣臿mn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序?yàn)橹餍虼娣?1m-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

例如：

稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維數(shù)組A中任一元素ai,j

的存儲(chǔ)位置：

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

L

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

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

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

…

ad1,c2…ad1,d2

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

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

個(gè)字節(jié)。答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例2：設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

?！週OC(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個(gè)非零元素，則稱為稀疏因子。5.3稀疏矩陣的壓縮存儲(chǔ)1.何謂稀疏矩陣？

通常認(rèn)為

0.05的矩陣為稀疏矩陣。

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

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

對(duì)角矩陣所有的非0元素都分布在以對(duì)角線為中心的帶狀區(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

對(duì)角矩陣151375080018926302510613

對(duì)稱矩陣

以常規(guī)方法，即以二維數(shù)組表示高階的稀疏或特殊矩陣時(shí)產(chǎn)生的問(wèn)題:1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。3.稀疏矩陣的壓縮存儲(chǔ)方法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時(shí)可放在data[0]}TSMatrix;//稀疏矩陣類型如何表示稀疏矩陣M的第i個(gè)非零元素所在的列？2)三元組表示例6

7

8

121213931-3361443245218611564-7ijv01234567M6

7

8

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

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

鞏固練習(xí)2.設(shè)矩陣A是一個(gè)對(duì)稱矩陣(第一個(gè)元素為a1,1)，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對(duì)下三角部分中任一元素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]以行序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為

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

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

。

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

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