【正文】 1 第 5 章 數(shù) 組 和 廣 義 表 數(shù)組的邏輯結構 數(shù)組的順序存儲結構 矩陣的壓縮存儲 廣義表 數(shù)組的邏輯結構 數(shù)組的順序存儲結構 矩陣的壓縮存儲 廣義表 數(shù)組 (array) 是最常用的數(shù)據(jù)結構之一 。 幾乎所有的程序設計語言都把數(shù)組類型設定為固有類型 。 數(shù)組的定義 線性結構中的數(shù)據(jù)都是非結構的原子類型 ， 元素的值是不再分解的 。 而數(shù)組可以看成是線性表在下述含義上的擴展： 數(shù)組的邏輯結構 2 數(shù)組的基本操作 表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結構 。 數(shù)組是由下標和值組成的序對集合 。 在數(shù)組中 ， 一旦給定下標 ， 都存在一個與其相對應的值 ， 這個值就稱為數(shù)組元素 。 也可以說 ， 數(shù)組中的每個數(shù)據(jù)元素都對應于一組下標 （ j1 , j2 , … , jn ） ， 每個下標取值范圍是 1≤ji≤bi ， bi 稱為第 i 維的長度 （ i = 1, 2, … , n） 。 顯然 ， 當 n = 1 時 ， n 維數(shù)組就退化為定長的線性表 。 反之 ， n 維數(shù)組也可以看成是線性表的推廣 。 3 數(shù)組的定義 可以把二維數(shù)組看成是這樣一個定長線性表：它的每個數(shù)據(jù)元素也是一個定長線性表 。 Am n = a11 a21 … am1 a12 a22 … am2 a13 a23 … am3 … … … … a a2, n … am, n 4 例如 ， 下面是一個二維數(shù)組 ， 且以 m 行 n 列的矩陣形式表示 。 每個數(shù)據(jù)元素 α j是一個列向量形式的線性表 Am n = … a1, n a2, n … am, n a13 a23 … am, 3 a12 a22 … am, 2 a11 a21 … am,1 二維數(shù)組 A 還可以看成是一個線性表： A = (α1, α 2, … , α n ) α j = ( a1j , a2j , … , am, j ) 1 ≤ j ≤ n 每個數(shù)據(jù)元素是一個行向量形式的線性表 B=(β1β2β3 … , βm) Am n = ( ( a11 a12 … a1, n ) , …, ( am, 1am, 2… am, n ) ) ( a21 a22 … a2, n ) , … , βi = ( ai 1 , ai 2 , … , ai, n ) 1 ≤ i ≤ m 5 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結構的初始化和銷毀之外，數(shù)組只有存取數(shù)據(jù)元素和修改數(shù)據(jù)元素值的操作。 6 數(shù)組的抽象類型定義 ADT Array { D={aj1j2j3… ..jn|n0,稱為數(shù)組的維數(shù) , ji是數(shù)組的第 i維下標 ,1≤ ji ≤ bi, bi為數(shù)組第 i維的長度 ， aj1j2j3… ..jn∈ ElementSet} 數(shù)據(jù)關系：Ｒ ={R1,R2, …… .Rn} Ri=aj1… ji… .jn,aj1… ji+1… jn| 1≤jk ≤bk, 1≤k≤n 且 k≠i, 1≤ji ≤bi1, aj1… j2… .jn,aj1… ji+1… jn∈ D,i=1,… n} 基本操作 : ? InitArray (A, n, bound1, … , boundn )。 操作結果：如果維數(shù) n 和各維長度合法 ， 則構造 相應的數(shù)組 A， 并且返回 TRUE。 8 數(shù)組的抽象類型定義 ?DestroyArray(A):銷毀數(shù)組 A。 ?GetValue(A,e, index1, … , indexn ): 初始條件： A 是 n 維數(shù)組， e 為元素變量，隨后是 n 個下標值。 操作結果：若各下標合法，則用 e返回數(shù)組Ａ中由由 index1,… index n所指定的元素的值 . ? SetValue ( A, e, index1, … , indexn )。 初始條件： A 是 n 維數(shù)組 ， e 為元素變量 ， 隨后是 n 個下標值 。 操作結果：若各下標合法 ， 則將數(shù)組 A中由index1,… indexn所指定的元素的值置為 e. 由于內(nèi)存儲器的結構是一維的 。 一維數(shù)組可直接采用順序存儲 。 用一維的內(nèi)存存儲表示多維數(shù)組時 ， 需按某種次序將數(shù)組中元素排成一線性序列 ， 再將這個線性序列存放在一維的內(nèi)存中 ， 即數(shù)組的順序存儲結構表示 。 順序存儲的定位公式 數(shù)組的順序存儲結構 9 數(shù)組的順序存儲表示 基本操作的算法描述 用順序存儲結構來存儲數(shù)組中的元素 ， 一定要按照某種次序將元素排成一個線性序列 。 有兩種存儲方式： (1) 以列為主序 ( column major order ) 的存儲方式 ，即按列優(yōu)先 ， 逐列順序存儲 。 (2) 以行為主序 ( row major order ) 的存儲方式 ， 即按行優(yōu)先 ， 逐行順序存儲 。 10 順序存儲的定位公式 a21 a11 … am, 1 a22 a12 … am, 2 a1, n … a2, n … am, n )()( 11)1(1 aL O CAL O C ?)()( 12)1(2 aL O CAL O C ?)1(1A)1(2A)1(nA21 11 … , 1 …Am,1………………… … , …… 11 )()( 1)1( nn aL O CAL O C ?列主次序存放 a12 a11 … a22 a21 … a2, n am, 1 … am, 2 … am, n )()( 11)1(1 aL O CAL O C ?)()( 21)1(2 aL O CAL O C ?)()( 1,)1( mm aL O CAL O C ?)1(1A)1(2A)1(mA ………… …, , … , …1, n …… 2, ……… a , n 12 行主次序存放 對于數(shù)組 ， 一旦規(guī)定了它的維數(shù)和各維的長度 ， 便可以為它分配存儲空間 。 反之 ， 只要給出一組下標 ， 便可以求得相應數(shù)組的存儲位置 。 13 （ １ ） 一維數(shù)組的地址計算： 設一維數(shù)組為：Ａ =(a1,a2,… ,ai,… ,an),數(shù)組中每個元素占 size個存儲單元 ， 則元素 ai的存儲地址為： Loc(A[i])=Loc(A[1])+(i1)*size。 數(shù)組的地址計算 14 ⑵ 二維數(shù)組的 地址計算 假設每個數(shù)據(jù)元素占 1 個存儲單元 ， 且以行序為主序的進行存儲 ， 則二維數(shù)組 A 中任一元素 aij 的存儲位置可以由下面定位公式確定 LOC (A[i],[ j]) = LOC (A[1], [1]) + n*(i1)+(j1) 其中： LOC (A[i[,[ j]) 是 aij 的存儲位置； LOC (A[1], [1]) 是 a11 的存儲位置 ， 即二維數(shù)組 A 的起始存儲位置 ， 也稱為基地址或基址； n 是數(shù)組第二維的長度 。 15 假設每個數(shù)據(jù)元素占 size個存儲單元 ， 則二維數(shù)組 A 中任一元素 aij 的存儲位置可以由下面定位公式確定 LOC (A[i],[ j]) = LOC (A[1], [1]) + (n*(i1)+(j1))*size ⑶ 三維數(shù)組的 地址計算 三維數(shù)組 A(1:r,1:m,1:n)。 假設每個數(shù)據(jù)元素占 size個存儲單元 ， 且以行序為主序的進行存儲 ， 首元素 a111的地址為 Loc(A[1][1][1]),求任意元素 aijk的地址 。 顯然 ， ai11地址為 Ｌ oc(A[i][1][1])=Loc(A[1][1][1])+(i1)*m*n,因為在該元素之前有 i1個 m*n的二維數(shù)組 。 16 不難得到三維數(shù)組任意元素 aijk的地址： Loc(A[i]