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

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

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

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

>|0jk

bk-1,1kn且ki,0ji

bi-2,i=2,...,n}

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

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

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

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

OK。Assign(&A,e,index1,...,indexn)

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

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

的存儲(chǔ)位置

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

L

以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象按行號(hào)從小到大的順序，先將第一行中元素全部存放完，再存放第二行元素，第三行元素，依次類推……二維數(shù)組Am×na0,0a0,1…a0,n-1……am-1,0am-1,1…am-1,n-1同理，三維數(shù)組Al×m×n按行優(yōu)先存放的地址計(jì)算公式為：LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L0l-1m-1n-1ijk行序?yàn)橹餍蚺帕幸?guī)律：最左邊下標(biāo)變化最慢，最右邊下標(biāo)變化最快，右邊下標(biāo)變化一遍，與之相鄰的左邊下標(biāo)才變化一次。稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系:其中cn=L，ci-1=bi×ci

,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n見(jiàn)教材P.93例如：

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

的存儲(chǔ)位置

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

L

以“列序?yàn)橹餍颉钡拇鎯?chǔ)映象按列號(hào)從小到大的順序，先將第一列中元素全部存放完，再存放第二列元素，第三列元素，依次類推……二維數(shù)組Am×na0,0a1,0…am-1,0……a0,n-1a1,n-1…am-1,n-1列序?yàn)橹餍蚺帕幸?guī)律：最右邊下標(biāo)變化最慢，最左邊下標(biāo)變化最快，左邊下標(biāo)變化一遍，與之相鄰的右邊下標(biāo)才變化一次。5.1.3矩陣的壓縮存儲(chǔ)1.特殊矩陣2.稀疏矩陣1.特殊矩陣——非零元在矩陣中的分布有一定的規(guī)律。

例如:對(duì)稱矩陣三角矩陣對(duì)角矩陣a11a12…a1na21a22…a2n

……an1an2…annA=以對(duì)稱矩陣為例，n階對(duì)稱矩陣A滿足：aij=aji1≤i,j≤n可為每一對(duì)對(duì)稱元分配一個(gè)存儲(chǔ)空間。若以行序?yàn)橹餍虼鎯?chǔ)其下三角中的元，以一維數(shù)組s[n(n+1)/2]作為其存儲(chǔ)結(jié)構(gòu)，則s[k]和矩陣元aij之間的對(duì)應(yīng)關(guān)系為：k=i(i-1)/2+j-1(i≥j)

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

(i<j)2.稀疏矩陣假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱為稀疏因子。通常認(rèn)為

0.05的矩陣為稀疏矩陣。何謂稀疏矩陣？非零元在矩陣中隨機(jī)出現(xiàn)。1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)會(huì)產(chǎn)生的問(wèn)題:例如：012900000000000-3000014000240000018000001500-7000M=1)盡可能少存或不存零值元素；2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；3)操作方便。即：盡可能快地找到與下標(biāo)值(i，j)對(duì)應(yīng)的元素，盡可能快地找到同一行或同一列的非零元素。解決問(wèn)題的原則:一、三元組順序表二、行邏輯鏈接的順序表三、十字鏈表稀疏矩陣的壓縮存儲(chǔ)方法:

#defineMAXSIZE12500

typedefstruct{

int

i,j;//該非零元的行下標(biāo)和列下標(biāo)

ElemTypee;//該非零元的值

}

Triple;//三元組類型typedef

struct{

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

intmu,nu,tu;}TSMatrix;//稀疏矩陣類型一、三元組順序表矩陣M可表示為：012900000000000-3000014000240000018000001500-7000M=2121391-3361432421811564-7ijeM.data:M.mu=6M.nu=7M.tu=8(TSMatrixM)例如：三元組順序表表示的稀疏矩陣的轉(zhuǎn)置運(yùn)算。轉(zhuǎn)置是矩陣中最簡(jiǎn)單的一種運(yùn)算。對(duì)于一個(gè)mn的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)nm的矩陣，且B[i][j]=A[j][i]，1≤i≤n,1≤j≤m。在三元組表表示的稀疏矩陣中，怎樣求得它的轉(zhuǎn)置呢?從轉(zhuǎn)置的性質(zhì)知道，將A轉(zhuǎn)置為B，就是將A的三元組表a.data變?yōu)锽的三元組表b.data，這時(shí)可以將a.data中i和j的值互換，則得到的b.data是一個(gè)按列序?yàn)橹餍蚺帕械娜M表，再將它的順序適當(dāng)調(diào)整，變成行序?yàn)橹餍蚺帕?，即得到轉(zhuǎn)置矩陣B。下面將用兩種方法處理：(1)按照A的列序進(jìn)行轉(zhuǎn)置由于A的列即為B的行，在a.data中，按列掃描，同一列的元素必按行序遞增，因此得到的b.data必按行優(yōu)先存放。但為了找到A的每一列中所有的非零元素，每次都必須從頭到尾掃描A的三元組表（有多少列，則掃描多少遍）。121415-522-731363428211451-522-713364328例如：voidtransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲(chǔ)表示，求稀疏矩陣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)//按列號(hào)掃描

for(p=1;p<=M.tu;++p)//對(duì)三元組掃描

if(M.data[p].j==col)//進(jìn)行轉(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算法的時(shí)間復(fù)雜度：O(nu×tu)其時(shí)間復(fù)雜度為:O(mu×nu)

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

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

cpot[1]=1

cpot[col]=pot[col-1]+num[col-1](2≤col≤a.nu){cpot[1]=1;for(col=2;col<=a.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];例如：

21153

51-56

22-74

13362

432851234512345T.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)置矩陣元素Status

FastTransposeSMatrix(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]時(shí)間復(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的時(shí)間復(fù)雜度：三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需存取某一行中的非零元，則需從頭開(kāi)始進(jìn)行查找。二、行邏輯鏈接的順序表修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個(gè)數(shù)據(jù)成員rpos[]，其各分量的值為對(duì)應(yīng)各行第一個(gè)非零元的位置(下標(biāo))（在稀疏矩陣的初始化函數(shù)中確定）。#defineMAXMN500

typedefstruct{

Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;

}RLSMatrix;//行邏輯鏈接順序表類型ElemTypevalue(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例如：給定一組下標(biāo)，求矩陣的元素值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]+=M[i][k]*N[k][j];

}其時(shí)間復(fù)雜度為:O(m1×n2×n1)矩陣乘法的精典算法:

Q初始化；

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

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

//處理M的每一行

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

}//forarow

}//if兩個(gè)稀疏矩陣相乘（QMN）

的過(guò)程可大致描述如下：

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){

ctemp[]=0;//當(dāng)前行各元素累加器清零

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

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中列號(hào)

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處理的每一行

M累加器ctemp初始化的時(shí)間復(fù)雜度為(M.muN.nu)，求Q的所有非零元的時(shí)間復(fù)雜度為(M.tuN.tu/N.mu)，進(jìn)行壓縮存儲(chǔ)的時(shí)間復(fù)雜度為(M.muN.nu)，總的時(shí)間復(fù)雜度就是(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個(gè)數(shù)M.tu=Mmn，N中非零元的個(gè)數(shù)

N.tu=Nnp，相乘算法的時(shí)間復(fù)雜度就是(mp(1+nMN))，當(dāng)M<0.05和N<0.05及n<1000時(shí)，相乘算法的時(shí)間復(fù)雜度就相當(dāng)于(mp)。分析上述算法的時(shí)間復(fù)雜度當(dāng)稀疏矩陣中非零元的位置或個(gè)數(shù)經(jīng)常變動(dòng)時(shí)，三元組就不適合于作稀疏矩陣的存儲(chǔ)結(jié)構(gòu)，此時(shí)，采用鏈表作為存儲(chǔ)結(jié)構(gòu)更為恰當(dāng)。三、十字鏈表十字鏈表是稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)方法，在該方法中，每一個(gè)非零元用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)形式為：ijedownright其中i,j,e表示非零元所在的行、列和值的三元組；right：行指針域，用來(lái)指向本行中下一個(gè)非零元素；down：列指針域，用來(lái)指向本列中下一個(gè)非零元素。稀疏矩陣中同一行的非零元通過(guò)right指針鏈接成一個(gè)帶表頭結(jié)點(diǎn)的鏈表。同一列的非零元通過(guò)down指針鏈接成一個(gè)帶表頭結(jié)點(diǎn)的鏈表。因此，每個(gè)非零元既是第i行鏈表中的一個(gè)結(jié)點(diǎn)，又是第j列鏈表中的一個(gè)結(jié)點(diǎn)，相當(dāng)于處在一個(gè)十字交叉路口，故稱鏈表為十字鏈表。十字鏈表的類型定義typedefstructOLNode{

inti,j;

ElemTypee;

structOLNode*down,*right;}OLNode;*Olink;typedefstruct{

Olink*rhead,*chead;//行、列鏈表頭指針向量基址

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

LISP語(yǔ)言把廣義表作為基本的數(shù)據(jù)結(jié)構(gòu)，就連程序也表示為一系列的廣義表。1.廣義表廣義表一般記作：LS=(1,2,…,n)其中,LS為廣義表的名字，n為廣義表的長(zhǎng)度，每一個(gè)i為廣義表的元素。i可以是原子(或稱單元素)，也可以是廣義表(稱為子表)。在習(xí)慣中，一般用大寫(xiě)字母表示廣義表，小寫(xiě)字母表示原子。2.廣義表的長(zhǎng)度廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)。若廣義表LS非空，則稱第一個(gè)元素1為L(zhǎng)S的表頭，其余元素組成的表(2,…n)為L(zhǎng)S的表尾。4.表頭和表尾廣義表的深度定義為所含括弧的重?cái)?shù)。注意：“原子”的深度為0

“空表”的深度為13.廣義表的深度任一非空的廣義表，均可分解為表頭和表尾；一對(duì)確定的表頭和表尾，可唯一確定一個(gè)廣義表。5.廣義表舉例（1）A=(e)GetHead(A)=e,GetTail(A)=()（2）B=(a,(b,c),d)GetHead(B)=a,GetTail(B)=((b,c),d)（3）C=()無(wú)表頭、也無(wú)表尾廣義表A只有一個(gè)單元素，其長(zhǎng)度為1，深度為1。B是長(zhǎng)度為3的廣義表，其深度為2。C是一個(gè)空表，其長(zhǎng)度為0，深度為1。廣義表舉例（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是長(zhǎng)度為3的廣義表，每一項(xiàng)都是上面提到的子表,即:D=((e),(a,(b,c),d),())，其深度為3。E是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。即：E=(a,(a,(a,…))),其深度為無(wú)窮。F是長(zhǎng)度為1的廣義表，其元素為空表，其深度為2。（廣義表）提要5.2.1廣義表的類型定義5.2.2廣義表的表示方法ADTGlist{

數(shù)據(jù)對(duì)象：D＝{ei|i=1,2,..,n;n≥0;

ei∈AtomSet或ei∈GList,AtomSet為某個(gè)數(shù)據(jù)對(duì)象}

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

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

LS=(1,2,,n)其中：i

或?yàn)樵踊驗(yàn)閺V義表廣義表

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

E=(a,

(b,

c))

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

結(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());基本操作由于廣義表中的數(shù)據(jù)元素可以是原子，也可以是列表，即其中的元素可以有不同的結(jié)構(gòu)，難以用順序存儲(chǔ)結(jié)構(gòu)表示，因此，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在用鏈?zhǔn)浇Y(jié)構(gòu)時(shí)，需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：(1)表結(jié)點(diǎn)，用以表示列表；(2)原子結(jié)點(diǎn)，用以表示原子。5.2.2廣義表的表示方法有兩種具體的表示方法：(1)頭尾鏈表存儲(chǔ)表示(2)擴(kuò)展線性鏈表存儲(chǔ)表示typedefenum{ATOM,LIST}ElemTag;//枚舉類型//ATOM==0:原子,LIST==1:子表typedefstructGLNode

{

ElemTagtag;//

公共部分，標(biāo)志域

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

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

struct

{structGLNode*hp,*tp;}ptr;

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

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

表結(jié)點(diǎn):tag=1

hptpptrtag=0atom原子結(jié)點(diǎn)：空表非空表tag=1

指向表頭的指針指向表尾的指針LSLS=NULL例如:L

10

a

1