數(shù)據(jù)結(jié)構(gòu)版全集

第五章數(shù)組和廣義表本章學習另外兩種特殊的線性表，數(shù)組和廣義表。數(shù)組是一個數(shù)據(jù)元素的集合，元素之間具有線性關(guān)系，但是，元素可以參與多個線性關(guān)系（前面講的都是參與一個）；廣義表是一個數(shù)據(jù)元素的集合，元素之間具有線性關(guān)系，但其前驅(qū)后繼可以是一般元素，也可以是一個表。第五章

數(shù)組和廣義表5.1數(shù)組5.2矩陣的壓縮存儲5.3廣義表學習要點1了解數(shù)組的邏輯結(jié)構(gòu)2了解數(shù)組的兩種存儲結(jié)構(gòu)；3掌握數(shù)組在以行為主序的方式存儲時，數(shù)組元素地址的計算方法；基本內(nèi)容數(shù)組的概念及基本操作數(shù)組的順序存貯結(jié)構(gòu)5．1數(shù)組數(shù)組的概念數(shù)組是我們十分熟悉的一種數(shù)據(jù)類型，幾乎所有的程序設(shè)計語言都包含數(shù)組。本書在討論各種數(shù)據(jù)結(jié)構(gòu)的順序存儲分配時，也都是借用一維數(shù)組來描述它們的存儲結(jié)構(gòu)。這一章將從數(shù)據(jù)結(jié)構(gòu)的角度，簡單討論數(shù)組的邏輯結(jié)構(gòu)及其存儲方式，另外書上還給出了數(shù)組的基本操作算法，如：數(shù)組的初始化，讀取指定下標的數(shù)組元素算法，給指定下標的數(shù)組元素賦值等操作算法；

注:數(shù)組的基本操作算法,不是本課程要求掌握的內(nèi)容數(shù)組(Array)：簡單說是數(shù)據(jù)類型相同的一組數(shù)據(jù)元素的有序集合。元素在集合中的序是由一組稱做“下標”的值確定的，一個數(shù)據(jù)元素稱為一個數(shù)組元素。

一個數(shù)據(jù)元素的位置由多個下標值確定，即參與多個線性關(guān)系，每個關(guān)系上都有前驅(qū)、后繼！即在每個關(guān)系中，每個元素aij都有且僅有一個直接前趨，都有且僅有一個直接后繼。

數(shù)組的維數(shù)：確定一個數(shù)據(jù)元素在集合中位置的下標的個數(shù)。

以二維數(shù)組為例：二維數(shù)組中的每個元素都受兩個線性關(guān)系的約束Amn=a11a12a1na21a22a2nam1am2amn在行關(guān)系中

aij直接前趨是aij-1

aij直接后繼是aij+1在列關(guān)系中

aij直接前趨是ai-1j

aij直接后繼是ai+1j此處未考慮第一個和最后一個元素注意:(1)數(shù)組中每個數(shù)據(jù)元素受多個線性關(guān)系制約，元素在每個線性關(guān)系上都有前驅(qū)、后繼。(2)一個N維數(shù)組N可以看作一個線性表，其每個數(shù)據(jù)元素是一個N-1維的數(shù)組。數(shù)組的基本操作初始化操作InitArray(&A,n,bound1,…,boundn)功能：參數(shù)合法，構(gòu)造數(shù)組A，并返回OK；銷毀操作DestroyArray(&A)功能：銷毀數(shù)組A3讀元素操作Value(A,&e,index1,…,indexn)功能：若指定下標不越界，讀指定下標的元素，用e返回，并返回OK；寫元素操作Assign(A,e,index1,…,indexn)功能：若指定下標不越界，將e賦值給A指定的下標元素，并返回OK；數(shù)組的順序存貯結(jié)構(gòu)

一般來說，數(shù)組一旦定義，其元素的個數(shù)和元素之間的相互關(guān)系不再發(fā)生變化，即對數(shù)組一般不進行插入和刪除操作。因此，數(shù)組采用順序存儲結(jié)構(gòu)是十分自然的事情計算機的內(nèi)存空間是一個一維結(jié)構(gòu)，而二維以上的數(shù)組是多維結(jié)構(gòu)。因此，用一組連續(xù)的存儲單元存放數(shù)組元素，就有次序約定的問題。以二維數(shù)組為例，它有兩種方式：一種是以行為主序的方式，另一種是以列序為主序的方式。行為主序方式是先存儲數(shù)組的第一行元素，再存儲第二行元素…；而列序為主序方式是先存儲數(shù)組的第一列元素，再存儲第二列元素…；在眾多的程序設(shè)計語言中，以行序為主序方式的有PASCAL、COBOL、C及擴展BASIC等，以列序為主序方式的有FORTRAN語言。設(shè)A是一個具有m行n列的元素的二維數(shù)組（借助矩陣形式給出比較直觀）如下：Amn=以行為主序的方式：a00a01a0n-1a10a11a1n-1am-10am-11am-1n-101n-1nn+12n-1mn-1a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1以列為主序的方式：a00a10am-10a01a11am-11a0n-1a1n-1am-1n-101m-1mm+12m-1nm-1a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1數(shù)組元素存儲地址的計算

無論采用哪種存儲方式，一旦確定了存儲映象的首地址。數(shù)組中任意元素的存儲地址都可以確定。

Amn一維數(shù)組存儲方式352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0

a+i*la

二維數(shù)組假設(shè)二維數(shù)組A每個元素占用k個存儲單元，Loc(aij)為元素aij的存儲地址，Loc(a00)是a00存儲位置,也是二維數(shù)組A的基址。若以行序為主序的方式存儲二維數(shù)組，則元素aij的存儲位置可由下式確定：

若以列序為主序的方式存儲二維數(shù)組，則元素aij的存儲位置可由下式確定：

Loc(aij)=Loc(a00)+（mj+i)kLoc(aij)=Loc(a00)+（ni+j)k行向量下表i列向量下表j頁向量下標i行向量下標j列向量下標k三維數(shù)組LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3

)*l

前i1頁總元素個數(shù)第i1頁的前i2行總元素個數(shù)各維元素個數(shù)為m1,m2,m3.下標為i1,i2,i3的數(shù)組元素的存儲地址：（按頁/行/列存放）

n維數(shù)組各維元素個數(shù)為m1,m2,m3,…,mn下標為i1,i2,i3,…,in

的數(shù)組元素的存儲地址：LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in

)*l

順序存儲的特點:

隨機存取，即存取任何元素花的時間相同。實現(xiàn):

根據(jù)數(shù)組說明，得到數(shù)組的元素個數(shù)，即元素類型（每個元素占用空間），然后，分配連續(xù)空間，空間的首地址存儲在數(shù)組名中。小結(jié)數(shù)組中的每個元素都受n個線性關(guān)系的約束，在每個關(guān)系中，每個元素aij都有且僅有一個直接前趨，都有且僅有一個直接后繼。二維數(shù)組有兩種方式：一種是以行為主序的方式，另一種是以列序為主序的方式。

5.2矩陣的壓縮存儲

一特殊矩陣的壓縮存儲二稀疏矩陣的壓縮存儲

基本內(nèi)容

1特殊矩陣的壓縮存儲；

2稀疏矩陣的壓縮存儲；

3稀疏矩陣在三元組順序表存儲方式下，矩陣的運算的實現(xiàn)；學習要點

1了解矩陣的兩種壓縮存儲方法及適用范圍;2了解在三元組順序表存儲方式下，實現(xiàn)矩陣運算的方法；矩陣是許多科學與工程計算問題中常常涉及到的一種運算對象。一個m行n列的矩陣是一平面陣列，有mn個元素。可以對矩陣作加、減、乘等運算。這里我們感興趣的不是矩陣本身，而是矩陣在計算機內(nèi)的有效存儲方法和對應(yīng)的各種矩陣運算的算法。

只有少數(shù)程序設(shè)計語言提供了矩陣運算。通常程序員是用二維數(shù)組存儲矩陣。由于這種存儲方法可以隨機地訪問矩陣的每個元素，因而能較為容易地實現(xiàn)矩陣的各種運算。Amn=a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1然而應(yīng)用中常遇到一些階數(shù)很高的矩陣，并且矩陣中有許多值相同的元素或零元素，用二維數(shù)組存儲矩陣會浪費很多的存儲單元存放實際上可以不必存放的元素。為了節(jié)省存儲空間，對這類矩陣可以壓縮存儲。所謂壓縮存儲是指為多個值相同的元素分配一個存儲空間，對零元素不分配存儲空間。例如，設(shè)一個10001000的矩陣中有800個非零元素，若用二維數(shù)組存儲需要106個存儲單元，而壓縮存儲只需800個存儲單元。本章將討論兩類矩陣的壓縮存儲：1特殊矩陣的壓縮存儲

2稀疏矩陣的壓縮存儲一特殊矩陣1什么是特殊矩陣具有某種特性的矩陣,如值相同元素或者零元素分布有一定規(guī)律的矩陣稱為特殊矩陣對稱矩陣(轉(zhuǎn)置矩陣):m[i][j]=m[j][i]對角矩陣:當i!=j時m[i][j]=0上三角矩陣:當i>=j時m[i][j]=0或常數(shù)C下三角矩陣:當i<=j時m[i][j]=0或常數(shù)C帶狀矩陣(帶寬為K):當|i-j|>k時m[i][j]=0a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1m[i][j]=m[j][i]當i!=j時m[i][j]=0當i>=j時m[i][j]=0或常數(shù)C當i<j時m[i][j]=0或常數(shù)C當|i-j|>k時m[i][j]=02特殊矩陣壓縮存儲特殊矩陣可以采用二維數(shù)組同樣的存儲方式，占用空間維m*n，但是，由于其特殊性，空間效率不高(存儲了許多零或相同的值)，為此，它們一般采用特殊的存儲方式（相同值只存放一個，零元素不存儲）

A矩陣越大,空間節(jié)省越多!!B有行主序,列主序之分!!a11a21a22a31a32a33am1am2amm012345n(n+1)/2-1下面以對稱矩陣為例，討論特殊矩陣的壓縮存儲.對稱矩陣是滿足下面條件的n階矩陣

aij=aji1

i,j

n

存儲元素數(shù):1+2+...+n=n(n+1)/2設(shè)用一維數(shù)組S[n(n+1)/2]存儲n階對稱對稱矩陣A的下三角(包括主對角線元素)的元素。不失一般性，我們以行序為主序方式存儲對稱矩陣下三角元素。a11a12a1na21a22a2nam1am2amn對任意一組下標值（i,j），均可以在S[]找到矩陣aij，反之，對所有k=0,2…n(n+1)/2-1,都能確定S[k]在矩陣中的位置（i,j）因此，稱S[]為n階對稱矩陣A的壓縮存儲。k=i(i-1)/2+j-1當i

jj(j-1)/2+i-1當i

jA中任意一元素aij與它的存儲位置之間存在著如下對應(yīng)關(guān)系：a11a12a1na21a22a2nam1am2amn例

對稱矩陣n=5,1+2+3+4+5=5*(5+1)/2=15一維數(shù)組SA[0..15]作為數(shù)組A的存儲結(jié)構(gòu):SA=(452313252816795)如:a[5,3]=a[3,5]=7k=5(5-1)/2+(3-1)=12故:sa[12]=74532152156313272528916795A=4520313252816795A=稀疏矩陣1什么是稀疏矩陣有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規(guī)律的矩陣稱為稀疏矩陣

例

M

=012900000000000-3000014000240000018000001500-7000M有42（67）個元素有8個非零元素m*n的矩陣中，非零元有t個，令k＝t/(m*n)，則k為矩陣稀疏因子，當k<=0.05時為稀疏矩陣分析：

根據(jù)稀疏矩陣的特點，如果存儲所有元素，顯然存放

了很多0，空間利用率低！我們可以考慮只存放非0元素，但如果僅僅存放一個元素值是不行的，因為不

能確定它在矩陣中的位置，所以必須存儲其下標。

稀疏矩陣的壓縮存儲（只討論有較多零元素矩陣的壓縮存儲）如何進行稀疏矩陣的壓縮存儲？稀疏矩陣的壓縮存儲有多種方法，本課程主要介紹三元組順序表這種存儲方式。1）三元組表按照壓縮存儲的概念，只須存儲稀疏矩陣的非零元素。但稀疏矩陣零元素分布沒有一定規(guī)律，因此，除了存儲非零元素的值之外，還必須同時記下它所在行和列號；反之，一個三元組（i,j,e)，能唯一確定矩陣的一個非零元。由此，稀疏矩陣可由非零元的三元組表及其行數(shù)、列數(shù)唯一確定。

線性表的存儲我們已經(jīng)介紹了,有順序和鏈式兩種,所以稀疏矩陣也有兩種存儲形式!2）三元組順序表

假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得稀疏矩陣的一種壓縮存儲方式——我們稱之為三元組順序表。稀疏矩陣的三元組順序表的類型定義#defineMAXSIZE12500//假設(shè)非零元個數(shù)的最大值為12500Typrdefstruct{inti,j;//非零元的行下標和列下標ElemTypee;//非零元}Triple;Typedefunion{Tripledata[MAXSIZE+1];

//用于存儲非零元三元組表,data[0]未用intmu,nu,tu;

//矩陣的行數(shù)、列數(shù)和非零元個數(shù)}TSMatrix;Triple：是包含三個域的結(jié)構(gòu)類型，其變量用于存儲矩陣的非零元三元組i,j：兩個整數(shù)域，用于存儲

非零元的行下標和列下標e：用于存儲非零元的值TSMatrix：是包含四個域的結(jié)構(gòu)類型，

data：一維數(shù)組，用于存儲矩陣的非零元三元組表mu,nu,tu：

三個整數(shù)域，分別存儲矩陣的行數(shù)、列數(shù)和非零元個數(shù)設(shè)M是TSMatrix類型的結(jié)構(gòu)變量，則M有四個域，其中M.data用于存儲矩陣M的三元組表，在此我們約定,M.data域中非零元三元組是以行序為主序順序存儲的。

M的三元組順序表圖示M

=012900000000000-3000014000240000018000001500-7000設(shè)M是TSMatrix

類型的結(jié)構(gòu)變量，則M有四個域，其中M.data用于存儲矩陣M的三元組表，如右圖所示ije01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tu3轉(zhuǎn)置運算算法對于一個m行n列的矩陣M，它的轉(zhuǎn)置矩陣T是一個n行m列的矩陣。M

=012900000000000-3000014000240000018000001500-7000T

=00-3001512000180900240000000-70000000014000000000

M第一列第二列第三列第四列第五列第六列

T第一行第二行第三行第四行第五行第六行T

=

00-3001512000180900240000000-70000000014000000000

M

=

012900000000000-3000014000240000018000001500-7000ijv01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tuijv01234567821124

6

-71

3

-33

4

241

6

153

1

963

142

5

18T.data768T.muT.nuT.tu矩陣M的三元組順序表M的轉(zhuǎn)置矩陣T的三元組順序表1)轉(zhuǎn)置運算算法TransposeSMatrix(TSMatrixM,TSMatrix&T)

基本思想對M.data從頭至尾掃描：

第一次掃描時，將M.data中列號為1的三元組賦值到T.data中，第二次掃描時，將M.data中列號為2的三元組賦值到T.data中，依此類推,直至將M.data所有三元組賦值到T.data中ijv01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tuijv01234567821124

6

-71

3

-33

4

241

6

153

1

963

142

5

18T.data768T.muT.nuT.tuStatusTransposeSMatrix(TSMatrixM,TSMatrix&T){

//采用三元組表存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu){

q=1;//q為當前三元組在T.data[]存儲位置(下標)

for(col=1;col<=M.nu;++col)

for(p=1;p<=M.tu;++p)//p為掃描M.data[]的“指示器”

//p“指向”三元組稱為當前三元組

if(M.data[p].j==col){

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++q;}

}

returnOK;}//TransposeSMtrix轉(zhuǎn)置運算算法對M六次掃描完成轉(zhuǎn)置運算轉(zhuǎn)置運算算法圖示ijv121213931-3361443245218611564-7ijv31-3251813-3611516151212211252181393194324342464-746-736146314M.dataT.data第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素時間復雜度分析算法的基本操作為將M.data中的三元組賦值到T.data，是在兩個循環(huán)中完成的，故算法的時間復雜度為O(nutu)我們知道，若用二維數(shù)組存儲矩陣，轉(zhuǎn)置算法的時間復雜度為O（munu）。當非零元的個數(shù)tu和矩陣元素個數(shù)munu同數(shù)量級時，轉(zhuǎn)置運算的時間復雜度為O(munu

nu)。由此可見：在這種情況下，用三元組順序表存儲矩陣，雖然可能節(jié)省了存儲空間，但時間復雜度提高了，因此算法僅適于tu<<munu的情況。

該算法效率不高的原因是：對為實現(xiàn)M到T的轉(zhuǎn)置，該算法對M.data進行了多次掃描。能否在對M.data一次掃描的過程中，完成M到T的轉(zhuǎn)置？快速轉(zhuǎn)置算法下面介紹轉(zhuǎn)置運算算法稱為快速轉(zhuǎn)置算法分析在M.data中，M的各列非零元對應(yīng)的三元組是以行為主序存儲的，故M的各列非零元對應(yīng)的三元組存儲位置不是“連續(xù)”的。然而，M的各列非零元三元組的存儲順序卻與各列非零元在M中的順序一致。如：M的第一列非零元素是-3、15，它們對應(yīng)的三元組在M.data中的存儲順序也是（3，1，-3）在前（6，1，15）后。ijv01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tu

如果能先求得M各列第一個非零元三元組在T.data中的位置，就能在對M.data一次掃描的過程中，完成M到T的轉(zhuǎn)置：對M.data一次掃描時，首先遇到各列的第一個非零元三元組，可按先前求出的位置，將其放至T.data中，當再次遇到各列的非零元三元組時，只須順序放到對應(yīng)列元素的后面。ijv01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tuM

=012900000000000-300001400024

0000018000001500-7000ijv01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tuM的各列非零元三元組的存儲順序與各列非零元在M中的順序一致ijv01234567831-3611512125218139432464-73614M.data678M.muM.nuM.tuijv01234567821124

6

-71

3

-33

4

241

6

153

1

963

142

5

18T.data768T.muT.nuT.tu各列第一個非零元三元組按先前求出的位置，放至T.data中各列后續(xù)的非零元三元組，順序放到對應(yīng)列元素的后面輔助向量num[]、cpos[]

為先求得M各列第一個非零元三元組在T.data中的位置。引入兩個輔助向量num[]、cpos[]：num[col]：存儲第col列非零元個數(shù)cpos[col]：存儲第col列第一個非零元三元組在T.data中的位置cpos[col]的計算方法：cpos[1]=1cpos[col]=cpos[col-1]+num[col-1]2<=col<=n例矩陣Mcolnum[col]cpot[col]123456722811001352784539M

=

012900000000000-3000014000240000018000001500-7000求M中各列非零元個數(shù)num[];求M中各列第一個非零元在T.data中的下標cpos[];3對M.data進行一次掃描，遇到col列的第一個非零元三元組時，按cpos[col]的位置，將其放至T.data中，當再次遇到col列的非零元三元組時，只須順序放到col列元素的后面;快速轉(zhuǎn)置算法主要步驟：StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){

//采用三元組順序表存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T。

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu){

for(col=1;col<=M.nu;++col)num[col]=0;

for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中每一列非零元個數(shù),求第col列中第一個非零元在T.data中的序號cpot[1]=1;

for(col=2;col<=M.tu;++col)cpot[col]=cpot[col-1]+num[col-1];

for(p=1;p<M.tu;++p)

{col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];

}

//for

}//ifreturnOK;}//FastTransposeSMatrixcolnum[col]cpot[col]123456722811001352789121213931-3361443245218611564-7ijvijvM.dataT.data12122112第2列第一個非零元在b中的位置139第3列第一個非零元在b中的位置31931-313-33614631443243424521825186115161564-746-74第2列第二個非零元在b中的位置65快速轉(zhuǎn)置算法圖示第3列第二個非零元在b中的位置第1列第一個非零元在b中的位置2793第4列第一個非零元在b中的位置求各列第1個非零元在b中位置求各列非零元個數(shù)掃描M.data實現(xiàn)M到T的轉(zhuǎn)置時間復雜度分析該算法利用兩個輔助向量num[]、cpos[]，實現(xiàn)了對M.data一次掃描完成M到T的轉(zhuǎn)置。從時間上看，算法中有四個并列的單循環(huán)，循環(huán)次數(shù)分別為mu、tu、t和tu，因而總的時間復雜度為O（mu+tu)，在M的非零元個數(shù)tu和munu同等數(shù)量級時，其時間復雜度為O(munu)，和轉(zhuǎn)置算法5.1的時間復雜度相同。由此可見，只有當tu<<munu時，使用快速轉(zhuǎn)置算法才有意義。4)稀疏矩陣三元組鏈式存儲-----十字鏈表:每個三元組用一個如下的結(jié)點存儲：row,col：非0元素的行、列值

val：非0元素的值

down：指向同列的下一個非O元素結(jié)點right：指向同行的下一個非O元素結(jié)點TypedefstructOLNode{inti,j;//該非零元的行和列下標ElemTypee;StructOLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域}OLNode;*OLink;Typedefstruct{OLink*rhead,*chead;

//行和列鏈表頭指針向量基址intmu,nu,tu;//稀疏矩陣的行數(shù),列數(shù)和非零元個數(shù)}CrossList;稀疏矩陣的十字鏈表存儲表示M.rheadM.chead…..………

小結(jié)1矩陣壓縮存儲是指為多個值相同的元素分配一個存儲空間，對零元素不分配存儲空間；2特殊矩陣的壓縮存儲是根據(jù)元素的分布規(guī)律，確定元素的存儲位置與元素在矩陣中的位置的對應(yīng)關(guān)系；3稀疏矩陣的壓縮存儲除了要保存零元素的值外，還要保存零元素在矩陣中的位置；

5.3廣義表5.3.1廣義表的概念5.3.2廣義表的存儲結(jié)構(gòu)基本內(nèi)容1廣義表的概念；2廣義表的基本操作；3廣義表的存儲結(jié)構(gòu)；學習要點了解廣義表的結(jié)構(gòu)特征及存儲方法；

5.3.1廣義表的概念1什么是廣義表廣義表也稱為列表，是線性表的一種擴展，也是數(shù)據(jù)元素的有限序列。記作：LS=(α1,α2。。αn)。其中αi其可以是單個元素，也可以是廣義表。說明:1）廣義表的定義是一個遞歸定義，因為在描述廣義表時又用到了廣義表；2）在線性表中數(shù)據(jù)元素是單個元素，而在廣義表中，元素可是以單個元素稱為原子，也可以是廣義表，稱為廣義表的子表；3）n是廣義表長度；4）下面是一些廣義表的例子:5）廣義表的術(shù)語：A=()空表，表長為0；

B=(e)B中只有一個元素e，表長為1；

C=(a,(b,c,d))C的表長為2，兩個元素分別為a和子表（b,c,d)；

D=(A,B,C)D的表長為3，它的三個元素A，B，C廣義表；長度：元素個數(shù)n（注意子表是一個數(shù)據(jù)元素）;單元素：一般用小寫字母表示；子表:一般用大寫字母表示；

表頭:當廣義表LS非空時，稱第一個元素為L的表頭，其余元素組成的表稱為LS的表尾；深度:簡單說就是表的嵌套層次，定義為：LS=(dl,d2，…，dn)depth(LS)=max{depth(dl),depth(d2)，…，depth(dn)}+l0di是單元素depth(di)=ldi是空表例如:B=(e)表頭：e表尾()C=(a,(b,c,d))表頭：a表尾((b,c,d))D=(A,B