數(shù)據(jù)結(jié)構(gòu)第5章 數(shù)組和廣義表

1、第五章第五章 數(shù)組和廣義表數(shù)組和廣義表本章主要介紹多維數(shù)組的概念及在計(jì)算機(jī)中的存本章主要介紹多維數(shù)組的概念及在計(jì)算機(jī)中的存放，放，特殊矩陣特殊矩陣的壓縮存儲(chǔ)及相應(yīng)運(yùn)算的壓縮存儲(chǔ)及相應(yīng)運(yùn)算，廣義表廣義表的的概念和概念和存儲(chǔ)結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過(guò)本章存儲(chǔ)結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過(guò)本章學(xué)習(xí)，要求掌握如下內(nèi)容：學(xué)習(xí)，要求掌握如下內(nèi)容：1 1多維數(shù)組的定義及在計(jì)算機(jī)中的存儲(chǔ)表示；多維數(shù)組的定義及在計(jì)算機(jī)中的存儲(chǔ)表示；2 2對(duì)稱(chēng)矩陣、三角矩陣、對(duì)角矩陣等特殊矩陣對(duì)稱(chēng)矩陣、三角矩陣、對(duì)角矩陣等特殊矩陣在計(jì)算機(jī)中的壓縮存儲(chǔ)表示及地址計(jì)算公式；在計(jì)算機(jī)中的壓縮存儲(chǔ)表示及地址計(jì)算公式；3 3稀疏矩陣的三元

2、組表示及轉(zhuǎn)置算法實(shí)現(xiàn)；稀疏矩陣的三元組表示及轉(zhuǎn)置算法實(shí)現(xiàn)；4 4廣義表存儲(chǔ)結(jié)構(gòu)表示及基本運(yùn)算。廣義表存儲(chǔ)結(jié)構(gòu)表示及基本運(yùn)算。5.1 多維數(shù)組5.1.1多維數(shù)組的定義5.1.2多維數(shù)組的存儲(chǔ)5.2 矩陣的壓縮存儲(chǔ) 5.2.1 特殊矩陣 5.2.2 稀疏矩陣5.3 廣義表5.15.1 多維數(shù)組多維數(shù)組數(shù)組：數(shù)組： 由一組名字相同、下標(biāo)不同的同類(lèi)型的元素由一組名字相同、下標(biāo)不同的同類(lèi)型的元素 組成組成 數(shù)組特點(diǎn)數(shù)組特點(diǎn) 數(shù)組結(jié)構(gòu)固定數(shù)組結(jié)構(gòu)固定,下標(biāo)一般具有下標(biāo)一般具有固定的上界和下界固定的上界和下界 數(shù)據(jù)元素?cái)?shù)據(jù)元素具有具有統(tǒng)一的類(lèi)型統(tǒng)一的類(lèi)型 數(shù)組運(yùn)算數(shù)組運(yùn)算 給定一組下標(biāo)，給定一組下標(biāo)，取取相

3、應(yīng)的數(shù)據(jù)元素相應(yīng)的數(shù)據(jù)元素. 給定一組下標(biāo)，給定一組下標(biāo)，修修改數(shù)據(jù)元素的值改數(shù)據(jù)元素的值.數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單5.1.15.1.1多維數(shù)組的定義多維數(shù)組的定義與高級(jí)語(yǔ)言中數(shù)組的區(qū)別：與高級(jí)語(yǔ)言中數(shù)組的區(qū)別： 1、本章所討論的數(shù)組是一種、本章所討論的數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)，而高級(jí)語(yǔ)，而高級(jí)語(yǔ) 言中數(shù)組是一種言中數(shù)組是一種數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型。2、高級(jí)語(yǔ)言高級(jí)語(yǔ)言中的數(shù)組是中的數(shù)組是順序結(jié)構(gòu)順序結(jié)構(gòu)；而本章的數(shù)組；而本章的數(shù)組 既可以是既可以是順序的，順序的，也可以是也可以是鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)，用戶(hù)可，用戶(hù)可 根據(jù)需要選擇。根據(jù)需要選擇。5.1.15.1

4、.1多維數(shù)組的定義多維數(shù)組的定義一維數(shù)組一維數(shù)組一維數(shù)組可以看成是一個(gè)線(xiàn)性表或一個(gè)向量，它在計(jì)算機(jī)內(nèi)一維數(shù)組可以看成是一個(gè)線(xiàn)性表或一個(gè)向量，它在計(jì)算機(jī)內(nèi)是存放在一塊是存放在一塊連續(xù)的存儲(chǔ)單元連續(xù)的存儲(chǔ)單元中，適合于中，適合于隨機(jī)查找隨機(jī)查找。有一個(gè)直接前驅(qū)和一個(gè)直接后繼有一個(gè)直接前驅(qū)和一個(gè)直接后繼二維數(shù)組二維數(shù)組二維數(shù)組可以看成是向量的推廣。二維數(shù)組可以看成是向量的推廣。有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼 例如，設(shè)例如，設(shè)A A是一個(gè)有是一個(gè)有m m行行n n列的二維數(shù)組，則列的二維數(shù)組，則A A可以表示為可以表示為：a00 a01 a0n-1 a10 a11 a1n-1

5、 . A= am-1 0 am-1 1 am-1 n-1 三維數(shù)組三維數(shù)組最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼多維數(shù)組多維數(shù)組把三維以上的數(shù)組稱(chēng)為多維數(shù)組，把三維以上的數(shù)組稱(chēng)為多維數(shù)組，可有多個(gè)直接前驅(qū)和多個(gè)直接后繼可有多個(gè)直接前驅(qū)和多個(gè)直接后繼是一種非線(xiàn)性結(jié)構(gòu)是一種非線(xiàn)性結(jié)構(gòu)?？偨Y(jié)：總結(jié)： 一維數(shù)組可以看作一個(gè)線(xiàn)性表，一維數(shù)組可以看作一個(gè)線(xiàn)性表， 二維數(shù)組可以看作二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組數(shù)據(jù)元素是一維數(shù)組”的一維的一維數(shù)組，數(shù)組， 三維數(shù)組可以看作三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)的一維數(shù)組，依組，依 此類(lèi)推。此類(lèi)推。

6、在在C C語(yǔ)言中的描述語(yǔ)言中的描述typedeftypedef intint datatypedatatype; ;datatypedatatype array1N; array1N; datatypedatatype array2array2MN;MN;datatypedatatype array3XYZ;array3XYZ; 數(shù)組一旦被定義，它的維數(shù)和維界就不再數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，數(shù)組只有存取元素和修改元素值改變。因此，數(shù)組只有存取元素和修改元素值的操作。的操作?？紤]問(wèn)題的基本出發(fā)點(diǎn)：考慮問(wèn)題的基本出發(fā)點(diǎn)： 計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的。因此用一維內(nèi)存來(lái)存多計(jì)算機(jī)的

7、內(nèi)存結(jié)構(gòu)是一維的。因此用一維內(nèi)存來(lái)存多維數(shù)組，就必須維數(shù)組，就必須按某種次序?qū)?shù)組元素排成線(xiàn)性序列按某種次序?qū)?shù)組元素排成線(xiàn)性序列，然后將這個(gè)線(xiàn)性序列順序存放在存儲(chǔ)器中然后將這個(gè)線(xiàn)性序列順序存放在存儲(chǔ)器中。數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法一般都是采用順序存儲(chǔ)的方法來(lái)表示數(shù)組來(lái)表示數(shù)組。5.2 5.2 多維數(shù)組的存儲(chǔ)多維數(shù)組的存儲(chǔ)兩種順序存儲(chǔ)方式兩種順序存儲(chǔ)方式行優(yōu)先順序行優(yōu)先順序?qū)?shù)組元素按行排列將數(shù)組元素按行排列在在PASCALPASCAL、C C語(yǔ)言中，數(shù)組就是按行

8、優(yōu)先順序存儲(chǔ)的。語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。列優(yōu)先順序列優(yōu)先順序?qū)?shù)組元素按列向量排列將數(shù)組元素按列向量排列在在FORTRANFORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。推廣到多維數(shù)組的情況：推廣到多維數(shù)組的情況：行優(yōu)先順序：先排最右下標(biāo)，從右到左，最后排最左下標(biāo)。行優(yōu)先順序：先排最右下標(biāo)，從右到左，最后排最左下標(biāo)。 因此，在算法中，最左邊下標(biāo)可以看成是外循環(huán)，最右邊下標(biāo)可因此，在算法中，最左邊下標(biāo)可以看成是外循環(huán)，最右邊下標(biāo)可以看以看 成是最內(nèi)循環(huán)。成是最內(nèi)循環(huán)。列優(yōu)先順序：先排最左下標(biāo)，從左向右，最后排最右下標(biāo)。列優(yōu)先順序：先排最左下標(biāo)，從

9、左向右，最后排最右下標(biāo)。 因此，在算法中，最右邊下標(biāo)可以看成是外循環(huán)，最左邊下標(biāo)可以看因此，在算法中，最右邊下標(biāo)可以看成是外循環(huán)，最左邊下標(biāo)可以看成是最內(nèi)循環(huán)。成是最內(nèi)循環(huán)。 按行序?yàn)橹餍虼娣虐葱行驗(yàn)橹餍虼娣?am-1,n-1 . am-1,1 am-1,0 . a1n-1 . a11 a10 a0,n-1 . a01 a00 a00 a01 . a0,n-1 a10 a11 . a1,n-1 am-1,0 am-1,1 am-1,n-1 .01n-1m*n-1n am-1,n-1 . a1,n-1 a0,n-1 . am-1,1 . a11 a01 am-1,0 . a10 a00 a00

10、a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 . am-1n-1 . 按列序?yàn)橹餍虼娣虐戳行驗(yàn)橹餍虼娣?1m*n-1m-1m計(jì)算機(jī)如何實(shí)現(xiàn)數(shù)組元素的隨機(jī)存??？計(jì)算機(jī)如何實(shí)現(xiàn)數(shù)組元素的隨機(jī)存取？ 按上述兩種方式順序存儲(chǔ)的序組，只要知道：按上述兩種方式順序存儲(chǔ)的序組，只要知道：開(kāi)始結(jié)點(diǎn)的存放地址（即基地址），開(kāi)始結(jié)點(diǎn)的存放地址（即基地址），維數(shù)維數(shù)每維的上、下界每維的上、下界每個(gè)數(shù)組元素所占用的單元數(shù)，每個(gè)數(shù)組元素所占用的單元數(shù)， 就可以將數(shù)組元素的就可以將數(shù)組元素的存放地址表示為存放地址表示為其下標(biāo)的線(xiàn)其下標(biāo)的線(xiàn)性函數(shù)性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)

11、間。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。如何計(jì)算數(shù)組元素的地址？如何計(jì)算數(shù)組元素的地址？計(jì)算二維數(shù)組元素地址的通式計(jì)算二維數(shù)組元素地址的通式二維數(shù)組二維數(shù)組列優(yōu)先列優(yōu)先存儲(chǔ)的通式為：存儲(chǔ)的通式為：LOC(aij)=LOC(a00)+(j*b1+i)*L則則行優(yōu)先行優(yōu)先存儲(chǔ)時(shí)的地址公式為：存儲(chǔ)時(shí)的地址公式為：LOC(aij)=LOC(a00)+(i*b2+j)*L設(shè)一般的二維數(shù)組是設(shè)一般的二維數(shù)組是A0.bA0.b1 1-1, 0.b-1, 0.b2 2-1-11b21,b11,0b11b2i,iji01b

12、20,00mna.a.a.a.a.a.aAbi稱(chēng)為第稱(chēng)為第i維維的長(zhǎng)度的長(zhǎng)度計(jì)算三維數(shù)組元素地址的通式計(jì)算三維數(shù)組元素地址的通式設(shè)一般的三維數(shù)組是設(shè)一般的三維數(shù)組是A0.b1-1, 0.b2-1，0.b3-1按按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)，其任一元素存儲(chǔ)，其任一元素A Aijkijk地址計(jì)地址計(jì)算函數(shù)為：算函數(shù)為：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(i i* *b b2 2* *b b3 3+ +j j* *b b3 3+k)+k)* *L L按按“列優(yōu)先順序列優(yōu)先順序”存儲(chǔ)，其任一元素存儲(chǔ)，其任一元素A Aijkijk地址計(jì)地址計(jì)算函數(shù)為：算

13、函數(shù)為：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(k k* *b b1 1* *b b2 2+ +j j* *b b1 1+i)+i)* *L L若是若是N N維數(shù)組，其中任一元素的地址該如何計(jì)算？維數(shù)組，其中任一元素的地址該如何計(jì)算？LjbjaLOCLjjbjbbbjbbbaLOCaLOCniniknkinnnnnnjjj1110.0012431320.00,.,21)()().()()(開(kāi)始結(jié)點(diǎn)的存放地址（即基地址）開(kāi)始結(jié)點(diǎn)的存放地址（即基地址）維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)每個(gè)數(shù)組元素所占用的單元數(shù)其中其中

14、Cn=L, Ci-1=biCi， 1in（遞歸）遞歸）Loc(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)niii1jC最基本的原理最基本的原理Ai1in的起始地址=第一個(gè)元素的起始地址該元素前面的元素個(gè)數(shù)單位長(zhǎng)度+對(duì)于二維數(shù)組對(duì)于二維數(shù)組Ac1:d1,c2:d2,設(shè)每個(gè)元素占用設(shè)每個(gè)元素占用k個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，LOC(c1,c2)是第一個(gè)元素是第一個(gè)元素ac1c2的存儲(chǔ)位置，則的存儲(chǔ)位置，則按行存放時(shí)按行存放時(shí)，aij的存儲(chǔ)位置為：的存儲(chǔ)位置為：LOC(i,j)=LOC(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*

15、k按列存放時(shí)按列存放時(shí),aij的存儲(chǔ)位置為：的存儲(chǔ)位置為：LOC(i,j)=LOC(c1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k2006-12006-1對(duì)于二維數(shù)組a04,15，設(shè)每個(gè)元素占1個(gè)存儲(chǔ)單元，且以行為主序存儲(chǔ)，則元素a2,1相對(duì)于數(shù)組空間起始地址的偏移量是()。 A5 B10 C15D25 20032003設(shè)數(shù)組a3.16，5.20的元素以列為主序存放，每個(gè)元素占用兩個(gè)存儲(chǔ)單元，則數(shù)組元素ai,j(3i16，5j20)的地址計(jì)算公式為_(kāi)。 Aa-118+2i+28jBa-116+2i+28j Ca-144+2i+28j Da-146+2i+28j5.25.2 矩

16、陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)在編程時(shí)，簡(jiǎn)單而又自然的方法，是在編程時(shí)，簡(jiǎn)單而又自然的方法，是將矩陣描述為將矩陣描述為一個(gè)二維數(shù)組一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取。其元素進(jìn)行隨機(jī)存取。 但是在一些特殊矩陣中，但是在一些特殊矩陣中，非零元素呈某種規(guī)律分布非零元素呈某種規(guī)律分布或者或者矩陣中有大量的零元素矩陣中有大量的零元素，如果仍用二維數(shù)組存，如果仍用二維數(shù)組存，會(huì)造成極大的浪費(fèi)，尤其是處理高階矩陣的時(shí)候。會(huì)造成極大的浪費(fèi)，尤其是處理高階矩陣的時(shí)候。 為了節(jié)省存儲(chǔ)空間，為了節(jié)省存儲(chǔ)空間， 我們可以對(duì)這類(lèi)矩陣進(jìn)行壓縮我們可以對(duì)這類(lèi)矩陣進(jìn)行壓

17、縮存儲(chǔ)。存儲(chǔ)。5.2.15.2.1 幾種常見(jiàn)的特殊矩陣幾種常見(jiàn)的特殊矩陣1 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9對(duì)稱(chēng)矩陣在一個(gè)在一個(gè)n n階方陣階方陣A A中，若元素滿(mǎn)足下中，若元素滿(mǎn)足下述性質(zhì)：述性質(zhì)：a aij ij= =a aji ji 0i,jn-1 0i,jn-1，則稱(chēng)，則稱(chēng)A A為對(duì)稱(chēng)矩陣。為對(duì)稱(chēng)矩陣。特征特征：元素關(guān)于主對(duì)角線(xiàn)對(duì)稱(chēng)：元素關(guān)于主對(duì)角線(xiàn)對(duì)稱(chēng)壓縮存儲(chǔ)的辦法：壓縮存儲(chǔ)的辦法： 只存矩陣中上三角或下三角中只存矩陣中上三角或下三角中的元素。的元素。所需空間：所需空間：

18、2) 1() 1(10nniNni三角矩陣三角矩陣特征：特征：上三角矩陣上三角矩陣中，主對(duì)角中，主對(duì)角線(xiàn)的線(xiàn)的下三角中的元素均下三角中的元素均為常數(shù)為常數(shù)。在大多數(shù)情況。在大多數(shù)情況下，常數(shù)為下，常數(shù)為零零。下三角矩陣下三角矩陣正好相反。正好相反。壓縮方法：壓縮方法：只存上只存上( (下下) )三角陣中上三角陣中上( (下下) )三角中的元素三角中的元素常數(shù)常數(shù)c c可共享一個(gè)存儲(chǔ)可共享一個(gè)存儲(chǔ)空間空間所需空間：所需空間：1 12 23 34 45 50 03 34 45 56 60 00 05 56 67 70 00 00 07 78 80 00 00 00 09 91 12 23 34 4

19、5 54 43 34 45 56 64 44 45 56 67 74 44 44 47 78 84 44 44 44 49 91 10 00 00 00 02 23 30 00 00 03 36 65 50 00 04 47 79 97 70 05 58 81 12 29 91 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912) 1(nnN上三角上三角下三角下三角對(duì)角矩陣對(duì)角矩陣特征：特征：所有的非零元素集中在以所有的非零元素集中在以主對(duì)角線(xiàn)主對(duì)角線(xiàn)為中心的帶狀區(qū)域中，為中心的帶狀區(qū)域中， 即

20、除了主對(duì)角線(xiàn)和主對(duì)角線(xiàn)相鄰兩即除了主對(duì)角線(xiàn)和主對(duì)角線(xiàn)相鄰兩側(cè)的若干條對(duì)角線(xiàn)上的元素之外，側(cè)的若干條對(duì)角線(xiàn)上的元素之外，其余元素皆為零。其余元素皆為零。壓縮存儲(chǔ)的辦法：壓縮存儲(chǔ)的辦法： 只存對(duì)角線(xiàn)以及相鄰兩側(cè)的若干只存對(duì)角線(xiàn)以及相鄰兩側(cè)的若干條對(duì)角線(xiàn)上的元素。條對(duì)角線(xiàn)上的元素。存存三對(duì)角矩陣三對(duì)角矩陣所需的空間：所需的空間：1 11 10 00 00 02 23 37 70 00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 9三對(duì)角矩陣三對(duì)角矩陣23 nN特征：只有特征：只有少量少量非零元素，且非非零元素，且非零元素的零元素的分布沒(méi)有規(guī)律分布沒(méi)有規(guī)律

21、。壓縮存儲(chǔ)的辦法：壓縮存儲(chǔ)的辦法： 只存非零元素。只存非零元素。所需空間：與非零元素的個(gè)數(shù)和所需空間：與非零元素的個(gè)數(shù)和存儲(chǔ)方式有關(guān)。存儲(chǔ)方式有關(guān)。稀疏矩陣稀疏矩陣1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 05.2.25.2.2 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)矩陣類(lèi)型矩陣類(lèi)型對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣三角矩陣三角矩陣三對(duì)角矩陣三對(duì)角矩陣壓縮的基本思想：壓縮的基本思想：只存有用的元素只存有用的元素由用二維數(shù)組改為用一維數(shù)組來(lái)存放由用二維數(shù)組改為用一維數(shù)組來(lái)存放說(shuō)明：說(shuō)明：按按C C語(yǔ)言中規(guī)定，下

22、標(biāo)從語(yǔ)言中規(guī)定，下標(biāo)從0 0開(kāi)始開(kāi)始不失一般性，按不失一般性，按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)存儲(chǔ)關(guān)鍵問(wèn)題關(guān)鍵問(wèn)題如何確定一維數(shù)組的大??？如何確定一維數(shù)組的大小？如何確定矩陣元素在一維數(shù)組中的位置？從如何確定矩陣元素在一維數(shù)組中的位置？從而保證對(duì)矩陣元素的隨機(jī)存取而保證對(duì)矩陣元素的隨機(jī)存取A Aijij的位置的位置 = 該元素前的元素個(gè)數(shù)該元素前的元素個(gè)數(shù)= = 所需空間所需空間12334545671 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9存儲(chǔ)下三角存儲(chǔ)下三角矩陣矩陣注意存儲(chǔ)矩陣元素注意存

23、儲(chǔ)矩陣元素的一維數(shù)組的下標(biāo)的一維數(shù)組的下標(biāo)是從是從0 0開(kāi)始開(kāi)始1 1 . . 對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣如何確定一維數(shù)組的大?。咳绾未_定一維數(shù)組的大??？2) 1( nnN設(shè)：存放下三角陣中的元素，設(shè)：存放下三角陣中的元素，則：如何確定元素則：如何確定元素A Aijij在一維數(shù)組中在一維數(shù)組中的位置？的位置？12334545671 1 2 2 3 3 4 4 5 52 2 3 3 4 4 5 5 6 63 3 4 4 5 5 6 6 7 74 4 5 5 6 6 7 7 8 85 5 6 6 7 7 8 8 9 9(1),2(1),2(A)()ijijijjiiijij Aijjjiij AALoc A

24、當(dāng)在下三角陣中當(dāng)在上三角陣中根據(jù)2. 2. 三角矩陣三角矩陣1 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912) 1(nnN1233654如何確定一維數(shù)組的大??？如何確定一維數(shù)組的大??？設(shè)：在下三角陣中，設(shè)：在下三角陣中，則：如何確定元素則：如何確定元素A Aijij在一維數(shù)在一維數(shù)組中的位置？組中的位置？(1), 2(1) 2()iijijijnnijLoc A 當(dāng)， 即下三角陣中的元素，當(dāng)，即上三角陣中的常數(shù)3.3.三對(duì)角矩陣三對(duì)角矩陣1 11 10 00 00 02 23 37 70

25、00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 923 nN如何確定一維數(shù)組的大?。咳绾未_定一維數(shù)組的大??？如何確定元素如何確定元素A Aijij在一維數(shù)組中在一維數(shù)組中的位置？的位置？1123745367589)(ijALoc在在A Aijij之前有之前有i i行行, ,共有共有3 3* *i-1i-1個(gè)非零元素個(gè)非零元素, ,在第在第i i行，行， a aijij之前有之前有j-i+1j-i+1個(gè)非零元素，個(gè)非零元素，3*i-1+(j-i+1) = 2*i+j程序員試題程序員試題2004-1 對(duì)矩陣壓縮存儲(chǔ)的主要目的是_。 A方便運(yùn)算B節(jié)省存

26、儲(chǔ)空間 C降低計(jì)算復(fù)雜度D提高運(yùn)算速度2003 將一個(gè)三對(duì)角矩陣Al.100，1.100中的元素按行存儲(chǔ)在一維數(shù)組Bl.298中，矩陣A中的元素A66,65在數(shù)組B中的下標(biāo)為_(kāi)。 A195 B196C197D1985.2.3 5.2.3 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)順序存儲(chǔ)：順序存儲(chǔ)：三元組表三元組表鏈?zhǔn)酱鎯?chǔ)：十字鏈表鏈?zhǔn)酱鎯?chǔ)：十字鏈表1.1.三元組表存稀疏矩陣三元組表存稀疏矩陣考慮：考慮：只存非零元素只存非零元素一個(gè)非零元素的必需信息有：一個(gè)非零元素的必需信息有： (i, j, aij)記錄一個(gè)稀疏矩陣的必需信息有：記錄一個(gè)稀疏矩陣的必需信息有：行數(shù)行數(shù)M，列數(shù)，列數(shù)N，非零元素個(gè)數(shù)

27、，非零元素個(gè)數(shù)T1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 0i ij jA Aijij0 00 01 10 01 12 20 04 45 51 11 13 32 21 14 43 32 26 64 43 38 8M=5N=5T=7三元組表的三元組表的C C語(yǔ)言描述語(yǔ)言描述typedef struct TriTupleNode datamaxsize; / /* *三元組表三元組表* */ / int m, n, t; ; / /* *m m行數(shù)行數(shù),n,n列數(shù)列數(shù),t,t非零元素個(gè)數(shù)非零元

28、素個(gè)數(shù)* */ / TriTupleTable; / 稀疏矩陣類(lèi)型稀疏矩陣類(lèi)型 i ij jV V#define maxsize 10000typedef int Elemtype;typedef struct /*三元組結(jié)點(diǎn)三元組結(jié)點(diǎn)*/ int i, j; /該非零元的行下標(biāo)和列下標(biāo)該非零元的行下標(biāo)和列下標(biāo) Elemtype e; / 該非零元的值該非零元的值 TriTupleNode; / 三元組類(lèi)型三元組類(lèi)型三元組表表示法：三元組表表示法：1 12 212121 13 39 93 31 1-3-33 35 514144 43 324245 52 218186 61 115156 64

29、4-7-7注意：注意：三元組表中的三元組表中的元素按行（或列）排元素按行（或列）排列。列。m=6m=6n=6n=6t=8t=8i ij jv v稀疏矩陣壓縮存儲(chǔ)的稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能缺點(diǎn)：將失去隨機(jī)存取功能1 12 23 34 45 56 67 78 80 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 05.2.45.2.4應(yīng)用舉例：應(yīng)用舉例： 稀疏矩陣的轉(zhuǎn)置稀疏矩陣的轉(zhuǎn)置1.矩陣轉(zhuǎn)置的數(shù)學(xué)解釋矩陣轉(zhuǎn)置的數(shù)學(xué)解釋 一個(gè)一個(gè)mn的矩陣的矩陣A，它的轉(zhuǎn)置，它的轉(zhuǎn)置B是一個(gè)是一個(gè)nm

30、的的矩陣，且矩陣，且aij=bji，0im，0jn。007650020060052700Aij=Bji求轉(zhuǎn)置矩陣算法求轉(zhuǎn)置矩陣算法028003600070500140M005280000007143600T用常規(guī)的二維數(shù)組表示時(shí)的算法用常規(guī)的二維數(shù)組表示時(shí)的算法 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為: O(mn) for (col=1; col=n; +col) for (row=1; row=m; +row) Tcolrow = Mrowcol;不正確！不正確?。? 1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的i i和和j j 互換互換）；）；（2 2）

31、T T的總行數(shù)的總行數(shù)m m和總列數(shù)和總列數(shù)n n與與M M值不同值不同（互換）；互換）；（3 3）重排重排三元組內(nèi)元素順序三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也按行，使轉(zhuǎn)置后的三元組也按行 （或列）為主序有規(guī)律的排列。（或列）為主序有規(guī)律的排列。上述（上述（1 1）和（）和（2 2）容易實(shí)現(xiàn)，難點(diǎn)在）容易實(shí)現(xiàn)，難點(diǎn)在（3 3）。提問(wèn)：提問(wèn)：若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的元素的行下標(biāo)和列下標(biāo)互換行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說(shuō)法正確嗎？算，這種說(shuō)法正確嗎？ 有二種實(shí)現(xiàn)方法有二種實(shí)現(xiàn)方法

32、壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置( (壓縮壓縮) )快速轉(zhuǎn)置快速轉(zhuǎn)置( (1, 2, 121, 2, 12) )( (1, 3, 91, 3, 9 ) )(3, 1, -3)(3, 1, -3)(3, 5, 14)(3, 5, 14)(4, 3, (4, 3, 24)24)(5, 2, 18)(5, 2, 18)(6, 1, 15)(6, 1, 15)(6, 4, -7)(6, 4, -7)(1, 3, -3)(1, 3, -3)(1, 6, 15)(1, 6, 15)( (2, 1, 122, 1, 12) )(2, 5, 18)(2, 5, 18)( (3, 1, 93, 1, 9) )(3, 4, 24

33、)(3, 4, 24)(4, 6, -7)(4, 6, -7)(5, 3, 14)(5, 3, 14)三三元元組組表表M.data三三元元組組表表T.data轉(zhuǎn)置后轉(zhuǎn)置后0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M=0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0T=?2.2.利用三元組表實(shí)現(xiàn)轉(zhuǎn)置利用三元組表實(shí)現(xiàn)轉(zhuǎn)置思想一：直接交換思想一：直接交換a.data中中i和和j的內(nèi)容的內(nèi)容 問(wèn)題：?jiǎn)栴}

34、：b.data是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B 解決方法：重新排列解決方法：重新排列B中三元組的順序。中三元組的順序。0 02 25 50 03 30 00 04 40 00 00 06 6i ij jA Aijij0 01 12 20 02 25 51 11 13 32 21 14 43 32 26 6M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6i ij jB Bijij1 10 02 22 20 05 51 11 13 31 12 24 42 23 36 6Aij=Bjii ij jB Bijij1 10 02

35、 21 11 13 31 12 24 42 20 05 52 23 36 6ji 按按i i排序排序M=2N=4T=5行優(yōu)先行優(yōu)先列優(yōu)先列優(yōu)先b.mb.m= =a.na.n; ; b.nb.n= =a.ma.m; ; b.tb.t= =a.ta.t; ; / /* *基本信息的賦值基本信息的賦值* */ / /* *按交換按交換i i、j j的方式給的方式給B B的三元組賦值的三元組賦值* */ /for ( i=0; ifor ( i=0; ib.tb.t; i+ ) ; i+ ) b.datai.ib.datai.i= =a.datai.ja.datai.j; ; b.datai.jb.d

36、atai.j= =a.datai.ia.datai.i; ; b.datai.eb.datai.e= =a.datai.ea.datai.e;/ /* *掃描掃描B B，按，按i i排序排序* */ /i ij jA Aijij0 01 12 20 02 25 51 11 13 32 21 14 43 32 26 6M=4N=2T=5i ij jB Bijij1 10 02 22 20 05 51 11 13 31 12 24 42 23 36 6i ij jB Bijij1 10 02 21 11 13 31 12 24 42 20 05 52 23 36 6ji 按按i i排序排序M=2N

37、=4T=5思想二：在思想二：在A A中按列序找中按列序找三元組，寫(xiě)入三元組，寫(xiě)入B BB B的行優(yōu)先即的行優(yōu)先即A A的列優(yōu)先的列優(yōu)先對(duì)對(duì)B B的第的第colcol列列 ，掃描掃描三元組表三元組表a.dataa.data，找出所有列號(hào)等于，找出所有列號(hào)等于colcol的三元組，將它們的行號(hào)和列號(hào)互換后依次放入的三元組，將它們的行號(hào)和列號(hào)互換后依次放入b.datab.data中，即可得到中，即可得到B B的按行優(yōu)先的壓縮存儲(chǔ)表示。的按行優(yōu)先的壓縮存儲(chǔ)表示。0 02 25 50 03 30 00 04 40 00 00 06 6i ij jA Aijij0 01 12 20 02 25 51 11

38、 13 32 21 14 43 32 26 6M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6Aij=Bjii ij jB Bijij1 10 02 21 11 13 31 12 24 42 20 05 52 23 36 6M=2N=4T=5col=0，沒(méi)有匹配的三元組，沒(méi)有匹配的三元組col=1，找到，找到2，3，4col=2，找到，找到5，6 思路：思路：反復(fù)掃描反復(fù)掃描A.dataA.data中的中的列序列序，從小到大從小到大依次進(jìn)行轉(zhuǎn)置。依次進(jìn)行轉(zhuǎn)置。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18

39、6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8A7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j e0 1 2 3 4 5 6 7 8Bqppppppppqqqqppppppppcol=1col=2qqqVoid transmatrix(tripletable a,tripletable &b) int pa, pb, col; b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的賦值基本信息的賦值*/ if(b.t=0) printf(“A=0n”); retur

40、n 0; /*無(wú)非零元素?zé)o非零元素*/ pb=0; /*pb指向三元組表指向三元組表B中的當(dāng)前位置中的當(dāng)前位置*/ for(col=0; cola.n; col+) /*按列按列col掃描表掃描表A*/ for(pa=0; pa=a.t; pa+) /*pa指向表指向表A中的當(dāng)前位置中的當(dāng)前位置*/ /*找所有列號(hào)等于找所有列號(hào)等于col的三元組，的三元組，i,j互換寫(xiě)放入互換寫(xiě)放入B*/ if(a.datapa.j=col) b.datapb.i=a.datapa.j; b.datapb.j=a.datapa.i; b.datapb.e=a.datapa.e; pb+; 1 1、主要時(shí)間消耗

41、在主要時(shí)間消耗在查找查找A.datapa.jA.datapa.j= =colcol的元素的元素，由兩重循，由兩重循環(huán)完成環(huán)完成: : for(col=0; cola.n; col+) 循環(huán)次數(shù)循環(huán)次數(shù)n for(pa=0; pa=a.t; pa+) 循環(huán)次數(shù)循環(huán)次數(shù)t所以該算法的時(shí)間復(fù)雜度為所以該算法的時(shí)間復(fù)雜度為O(O(n*t) ) - -即即M M的列數(shù)與的列數(shù)與M M中非零元素的個(gè)數(shù)之中非零元素的個(gè)數(shù)之積積最壞情況最壞情況：M M中全是非零元素，此時(shí)中全是非零元素，此時(shí)t=mt=m* *n n， 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(O(n2 2*m ) )注：注：若若M M中基本上是非零元素時(shí)

42、，即使用中基本上是非零元素時(shí)，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法非壓縮傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過(guò)是的時(shí)間復(fù)雜度也不過(guò)是O(O(n*m) )結(jié)論：結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。壓縮轉(zhuǎn)置算法不能濫用。前提前提：僅適用于非零元素個(gè)數(shù)很少（即僅適用于非零元素個(gè)數(shù)很少（即t tm m* *n n）的情況。的情況。算法的效率分析算法的效率分析三三元元組組表表A.data三三元元組組表表B.data(1, 3, -3)(2 ,1, 12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)( (1, 2, 121, 2, 12) )( (1, 3,

43、91, 3, 9 ) )(3, 1, -3)(3, 1, -3)(3, 5, 14)(3, 5, 14)(4, 3, 24)(4, 3, 24)(5, 2, 18)(5, 2, 18)(6, 1, 15)(6, 1, 15)(6, 4, -7)(6, 4, -7)基本思想：基本思想：在在A A中按行序找三元組，確定該三元組在中按行序找三元組，確定該三元組在B B中的中的位置，寫(xiě)入位置，寫(xiě)入B B中適當(dāng)位置。中適當(dāng)位置。 即依次即依次把把A.dataA.data中的元素直接送入中的元素直接送入B.dataB.data的恰當(dāng)位置上的恰當(dāng)位置上 p0123 q 2 4思想三：思想三：快速轉(zhuǎn)置快速轉(zhuǎn)置

44、關(guān)鍵問(wèn)題：如何確定每個(gè)三元組在關(guān)鍵問(wèn)題：如何確定每個(gè)三元組在B B中的位置中的位置A A中某個(gè)三元組在中某個(gè)三元組在B B的中位置的中位置= = 每列的第一個(gè)非零元素在數(shù)組每列的第一個(gè)非零元素在數(shù)組B B中應(yīng)有的位置中應(yīng)有的位置 + + 每一列在它之前非零元素的個(gè)數(shù)每一列在它之前非零元素的個(gè)數(shù)注意：注意：根據(jù)根據(jù)M.dataM.data的特征，每列第一個(gè)非零元素必的特征，每列第一個(gè)非零元素必 定先被掃描到。定先被掃描到。為了求得每列的第一個(gè)非零元素在數(shù)組為了求得每列的第一個(gè)非零元素在數(shù)組B B中應(yīng)有的位置需先求中應(yīng)有的位置需先求1.1. 矩陣矩陣M M中的每一列中非零元的個(gè)數(shù)中的每一列中非零元

45、的個(gè)數(shù)令令：A A中的列變量用中的列變量用colcol表示；表示； cnumcnum colcol ：存放存放A A中第中第colcol 列中非列中非0 0元素個(gè)數(shù)元素個(gè)數(shù) cposcpos colcol ：存放存放A A中第中第colcol列的第一個(gè)非列的第一個(gè)非0 0元素的位置元素的位置 （即（即A.dataA.data中待計(jì)算的中待計(jì)算的“恰當(dāng)恰當(dāng)”位置所需參考點(diǎn)）位置所需參考點(diǎn)）colcol123456cnumcolcnumcol 222110cposcolcposcol 0規(guī)律規(guī)律: cpos00 cposcol cposcol-1 + cnumcol-10 12 9 0 0 00

46、0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M= 2 col 1 2 3 4 5 6 4 8 7 6 6 6 8 1 2 12 1 3 9 3 1 -3 3 5 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8M6 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 5 3 14 pppppppp4629753colcol1 12 23 34 45 56 6cnumcolcnumcol 2 22 22 21 1

47、1 10 0cposcolcposcol 1 13 35 57 78 89 9i j v0 1 2 3 4 5 6 7 8Tvoid fasttranstri(tritupletable a, tritupletable &b) int col；/*當(dāng)前列號(hào)當(dāng)前列號(hào)*/ int pa,pb; /*分別表示分別表示a,b的當(dāng)前位置的當(dāng)前位置*/ int cnumn, cposn; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); return 0; for(col=0;cola.n;col+) cnumcol=0; /每列元素的個(gè)數(shù)

48、初始化每列元素的個(gè)數(shù)初始化 /*統(tǒng)計(jì)統(tǒng)計(jì)a中每列非零元素的個(gè)數(shù)；中每列非零元素的個(gè)數(shù)；*/ for(pa=0; paa.t; pa+) col=a.datapa.j; cnumcol+; /*由遞推關(guān)系計(jì)算由遞推關(guān)系計(jì)算cpos的值的值*/ cpos0=0; for(col=1;col=a.n;col+) cposcol = cposcol-1 + cnumcol-1; /*掃描掃描a，將元素交換，將元素交換i,j寫(xiě)入寫(xiě)入b*/ for( pa=0; paa.t; pa+ ) col = a.datapa.j; pb = cposcol; b.datapb.i = a.datapa.j; b.

49、datapb.j = a.datapa.i; b.datapb.v = a.datapa.v; cposcol+; /修改向量表中列坐標(biāo)值，供同一修改向量表中列坐標(biāo)值，供同一列下一非零元素定位之用！列下一非零元素定位之用！ 1.1. 與常規(guī)算法相比，增加了與常規(guī)算法相比，增加了2 2個(gè)長(zhǎng)度為列長(zhǎng)的輔助數(shù)個(gè)長(zhǎng)度為列長(zhǎng)的輔助數(shù)組組( (cnum 和和cpos ）?？焖俎D(zhuǎn)置算法的效率分析快速轉(zhuǎn)置算法的效率分析：2.2. 從時(shí)間上，此算法用了從時(shí)間上，此算法用了4 4個(gè)并列的單循環(huán)，而且其個(gè)并列的單循環(huán)，而且其中前中前3 3個(gè)單循環(huán)都是用來(lái)產(chǎn)生輔助數(shù)組的。個(gè)單循環(huán)都是用來(lái)產(chǎn)生輔助數(shù)組的。 for(co

50、l = 0; col a.n; col+) 循環(huán)次數(shù)循環(huán)次數(shù)n;n; for( pa = 0; pa a.t; pa +) 循環(huán)次數(shù)循環(huán)次數(shù)t;t; for(col = 1; col a.n; col+) 循環(huán)次數(shù)循環(huán)次數(shù)n;n; for( pa=0; pa a.t ; pa + ) 循環(huán)次數(shù)循環(huán)次數(shù)t;t; 該算法的時(shí)間復(fù)雜度該算法的時(shí)間復(fù)雜度( (n n* *2)+(t2)+(t* *2)=2)=O(O(n+tn+t） 傳統(tǒng)轉(zhuǎn)置：傳統(tǒng)轉(zhuǎn)置：O(O(m m* *n n) ) 壓縮轉(zhuǎn)置：壓縮轉(zhuǎn)置：O(O(m m* *t t) ) 壓縮快速轉(zhuǎn)置：壓縮快速轉(zhuǎn)置：O(O(n+tn+t) )犧牲空間效

51、率換時(shí)犧牲空間效率換時(shí) 間效率。間效率。小結(jié)：小結(jié)：討論：討論：最壞情況是最壞情況是t=nt=n* *m m( (即矩陣中全部是非零元素），即矩陣中全部是非零元素），而此時(shí)的時(shí)間復(fù)雜度也只是而此時(shí)的時(shí)間復(fù)雜度也只是O(O(m m* *n n) )，并未超過(guò)傳統(tǒng)轉(zhuǎn)并未超過(guò)傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。置算法的時(shí)間復(fù)雜度。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)o 帶行指針向量的單鏈表表示Y每行的非零元用一個(gè)單鏈表存放 Y設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無(wú)非零元，則指針為空Y表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類(lèi)型定義typedef struct node int col; int val; struct node *lin

52、k;JD;typedef struct node *TD;0200000000000210010070003A1 35 73 -11 -12 -24 2需存儲(chǔ)單元個(gè)數(shù)為3t+mo 十字鏈表Y設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元Y結(jié)點(diǎn)定義tpedef struct node int row,col,val; struct node *down, *right;JD;row col valdownright34008000450003A113418225234廣義表是第廣義表是第2 2章提到的線(xiàn)性表的推廣。線(xiàn)性表中的元素僅限于章提到的線(xiàn)性表的推廣。線(xiàn)性表中的元素僅限于原子項(xiàng)，即不

53、可以再分，而廣義表中的元素既可以是原子項(xiàng)原子項(xiàng)，即不可以再分，而廣義表中的元素既可以是原子項(xiàng)，也可以是子表（另一個(gè)線(xiàn)性表）。，也可以是子表（另一個(gè)線(xiàn)性表）。5.3 5.3 廣義表廣義表5.4 5.4 廣義表的定義廣義表的定義廣義表是線(xiàn)性表的推廣，也稱(chēng)為列表（廣義表是線(xiàn)性表的推廣，也稱(chēng)為列表（lists）。廣義表中元素。廣義表中元素既可以是原子類(lèi)型，也可以是列表。既可以是原子類(lèi)型，也可以是列表。記為：記為： LS = ( a1 , a2 , ， an ) 廣義表名廣義表名 a1是表頭是表頭(Head） （ a2 ,an ）是表尾是表尾 (Tail)1、定義：、定義：n n是表長(zhǎng)是表長(zhǎng) ai可以是

54、單個(gè)元素，也可以是廣義表，分別稱(chēng)為廣義表可以是單個(gè)元素，也可以是廣義表，分別稱(chēng)為廣義表LS的的原原子子和和子表子表；第一個(gè)第一個(gè)元素是表頭元素是表頭，而其余元素組成的，而其余元素組成的表表稱(chēng)為表尾稱(chēng)為表尾； 所以任何一個(gè)非空表，表頭可能是原子，也可能是列表；但所以任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾表尾一定是列表一定是列表。 約定：用小寫(xiě)字母表示原子類(lèi)型，用約定：用小寫(xiě)字母表示原子類(lèi)型，用大寫(xiě)字母大寫(xiě)字母表示列表。表示列表。在廣義表中約定：在廣義表中約定：2、特點(diǎn)：、特點(diǎn)：1）次序性：）次序性：一個(gè)直接前驅(qū)和一個(gè)直接后繼一個(gè)直接前驅(qū)和一個(gè)直接后繼2）長(zhǎng)度：）長(zhǎng)度：表中表中最外層

55、最外層包含元素個(gè)數(shù)包含元素個(gè)數(shù)3）深度：）深度：當(dāng)廣義表全部用原子代替后，表當(dāng)廣義表全部用原子代替后，表中中括號(hào)的最大重?cái)?shù)括號(hào)的最大重?cái)?shù) 空表（空表（ ）的深度為）的深度為1，長(zhǎng)度為，長(zhǎng)度為0 ，原子的深度為，原子的深度為0.4）可遞歸：）可遞歸：自己可以作為自己的子表。自己可以作為自己的子表。 例例E=(a, E) 遞歸表的深度是無(wú)窮值，長(zhǎng)度是遞歸表的深度是無(wú)窮值，長(zhǎng)度是2。5）可共享）可共享: 可以為其它廣義表所共享的表?？梢詾槠渌鼜V義表所共享的表。6 6）任何一個(gè)非空廣義表）任何一個(gè)非空廣義表 LS = ( LS = ( 1, 1, 2, 2, , , n)n) 均可分解為均可分解為 表頭表頭 GetHead(LS) = 1 和和 表尾表尾 GetTa