數(shù)據(jù)結(jié)構(gòu)：第5章 - 數(shù)組和廣義表（2課時(shí)）

1、數(shù)據(jù)結(jié)構(gòu),2013年11月,第五章 數(shù)組和廣義表,Page 2,5.1 數(shù)組 5.2 矩陣的壓縮存儲(chǔ) 5.3 廣義表,內(nèi)容 設(shè)置,Page 3,5.1 數(shù)組,定義,一維數(shù)組：具有相同類(lèi)型的一組元素的有限序列。 二維數(shù)組：元素為一維數(shù)組的一維數(shù)組。 N維數(shù)組是元素為（N-1）維數(shù)組的一維數(shù)組。 數(shù)組是一個(gè)靜態(tài)變量，無(wú)插入、刪除運(yùn)算。 常見(jiàn)運(yùn)算：計(jì)算元素地址、存取元素的值。 數(shù)組也是一種特殊的線性表（長(zhǎng)度固定）。 二維數(shù)組中每個(gè)元素aij均屬于兩個(gè)向量：行、列向量，除邊界外,每個(gè)元素有兩個(gè)直接前趨和兩個(gè)直接后繼。同樣，三維數(shù)組中每個(gè)元素amnt均屬于三個(gè)向量，除邊界外,每個(gè)元素有三個(gè)直接前趨和三個(gè)

2、直接后繼。依次類(lèi)推，m維數(shù)組an1n2nm屬于m個(gè)向量，有m個(gè)直接前趨和m個(gè)直接后繼。(從這一點(diǎn)看，數(shù)組又不是一種線性表,Page 4,5.1 數(shù)組,存儲(chǔ) 結(jié)構(gòu),順序存儲(chǔ)結(jié)構(gòu)： (1) 行優(yōu)先：逐行存儲(chǔ)（E.g. PASCAL、C語(yǔ)言等）； (2) 列優(yōu)先：逐列存儲(chǔ)（E.g. Fortran語(yǔ)言等,Page 5,5.1 數(shù)組,存儲(chǔ) 結(jié)構(gòu),1) 行優(yōu)先：逐行存儲(chǔ)（E.g. PASCAL、C語(yǔ)言等,Page 6,5.1 數(shù)組,存儲(chǔ) 結(jié)構(gòu),2) 列優(yōu)先：逐列存儲(chǔ)（E.g. Fortran語(yǔ)言等,Page 7,5.2 矩陣的壓縮存儲(chǔ),特殊 矩陣,當(dāng)矩陣中非零元素呈某種規(guī)律分布(特殊矩陣)，或出現(xiàn)大量零

3、元素(稀疏矩陣)情況下，若用一般順序存儲(chǔ)(二維數(shù)組)會(huì)造成浪費(fèi)。 方法： 為多個(gè)相同的元素只分配一個(gè)存儲(chǔ)單元; 對(duì)零元素不分配存儲(chǔ)空間,Page 8,5.2 矩陣的壓縮存儲(chǔ),特殊 矩陣,對(duì)稱(chēng)矩陣： 滿足: a ij=a ji (0i, jn -1) 按行序?yàn)橹餍?、存?chǔ)元素總數(shù): 為訪問(wèn)元素,必須找到i,j與k的關(guān)系,Page 9,5.2 矩陣的壓縮存儲(chǔ),特殊 矩陣,三角矩陣：矩陣的上(下)三角(不含對(duì)角線)中的元素均為常數(shù)的n階矩陣。 按行序?yàn)橹餍颉⒋鎯?chǔ)元素總數(shù): 為訪問(wèn)元素,必須找到i,j與k的關(guān)系,Page 10,5.2 矩陣的壓縮存儲(chǔ),稀疏 矩陣,定義：元素大部分為0,且分布沒(méi)有一定規(guī)律

4、的矩陣。 壓縮存儲(chǔ)原則：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值(三元組)。 M由(0,1,12), (0,2,9), (2,0,-3), (2,5,14), (3,2,24), (4,1,18), (5,01,15), (5,3,-7) 和矩陣維數(shù) (6,7)唯一確定,Page 11,5.2 矩陣的壓縮存儲(chǔ),稀疏 矩陣,稀疏矩陣的壓縮存儲(chǔ)方法三元組表 將三元組按行優(yōu)先順序排列，則得到結(jié)點(diǎn)為三元組的線性表,Page 12,5.2 矩陣的壓縮存儲(chǔ),稀疏 矩陣,稀疏矩陣的壓縮存儲(chǔ)方法：三元組表 typedef struct int i, j; /行、列下標(biāo) Element_Type v; /

5、對(duì)應(yīng)元素值 tuple; Typedef struct int mu, nu, tu; /行數(shù)、列數(shù)、非零元素個(gè)數(shù) tuple datamaxnum; spmatrix,Page 13,5.3 廣義表,定義,定義：廣義表L是由n個(gè)元素a1, a2, , an組成的有限序列，記作L=(a1, a2, , an)，其中n0為表長(zhǎng)度；當(dāng)n=0時(shí)L為空表，記作L=( )；元素ai(i=1,2,n)可以是不可分割的原子(用小寫(xiě)字母表示)，也可以是廣義表(用大寫(xiě)字母表示)。 例如： 深度 長(zhǎng)度 A=(a, b, c) 1 3 B=(A, (c, d) 2 2 C=(A, B) 3 2 D=(d, D) ?

6、 2 (遞歸表) E=( ) 0 0 (空表,Page 14,5.3 廣義表,基本 運(yùn)算,取表頭head(L): 取出廣義表A的第一個(gè)元素。 例如： A=(a, b, c); head(A)=a 取表尾(去表頭)tail(L): 去掉表頭元素后得到的廣義表。 例如：tail(A)=(b, c) 說(shuō)明： 其他操作可由此兩個(gè)基本操組合來(lái)實(shí)現(xiàn)： 例如：取第2個(gè)元素：去表頭+取表頭,Page 15,5.3 廣義表,鏈接存儲(chǔ)方式,不帶頭結(jié)點(diǎn)的單鏈表 第1個(gè)域里用0表示原子元素，用1表示廣義表元素。 缺點(diǎn)： 如果A最前面插 入一個(gè)元素，而 C表的內(nèi)容沒(méi)有 變化，此時(shí)，C 表內(nèi)容出現(xiàn)錯(cuò)誤,Page 16,5.3 廣義表,鏈接存儲(chǔ)方式,帶頭結(jié)點(diǎn)的單鏈表 第1個(gè)域里用0表示原子元素，用1表示廣義表元素,Page 17,5.3 廣義表,練習(xí),head(p, h, w) tail(b, k, p, h) head(a, b), (c, d) tail(a