數(shù)據(jù)結(jié)構(gòu)數(shù)組

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 數(shù)組4.1 4.1 數(shù)組的定義數(shù)組的定義數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級(jí)語言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單4.1 4.1 數(shù)組的定義數(shù)組的定義多維數(shù)組是向量的推廣。例如，二維數(shù)組： a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1 amn=可以看成是由m個(gè)行向量組成的向量，也可以看成是n個(gè)列向量組成的向量。4.1 4.1 數(shù)組的定義數(shù)組的定義4.2 4.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn) 由于計(jì)

2、算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。 又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法來表示數(shù)組。 4.2 4.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)行優(yōu)先順序?qū)?shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為： 列優(yōu)先順序?qū)?shù)組元素按列向量排列，第j+1個(gè)列向量緊接在第j個(gè)列向量之后，按列優(yōu)先順序存儲(chǔ)的線性序列為：a0,1a0,0a0,2a1,0a1,1

3、a1,2a0,1a0,0a0,2a1,0a1,1a1,2da1,0a0,0a2,0a2,1a0,1a1,1a1,0a0,0a2,0a0,1a1,1a2,1d 例如，二維數(shù)組amn按“行優(yōu)先順序”存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用d個(gè)存儲(chǔ)單元。 元素aij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因?yàn)閍ij位于第i行、第j列，前面i-1行一共有in個(gè)元素，第i行上aij前面又有j個(gè)元素，故它前面一共有(in+j）個(gè)元素，因此，aij的地址計(jì)算函數(shù)為： loc(aloc(aijij)=loc(a)=loc(a0000)+i)+i* *n+jn+j* *d (0imd (0im，

4、 0jn)0jn)注：注：c c語言中數(shù)組元素采用行主序的存放方法，即語言中數(shù)組元素采用行主序的存放方法，即行優(yōu)先行優(yōu)先順序。順序。一個(gè)一個(gè)mn的二維數(shù)組可以的二維數(shù)組可以看成是看成是m行的一維數(shù)組，或行的一維數(shù)組，或者者n列的一維數(shù)組。列的一維數(shù)組。 a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 amn=4.2 4.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)4.2 4.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn) 同樣，三維數(shù)組aijk按“行優(yōu)先順序”存儲(chǔ)，其地址計(jì)算函數(shù)為：loc(aijk)=loc(a000)+inp+

5、jp+kd注：只要知道以下三要素便可隨時(shí)求出任一元素的地址（意義：數(shù)組中的注：只要知道以下三要素便可隨時(shí)求出任一元素的地址（意義：數(shù)組中的任一元素可隨機(jī)存?。┤我辉乜呻S機(jī)存?。╅_始結(jié)點(diǎn)的存放地址（即基地址）；開始結(jié)點(diǎn)的存放地址（即基地址）；維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)每個(gè)數(shù)組元素所占用的單元數(shù)例：一個(gè)二維數(shù)組例：一個(gè)二維數(shù)組a a，行下標(biāo)的范圍是，行下標(biāo)的范圍是1 1到到6 6，列下標(biāo)的范圍是，列下標(biāo)的范圍是0 0到到7 7，每個(gè)數(shù)，每個(gè)數(shù)組元素用相鄰的組元素用相鄰的6 6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編

6、址。那么，這個(gè)數(shù)組的體積是 多少個(gè)字節(jié)。多少個(gè)字節(jié)。答：答： volume=mvolume=m* *n n* *l=(6-1+1)l=(6-1+1)* *(7- 0 +1)(7- 0 +1)* *6=486=48* *6=2886=288例例 設(shè)數(shù)組設(shè)數(shù)組aa60, 60, 7070的基地址為的基地址為20482048，每個(gè)元素占，每個(gè)元素占2 2個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58a32,58的存儲(chǔ)地址？的存儲(chǔ)地址？答：根據(jù)行優(yōu)先公式答：根據(jù)行優(yōu)先公式 loc(aij)=loc(a00)+(iloc(aij)=loc(a00)+(i

7、* *n+j)n+j)* *k (0k (0i im，0 0j jn)n)得：得：loc(a32,58)=2048+(32loc(a32,58)=2048+(32* *70+58)70+58)* *2 2664466445.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。 5.3.1 特殊矩陣特殊矩陣5.3.2 稀疏矩陣稀疏矩陣5.3.1 5.3.1 特殊矩陣特殊矩陣5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)1 1、對(duì)

8、稱矩陣、對(duì)稱矩陣 在一個(gè)在一個(gè)n n階方陣階方陣a a中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： a aijij=a=ajiji （0i,jn-10i,jn-1） 則稱則稱a a為對(duì)稱矩陣。如圖為對(duì)稱矩陣。如圖5.15.1便是一個(gè)便是一個(gè)5 5階對(duì)稱矩陣。階對(duì)稱矩陣。 5.3.1 5.3.1 特殊矩陣特殊矩陣5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空

9、間。不失一般性，我們空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示：其存儲(chǔ)形式如圖所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 . 7 0 6 1 3 an-1 0 an-1 1 an-1 n-1 圖 5.1 對(duì)稱矩陣若ij，則ai j在下三角形中。 ai j之前的i行（從第0行到第i-1行）一共有1+2+i = i(i+1)/2個(gè)元素，在第i行上， ai j之前恰有j個(gè)元素（即

10、ai0, ai1, ai2, aij-1），因此有： k=i(i+1)/2+j 0kn(n+1)/2 若ij，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到： k=j(j+1)/2+i 0 kn(n+1)/2 令 i=max(i,j)， j=min(i,j)，則k和 i, j的對(duì)應(yīng)關(guān)系可統(tǒng)一為： k=i(i+1)/2+j 0 k1時(shí)，元素aij=0。 由此可知，一個(gè)k對(duì)角矩陣(k為奇數(shù))a是滿足下述條件的矩陣： 若i-j(k-1)/2 ， 則元素 aij=0。 對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和

11、向量下標(biāo)的對(duì)應(yīng)關(guān)系。 5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ) 對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺泶鎯?chǔ)。除第0行和第n-1行是2個(gè)元素外，每行的非零元素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1k=0 1 2 3 4 5 3n-2 3n-1 數(shù)組sa中的元素sak與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3i-1個(gè)非零元素，在第i行，有j-i+1個(gè)非零元素，這樣，非零元素aij的地址為： 5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ) loc(i,j) = loc(0,0)+3i-

12、1+(j-i+1)d = loc(0,0)+(2i+j)d 上例中，a34對(duì)應(yīng)著 a21對(duì)應(yīng)著 sa10k=2i+j=23+4=10sa5k=22+1=5由此，我們稱sa0.3n-1是n階三對(duì)角陣的壓縮存儲(chǔ)表示。5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)5.3.2 5.3.2 稀疏矩陣稀疏矩陣5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)5.3.2 5.3.2 稀疏矩陣稀疏矩陣三元組順序表三元組順序表行邏輯鏈接順序表行邏輯鏈接順序表十字鏈表十字鏈表5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)1 1、三元組順序表、三元組順序表5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)1 1、三元組順序表、三元組順序表5.3 5.3 數(shù)組的壓縮存儲(chǔ)數(shù)組的壓縮存儲(chǔ)1 1、三元組順序表、三元組順序表(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 6, 14)(4, 3, 24)(5, 2, 18)(