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

第5章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲5.4廣義表的定義5.5廣義表的存儲結(jié)構(gòu)5.1數(shù)組的定義數(shù)組：按一定格式排列起來的具有相同類型的數(shù)據(jù)元素的集合。一維數(shù)組：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡單元素，則稱為一維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。定長的線性表。聲明格式：數(shù)據(jù)類型變量名稱[長度]；

例：intnum[5]={0，1，2，3，4};二維數(shù)組：若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱為二維數(shù)組。非線性結(jié)構(gòu)

num[5]={0，1，2，3，4};A=(0,1,…,p)(p=m-1orn-1)j=(a0j,a1j,…,am-1,j)0≤j≤n-1i=(ai0,ai1,…,ai,n-1)0≤i≤m-1二維數(shù)組的邏輯結(jié)構(gòu)線性結(jié)構(gòu)定長的線性表每一個數(shù)據(jù)元素既在一個行表中，又在一個列表中。

該線性表的每個數(shù)據(jù)元素也是一個定長的線性表。

在C語言中，一個二維數(shù)組類型也可以定義為一維數(shù)組類型（其分量類型為一維數(shù)組類型），即：

typedefelemtypearray2[m][n];等價于：

typedefelemtypearray1[n];typedefarray1array2[m];聲明格式：數(shù)據(jù)類型變量名稱[行數(shù)][列數(shù)]

；

例：intnum[5][8];三維數(shù)組：若二維數(shù)組中的元素又是一個一維數(shù)組結(jié)構(gòu)，則稱作三維數(shù)組。…

n

維數(shù)組：若n-1維數(shù)組中的元素又是一個一維數(shù)組結(jié)構(gòu)，則稱作n

維數(shù)組。線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。結(jié)論數(shù)組特點(diǎn)：結(jié)構(gòu)固定——定義后，維數(shù)和維界不再改變。

數(shù)組基本操作：除了結(jié)構(gòu)的初始化和銷毀之外，只有取元素和修改元素值的操作。

數(shù)組的抽象數(shù)據(jù)類型的定義ADTArray{

數(shù)據(jù)對象：D＝{aj1j2…jn|ji

=0,...,bi-1,i=1,2,..,n,

n(>0)稱為數(shù)組的維數(shù)，

bi

是數(shù)組第i

維的長度，

ji

是數(shù)組元素的第i

維下標(biāo)，

aj1j2…jn∈ElemSet}數(shù)據(jù)關(guān)系：R＝{R1,R2,...,Rn}Ri＝{<aj1...ji...jn,aj1...ji+1...jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,

aj1…ji…jn

,aj1…ji+1…jn∈D,i=2,...,n}數(shù)據(jù)對象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}數(shù)據(jù)關(guān)系:

R={ROW,COL}ROW={<ai,j

,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}COL={<ai,j

,ai,

j+1>|0≤i≤b1-1,0≤j≤b2-2}二維數(shù)組的抽象數(shù)據(jù)類型的數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義基本操作：InitArray(&A,n,bound1,...,boundn)操作結(jié)果：若維數(shù)n

和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A)操作結(jié)果：銷毀數(shù)組A。Value(A,&e,index1,...,indexn)初始條件：A是n

維數(shù)組，e

為元素變量，隨后是n

個下標(biāo)值。操作結(jié)果：若各下標(biāo)不超界，則e

賦值為所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始條件：A是n

維數(shù)組，e

為元素變量，隨后是n

個下標(biāo)值。操作結(jié)果：若下標(biāo)不超界，則將e

的值賦給所指定的A的元素，并返回OK。}ADTArray數(shù)組特點(diǎn)：結(jié)構(gòu)固定——維數(shù)和維界不變。

數(shù)組基本操作：初始化、銷毀、取元素、修改元素值。

5.2數(shù)組的順序表示和實(shí)現(xiàn)一般不做插入和刪除操作。因為所以：一般都是采用順序存儲結(jié)構(gòu)來表示數(shù)組。注意：數(shù)組可以是多維的，但存儲數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問題。兩種順序存儲方式以行序為主序(低下標(biāo)優(yōu)先)BASIC、COBOL和PASCAL以列序為主序(高下標(biāo)優(yōu)先)FORTRAN以行序為主序存放：

am-1,n-1

……..

am-1,1

am-1,0

……….

a1,n-1

……..

a11

a10

a0,n-1

…….

a01

a0001n-1m*n-1n二維數(shù)組中任一元素

aij

的存儲位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×L某個元素的地址就是它前面所有行所占的單元加上它所在行前面所有列元素所占的單元數(shù)之和?；刂坊蚧范S數(shù)組的映象函數(shù)

a00a01……..a0,n-1

a10a11……..a1,n-1

am-1,0

am-1,1……..am-1,n-1

….按列序為主序存放01m-1m*n-1m

am-1,n-1

……..

a1,n-1

a0,n-1

……….

am-1,1

……..

a11

a01

am-1,0

…….

a10

a00

a00

a01

……..

a0,n-1

a10

a11

……..

a1,n-1

am-1,0

am-1,1

……..

am-1,n-1

….二維數(shù)組中任一元素

aij

的存儲位置

LOC(i,j)=LOC(0,0)+(b1×j＋i)×L某個元素的地址就是它前面所有列所占的單元加上它所在列前面所有行元素所占的單元數(shù)之和。例

1：一個二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個數(shù)組元素用相鄰的6

個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是

個字節(jié)。答：

Volume=m×n×L=(6–1+1)×(7–0+1)×6=48×6=288288例2：〖某校計算機(jī)系考研題〗

設(shè)數(shù)組A[0…59,0…69]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素A[31,57]的存儲地址為

。解：LOC(i,j)=LOC(31,57)=LOC(0,0)+(b1×j＋i)×L=2048+(60×57＋31

)×2=89508950

a00a01…a0,69

a10a11…a1,69

a59,0a59,1…a59,69

………a31,57……

……………

……………▲5.3矩陣的壓縮存儲

矩陣定義：一個由m×n

個元素排成的m

行（橫向）

n

列（縱向）的表。

矩陣的常規(guī)存儲：

將矩陣描述為一個二維數(shù)組。

矩陣的常規(guī)存儲的特點(diǎn)：

可以對其元素進(jìn)行隨機(jī)存取；矩陣運(yùn)算非常簡單；存儲的密度為1。

不適宜常規(guī)存儲的矩陣：值相同的元素很多且呈某種規(guī)律分布；零元素多。

矩陣的壓縮存儲：為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。5.3.1特殊矩陣

特殊矩陣：元素值的排列具有一定規(guī)律的矩陣。對稱矩陣、下（上）三角矩陣、對角線矩陣等。

1、對稱矩陣

在一個n

階方陣A中，若元素滿足下述性質(zhì)：

aij=aji

1≤i,j≤n

則稱A為對稱矩陣。對稱矩陣上下三角中的元素數(shù)均為：n(n+1)/2

可以行序為主序?qū)⒃卮娣旁谝粋€一維數(shù)組

sa[n(n+1)/2]中。對稱矩陣的存儲結(jié)構(gòu)k=01234n(n-1)/2n(n+1)/2-1以行序為主序存儲下三角：a11a21a22a31a32

…an1…ann則aij

和sa[k]存在著一一對應(yīng)關(guān)系：aij

前的i-1行有1+2+…+(i-1)=i(i-1)/2個元素，在第i

行上有

j個元素。因為aij

=aji，所以只要交換上述對應(yīng)關(guān)系式中的i

和j

即可。k=01234n(n-1)/2以行序為主序存儲下三角：a11a21a22a31a32

…an1…ann

2、三角矩陣以主對角線劃分，三角矩陣有上（下）三角兩種。上（下）三角矩陣的下（上）三角（不含主對角線）中的元素均為常數(shù)。在大多數(shù)情況下，三角矩陣常數(shù)為零。上三角矩陣下三角矩陣

三角矩陣的存儲：除了存儲主對角線及上（下）三角中的元素外，再加一個存儲常數(shù)c

的空間。

3、對角矩陣在對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一維數(shù)組中，且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。5.3.2稀疏矩陣稀疏矩陣：設(shè)在m×n

的矩陣中有t

個非零元素。令

=t/(m×n)

通常認(rèn)為當(dāng)

≤0.05

時稱為稀疏矩陣。壓縮存儲原則：存各非零元的值、行列位置和矩陣的行列數(shù)。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ù)(6,

7)唯一確定。三元組(i,j,aij)惟一確定矩陣的一個非零元。三元組的不同表示方法可決定稀疏矩陣不同的壓縮存儲方法。#defineMAXSIZE12500//假設(shè)非零元個數(shù)的最大值typedefstruct{inti,j;//該非零元的行列下標(biāo)

Elemtypee;}Triple;

typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;//矩陣的行、列數(shù)和非零元個數(shù)}TSMatrix;ijtu012345678稀疏矩陣的壓縮存儲方法——順序存儲結(jié)構(gòu)

1、三元組順序表

6

7

8

1

2

12

1

3

9

3

1

-3

3

6

14

4

3

24

5

2

18

6

1

15

6

4

-7

轉(zhuǎn)置矩陣：一個m×n的矩陣M，它的轉(zhuǎn)置T是一個n×m的矩陣，且T(i,j)=M(j,i)，1≤i≤n，1≤j≤m，即M的行是T的列，M的列是T的行。求轉(zhuǎn)置矩陣

問題描述：已知一個稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表。ijtu012345678

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7

解決思路：將矩陣行、列

維數(shù)互換將每個三元組

中的i

和

j

相

互調(diào)換

重排三元組次序，使b.data

中元素以

T

的

行

(M的列)

為

主序。

M.dataijtu012345678

7

6

8

1

3

-3

1

615

2

112

2

518

3

1

9

3

424

4

6

-7

6

314T.datab.dataijtu0123456787

6

8

211231913-3631434242518161546-7▲方法一：按M

的列序轉(zhuǎn)置

為找到

M

中每一列所有非零元素，需對其三元組表

M.data

從第一行起掃描一遍。由于M的列是T的行，且T.data

中以

M的

列序為主序，所以由此得到的

T.data必定是按行優(yōu)先存放的。

7

6

8

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7T.dataM.data13-3161521122518319342446-76314typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;//行、列、非零元數(shù)}TSMatrix;StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){

T.mu=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.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;}//TransposeSMatrix時間復(fù)雜度：O(nutu)若tu與munu同數(shù)量級，

則為：O(munu2)

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-713-3161521122518319342446-763147

6

8

qppqpqpfor(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];一般矩陣轉(zhuǎn)置算法：一般矩陣轉(zhuǎn)置算法時間復(fù)雜度：O(munu)用三元組順序表存儲的矩陣轉(zhuǎn)置算法時間復(fù)雜度：O(nutu)若tu與munu同數(shù)量級，則為：O(munu2)算法僅適用于tu<<munu的情況。結(jié)論用三元組順序表存儲稀疏矩陣節(jié)約存儲空間（優(yōu)點(diǎn)）；

tu與munu同數(shù)量級時，算法時間復(fù)雜度高（缺點(diǎn)）；方法二：按M

的行序轉(zhuǎn)置

——

快速轉(zhuǎn)置

7

6

8

1

3

-3

1

615

2

112

2

518

3

1

9

3

424

4

6

-7

6

314

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7T.dataM.data實(shí)施步驟：1、確定M

的第1列的第1個非零元在T.data

中的位置。13、確定M

的第col列的第一個非零元在

T.data

中的位置。2、確定M

的第col-1列的非零元個數(shù)。存入數(shù)組num[M.nu]存入數(shù)組cpot[M.nu]cpot[1]=1;cpot[col]=cpot[col–1]+num[col–1]2≤col≤a.nu

col

1

2

3

4

5

6

7

num(col)

2

2

2

1

0

1

0

cpot(col)

1

3

5

7

8

8

9StatusFastTransposeSMatrix(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ù)

cpot[1]=1;

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

//求M中各列的第一個非零元在

T.data

中的序號

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7

col

1

2

3

4

5

6

7

num(col)

cpot(col)

76

8

0000000111122211357889

for(p=1;p<=M.tu;++p){//轉(zhuǎn)置矩陣元素

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

}//if

returnOK;

}//FastTransposeSMatrix

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7

col

1

2

3

4

5

6

7

num(col)

2

2

2

1

0

1

0

cpot(col)

1

3

5

7

8

8

976

8

2112431

9613-326314934247251851615346-78012345678012345678pqpqpqpqpqpqpqpqStatusFastTransposeSMatrix(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ù)

cpot[1]=1;

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

//求M中各列的第一個非零元在

T.data

中的序號

for(p=1;p<=M.tu;++p){//轉(zhuǎn)置矩陣元素

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

}//if

returnOK;

}//FastTransposeSMatrix時間復(fù)雜度為:O(nu+tu)

若tu與munu同數(shù)量級，則為：O(munu)

與經(jīng)典算法相同。三元組順序表又稱有序的雙下標(biāo)法。三元組順序表的優(yōu)點(diǎn)：非零元在表中按行序有序存儲，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。三元組順序表的缺點(diǎn)：不能隨機(jī)存取。若按行號存取某一行中的非零元，則需從頭開始進(jìn)行查找。

2、行邏輯鏈接的順序表（帶行表的三元組）在稀疏矩陣中，若要隨機(jī)存取任意一行的非零元，需要知道每一行的第一個非零元在三元組表中的位置，而這必須從第一個元素起進(jìn)行搜索查詢。

7

6

8

1

3

-3

1

615

2

112

2

518

3

1

9

3

424

4

6

-7

6

314

col

1

2

3

4

5

6

7

num(col)

2

2

2

1

0

1

0

cpot(col)

1

3

5

7

8

8

9若在稀疏矩陣的存儲結(jié)構(gòu)中增加一個行表rpos——快速轉(zhuǎn)置算法中的

cpot，指示稀疏矩陣中每行的非零元素在三元組表中的起始位置，則不必從第一個元素起進(jìn)行搜索查詢。稱這種“帶行鏈接信息”的三元組表為：行邏輯鏈接的順序表。#defineMAXSIZE12500//假設(shè)非零元個數(shù)的最大值typedefstruct{inti,j;//該非零元的行列下標(biāo)

Elemtypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];

intmu,nu,tu;//矩陣的行、列數(shù)和非零元個數(shù)}TSMatrix;intrpos[MAXRC+1];//

指示各行第一個非零元的位置兩個稀疏矩陣相乘時，可以看出這種表示方法的優(yōu)越性。RLSMatrix;▲矩陣乘法設(shè)矩陣M是m1×n1

矩陣，N

是m2×n2

矩陣；只有n1=m2時，才能相乘得到結(jié)果矩陣Q=M×N（一個m1×n2

的矩陣）。矩陣相乘的經(jīng)典算法：for(i=1;i<=m1;i++)for(j=1;j<=n2;j++){Q[i][j]=0;for(k=1;k<=n1;k++)

Q[i][j]=Q[i][j]+M[i][k]*N[k][j];}i

i

j

j

k

k

不論是否為零，都要進(jìn)行一次乘法運(yùn)算。沒必要！

i

j

e

1

1

3

1

4

5

2

2

-1

3

1

2

i

j

e

1

2

2

2

1

1

3

1

-2

3

2

4

i

j

e

M[i][k]*N[k][j];

row

1

2

3

4rpos[row]

1

2

3

5

1

26

2

1

-1

3

2

4

0

06-1004注意：兩個稀疏矩陣相乘的結(jié)果

不一定是稀疏矩陣。3、稀疏矩陣的鏈?zhǔn)酱鎯Y(jié)構(gòu)：十字鏈表優(yōu)點(diǎn)：它能夠靈活地插入因運(yùn)算而產(chǎn)生的新的非零元素，刪除因運(yùn)算而產(chǎn)生的新的零元素，實(shí)現(xiàn)矩陣的各種運(yùn)算。在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點(diǎn)表示，該結(jié)點(diǎn)除了（row，col，value）以外，還要有兩個域：

right：用于鏈接同一行中的下一個非零元素；

down：用以鏈接同一列中的下一個非零元素。rowcolvaluedownright十字鏈表中結(jié)點(diǎn)的結(jié)構(gòu)示意圖：113145^^312^^22-1^^

^M.rheadM.chead211^122^31-2^324^^

M.rheadM.chead

^十字鏈表的結(jié)構(gòu)類型說明如下：typedefstructOLNode{inti,j;//非零元素的行和列下標(biāo)

ElementTypee;structOLNode*right,*down;//非零元素所在行表列表的后繼鏈域}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;//行、列鏈表的頭指針向量基址

intmu,nu,tu;//稀疏矩陣的行數(shù)、列數(shù)、非零元個數(shù)}CrossList;建立稀疏矩陣的十字鏈表算法：CreateCrossList(CrossList*M){//采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣Mif(M!=NULL)free(M);scanf(&m,&n,&t);//輸入M的行數(shù),列數(shù)和非零元素的個數(shù)

M->m=m;M->n=n;M->len=t;If(!(M->row_head=(Olink*)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);If(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);M->rhead[]=M->chead[]=NULL;//初始化行、列頭指針向量，各行、列鏈表為空的鏈表for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e))//按任意次序輸入非0元{if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;//生成結(jié)點(diǎn)

if(M->rhead[i]==NULL||M->rhead[i]->j>j) {p->right=M->rhead[i];M->rhead[i]=p;}else{/*尋找行表中的插入位置*/ for(q=M->rhead[i];q->right&&q->right->j<j;q=q->right);p->right=q->right;q->right=p;/*完成插入*/}if(M->chead[j]==NULL||M->rhead[j]->i>i)

{p->down=M->chead[j];M->chead[j]=p;}else{/*尋找列表中的插入位置*/for(q=M->chead[j];q->down&&q->down->i<i;q=q->down);p->down=q->down;q->down=p;/*完成插入*/}}}

廣義表（又稱列表Lists）是n≥0個元素a0,a1,…,an-1

的有限序列，其中每一個ai

或者是原子，或者是一個子表。5.4廣義表的定義例：中國舉辦的國際足球邀請賽，參賽隊名單可表示如下：

（阿根廷，巴西，德國，法國，（），西班牙，意大利，英國，（國家隊，魯能，恒大））

在這個表中，韓國隊?wèi)?yīng)排在法國隊后面，但由于其水平低未敢參加，成為空表。國家隊、魯能隊、恒大隊均作為東道主的參賽隊參加，構(gòu)成一個小的線性表，成為原線性表的一個數(shù)據(jù)元素。這種拓寬了的線性表就是廣義表。單個元素廣義表通常記作：LS=(a1，a2，…，an)其中：LS為表名，n為表的長度，每一個ai

為表的元素。習(xí)慣上，一般用大寫字母表示廣義表，小寫字母表示原子。

表頭：若LS

非空(n≥1)，則其第一個元素a1

就是表頭。記作head(LS)=a1。注：表頭可以是原子，也可以是子表。

表尾：除表頭之外的其它元素組成的表。記作

tail(LS)=(a2,...,an)。

注：表尾不是最后一個元素，而是一個子表。(1)A=()例：空表，長度為0。(2)B=(())(3)C=(a,(b,c))長度為1，表頭、表尾均為()。長度為2，由原子a和子表(b,c)構(gòu)成。(4)D=(x,y,z)表頭為a；表尾為((b,c))。長度為3，每一項都是原子。(5)E=(C,D)表頭為x；表尾為(y,z)。(6)F=(a,F)長度為2，每一項都是子表。表頭為C；表尾為(D)。長度為2，第一項為原子，第二項為它本身。F=(a,(a,(a,…)))表頭為a；表尾為(F)。廣義表的性質(zhì)(1)廣義表中的數(shù)據(jù)元素有相對次序；廣義表的長度定義為最外層所包含元素的個數(shù)；

如：

C=(a,(b,c))是長度為2的廣義表。(3)廣義表的深度定義為該廣義表展開后所含括號的重數(shù)；

A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。

注意：“原子”的深度為0;

“空表”的深度為1。

(4)廣義表可以為其他廣義表共享；如：廣義表B

就共享表A。在B

中不必列出A

的值，而是通過名稱來引用。(5)廣義表可以是一個遞歸的表。如：F=(a,F)=(a,(a,(a,…)))

注意：遞歸表的深度是無窮值，長度是有限值。廣義表是多層次結(jié)構(gòu)，廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，…。可以用圖形象地表示。

例：D=(E,F)其中：

E=(a,(b,c))F=(d,(e))DadbceEF廣義表可以看成是線性表的推廣，線性表是廣義表的特例。廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下，它可以兼容線性表、數(shù)組、樹和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。當(dāng)二維數(shù)組的每行（或每列）作為子表處理時，二維數(shù)組即為一個廣義表。另外，樹和有向圖也可以用廣義表來表示。由于廣義表不僅集中了線性表、數(shù)組、樹和有向圖等常見數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可有效地利用存儲空間，因此在計算機(jī)的許多應(yīng)用領(lǐng)域都有成功使用廣義表的實(shí)例。取表頭運(yùn)算GetHead和取表尾運(yùn)算GetTail若廣義表LS=(a1,a2,…,an)，則GetHead(LS)=a1。

GetTail(LS)=(a2,…,an)。注意：取表頭運(yùn)算得到的結(jié)果可以是原子，也可以是一個子表。取表尾運(yùn)算得到的結(jié)果一定是一個子表。例:

D=(E,F)=((a,(b,c))，F(xiàn))GetHead(D)=EGetTail(D)=(F)GetHead(E)=aGetTail(E)=((b,c))GetHead(((b,c)))=(b,c)GetTail(((b,c)))=