1、第5章數(shù)組和廣義表第5章數(shù)組和廣義表的定義5.1數(shù)組的順序表示和實現(xiàn)5.3矩陣壓縮存儲5.4廣義表，數(shù)組是由n(n=)個相同數(shù)據(jù)類型的數(shù)據(jù)元素組成的有限序列。它分為一維陣列、二維陣列和多維陣列。5.1數(shù)組的定義，一維數(shù)組。一旦確定了第一個元素ai的存儲地址LOC (ai)，并且每個元素所占用的存儲空間K為0，則第ith個元素的地址可以通過以下公式計算：一維數(shù)組、二維數(shù)組和多維數(shù)組可以看作是一維數(shù)組的推廣。例如，二維數(shù)組：typedefelementtype array2mn，二維數(shù)組和多維數(shù)組，相當(dāng)于：typedefelementtypearray1ntypedef array1 array2

2、m，二維數(shù)組，三維數(shù)組，行向量下標(biāo)I頁向量下標(biāo)I列向量下標(biāo)j行向量下標(biāo)j列向量下標(biāo)k，數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型；數(shù)組中的每個數(shù)據(jù)元素對應(yīng)一組唯一的下標(biāo)值；數(shù)組元素是隨機(jī)可訪問的。一旦定義了數(shù)組，它的尺寸和邊界就不會改變。數(shù)組操作包括初始化、銷毀、訪問元素和修改元素值。數(shù)組屬性：5.2數(shù)組的順序表示和實現(xiàn)，一維數(shù)組，LOC (i)=LOC (i -1) l=i*l，二維數(shù)組，行優(yōu)先級：LOC (i，j)=a (i * m j) * l，列優(yōu)先級：LOC (i J)=a (j * n i) * l，對稱矩陣是一個n階方陣A。5.3.1特殊矩陣是指非零元素或零元素有規(guī)律分布的矩陣。5.3矩

3、陣的壓縮存儲，1 51 3 7 5 0 8 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3，并且元素可以根據(jù)行優(yōu)先級順序存儲在向量san(n 1)/2中。a00a10a11a20a21a23.a n-11an-12an-1 n-1，矩陣元素aij和數(shù)組元素sak之間的對應(yīng)關(guān)系：k=i*(i 1)/2 j如果i=j k=j*(j 1)/2 i如果ij，讓s在矩陣a中有非零元素，如果，5.3.2稀疏矩陣、M=，T=， 0 12 9 0 0 0 0 0 0-3 0 0 15 0 0 0 0 0 12 0 0 0 18 0-3 0 0 0 0 14 0 9 0 24 0 0 0 0 2

4、4 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 14 0 0 15 0 7 0一般來說，稀疏矩陣的非零元素分布是不規(guī)則的。 因此，在存儲非零元素時，需要存儲適當(dāng)?shù)妮o助信息，以便快速確定指定非零元素的位置。稀疏矩陣常用的壓縮存儲方法：三表交叉鏈表，m=(0，1，12)，(0，2，9)，(2，0，-3)，(2，5，14)，(3，2，24)，(4，1，18)，為了解決這個問題，采用了交叉鏈表的存儲結(jié)構(gòu)。節(jié)點結(jié)構(gòu)如下：2 .交叉鏈接列表，5.4通用列表，通用列表的定義：通用列表是由n (0)個表元素組成的有限序列，表示為：LS=(a0，a1，a2，an-1)，其中LS是表名，ai

5、是表元素，它可以是表(稱為子表)，N是表的長度。n=0的通用表為空。N 0，表的第一個表元素稱為廣義表的頭，由其他表元素組成的表稱為廣義表的尾。(1) a=() (2) b=(e) (3) c=(a，(b，C，d) (4) d=(a，b，C) (5)E=(a，E)，任何非空廣義表對于非空廣義表，其標(biāo)題可以是原子或子表；頁腳必須是子表。，廣義表的特征，這是一個多層次的結(jié)構(gòu)；廣義表的深度被定義為括號的多樣性。注意：“原子”的深度是0；“空表”的深度為1，廣義表可以共享；廣義表可以是遞歸表；a=() b=(6，2) c=(a，(5，3，x) d=(b，c，a) e=(b，d) f=(4，f)，各種廣義表的示意圖，廣義表的存儲結(jié)構(gòu)，基本思想：使用鏈存儲結(jié)構(gòu)Tp:指向下一個元素節(jié)點，例如：(1) a=() (2) b=(e) anull，0，e，1，b，0，A，1，e，(3) e=(a，A)讓2D數(shù)組A56的每個元素占用4個字節(jié)。眾所周知，Loc(a00)=1000。A占用多少字節(jié)？A的終端節(jié)點a45的起始地址是什么？當(dāng)按行和列先存儲時，a25的起始地址是什么？2.畫出下列廣義表的圖示：a (a，b (b，d)，c (e，b