數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組與廣義表(已修改)
2024-10-27 17:00 本頁(yè)面
【正文】 《 數(shù)據(jù)結(jié)構(gòu) 》 課程 中國(guó)科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)學(xué)院 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組與廣義表 本章內(nèi)容 數(shù)組的定義 數(shù)組的順序表示和實(shí)現(xiàn) 矩陣的壓縮存儲(chǔ) 廣義表的定義 廣義表的存儲(chǔ)結(jié)構(gòu) 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 53 ? 數(shù)組和廣義表可看成是一種特殊的線性表。表中的元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。 ? 數(shù)組的的數(shù)據(jù)元素是數(shù)組；廣義表的數(shù)據(jù)元素可以是原子類型，也可以是廣義表，分別稱為廣義表的原子項(xiàng)和子表 數(shù)組和廣義表簡(jiǎn)單描述 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 54 數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級(jí)語(yǔ)言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。多維數(shù)組是向量的推廣。例如，二維數(shù)組： 數(shù)組的定義 Amn= a11 a12 … a 1n a21 a22 … a 2n … … … … am1 am2 … a mn 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 55 數(shù)組的定義 ? 二維數(shù)組 ? 二維數(shù)組可以看成是由若干個(gè)行向量組成的向量，也可以看成是若干個(gè)列向量組成的向量。 ? 在 C語(yǔ)言中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說， typedef elemtype array2[m][n]。 等價(jià)于： typedef elemtype array1[n]。 typedef array1 array2[m]。 ? 多維數(shù)組： 用一維順序結(jié)構(gòu)線性表實(shí)現(xiàn)多維數(shù)組 struct Array { ElemType *buffer。 // 數(shù)據(jù)區(qū) int dims。 // 維數(shù) int *L。 // 各維長(zhǎng)度 }。 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 56 數(shù)組的順序表示和實(shí)現(xiàn) ? 設(shè)一 3維數(shù)組 A[4][2][3]，存貯在一個(gè)順序線性表 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 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 57 數(shù)組的順序表示和實(shí)現(xiàn) ? 兩種順序存儲(chǔ)方式： ? 行優(yōu)先順序 —— 將數(shù)組元素按行排列，第 i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為： a11,a12,…,a 1n,a21,a22,…a 2n,……,a m1,am2,…,a mn。在PASCAL、 C語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。 行優(yōu)先順序推廣到多維數(shù)組，可規(guī)定為先排最右的下標(biāo)。 ? 列優(yōu)先順序 —— 將數(shù)組元素按列向量排列，第 j+1個(gè)列向量緊接在第 j個(gè)列向量之后， A的 m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為： a11,a21,…,a m1,a12,a22,…a m2,……,a n1,an2,…,a nm 。在FORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。 列優(yōu)先順序推廣到多維數(shù)組，可規(guī)定為先排最左的下標(biāo)。 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 58 數(shù)組的順序表示和實(shí)現(xiàn) ? 二維數(shù)組元素的存取 ? 二維數(shù)組 Amn按“行優(yōu)先順序”存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用 L個(gè)存儲(chǔ)單元。 ? 元素 aij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在 aij前面的元素所占用的單元數(shù)。因?yàn)?aij位于第 i行、第 j列，前面 i1 行一共有(i1) n 個(gè)元素，第 i行上 aij前面又有 j1個(gè)元素，故它前面一共有 (i1) n+j1個(gè)元素，因此， aij的地址計(jì)算函數(shù)為： LOC(aij) = LOC(a11)+[(i1)*n+j1]*L 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 59 數(shù)組的順序表示和實(shí)現(xiàn) ? 例：二維數(shù)組 A[c1..d1,c2..d2]的存取 ? 分析： aij前一共有 ic1行，二維數(shù)組一共有 d2c2+1列，故這 ic1行共有 (ic1)*(d2c2+1)個(gè)元素，第 i行上 aij前一共有 jc2個(gè)元素，因此， aij的地址計(jì)算函數(shù)為： LOC(aij) = LOC(ac1c2)+[(ic1)*(d2c2+1)+jc2)]*L ? 在 C語(yǔ)言中，數(shù)組各維下標(biāo)的下界是 0，因此二維數(shù)組 Am?n的地址計(jì)算公式為： LOC(aij) = LOC(a00)+(i*n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1