數(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ù)類型，在早期的高級語言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標一般具有固定的上界和下界，因此，數(shù)組的處理比其它復雜的結(jié)構(gòu)更為簡單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個行向量組成的向量，也可以看成是n個列向量組成的向量。4.1 4.1 數(shù)組的定義數(shù)組的定義4.2 4.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 由于計

2、算機的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。 又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。 4.2 4.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)行優(yōu)先順序?qū)?shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為： 列優(yōu)先順序?qū)?shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，按列優(yōu)先順序存儲的線性序列為：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)先順序”存儲在內(nèi)存中，假設(shè)每個元素占用d個存儲單元。 元素aij的存儲地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因為aij位于第i行、第j列，前面i-1行一共有in個元素，第i行上aij前面又有j個元素，故它前面一共有(in+j）個元素，因此，aij的地址計算函數(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)先順序。順序。一個一個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ù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)4.2 4.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 同樣，三維數(shù)組aijk按“行優(yōu)先順序”存儲，其地址計算函數(shù)為：loc(aijk)=loc(a000)+inp+

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

6、址。那么，這個數(shù)組的體積是 多少個字節(jié)。多少個字節(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，每個元素占，每個元素占2 2個存儲單元，個存儲單元，若以行序為主序順序存儲，則元素若以行序為主序順序存儲，則元素a32,58a32,58的存儲地址？的存儲地址？答：根據(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ù)組的壓縮存儲數(shù)組的壓縮存儲所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。陣，下面我們討論幾種特殊矩陣的壓縮存儲。 5.3.1 特殊矩陣特殊矩陣5.3.2 稀疏矩陣稀疏矩陣5.3.1 5.3.1 特殊矩陣特殊矩陣5.3 5.3 數(shù)組的壓縮存儲數(shù)組的壓縮存儲1 1、對

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

9、間。不失一般性，我們空間，這樣，能節(jié)約近一半的存儲空間。不失一般性，我們按按“行優(yōu)先順序行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示：其存儲形式如圖所示： 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 對稱矩陣若ij，則ai j在下三角形中。 ai j之前的i行（從第0行到第i-1行）一共有1+2+i = i(i+1)/2個元素，在第i行上， ai j之前恰有j個元素（即

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

11、向量下標的對應(yīng)關(guān)系。 5.3 5.3 數(shù)組的壓縮存儲數(shù)組的壓縮存儲 對這種矩陣，我們也可按行優(yōu)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(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與三對角帶狀矩陣中的元素aij存在一一對應(yīng)關(guān)系，在aij之前有i行,共有3i-1個非零元素，在第i行，有j-i+1個非零元素，這樣，非零元素aij的地址為： 5.3 5.3 數(shù)組的壓縮存儲數(shù)組的壓縮存儲 loc(i,j) = loc(0,0)+3i-

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