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

第五章數(shù)組和廣義表.5.1數(shù)組的類型定義5.3稀疏矩陣的壓縮存儲(chǔ)5.2數(shù)組的順序表示和實(shí)現(xiàn)5.4廣義表的類型定義5.5

廣義表的表示方法5.6廣義表操作的遞歸函數(shù).5.1數(shù)組的類型定義ADTArray{

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

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

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

R＝{R1,R2,...,Rn}Ri＝{<aj1,...ji,...jn

,aj1,...ji+1,...jn

>|0jkbk-1,1kn且ki,0ji

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

}ADTArray基本操作:.二維數(shù)組的定義:數(shù)據(jù)對(duì)象:

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}.基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn).InitArray(&A,n,bound1,...,boundn)

操作結(jié)果：若維數(shù)n和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。.DestroyArray(&A)

操作結(jié)果：銷毀數(shù)組A。.Value(A,&e,index1,...,indexn)

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值。

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

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

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值。

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

OK。.5.2數(shù)組的順序表示和實(shí)現(xiàn)

類型特點(diǎn):1)只有引用型操作，沒(méi)有加工型操作；2)數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。

有兩種順序映象的方式:1)以行序?yàn)橹餍?低下標(biāo)優(yōu)先)；2)以列序?yàn)橹餍?高下標(biāo)優(yōu)先)。.例如：

稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維數(shù)組A中任一元素ai,j

的存儲(chǔ)位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

.

二維數(shù)組三維數(shù)組行向量下標(biāo)

i頁(yè)向量下標(biāo)

i列向量下標(biāo)

j行向量下標(biāo)

j

列向量下標(biāo)k.推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系

稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n..練習(xí)三維數(shù)組a[4][5][6]（下標(biāo)從0開(kāi)始計(jì)），每個(gè)元素的長(zhǎng)度是2，則a[2][3][4]的地址是____________。(設(shè)a[0][0][0]的地址是1000,數(shù)據(jù)以行為主方式存儲(chǔ))1164.練習(xí)二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲(chǔ)時(shí)元素M[3][5]的起始地址與M按列存儲(chǔ)時(shí)元素（）的起始地址相同。 A.M[2][4] B.M[4][4] C.M[3][4] D.M[3][5]C.練習(xí)有一個(gè)二維數(shù)組A[1:6，0:7]每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，那么這個(gè)數(shù)組的體積是（①）個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A[1，0]的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是（②）。若按行存儲(chǔ)，則A[2，4]的第一個(gè)字節(jié)的地址是（③）。若按列存儲(chǔ)，則A[5，7]的第一個(gè)字節(jié)的地址是（④）。就一般情況而言，當(dāng)（⑤）時(shí)，按行存儲(chǔ)的A[I，J]地址與按列存儲(chǔ)的A[J，I]地址相等。①-④：A．12B.66C.72D.96E.114F.120G.156H.234I.276J.282K.283L.288⑤：A．行與列的上界相同B.行與列的下界相同C.行與列的上、下界都相同D.行的元素個(gè)數(shù)與列的元素個(gè)數(shù)相同

LJCIC.練習(xí)一n×n的三角矩陣A=[aij]如下：將三角矩陣中元素aij(i≤j)按行序?yàn)橹餍虻捻樞虼鎯?chǔ)在一維數(shù)組B[1..n(n+1)/2]中，則aij在B中的位置是（）。(i-1)(2n+i)/2+i-j+1 B.(i-1)(2n-i+2)/2+j-i+1C.(i-1)(2n-i)/2+j-iD.(i-1)(2n-i+2)/2+j-iB.假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱為稀疏因子。通常認(rèn)為

0.05的矩陣為稀疏矩陣。5.3稀疏矩陣的壓縮存儲(chǔ)何謂稀疏矩陣？.

以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題:1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。.1)盡可能少存或不存零值元素；解決問(wèn)題的原則:2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；3)操作方便。即：能盡可能快地找到與下標(biāo)值(i，j)對(duì)應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。.1)特殊矩陣

非零元在矩陣中的分布有一定規(guī)則例如:三角矩陣對(duì)角矩陣2)隨機(jī)稀疏矩陣非零元在矩陣中隨機(jī)出現(xiàn)有兩類稀疏矩陣：.隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表二、行邏輯聯(lián)接的順序表三、十字鏈表.

#defineMAXSIZE12500

typedefstruct{

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

ElemTypee;//該非零元的值

}Triple;//三元組類型一、三元組順序表typedefunion{

Tripledata[MAXSIZE+1];

intmu,nu,tu;}TSMatrix;//稀疏矩陣類型.如何求轉(zhuǎn)置矩陣？.用常規(guī)的二維數(shù)組表示時(shí)的算法

其時(shí)間復(fù)雜度為:O(mu×nu)for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)T[col][row]=M[row][col];.用“三元組”表示時(shí)如何實(shí)現(xiàn)？121415-522-731363428211451-522-713364328.

首先應(yīng)該確定每一行的第一個(gè)非零元在三元組中的位置。

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];.三元組快速轉(zhuǎn)置.StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&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];

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)置矩陣元素.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].

分析算法FastTransposeSMatrix的時(shí)間復(fù)雜度：時(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)…….

三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需隨機(jī)存取某一行中的非零元，則需從頭開(kāi)始進(jìn)行查找。二、行邏輯聯(lián)接的順序表.#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;}RLSMatrix;//行邏輯鏈接順序表類型

修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個(gè)數(shù)據(jù)成員rpos，其值在稀疏矩陣的初始化函數(shù)中確定。.例如：給定一組下標(biāo)，求矩陣的元素值ElemTypevalue(RLSMatrixM,intr,intc){

p=M.rpos[r];

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

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

returnM.data[p].e;

elsereturn0;}//value.矩陣乘法的精典算法: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ò)程可大致描述如下：.StatusMultSMatrix

(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){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;}//MultSMatrix.

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

Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//處理M當(dāng)前行中每一個(gè)非零元brow=M.data[p].j;//找到對(duì)應(yīng)元在N中的行號(hào)if(brow<N.nu)t=N.rpos[brow+1];//是否N最后一行

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)//壓縮存儲(chǔ)該行非零元 if(ctemp[ccol]){

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

}//if處理的每一行M.分析上述算法的時(shí)間復(fù)雜度累加器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)。.討論有沒(méi)有發(fā)現(xiàn)以上討論的矩陣運(yùn)算有沒(méi)有一個(gè)“適于采用順序結(jié)構(gòu)”的共同特點(diǎn)？如果矩陣運(yùn)算的結(jié)果將增加或減少已知矩陣中的非零元的個(gè)數(shù)，則顯然不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)以鏈?zhǔn)接诚笞鳛槿M線性表的存儲(chǔ)結(jié)構(gòu)。.三、十字鏈表30050-100200011314522-1312^^^^^^^.5.4廣義表的類型定義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基本操作:.廣義表是遞歸定義的線性結(jié)構(gòu)，LS=(1,2,,n)其中：i

或?yàn)樵踊驗(yàn)閺V義表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,,))).廣義表是一個(gè)多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce.廣義表

LS=(1,2,…,n)結(jié)構(gòu)特點(diǎn):1)廣義表中的數(shù)據(jù)元素有相對(duì)次序；2)廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；3)廣義表的深度定義為所含括弧的重?cái)?shù)；注意：“原子”的深度為0

“空表”的深度為14)廣義表可以共享；5)廣義表可以是一個(gè)遞歸的表。遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。.6)任何一個(gè)非空廣義表

LS=(1,2,…,n)

均可分解為

表頭

Head(LS)=1和

表尾

Tail(LS)=(2,…,n)兩部分。例如:

D=(E,F)=((a,(b,c))，F(xiàn))Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=().

結(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());.5.5

廣義表的表示方法通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn):原子結(jié)點(diǎn)：tag=1hptptag=0data.1)表頭、表尾分析法：構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法:若表頭為原子，則為空表

ls=NIL非空表lstag=1指向表頭的指針指向表尾的指針tag=0data否則，依次類推。..L=(a,(x,y),((x)))a(x,y)(

)

1LL=()0a

1

1

1

1

10a()x0x

10y.2)子表分析法：若子表為原子，則為空表

ls=NIL非空表1指向子表1

的指針tag=0data否則，依次類推。1指向子表2

的指針1指向子表n

的指針ls….例如:

a(x,y)((x))LS=(a,(x,y),((x)))ls.5.6廣義表操作的遞歸函數(shù)遞歸函數(shù)

一個(gè)含直接或間接調(diào)用本函數(shù)語(yǔ)句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件：1)在每一次調(diào)用自己時(shí)，必須是(在某種意義上)更接近于解;2)必須有一個(gè)終止處理或計(jì)算的準(zhǔn)則。.例如:

hanoi塔的遞歸函數(shù)voidhanoi(int

n,

charx,chary,charz){if

(n==1)move(x,1,z);else{

hanoi(n-1,x,z,y);move(x,n,z);

hanoi(n-1,

y,x,z);}}.二叉樹(shù)的遍歷void

PreOrderTraverse(

BiTree

T,void(Visit)(BiTreeP))

{

if(T)

{Visit(T->data);

(PreOrderTraverse(T->lchild,Visit);(PreOrderTraverse(T->rchild,Visit);

}}

//PreOrderTraverse.一、分治法(DivideandConquer)(又稱分割求解法)如何設(shè)計(jì)遞歸函數(shù)？二、后置遞歸法(Postponingthework)三、回溯法(Backtracking).

對(duì)于一個(gè)輸入規(guī)模為n的函數(shù)或問(wèn)題，用某種方法把輸入分割成k(1<k≤n)個(gè)子集，從而產(chǎn)生l

個(gè)子問(wèn)題，分別求解這l個(gè)問(wèn)題，得出

l

個(gè)問(wèn)題的子解，再用某種方法把它們組合成原來(lái)問(wèn)題的解。若子問(wèn)題還相當(dāng)大，則可以反復(fù)使用分治法，直至最后所分得的子問(wèn)題足夠小，以至可以直接求解為止。分治法的設(shè)計(jì)思想為:.

在利用分治法求解時(shí)，所得子問(wèn)題的類型常常和原問(wèn)題相同，因而很自然地導(dǎo)致遞歸求解。.例如:梵塔問(wèn)題:

Hanoi(n,x,y,z)可遞歸求解Hanoi(n-1,x,z,y)

將n個(gè)盤(pán)分成兩個(gè)子集(1至n-1和n)，從而產(chǎn)生下列三個(gè)子問(wèn)題：1)將1至n-1號(hào)盤(pán)從x軸移動(dòng)至y軸；3)將1至n-1號(hào)盤(pán)從y軸移動(dòng)至z軸；2)將n號(hào)盤(pán)從x軸移動(dòng)至z軸；可遞歸求解Hanoi(n-1,x,z,y).又如:遍歷二叉樹(shù):

Traverse(BT)

可遞歸求解Traverse(LBT)

將n個(gè)結(jié)點(diǎn)分成三個(gè)子集(根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù))，從而產(chǎn)生下列三個(gè)子問(wèn)題：1)訪問(wèn)根結(jié)點(diǎn)；3)遍歷右子樹(shù);2)遍歷左子樹(shù)；可遞歸求解Traverse(RBT).廣義表從結(jié)構(gòu)上可以分解成廣義表=表頭+表尾或者廣義表=

子表1+子表2+···+子表n

因此常利用分治法求解之。算法設(shè)計(jì)中的關(guān)鍵問(wèn)題是，如何將l

個(gè)子問(wèn)題的解組合成原問(wèn)題的解。.廣義表的頭尾鏈表存儲(chǔ)表示：typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//標(biāo)志域

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

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

};}*GListtag=1

hp

tpptr表結(jié)點(diǎn).例一求廣義表的深度例二復(fù)制廣義表例三創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu).廣義表的深度=Max{子表的深度}+1例一求廣義表的深度可以直接求解的兩種簡(jiǎn)單情況為：

空表的深度=1

原子的深度=0

將廣義表分解成n個(gè)子表，分別(遞歸)求得每個(gè)子表的深度，.

int

GlistDepth(GlistL){

//返回指針L所指的廣義表的深度

for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;

}

returnmax+1;}//GlistDepthif(!L)return1;if(L->tag==ATOM)return0;.111L…for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;

}例如:pppp->ptr.hppppppp->ptr.hppp->ptr.hp.例二復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡(jiǎn)單情況為：

空表復(fù)制求得的新表自然也是空表;

原子結(jié)點(diǎn)可以直接復(fù)制求得。

將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，.若ls=NIL則newls=NIL否則構(gòu)造結(jié)點(diǎn)newls,

由表頭ls->ptr.hp復(fù)制得newhp

由表尾ls->ptr.tp復(fù)制得newtp

并使newls->ptr.hp=newhp,newls->ptr.tp=newtp復(fù)制求廣義表的算法描述如下:. Status

CopyGList(Glist&T,GlistL){ if(!L)T=NULL;//復(fù)制空表

else{if(!(T=(Glist)malloc(sizeof(GLNode))))

exit(OVERFLOW);//建表結(jié)點(diǎn)

T->tag=L->tag;if(L->tag==ATOM)

T->atom=L->atom;//復(fù)制單原子結(jié)點(diǎn)

else{}

}//elsereturnOK;}//CopyGList分別復(fù)制表頭和表尾.CopyGList(T->ptr.hp,

L->ptr.hp);

//復(fù)制求得表頭T->ptr.hp的一個(gè)副本L->ptr.hpCopyGList(T->ptr.tp,

L->ptr.tp);//復(fù)制求得表尾T->ptr.tp的一個(gè)副本L->ptr.tp語(yǔ)句

CopyGList(T->ptr.hp,

L->ptr.hp);等價(jià)于

CopyGList(newhp,

L->ptr.tp);

T->ptr.hp=newhp;.例三創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)

對(duì)應(yīng)廣義表的不同定義方法相應(yīng)地有不同的創(chuàng)建存儲(chǔ)結(jié)構(gòu)的算法。.

假設(shè)以字符串S=(1,2,,n)

的形式定義廣義表L，建立相應(yīng)的存儲(chǔ)結(jié)構(gòu)。

由于S中的每個(gè)子串i定義L的一個(gè)子表，從而產(chǎn)生n個(gè)子問(wèn)題，即分別由這n個(gè)子串(遞歸)建立n個(gè)子表，再組合成一個(gè)廣義表。

可以直接求解的兩種簡(jiǎn)單情況為：由串(

)建立的廣義表是空表；由單字符建立的子表只是一個(gè)原子結(jié)點(diǎn)。.如何由子表組合成一個(gè)廣義表？

首先分析廣義表和子表在存儲(chǔ)結(jié)構(gòu)中的關(guān)系。先看第一個(gè)子表和廣義表的關(guān)系:1L指向廣義表的頭指針指向第一個(gè)子表的頭指針.再看相鄰兩個(gè)子表之間的關(guān)系:11指向第i+1個(gè)子表的頭指針指向第i個(gè)子表的頭指針可見(jiàn)，兩者之間通過(guò)表結(jié)點(diǎn)相鏈接。.若S=()

則L=NIL；否則，構(gòu)造第一個(gè)表結(jié)點(diǎn)*L，

并從串S中分解出第一個(gè)子串1，對(duì)應(yīng)創(chuàng)建第一個(gè)子廣義表L->ptr.hp；若剩余串非空，則構(gòu)造第二個(gè)表結(jié)點(diǎn)

L->ptr.tp，并從串S中分解出第二個(gè)子串2，對(duì)應(yīng)創(chuàng)建第二個(gè)子廣義表

……；

依次類推，直至剩余串為空串止。.void

CreateGList(Glist&L,StringS){if(空串)L=NULL;//創(chuàng)建空表

else{

L=(Glist)malloc(sizeof(GLNode));L->tag=List;

p=L;sub=SubString(S,2,StrLength(S)-1);//脫去串S的外層括弧

}//else}

由sub中所含n個(gè)子串建立n個(gè)子表;. do{sever(sub,

hsub);//分離出子表串hsub=i

if(!StrEmpty(sub){

p->ptr.tp=(Glist)malloc(sizeof(GLNode));

//建下一個(gè)子表的表結(jié)點(diǎn)*(p->ptr.tp)

p=p->ptr.tp;

}}while(!StrEmpty(sub));p->ptr.tp=NULL;//表尾為空表創(chuàng)建由串hsub定義的廣義表p->ptr.hp;.if(StrLength(hsub)==1){

p->ptr.hp=(GList)malloc(sizeof(GLNode));p->ptr.hp->tag=ATOM;p->ptr.hp->atom=hsub;//創(chuàng)建單原子結(jié)點(diǎn)}elseCreateGList(p->ptr.hp,hsub);

//遞歸建廣義表

.后置遞歸的設(shè)計(jì)思想為:.

遞歸的終結(jié)狀態(tài)是，當(dāng)前的問(wèn)題可以直接求解，對(duì)原問(wèn)題而言，則是已走到了求解的最后一步。鏈表是可以如此求解的一個(gè)典型例子。例如：編寫(xiě)“刪除單鏈表中所有值為x的數(shù)據(jù)元素”的算法。.1)單鏈表是一種順序結(jié)構(gòu)，必須從第一個(gè)結(jié)點(diǎn)起，逐個(gè)檢查每個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素；分析:2)從另一角度看，鏈表又是一個(gè)遞歸結(jié)構(gòu)，若L是線性鏈表(a1,a2,,an)的頭指針，則L->next是線性鏈表(a2,,an)的頭指針。.

a1

a2

a3

an

…L例如:

a1

a2

a3

an

L

a1

a2

a3

an

L已知下列鏈表1)“a1=x”，則L

仍為刪除x后的鏈表頭指針2)“a1≠x”，則余下問(wèn)題是考慮以L->next為頭指針的鏈表……

a1

L->nextL->next=p->nextp=L->next.void

delete(LinkList&L,ElemTypex)

{

//刪除以L為頭指針的帶頭結(jié)點(diǎn)的單鏈表中

//所有值為x的數(shù)據(jù)元素

if(L->next){

if(L->next->data==x){p=L->next;L->next=p->next;

free(p);delete(L,x);

}else

delete(L->next,x);

}}//delete.刪除廣義表中所有元素為x的原子結(jié)點(diǎn)分析:

比較廣義表和線性表的結(jié)構(gòu)特點(diǎn)：相似處：都是鏈表結(jié)構(gòu)。不同處：1)廣義表的數(shù)據(jù)元素可能還是個(gè)廣義表；

2)刪除時(shí)，不僅要?jiǎng)h除原子結(jié)點(diǎn)，還需要?jiǎng)h除相應(yīng)的表結(jié)點(diǎn)。.void

Delete_GL(Glist&L,AtomTypex)

{//刪除廣義表L中所有值為x的原子結(jié)點(diǎn)

if(L){

head=L->ptr.hp;

//考察第一個(gè)子表

if((head->tag==Atom)&&

(head->atom==x))

{}//刪除原子項(xiàng)x的情況

else{}//第一項(xiàng)沒(méi)有被刪除的情況

}}//Delete_GL………….p=L;L=L->ptr.tp;//修改指針free(head);//釋放原子結(jié)點(diǎn)free(p);//釋放表結(jié)點(diǎn)Delete_GL(L,x);//遞歸處理剩余表項(xiàng)

1L0x

1pL

head.if(head->tag==LIST)//該項(xiàng)為廣義表

Delete_GL(head,x);Delete_GL(L->ptr.tp,x);

//遞歸處理剩余表項(xiàng)

1L0a

1

1headL->ptr.tp.回溯法是一種“窮舉”方法。其基本思想為：

假設(shè)問(wèn)題的解為n元組(x1,x2,…,xn)，其中xi

取值于集合Si。

n

元組的子組(x1,x2,…,xi)(i<n)稱為部分解，應(yīng)滿足一定的約束條件。對(duì)于已求得的部分解(x1,x2,…,xi)，若在添加xi+1Si+1

之后仍然滿足約束條件，則得到一個(gè)新的部分解(x1,x2,…,xi+1),之后繼續(xù)添加xi+2Si+2

并檢查之。..例一、皇后問(wèn)題求解

設(shè)四皇后問(wèn)題的解為(x1,x2,x3,x4),

其中：xi(i=1,2,3,4)Si={1,2,3,4}約束條件為：其中任意兩個(gè)xi

和xj不能位于棋盤(pán)的同行、同列及同對(duì)角線。

按回溯法的定義，皇后問(wèn)題求解過(guò)程為：解的初始值為空；首先添加x1=1,之后添加滿足條件的x2=3，由于對(duì)所有的x3{1,2,3,4}都不能找到滿足約束條件的部分解(x1,x2,x3),

則回溯到部分解(x1),

重新添加滿足約束條件的x2=4,依次類推。. void

Trial(inti,intn)

{//進(jìn)入本函數(shù)時(shí)，在n×n棋盤(pán)前i-1行已放置了互不攻

//擊的i-1個(gè)棋子?，F(xiàn)從第i行起繼續(xù)為后續(xù)棋子選擇

//滿足約束條件的位置。當(dāng)求得(i>n)的一個(gè)合法布局

//時(shí)，輸出之。

if(i>n)輸出棋盤(pán)的當(dāng)前布局;

elsefor(j=1;j<=n;++j){

在第i行第j列放置一個(gè)棋子;

if(當(dāng)前布局合法)Trial(i+1,n);

移去第i行第j列的棋子;

}}//trial.回溯法求解的算法一般形式：void

B(inti,intn){

//假設(shè)已求得滿足約束條件的部分解(x1,...,xi-1)，本函

//數(shù)從xi起繼續(xù)搜索，直到求得整個(gè)解(x1,x2,…xn)。

if(i>n)

elsewhile(!Empty(Si)){

從Si

中取xi

的一個(gè)值

viSi;

if(x1,x2,…,xi)滿足約束條件

B(i+1,n);//繼續(xù)求下一個(gè)部分解

從Si

中刪除值

vi;}}//B. 綜合幾點(diǎn)：1.

對(duì)于含有遞歸特性的問(wèn)題，最好設(shè)計(jì)遞歸形式的算法。但也不要單純追求形式，應(yīng)在算法設(shè)計(jì)的分析過(guò)程中“就事論事”。例如，在利用分割求解設(shè)計(jì)算法時(shí)，子問(wèn)題和原問(wèn)題的性質(zhì)相同；或者，問(wèn)題的當(dāng)前一步解決之后，余下的問(wèn)題和原問(wèn)題性質(zhì)相同，則自然導(dǎo)致遞歸求解。.2.實(shí)現(xiàn)遞歸函數(shù)，目前必須利用“?！?。一個(gè)遞歸函數(shù)必定能改寫(xiě)為利用棧實(shí)現(xiàn)的非遞歸函數(shù)；反之，一個(gè)用棧實(shí)現(xiàn)的非遞歸函數(shù)可以改寫(xiě)為遞歸函數(shù)。需要注意的是遞歸函數(shù)遞歸層次的深度決定所需存儲(chǔ)量的大小。.3.

分析遞歸算法的工具是遞歸樹(shù)，從遞歸樹(shù)上可以得到遞歸函數(shù)的各種相關(guān)信息。例如：遞歸樹(shù)的深度即為遞歸函數(shù)的遞歸深度；遞歸樹(shù)上的結(jié)點(diǎn)數(shù)目恰為函數(shù)中的主要操作重復(fù)進(jìn)行的次數(shù)；若遞歸樹(shù)蛻化為單支樹(shù)或者遞歸樹(shù)中含有很多相同的結(jié)點(diǎn)，則表明該遞歸函數(shù)不適用。.

例如:n=3的梵塔算法中主要操作move的執(zhí)行次數(shù)可以利用下列遞歸樹(shù)進(jìn)行分