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

1、安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)第第5章章 數(shù)組和廣義表數(shù)組和廣義表本章學(xué)習(xí)導(dǎo)讀本章學(xué)習(xí)導(dǎo)讀v 數(shù)組與廣義表可視為線性表的推廣，其特點是數(shù)據(jù)元數(shù)組與廣義表可視為線性表的推廣，其特點是數(shù)據(jù)元素仍然是一個表。本章重點討論二維數(shù)組的邏輯結(jié)構(gòu)和存素仍然是一個表。本章重點討論二維數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、特殊矩陣、矩陣的壓縮存儲，以及廣義表的邏輯儲結(jié)構(gòu)、特殊矩陣、矩陣的壓縮存儲，以及廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)等。結(jié)構(gòu)和存儲結(jié)構(gòu)等。安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)5.1 數(shù)組的定義數(shù)組的定義a00 a01 a0,n-1a10

2、a11 a1,n-1 am-1,0 am-1,1 am-1,n-1Amn=v 數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它結(jié)構(gòu)更為具有固定的上界和下界，因此，數(shù)組的處理比其它結(jié)構(gòu)更為簡單。二維數(shù)組可看成由若干個行向量組成的向量，也可以簡單。二維數(shù)組可看成由若干個行向量組成的向量，也可以看成是若干個列向量組成的向量?？闯墒侨舾蓚€列向量組成的向量。安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)5.1 數(shù)組的定義數(shù)組的定義v 二維數(shù)組可看成一個線性表二維數(shù)組可看成一個線性表A

3、=(a0，a1，ap) (p=m-1或或n-1)，其中其中aj是一個列向量形式的線性表：是一個列向量形式的線性表： aj=（a0j，a1j，am-1,j），）， 0jn-1 或或ai是一個行向量形式的線性表：是一個行向量形式的線性表： ai=（ai0，ai1，ai,n-1），）， 0im-1 a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1 a0 a1 apa0a1 ap安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)

4、學(xué)5.2 數(shù)組的順序表示與實現(xiàn)數(shù)組的順序表示與實現(xiàn)v 計算機(jī)內(nèi)存是一維的，用一維內(nèi)存來表示多維數(shù)組，就必計算機(jī)內(nèi)存是一維的，用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。通常有兩種順序存儲方式：列存放在存儲器中。通常有兩種順序存儲方式： 1. 行優(yōu)先順序行優(yōu)先順序?qū)?shù)組元素按行排列，第將數(shù)組元素按行排列，第i+1個行向量緊個行向量緊接在第接在第i個行向量后面。其存儲的線性序列為：個行向量后面。其存儲的線性序列為： a00,a01,a0,n-1,a10,a11,a1,n-1,am-1,0,

5、,am-1,n-1 2. 列優(yōu)先順序列優(yōu)先順序?qū)?shù)組元素按列排列，第將數(shù)組元素按列排列，第j+1個列向量緊個列向量緊接在第接在第j個列向量之后，其存儲的線性序列為：個列向量之后，其存儲的線性序列為： a00,a10,am-1,0,a01,a11,am-1,1,am-1,1, ,an-1,m-1 安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1 am-1,n-1 am-1,1 am-1,0 a1,n-1 a11 a10 a0,n-1 a01 a00 am-1,n-1 a1

6、,n-1 a0,n-1 am-1,1 a11 a01 am-1,0 a10 a00a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1行行優(yōu)優(yōu)先先順順序序列列優(yōu)優(yōu)先先順順序序5.2 數(shù)組的順序表示與實現(xiàn)數(shù)組的順序表示與實現(xiàn)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)v 按上述兩種方式順序存儲的數(shù)組，只要知道開始結(jié)點的地按上述兩種方式順序存儲的數(shù)組，只要知道開始結(jié)點的地址，維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單址，維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素存放地址表示為其下標(biāo)的線性

7、函數(shù)。元數(shù)，就可以將數(shù)組元素存放地址表示為其下標(biāo)的線性函數(shù)。 例如，二維數(shù)組例如，二維數(shù)組Amn按按“行優(yōu)先順序行優(yōu)先順序”存儲在內(nèi)存中，存儲在內(nèi)存中，假設(shè)每個元素占用假設(shè)每個元素占用L個存儲單元。個存儲單元。 元素元素aij的存儲地址應(yīng)是數(shù)組的基地址加上排在的存儲地址應(yīng)是數(shù)組的基地址加上排在aij前面的前面的元素所占用的單元數(shù)。因為元素所占用的單元數(shù)。因為aij位于第位于第i+1行、第行、第j+1列，前面列，前面i行一共有行一共有in個元素，第個元素，第i+1行上行上aij前面又有前面又有j個元素，故它前個元素，故它前面一共有面一共有in+j個元素，因此，個元素，因此，aij的地址計算函數(shù)為

8、：的地址計算函數(shù)為： LOC(i,j)=LOC(0,0)+in+jL5.2 數(shù)組的順序表示與實現(xiàn)數(shù)組的順序表示與實現(xiàn)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)v 在科學(xué)與工程計算問題中，矩陣是一種常用的數(shù)學(xué)對象，在科學(xué)與工程計算問題中，矩陣是一種常用的數(shù)學(xué)對象，可以將一個矩陣描述為一個二維數(shù)組。如果在矩陣中非零元可以將一個矩陣描述為一個二維數(shù)組。如果在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，實際上占用了許多單元去存儲重復(fù)的非零元素或零元素，這實際上占用了許多單元去存儲重復(fù)的非零元素或零元素

9、，這對高階矩陣會造成極大的浪費(fèi)，為了節(jié)省存儲空間，對高階矩陣會造成極大的浪費(fèi)，為了節(jié)省存儲空間， 可以對可以對這類矩陣進(jìn)行壓縮存儲：這類矩陣進(jìn)行壓縮存儲：即為多個相同的非零元素只分配一即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間個存儲空間；對零元素不分配空間。5.3 矩陣的壓縮存儲矩陣的壓縮存儲安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)v 對稱矩陣對稱矩陣 若若n階矩陣階矩陣A中的數(shù)據(jù)元素滿足下述性質(zhì)中的數(shù)據(jù)元素滿足下述性質(zhì)aij=aji (1i，jn)稱稱A為為n階對稱矩陣；因階對稱矩陣；因aij與與aji相等，二者只需分配一個存儲相等，二者只需

10、分配一個存儲單元。這樣，可將單元。這樣，可將nn個存儲單元壓縮到個存儲單元壓縮到n(n+1)/2個單元。個單元。 5.3.1 特殊矩陣特殊矩陣1 3 5 73 2 6 95 6 3 87 9 8 4a11 a12 . . a1na21 a22 . . a2n .an1 an2 . ann安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 為節(jié)約存儲空間，只存對角線及對角線以為節(jié)約存儲空間，只存對角線及對角線以上或以下的元素。假設(shè)以行主序存儲下三角上或以下的元素。假設(shè)以行主序存儲下三角（包括對角線）中的元素。（包括對角線）中的元素。 以一維數(shù)組以一維數(shù)組san(n+1)/2

11、作為作為n階對稱矩陣階對稱矩陣A的存儲結(jié)構(gòu)，則的存儲結(jié)構(gòu)，則sak和矩陣元和矩陣元aij之間存在之間存在著一一對應(yīng)的關(guān)系：著一一對應(yīng)的關(guān)系： i(i-1)/2+j-1 當(dāng)當(dāng)ij j(j-1)/2+i-1 當(dāng)當(dāng)ijv 對稱矩陣對稱矩陣a11a21a22a31a32an,1an,n01234n(n+1)/2-1kk=安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)v 對稱矩陣對稱矩陣 若若ij，則，則aij在下三角形中。在下三角形中。 aij之前的之前的i-1行（從第行（從第1行到第行到第i-1行）一共有行）一共有1+2+i-1=i(i-1)/2個元素，在第個元素，在第i行

12、上，行上，aij之前之前恰有恰有j-1個元素，因此有：個元素，因此有： k=i (i-1)/2+j-1 若若i1時，元素時，元素aij=0。 主對角線元素主對角線元素aii所在位置分別是一維數(shù)組下標(biāo)為所在位置分別是一維數(shù)組下標(biāo)為0，3，6，9，。而主對角線上面元素。而主對角線上面元素ai,i+1所在位置分別是一維數(shù)組所在位置分別是一維數(shù)組下標(biāo)為下標(biāo)為1，4，7，10，。 主對角線下面的那條對角線主對角線下面的那條對角線 ai+1,i所在位置分別是一維數(shù)組下標(biāo)為所在位置分別是一維數(shù)組下標(biāo)為2，5，8，11，。 3(i-1)+1 當(dāng)當(dāng)i=j-1 3(i-1) 當(dāng)當(dāng)i=j 3(i-1)-1 當(dāng)當(dāng)i=

13、j+1k=安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 設(shè)矩陣設(shè)矩陣Amn中有中有s個非零元素，若個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)數(shù)(即即smn)，則稱，則稱A為稀疏矩陣。為稀疏矩陣。 稀疏矩陣的三元組表表示稀疏矩陣的三元組表表示 在存儲稀疏矩陣時，為了節(jié)省存儲單元，使用壓縮存儲在存儲稀疏矩陣時，為了節(jié)省存儲單元，使用壓縮存儲方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置儲非零元素的同時，還必須同時記下它所在的行和列的位置(i，j)

14、。一個三元組。一個三元組(i，j，aij)唯一確定了矩陣唯一確定了矩陣A的一個非零元的一個非零元素。因此，稀疏矩陣可由表示非零元素的三元組及其行列數(shù)素。因此，稀疏矩陣可由表示非零元素的三元組及其行列數(shù)唯一確定。唯一確定。5.3.2 稀疏矩陣稀疏矩陣安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)例如：例如： M由由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩陣維數(shù)和矩陣維數(shù)(6,7)唯一確定唯一確定。5.3.2 稀疏矩陣稀疏矩陣 0 12 9 0 0 0

15、0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0M =安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 三元組順序表三元組順序表 假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法陣的一種壓縮存儲方法三元順序表。三元順序表。 # define MAXSIZE 12500 /非零元個數(shù)最大值非零元個數(shù)最大值 typedef struct int i, j; /行下標(biāo)和列下標(biāo)行下標(biāo)和列下標(biāo)ElemType e

16、; Triple; typedef structTriple dataMAXSIZE+1; /非零元三元組表非零元三元組表int mu,nu,tu; /行數(shù)、列數(shù)、非零元個數(shù)行數(shù)、列數(shù)、非零元個數(shù) TSMatrix;v 稀疏矩陣的存儲稀疏矩陣的存儲安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)以矩陣的轉(zhuǎn)置為例，說明稀疏矩陣的存儲。以矩陣的轉(zhuǎn)置為例，說明稀疏矩陣的存儲。o 一個一個mn的矩陣的矩陣M，它的轉(zhuǎn)置，它的轉(zhuǎn)置T是一個是一個nm的矩陣，且的矩陣，且T（i，j）=M（j，i），），1 i n，1 j m，即，即M的行是的行是T的的列，列，T的列是的列是M的行。的行

17、。o 將將M轉(zhuǎn)置為轉(zhuǎn)置為T，就是將，就是將M的三元組表的三元組表M.data置換為表置換為表T的三的三元組表元組表T.data，如果只是簡單地交換，如果只是簡單地交換M.data中中i和和j的內(nèi)容，那的內(nèi)容，那么得到的么得到的T.data將是一個按列優(yōu)先順序存儲的稀疏矩陣將是一個按列優(yōu)先順序存儲的稀疏矩陣T，要，要得到按行優(yōu)先順序存儲的得到按行優(yōu)先順序存儲的T.data，就必須重新排列三元組的，就必須重新排列三元組的順序。順序。v 矩陣的轉(zhuǎn)置矩陣的轉(zhuǎn)置 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0

18、 015 0 0 -7 0 0 0M = 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0 0T =三三元元組組表表M.data(6, 4, -7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)三三元元組組表表T.data(4, 6, -7)(1, 6, 15)(2, 5, 18)(3, 4, 24)(5, 3, 14)(1, 3, -3)(3, 1, 9 )(2, 1, 12

19、)1234567812345678安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 由于由于M的列是的列是T的行，按的行，按M.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣矩陣T的三元組表的三元組表T.data必定是按行優(yōu)先存放。必定是按行優(yōu)先存放。思路：反復(fù)掃描思路：反復(fù)掃描M.data中的列序，從小到大依次進(jìn)行轉(zhuǎn)置。中的列序，從小到大依次進(jìn)行轉(zhuǎn)置。v 矩陣轉(zhuǎn)置方法一矩陣轉(zhuǎn)置方法一(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7) (5, 3, 14)(6, 4,

20、-7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)三三元元組組表表a.data三三元元組組表表b.data1234567812345678 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0 0T =安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) Status TransPoseSMatrix(TSMatrix M, TSMatrix &N) T.mu

21、=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; for(col=1; col=M.nu; col+) for(p=1; p=M.tu; p+) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.value=M.datap.value; q+; return OK; /TranposeSMatrix;v 矩陣轉(zhuǎn)置算法矩陣轉(zhuǎn)置算法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)678012121139231-33361444324552186611

22、5764-78M.datai j v7 6 8 0 1 2 3 4 5 6 7 8T.datai j vppppppppppppppppqqqqq1 3 -31 6 152 1 122 5 183 1 93 4 2446 -76 3 14col=1col=2v 矩陣的轉(zhuǎn)置方法一的演示矩陣的轉(zhuǎn)置方法一的演示安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 依次把依次把M.data中的元素直接送入中的元素直接送入T.data的恰當(dāng)位置上（即的恰當(dāng)位置上（即M三元組的三元組的p指針不回溯）。指針不回溯）。v 矩陣轉(zhuǎn)置方法二矩陣轉(zhuǎn)置方法二(1, 3, -3)(2 ,1, 12)

23、(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)(6, 4, -7)(6, 1, 15)(5, 2, 18)(4, 3, 24)(3, 5, 14)(3, 1, -3)(1, 3, 9 )(1, 2, 12)1234567812345678安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)設(shè)兩個數(shù)組設(shè)兩個數(shù)組numcol：表示矩陣：表示矩陣M中第中第col列中非零元個數(shù)列中非零元個數(shù)cpotcol：指示：指示M中第中第col列第一個非零元在列第一個非零元在T.data中位置中位置顯然有：顯然有：cpot

24、1=1; cpotcol=cpotcol-1+numcol-1; (1col M.nu)v 矩陣轉(zhuǎn)置具體實現(xiàn)矩陣轉(zhuǎn)置具體實現(xiàn)1357889colnumcolcpotcol12223241506170 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0M =安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)Status FastTransposeSMatrix（TSMatirx M, TSMatirx &N） T.mu = M.nu ;T .nu =

25、 M.mu ; T.tu = M.tu ; if ( T.tu ) for(col = 1; col =M.nu; col+) numcol =0; for( i = 1; i =M.tu; i +) col =M.data i .j ; +num col ; cpot 1 =1; for(col = 2; col =M.nu; col+) cpotcol =cpotcol-1+num col-1 ; for( p =1; p =M.tu ; p + ) col =M.data p . j ; q =cpot col ; T.dataq.i = M.datap. j; T.dataq.j =

26、M.datap. i; T.dataq. value = M.datap. value; return OK; ;v 矩陣轉(zhuǎn)置算法矩陣轉(zhuǎn)置算法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)v 實現(xiàn)過程演示實現(xiàn)過程演示4629753colnumcolcpotcol112232352471580681790678012121139231-333614443245521866115764-78i j v 0 1 2 3 4 5 6 7 8i j v7 6 8pppppppp1 3 -31 6 152 1 122 5 183 1 93 4 2446 -76 3 14安安安安安

27、安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)v 廣義表是線性表的推廣。即廣義表中放松對表元素的原子限制，廣義表是線性表的推廣。即廣義表中放松對表元素的原子限制，容許它們具有其自身結(jié)構(gòu)。容許它們具有其自身結(jié)構(gòu)。v 廣義表是廣義表是n(n0)個元素個元素a1，a2，ai，an的有限序列。的有限序列。 其中：其中： ai或者是原子或者是原子(單個元素單個元素)或者是一個廣義表。或者是一個廣義表。 廣義表記作廣義表記作LS=(a1，a2，ai，an )，LS是廣義是廣義 表的名字，表的名字，n為它的長度。為它的長度。 若若ai是廣義表，則稱它為是廣義表，則稱它為LS的子表。的子表。

28、注意：注意： 廣義表通常用圓括號括起來，用逗號分隔其中的元素。廣義表通常用圓括號括起來，用逗號分隔其中的元素。 若廣義表若廣義表LS非空非空(n1)，則，則a1是是LS的表頭，其余元素的表頭，其余元素 組成的表組成的表(a2，a3，an)稱為稱為LS的表尾。的表尾。 廣義表是遞歸定義的。廣義表是遞歸定義的。5.4 廣義表的定義廣義表的定義安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)1. A=( )A是一個空表，其長度為零。是一個空表，其長度為零。2. B=(e)表表B只有一個原子只有一個原子e，B的長度為的長度為1。3. C=(a,(b,c,d)表表C的長度為的長度

29、為2，兩個元素分別為原子，兩個元素分別為原子a和子表和子表(b,c,d)。4. D=(A,B,C)表表D的長度為的長度為3，三個元素都是廣義表。顯，三個元素都是廣義表。顯然，將子表的值代入后，則有然，將子表的值代入后，則有 D=( ),(e),(a,(b,c,d)。5. E=(a,E)這是一個遞歸的表，它的長度為這是一個遞歸的表，它的長度為2，E相當(dāng)于相當(dāng)于一個無限的廣義表一個無限的廣義表E=(a,(a,(a,(a,)。v 廣義表表示廣義表表示安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 由表頭、表尾的定義可知：任何一個非空廣義表其表頭可由表頭、表尾的定義可知：任何

30、一個非空廣義表其表頭可能是原子，也可能是廣義表，而其表尾必定是廣義表。能是原子，也可能是廣義表，而其表尾必定是廣義表。 A=(e) 則：則：gethead(A)=e gettail(A)=( ) B=(a,b),c,d,e,f) 則：則：gethead(B)=(a,b) gettail(B)=(c,d,e,f) C = (a,(b,c,d) 則：則： gethead(C)= a gettail(C)= (b,c,d) 注意：廣義表注意：廣義表( )和和( ( ) )不同。前者是長度為不同。前者是長度為0的空表，對其的空表，對其不能做求表頭的和表尾的運(yùn)算；而后者是長度為不能做求表頭的和表尾的運(yùn)算

31、；而后者是長度為1的非空表的非空表(只不過該表中唯一的一個元素是空表只不過該表中唯一的一個元素是空表)。對其可進(jìn)行分解，。對其可進(jìn)行分解，得到表頭和表尾均為空表得到表頭和表尾均為空表( )。v 廣義表表示廣義表表示安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大學(xué)學(xué)學(xué)學(xué)學(xué)學(xué) 由于廣義表由于廣義表(a1,a2,a3, ,an)中的數(shù)據(jù)元素可以具有不同的中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)結(jié)構(gòu)(或是原子，或是廣義表或是原子，或是廣義表)，因此，難以用順序存儲結(jié)構(gòu)，因此，難以用順序存儲結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個數(shù)據(jù)元素可用一個結(jié)點表示，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個數(shù)據(jù)元素可用一個結(jié)點表示。表示。 需要兩種結(jié)構(gòu)的結(jié)點：一種是表結(jié)點，一種是原子結(jié)點。需要兩種結(jié)構(gòu)的結(jié)點：一種是表結(jié)點，一種是原子結(jié)點。 下面介紹兩種廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。下面介紹兩種廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。5.5 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)安安安安安安徽徽徽徽徽徽理理理理理理工工工工