數(shù)據(jù)結(jié)構(gòu)組廣義表課件

數(shù)組和廣義表可以看成是線性表在以下含義上的擴展：

——表中的數(shù)據(jù)元素本身也是一個數(shù)據(jù)結(jié)構(gòu)。數(shù)組和廣義表可以看成是線性表在以下含義上的擴展：—15.1數(shù)組數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級程序設(shè)計語言中都設(shè)定了數(shù)組類型。在此，我們僅簡單地討論數(shù)組的邏輯結(jié)構(gòu)及在計算機內(nèi)的存儲方式。5.1數(shù)組數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)2一.多維數(shù)組的概念1．一維數(shù)組一維數(shù)組可以看成是一個線性表或一個向量，它在計算機內(nèi)存放在一塊連續(xù)的存儲單元中，適合于隨機查找。這在第2章的線性表的順序存儲結(jié)構(gòu)中已經(jīng)討論。一.多維數(shù)組的概念1．一維數(shù)組32．二維數(shù)組二維數(shù)組可以看成是向量的推廣。例如，設(shè)A是一個有m行n列的二維數(shù)組，則A可以表示為：在此，可以將二維數(shù)組A看成是由m個行向量[X0，X1，…，Xm-1]T組成，其中，Xi=(ai0,ai1,….,ain-1)，0≤i≤m-1；也可以將二維數(shù)組A看成是由n個列向量[Y0,Y1,……,Yn-1]組成，其中Yj=(a0j,a1j,…..,am-1j)，0≤j≤n-1。由此可知二維數(shù)組中的每一個元素最多可有兩個直接前驅(qū)和兩個直接后繼（邊界除外）。2．二維數(shù)組二維數(shù)組可以看成是向量的推廣。例如，設(shè)A43．多維數(shù)組同理，三維數(shù)組最多可有三個直接前驅(qū)和三個直接后繼，三維以上數(shù)組可以作類似分析?？梢园讶S以上的數(shù)組稱為多維數(shù)組，多維數(shù)組可有多個直接前驅(qū)和多個直接后繼。3．多維數(shù)組同理，三維數(shù)組最多可有三個直接前5二.多維數(shù)組在計算機內(nèi)的存放高級語言對數(shù)組的存儲都是采取順序存儲的方式，由于計算機內(nèi)存結(jié)構(gòu)是一維的（線性的），因此，用一維內(nèi)存存放多維數(shù)組就必須按某種次序?qū)?shù)組元素排成一個線性序列，然后將這個線性序列順序存放在存儲器中，具體實現(xiàn)方法在下面介紹。二.多維數(shù)組在計算機內(nèi)的存放高級語言對數(shù)組65.1.1數(shù)組的類型定義5.1.3矩陣的壓縮存儲5.1.2數(shù)組的順序表示和實現(xiàn)（數(shù)組）提要5.1.1數(shù)組的類型定義5.1.3矩陣的壓縮存儲7ADTArray{

數(shù)據(jù)對象：

D＝{aj1,j2,...,

jn|ji=0,...,bi-1,i=1,2,..,n(n>0),aj1,j2,...,

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,i=2,...,n}

}ADTArray基本操作:5.1.1數(shù)組的類型定義ADTArray{基本操作:5.1.1數(shù)組的類型定義8數(shù)據(jù)對象:

D={aij|0≤i≤b1-1,0≤j≤b2-1,

aij∈ElemSet}數(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ù)組的定義:9基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)基本操作：InitArray(&A,n,bound1,10操作結(jié)果：若維數(shù)n和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。InitArray(&A,n,bound1,...,boundn)操作結(jié)果：若維數(shù)n和各維長度合法，InitArray(&11

DestroyArray(&A)操作結(jié)果：銷毀數(shù)組A。DestroyArray(&A)操作結(jié)果：銷毀數(shù)組A。12初始條件：A是n維數(shù)組，e為元素變量，隨后是n個下標值。操作結(jié)果：若各下標不超界，則e賦值為所指定的A的元素值，并返回OK。Value(A,&e,index1,...,indexn)初始條件：A是n維數(shù)組，e為元素變量，Value(A,&e13初始條件：A是n維數(shù)組，e為元素變量，隨后是n個下標值。

操作結(jié)果：若下標不超界，則將e的值賦給所指定的A的元素，并返回

OK。Assign(&A,e,index1,...,indexn)初始條件：A是n維數(shù)組，e為元素變量，Assign(&A,14

類型特點:

數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一維的結(jié)構(gòu)。有兩種順序映象的方式:1)以行序為主序(行優(yōu)先，低下標優(yōu)先)；2)以列序為主序(列優(yōu)先，高下標優(yōu)先)。5.1.2數(shù)組的順序表示和實現(xiàn)由于一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)組元素個數(shù)和元素之間的關(guān)系就已確定，即它們的邏輯結(jié)構(gòu)就固定下來了，不再發(fā)生變化；數(shù)組一般不作插入或刪除操作。因此，采用順序存儲結(jié)構(gòu)表示數(shù)組是順理成章的事了。類型特點:有兩種順序映象的方式:5.1.2數(shù)組的順15例如：

稱為基地址或基址。二維數(shù)組A中任一元素ai,j

的存儲位置

LOC(i,j)=LOC(0,0)+(n×i＋j)×L

L

以“行序為主序”的存儲映象按行號從小到大的順序，先將第一行中元素全部存放完，再存放第二行元素，第三行元素，依次類推……二維數(shù)組Am×n

a0,0

a0,1

…

a0,n-1……am-1,0am-1,1

…am-1,n-1例如：稱為基地址或基址。二維數(shù)組A中任一元素ai,j16同理，三維數(shù)組Al×m×n按行優(yōu)先存放的地址計算公式為：LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L0l-1m-1n-1ijk同理，三維數(shù)組Al×m×n按行優(yōu)先存放的地址計算公式17行序為主序排列規(guī)律：最左邊下標變化最慢，最右邊下標變化最快，右邊下標變化一遍，與之相鄰的左邊下標才變化一次。行序為主序排列規(guī)律：最左邊下標變化最慢，最右18稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲位置是其下標的線性函數(shù)。推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲位置的映象關(guān)系:其中cn=L，ci-1=bi×ci,1<i

n。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n見教材P.93稱為n維數(shù)組的映象函數(shù)。數(shù)組元素19例如：

基地址或基址。二維數(shù)組A中任一元素ai,j

的存儲位置

LOC(i,j)=LOC(0,0)+(m×j＋i)×L

L

以“列序為主序”的存儲映象按列號從小到大的順序，先將第一列中元素全部存放完，再存放第二列元素，第三列元素，依次類推……二維數(shù)組Am×n

a0,0

a1,0

…

am-1,0……a0,n-1a1,n-1

…am-1,n-1例如：基地址或基址。二維數(shù)組A中任一元素ai,j的存20列序為主序排列規(guī)律：最右邊下標變化最慢，最左邊下標變化最快，左邊下標變化一遍，與之相鄰的右邊下標才變化一次。列序為主序排列規(guī)律：最右邊下標變化最慢，最左215.1.3矩陣的壓縮存儲1.特殊矩陣2.稀疏矩陣5.1.3矩陣的壓縮存儲1.特殊矩陣2.稀疏矩陣221.特殊矩陣——非零元在矩陣中的分布有一定的規(guī)律。

例如:對稱矩陣三角矩陣對角矩陣a11a12…a1na21a22…a2n

……an1an2…annA=1.特殊矩陣——非零元在矩陣中的分布有一定的規(guī)律。a1123以對稱矩陣為例，n階對稱矩陣A滿足：aij=aji1≤i,j≤n可為每一對對稱元分配一個存儲空間。若以行序為主序存儲其下三角中的元，以一維數(shù)組s[n(n+1)/2]作為其存儲結(jié)構(gòu)，則s[k]和矩陣元aij之間的對應(yīng)關(guān)系為：k=i(i-1)/2+j-1(i≥j)

j(j-1)/2+i-1(i<j)以對稱矩陣為例，n階對稱矩陣A滿足：aij=aji242.稀疏矩陣假設(shè)m行n列的矩陣含t個非零元素，則稱為稀疏因子。通常認為

0.05的矩陣為稀疏矩陣。何謂稀疏矩陣？非零元在矩陣中隨機出現(xiàn)。2.稀疏矩陣假設(shè)m行n列的矩陣含t個非零元素，251)零值元素占了很大空間;2)計算中進行了很多和零值的運算，遇除法，還需判別除數(shù)是否為零。以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時會產(chǎn)生的問題:例如：

012900000000000-3000014000240000018000001500-7000M=1)零值元素占了很大空間;2)計算中進行了很多和零值261)盡可能少存或不存零值元素；2)盡可能減少沒有實際意義的運算；3)操作方便。即：盡可能快地找到與下標值(i，j)對應(yīng)的元素，盡可能快地找到同一行或同一列的非零元素。解決問題的原則:1)盡可能少存或不存零值元素；2)盡可能減少沒有實際意義27一、三元組順序表二、行邏輯鏈接的順序表三、十字鏈表稀疏矩陣的壓縮存儲方法:一、三元組順序表二、行邏輯鏈接的順序表三、十字鏈表稀疏矩陣28

#defineMAXSIZE12500

typedefstruct{

inti,j;//該非零元的行下標和列下標

ElemTypee;//該非零元的值

}Triple;//三元組類型typedefstruct{

Tripledata[MAXSIZE+1];//data[0]未用

intmu,nu,tu;}TSMatrix;//稀疏矩陣類型一、三元組順序表#defineMAXSIZE12500typede29矩陣M可表示為：

012900000000000-3000014000240000018000001500-7000M=2121391-3361432421811564-7ijeM.data:M.mu=6M.nu=7M.tu=8(TSMatrixM)例如：矩陣M可表示為：0129030三元組順序表表示的稀疏矩陣的轉(zhuǎn)置運算。轉(zhuǎn)置是矩陣中最簡單的一種運算。對于一個m

n的矩陣A，它的轉(zhuǎn)置矩陣B是一個nm的矩陣，且B[i][j]=A[j][i]，1≤i≤n,1≤j≤m。三元組順序表表示的稀疏矩陣的轉(zhuǎn)置運算。轉(zhuǎn)置是矩陣中最31在三元組表表示的稀疏矩陣中，怎樣求得它的轉(zhuǎn)置呢?從轉(zhuǎn)置的性質(zhì)知道，將A轉(zhuǎn)置為B，就是將A的三元組表a.data變?yōu)锽的三元組表b.data，這時可以將a.data中i和j的值互換，則得到的b.data是一個按列序為主序排列的三元組表，再將它的順序適當調(diào)整，變成行序為主序排列，即得到轉(zhuǎn)置矩陣B。下面將用兩種方法處理：(1)按照A的列序進行轉(zhuǎn)置由于A的列即為B的行，在a.data中，按列掃描，同一列的元素必按行序遞增，因此得到的b.data必按行優(yōu)先存放。但為了找到A的每一列中所有的非零元素，每次都必須從頭到尾掃描A的三元組表（有多少列，則掃描多少遍）。在三元組表表示的稀疏矩陣中，怎樣求得它的轉(zhuǎn)置呢?32121415-522-731363428211451-522-713364328例如：121415-522-73133voidtransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣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)//進行轉(zhuǎn)置

{T.data[q].j=M.data[p].i;T.data[q].i=M.data[p].j;T.data[q].e=M.data[p].e;++q;}}}//transposeSMatrix算法的時間復(fù)雜度：O(nu×tu)voidtransposeSMatrix(TSMatr34其時間復(fù)雜度為:O(mu×nu)

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

for(row=1;row<=mu;++row)T[col][row]=M[row][col];用常規(guī)的二維數(shù)組表示時的算法：相比較后可以發(fā)現(xiàn)，當非零元的個數(shù)tu與mu×nu同數(shù)量級時，transposeSMatrix算法的時間復(fù)雜度就成為O(mu×nu2)了，比不壓縮存儲時的時間復(fù)雜度要大。因此，該算法僅適于tu<<mu×nu的情況。其時間復(fù)雜度為:O(mu×nu)for(co35（2）按照A的行序進行轉(zhuǎn)置(快速轉(zhuǎn)置)即按a.data中三元組的次序進行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組放入b中恰當?shù)奈恢?。首先，在轉(zhuǎn)置前求出矩陣A的每一列col（即B中每一行）的第一個非零元轉(zhuǎn)置后在b.data中的正確位置cpot[col](1≤col≤a.nu)，然后，在對a.data的三元組依次作轉(zhuǎn)置時，只要將三元組按列號col放置到b.data[cpot[col]]中，之后將cpot[col]內(nèi)容加1，以指示第col列的下一個非零元的正確位置。為了求得位置向量cpot，要先求出A的每一列中非零元個數(shù)num[col]，然后利用下面公式：

cpot[1]=1cpot[col]=pot[col-1]+num[col-1](2≤col≤a.nu){（2）按照A的行序進行轉(zhuǎn)置(快速轉(zhuǎn)置)即按a.dat36cpot[1]=1;for(col=2;col<=a.nu;++col)cpot[col]=cpot[col-1]+num[col-1];例如：

21153

51-56

22-74

13362

432851234512345cpot[1]=1;例如：211537T.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];

cpot[1]=1;

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

}//if

returnOK;}//FastTransposeSMatrix

轉(zhuǎn)置矩陣元素StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){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]T.mu=M.nu;T.nu=M.mu;T.38時間復(fù)雜度為:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……分析算法FastTransposeSMatrix的時間復(fù)雜度：時間復(fù)雜度為:O(M.nu+M.tu)for(col=139三元組順序表又稱有序的雙下標法，它的特點是，非零元在表中按行序有序存儲，因此便于進行依行順序處理的矩陣運算。然而，若需存取某一行中的非零元，則需從頭開始進行查找。二、行邏輯鏈接的順序表三元組順序表又稱有序的雙下標法，它的特點是，40修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個數(shù)據(jù)成員rpos[]，其各分量的值為對應(yīng)各行第一個非零元的位置(下標)（在稀疏矩陣的初始化函數(shù)中確定）。#defineMAXMN500

typedefstruct{

Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;

}RLSMatrix;//行邏輯鏈接順序表類型修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個數(shù)據(jù)成41ElemTypevalue(RLSMatrixM,intr,intc){

p=M.rpos[r];

while(p<=M.tu&&M.data[p].i==r&&M.data[p].j<c)p++;

if(p<=M.tu&&M.data[p].i==r&&M.data[p].j==c)

returnM.data[p].e;

elsereturn0;}//value例如：給定一組下標，求矩陣的元素值ElemTypevalue(RLSMatrixM,in42for(i=1;i<=m1;++i)

for(j=1;j<=n2;++j){Q[i][j]=0;

for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];

}其時間復(fù)雜度為:O(m1×n2×n1)矩陣乘法的精典算法:for(i=1;i<=m1;++i)其時間復(fù)雜度為:43

Q初始化；

ifQ是非零矩陣{//逐行求積

for(arow=1;arow<=M.mu;++arow){

//處理M的每一行

ctemp[]=0;//累加器清零計算Q中第arow行的積并存入ctemp[]中；將ctemp[]中非零元壓縮存儲到Q.data；

}//forarow}//if兩個稀疏矩陣相乘（Q

M

N）

的過程可大致描述如下：Q初始化；兩個稀疏矩陣相乘（QMN）

44

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;

if(M.tu*N.tu!=0){//Q是非零矩陣

for(arow=1;arow<=M.mu;++arow){

//處理M的每一行

}//forarow}//ifreturnOK;}//MultSMatrixStatusMultSMatrix

(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){if(M.nu!=N.mu)returnERR45

ctemp[]=0;//當前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//對當前行中每一個非零元

brow=M.data[p].j;if(brow<N.nu)t=N.rpos[brow+1];

else{t=N.tu+1}

for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘積元素在Q中列號

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}//forq

}//求得Q中第crow(=arow)行的非零元

for(ccol=1;ccol<=Q.nu;++ccol)if(ctemp[ccol]){

if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu]={arow,ccol,ctemp[ccol]};

}//if處理的每一行

Mctemp[]=0;46累加器ctemp初始化的時間復(fù)雜度為

(M.mu

N.nu)，求Q的所有非零元的時間復(fù)雜度為

(M.tu

N.tu/N.mu)，進行壓縮存儲的時間復(fù)雜度為

(M.mu

N.nu)，總的時間復(fù)雜度就是

(M.mu

N.nu+M.tu

N.tu/N.mu)。若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個數(shù)M.tu=

M

m

n，

N中非零元的個數(shù)

N.tu=

N

n

p，相乘算法的時間復(fù)雜度就是

(m

p

(1+n

M

N))

，當

M<0.05和

N<0.05及n<1000時，相乘算法的時間復(fù)雜度就相當于

(m

p)。分析上述算法的時間復(fù)雜度累加器ctemp初始化的時間復(fù)雜度為(M.muN.nu)47當稀疏矩陣中非零元的位置或個數(shù)經(jīng)常變動時，三元組就不適合于作稀疏矩陣的存儲結(jié)構(gòu)，此時，采用鏈表作為存儲結(jié)構(gòu)更為恰當。三、十字鏈表當稀疏矩陣中非零元的位置或個數(shù)經(jīng)常變動時，三元組就不48十字鏈表是稀疏矩陣的鏈式存儲方法，在該方法中，每一個非零元用一個結(jié)點表示，結(jié)點形式為：ijedownright其中i,j,e表示非零元所在的行、列和值的三元組；right：行指針域，用來指向本行中下一個非零元素；down：列指針域，用來指向本列中下一個非零元素。稀疏矩陣中同一行的非零元通過right指針鏈接成一個帶表頭結(jié)點的鏈表。同一列的非零元通過down指針鏈接成一個帶表頭結(jié)點的鏈表。因此，每個非零元既是第i行鏈表中的一個結(jié)點，又是第j列鏈表中的一個結(jié)點，相當于處在一個十字交叉路口，故稱鏈表為十字鏈表。十字鏈表是稀疏矩陣的鏈式存儲方法，在該方法中，每一個49十字鏈表的類型定義typedefstructOLNode{inti,j;ElemTypee;structOLNode*down,*right;}OLNode;*Olink;typedefstruct{Olink*rhead,*chead;//行、列鏈表頭指針向量基址

intmu,nu,tu;}CrossList;十字鏈表的類型定義typedefstructOLNod5030050-100200011314522-1312^^^^^^^例：M.mu=3M.nu=4M.tu=4300511314522-1312^^^^^^^515.2廣義表廣義表的概念廣義表是線性表的推廣，也稱為列表。線性表中的元素僅限于原子，即從結(jié)構(gòu)上是不可以再分的，而廣義表中的元素既可以是原子，也可以是廣義表。

LISP語言把廣義表作為基本的數(shù)據(jù)結(jié)構(gòu)，就連程序也表示為一系列的廣義表。5.2廣義表廣義表的概念線性表中的元素僅521.廣義表廣義表一般記作：LS=(

1,

2,…,

n)其中,LS為廣義表的名字，n為廣義表的長度，每一個

i為廣義表的元素。

i可以是原子(或稱單元素)，也可以是廣義表(稱為子表)。在習(xí)慣中，一般用大寫字母表示廣義表，小寫字母表示原子。2.廣義表的長度廣義表的長度定義為最外層包含元素個數(shù)。1.廣義表廣義表一般記作：LS=(1,2,…,n)53若廣義表LS非空，則稱第一個元素

1為LS的表頭，其余元素組成的表(

2,…

n)為LS的表尾。4.表頭和表尾廣義表的深度定義為所含括弧的重數(shù)。注意：“原子”的深度為0

“空表”的深度為13.廣義表的深度任一非空的廣義表，均可分解為表頭和表尾；一對確定的表頭和表尾，可唯一確定一個廣義表。若廣義表LS非空，則稱第一個元素1為LS的表頭，其余元素組545.廣義表舉例（1）A=(e)GetHead(A)=e,GetTail(A)=()（2）B=(a,(b,c),d)GetHead(B)=a,GetTail(B)=((b,c),d)（3）C=()無表頭、也無表尾廣義表A只有一個單元素，其長度為1，深度為1。B是長度為3的廣義表，其深度為2。C是一個空表，其長度為0，深度為1。5.廣義表舉例（1）A=(e)GetHead(A)=e,55廣義表舉例（5）E=(a,E)（4）D=(A,B,C)GetHead(D)=(e),GetTail(D)=((a,(b,c),d),())GetHead(E)=a,GetTail(E)=(E)（6）F=(())GetHead(F)=(),GetTail(F)=()D是長度為3的廣義表，每一項都是上面提到的子表,即:D=((e),(a,(b,c),d),())，其深度為3。E是長度為2的廣義表，第一項為原子，第二項為它本身。即：E=(a,(a,(a,…))),其深度為無窮。F是長度為1的廣義表，其元素為空表，其深度為2。廣義表舉例（5）E=(a,E)（4）D=(A,B,C)Get56（廣義表）提要5.2.1廣義表的類型定義5.2.2

廣義表的表示方法（廣義表）提要5.2.1廣義表的類型定義5.2.2廣義57ADTGlist{

數(shù)據(jù)對象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet為某個數(shù)據(jù)對象}

數(shù)據(jù)關(guān)系：

LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist基本操作:5.2.1廣義表的類型定義ADTGlist{基本操作:5.2.1廣義表的類型定義58

LS=(

1,

2,

,

n)其中：

i

或為原子或為廣義表廣義表

LS=(

1,

2,…,

n)的結(jié)構(gòu)特點:2)廣義表是遞歸定義的線性結(jié)構(gòu)1)廣義表中的數(shù)據(jù)元素有相對次序；LS=(1,2,,n59例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce3)廣義表是一個多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:DEFa()d()bce604)廣義表可以共享；5)廣義表可以是一個遞歸的表。例如：A=(e)B=(a,(b,c),d)C=(A,B)D=(d,A,f,B)例如：E=(a,E)遞歸表的深度是無窮值，長度是有限值。4)廣義表可以共享；5)廣義表可以是一個遞歸的表。例61

結(jié)構(gòu)的創(chuàng)建和銷毀

InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);

狀態(tài)函數(shù)

GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);

插入和刪除操作

InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);

遍歷

Traverse_GL(L,Visit());基本操作結(jié)構(gòu)的創(chuàng)建和銷毀狀態(tài)函數(shù)插入和刪除操作62由于廣義表中的數(shù)據(jù)元素可以是原子，也可以是列表，即其中的元素可以有不同的結(jié)構(gòu)，難以用順序存儲結(jié)構(gòu)表示，因此，通常采用鏈式存儲結(jié)構(gòu)。在用鏈式結(jié)構(gòu)時，需要兩種結(jié)構(gòu)的結(jié)點：

(1)表結(jié)點，用以表示列表；

(2)原子結(jié)點，用以表示原子。5.2.2

廣義表的表示方法由于廣義表中的數(shù)據(jù)元素可以是原子，也可以是列表，即其63有兩種具體的表示方法：(1)頭尾鏈表存儲表示(2)擴展線性鏈表存儲表示有兩種具體的表示方法：(1)頭尾鏈表存儲表示(2)擴展線64typedefenum{ATOM,LIST}ElemTag;//枚舉類型

//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//

公共部分，標志域

union{//聯(lián)合部分

AtomTypeatom;//原子結(jié)點的數(shù)據(jù)域

struct{structGLNode*hp,*tp;}ptr;

//表結(jié)點的指針域

};}*GList(1)廣義表的頭尾鏈表存儲表示：

表結(jié)點:tag=1hptpptrtag=0atom原子結(jié)點：typedefenum{ATOM,LIST}Elem65空表非空表tag=1指向表頭的指針指向表尾的指針LSLS=NULL空表非空表tag=1指向表頭的指針指66例如:例如:67L

10a

1

10x

1

1

1

0x

1

0y(a,(x,y),((x)))a((x,y),((x)))(