數(shù)據(jù)結(jié)構(gòu)課件第5章數(shù)組和廣義表-展示頁(yè)
2025-05-08 08:39本頁(yè)面
【正文】 即二維數(shù)組 A 的起始存儲(chǔ)位置 ， 也稱為基地址或基址； n 是數(shù)組第二維的長(zhǎng)度 。 反之 ， 只要給出一組下標(biāo) ， 便可以求得相應(yīng)數(shù)組的存儲(chǔ)位置 。 (2) 以行為主序 ( row major order ) 的存儲(chǔ)方式 ， 即按行優(yōu)先 ， 逐行順序存儲(chǔ) 。 順序存儲(chǔ)的定位公式 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 9 數(shù)組的順序存儲(chǔ)表示 基本操作的算法描述 用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)組中的元素 ， 一定要按照某種次序?qū)⒃嘏懦梢粋€(gè)線性序列 。 一維數(shù)組可直接采用順序存儲(chǔ) 。 初始條件： A 是 n 維數(shù)組 ， e 為元素變量 ， 隨后是 n 個(gè)下標(biāo)值 。 ?GetValue(A,e, index1, … , indexn ): 初始條件： A 是 n 維數(shù)組， e 為元素變量，隨后是 n 個(gè)下標(biāo)值。 操作結(jié)果：如果維數(shù) n 和各維長(zhǎng)度合法 ， 則構(gòu)造 相應(yīng)的數(shù)組 A， 并且返回 TRUE。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取數(shù)據(jù)元素和修改數(shù)據(jù)元素值的操作。 Am n = a11 a21 … am1 a12 a22 … am2 a13 a23 … am3 … … … … a a2, n … am, n 4 例如 ， 下面是一個(gè)二維數(shù)組 ， 且以 m 行 n 列的矩陣形式表示 。 反之 ， n 維數(shù)組也可以看成是線性表的推廣 。 也可以說(shuō) ， 數(shù)組中的每個(gè)數(shù)據(jù)元素都對(duì)應(yīng)于一組下標(biāo) （ j1 , j2 , … , jn ） ， 每個(gè)下標(biāo)取值范圍是 1≤ji≤bi ， bi 稱為第 i 維的長(zhǎng)度 （ i = 1, 2, … , n） 。 數(shù)組是由下標(biāo)和值組成的序?qū)?。 數(shù)組的定義 線性結(jié)構(gòu)中的數(shù)據(jù)都是非結(jié)構(gòu)的原子類型 ， 元素的值是不再分解的 。1 第 5 章 數(shù) 組 和 廣 義 表 數(shù)組的邏輯結(jié)構(gòu) 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 矩陣的壓縮存儲(chǔ) 廣義表 數(shù)組的邏輯結(jié)構(gòu) 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 矩陣的壓縮存儲(chǔ) 廣義表 數(shù)組 (array) 是最常用的數(shù)據(jù)結(jié)構(gòu)之一 。 幾乎所有的程序設(shè)計(jì)語(yǔ)言都把數(shù)組類型設(shè)定為固有類型 。 而數(shù)組可以看成是線性表在下述含義上的擴(kuò)展： 數(shù)組的邏輯結(jié)構(gòu) 2 數(shù)組的基本操作 表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu) 。 在數(shù)組中 ， 一旦給定下標(biāo) ， 都存在一個(gè)與其相對(duì)應(yīng)的值 ， 這個(gè)值就稱為數(shù)組元素 。 顯然 ， 當(dāng) n = 1 時(shí) ， n 維數(shù)組就退化為定長(zhǎng)的線性表 。 3 數(shù)組的定義 可以把二維數(shù)組看成是這樣一個(gè)定長(zhǎng)線性表：它的每個(gè)數(shù)據(jù)元素也是一個(gè)定長(zhǎng)線性表 。 每個(gè)數(shù)據(jù)元素 α j是一個(gè)列向量形式的線性表 Am n = … a1, n a2, n … am, n a13 a23 … am, 3 a12 a22 … am, 2 a11 a21 … am,1 二維數(shù)組 A 還可以看成是一個(gè)線性表： A = (α1, α 2, … , α n ) α j = ( a1j , a2j , … , am, j ) 1 ≤ j ≤ n 每個(gè)數(shù)據(jù)元素是一個(gè)行向量形式的線性表 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ù)和維界就不再改變。 6 數(shù)組的抽象類型定義 ADT Array { D={aj1j2j3… ..jn|n0,稱為數(shù)組的維數(shù) , ji是數(shù)組的第 i維下標(biāo) ,1≤ ji ≤ bi, bi為數(shù)組第 i維的長(zhǎng)度 ， aj1j2j3… ..jn∈ ElementSet} 數(shù)據(jù)關(guān)系：Ｒ ={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 )。 8 數(shù)組的抽象類型定義 ?DestroyArray(A):銷毀數(shù)組 A。 操作結(jié)果：若各下標(biāo)合法，則用 e返回?cái)?shù)組Ａ中由由 index1,… index n所指定的元素的值 . ? SetValue ( A, e, index1, … , indexn )。 操作結(jié)果：若各下標(biāo)合法 ， 則將數(shù)組 A中由index1,… indexn所指定的元素的值置為 e. 由于內(nèi)存儲(chǔ)器的結(jié)構(gòu)是一維的 。 用一維的內(nèi)存存儲(chǔ)表示多維數(shù)組時(shí) ， 需按某種次序?qū)?shù)組中元素排成一線性序列 ， 再將這個(gè)線性序列存放在一維的內(nèi)存中 ， 即數(shù)組的順序存儲(chǔ)結(jié)構(gòu)表示 。 有兩種存儲(chǔ)方式： (1) 以列為主序 ( column major order ) 的存儲(chǔ)方式 ，即按列優(yōu)先 ， 逐列順序存儲(chǔ) 。 10 順序存儲(chǔ)的定位公式 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 行主次序存放 對(duì)于數(shù)組 ， 一旦規(guī)定了它的維數(shù)和各維的長(zhǎng)度 ， 便可以為它分配存儲(chǔ)空間 。 13 （ １ ） 一維數(shù)組的地址計(jì)算： 設(shè)一維數(shù)組為：Ａ =(a1,a2,… ,ai,… ,an),數(shù)組中每個(gè)元素占 size個(gè)存儲(chǔ)單元 ， 則元素 ai的存儲(chǔ)地址為： Loc(A[i])=Loc(A[1])+(i1)*size。 15 假設(shè)每個(gè)數(shù)據(jù)元素占 size個(gè)存儲(chǔ)單元 ， 則二維數(shù)組 A 中任一元素 aij 的存儲(chǔ)位置可以由下面定位公式確定 LOC (A[i],[ j]) = LOC (A[1], [1]) + (n*(i1)+(j1))*size ⑶ 三維數(shù)組的 地址計(jì)算 三維數(shù)組 A(1:r,1:m,1:n)。 顯然 ， ai11地址為 Ｌ oc(A[i][1][1])=Loc(A[1][1][1])+(i1)*m*n,因?yàn)樵谠撛刂坝?i1個(gè) m*n的二維數(shù)組 。 矩陣 (matrix) 是很多科學(xué)與工程計(jì)算問(wèn)題中研究的數(shù)學(xué)對(duì)象 。 特殊矩陣 包括兩個(gè)部份： ① 元素分布有特殊規(guī)律的矩陣 ,找到 規(guī)律對(duì)應(yīng)的公式 ， 實(shí)現(xiàn)壓縮存儲(chǔ) 。 矩陣的壓縮存儲(chǔ) 17 特殊矩陣的壓縮存儲(chǔ) 所謂壓縮存儲(chǔ)是指：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元不分配空間 。 特殊矩陣主要有 3 種：對(duì)稱矩陣 、三角矩陣 、 帶狀矩陣 。 19 特殊矩陣的壓縮存儲(chǔ) ???????????????? u t r o k ft s q n je r q p mi do n m
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1