數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組與廣義表-展示頁
2024-10-23 17:00本頁面
【正文】 typedef array1 array2[m]。 ? 在 C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說， typedef elemtype array2[m][n]。多維數(shù)組是向量的推廣。 ? 數(shù)組的的數(shù)據(jù)元素是數(shù)組；廣義表的數(shù)據(jù)元素可以是原子類型，也可以是廣義表，分別稱為廣義表的原子項和子表 數(shù)組和廣義表簡單描述 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 54 數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級語言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型?！? 數(shù)據(jù)結(jié)構(gòu) 》 課程 中國科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)學(xué)院 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組與廣義表 本章內(nèi)容 數(shù)組的定義 數(shù)組的順序表示和實現(xiàn) 矩陣的壓縮存儲 廣義表的定義 廣義表的存儲結(jié)構(gòu) 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 53 ? 數(shù)組和廣義表可看成是一種特殊的線性表。表中的元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。例如，二維數(shù)組： 數(shù)組的定義 Amn= a11 a12 … a 1n a21 a22 … a 2n … … … … am1 am2 … a mn 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 55 數(shù)組的定義 ? 二維數(shù)組 ? 二維數(shù)組可以看成是由若干個行向量組成的向量，也可以看成是若干個列向量組成的向量。 等價于： typedef elemtype array1[n]。 ? 多維數(shù)組： 用一維順序結(jié)構(gòu)線性表實現(xiàn)多維數(shù)組 struct Array { ElemType *buffer。 // 維數(shù) int *L。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 56 數(shù)組的順序表示和實現(xiàn) ? 設(shè)一 3維數(shù)組 A[4][2][3]，存貯在一個順序線性表 S中，結(jié)構(gòu)如下所示： A312 A311 A310 A302 A301 A300 A212 A211 A210 A202 A201 A200 A112 A111 A110 A102 A101 A100 A012 A011 A010 A002 A001 A000 A312 A311 A310 A302 A301 A300 A212 A211 A210 A202 A201 A200 A112 A111 A110 A102 A101 A100 A012 A011 A010 A002 A001 A000 0 1 2 3 4 5 6 7 ... 22 23 A000 A001 A002 A010 A011 A012 A100 A101 ... A311 A312 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 57 數(shù)組的順序表示和實現(xiàn) ? 兩種順序存儲方式： ? 行優(yōu)先順序 —— 將數(shù)組元素按行排列，第 i+1個行向量緊接在第i個行向量后面。在PASCAL、 C語言中，數(shù)組就是按行優(yōu)先順序存儲的。 ? 列優(yōu)先順序 —— 將數(shù)組元素按列向量排列，第 j+1個列向量緊接在第 j個列向量之后， A的 m*n個元素按列優(yōu)先順序存儲的線性序列為： a11,a21,…,a m1,a12,a22,…a m2,……,a n1,an2,…,a nm 。 列優(yōu)先順序推廣到多維數(shù)組，可規(guī)定為先排最左的下標(biāo)。 ? 元素 aij的存儲地址應(yīng)是數(shù)組的基地址加上排在 aij前面的元素所占用的單元數(shù)。 ? 矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為 1。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 511 矩陣的壓縮存儲 特殊矩陣 所謂 特殊矩陣 是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。如下圖是一個 5階對稱矩陣。不失一般性，我們按“行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如上圖示。 ? aij和 sa[k ]之間對應(yīng)關(guān)系 ? 若 i≧j ，則 ai j在下三角形中。因為 aij=aji，所以只要交換上述對應(yīng)關(guān)系式中的 i和 j即可得到： k=j*(j+1)/2+i 0≦ kn(n+1)/2 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 514 矩陣的壓縮存儲 ? aij的地址可用下列式子計算： LOC(aij ) = LOC(sa[k]) =LOC(sa[0])+k*L = LOC(sa[0]） +[I*(I+1)/2+J]*L 有了上述的下標(biāo)交換關(guān)系，對于任意給定一組下標(biāo) (i， j)，均可在 sa[k]中找到矩陣元素 aij，反之，對所有的 k=0,1,2,? ，n(n1)/21，都能確定 sa[k]中的元素在矩陣中的位置 (i,j)。下圖給出了一個三對角矩陣。顯然，當(dāng) ∣ ij∣1 時，元素aij=0。 ? 對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。 對這種矩陣，我們也可按行優(yōu)序為主
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1