專業(yè)課參考數(shù)據(jù)結(jié)構(gòu)

1第5章數(shù)組與廣義表25.1數(shù)組的概念數(shù)量固定，數(shù)據(jù)類型相同的（變量）元素組合在一起。使用一個(gè)名稱代表它。這個(gè)名稱就是數(shù)組名。如果要訪問其中某個(gè)元素(變量)，可以使用元素的索引值(下標(biāo))來訪問它。在C語言中，數(shù)組元素的索引值從0開始。

intA[30][10];e=A[i][j];

intA[c1..d1,c2..d2]

更一般情況：子界35.1數(shù)組的概念數(shù)組的邏輯結(jié)構(gòu) 1.線性結(jié)構(gòu)擴(kuò)展AMN=a00a01…

a0N-1a10a11…

a1N-1aM-10aM-11…aM-1N-1

A=(A0，A1，…，AN-1)其中：Ai=(a0i,a1i,…,Am-1i)(0≤i≤N-1)二維數(shù)組是數(shù)據(jù)元素為線性表的線性表45.1數(shù)組的概念數(shù)組的邏輯結(jié)構(gòu)2.二維數(shù)組中的每個(gè)元素都受兩個(gè)線性關(guān)系的約束——行關(guān)系、列關(guān)系A(chǔ)MN=a00a01…

a0N-1a10a11…

a1N-1aM-10aM-11…aM-1N-1在行關(guān)系中aij直接前趨是aij-1aij直接后繼是aij+1在列關(guān)系中aij直接前趨是ai-1jaij直接后繼是ai+1jN維數(shù)組中的每個(gè)元素都受N個(gè)線性關(guān)系的約束55.1數(shù)組的概念數(shù)組的基本操作初始化操作InitArray(&A,n,bound1,…,boundn)銷毀操作DestroyArray(&A)讀元素操作Value(A,&e,index1,…,indexn)寫元素操作Assign(&A,e,index1,…,indexn)在高級語言中的典型體現(xiàn)：intA[M][N];A[i][j]=x;寫y=A[i][j];讀AMN=a00a01…

a0N-1a10a11…

a1N-1aM-10aM-11…aM-1N-165.1數(shù)組的概念數(shù)組的基本操作1. 讀：給定一組下標(biāo)，讀出對應(yīng)的數(shù)組元素；2. 寫：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)組元素。 讀/寫操作本質(zhì)上只對應(yīng)一種操作——尋址。確定指定元素在內(nèi)存中的物理地址。數(shù)組的存儲 兩種形式：既可以是順序存儲，也可以采用鏈?zhǔn)浇Y(jié)構(gòu)。75.2數(shù)組的存儲和實(shí)現(xiàn)數(shù)組的存儲結(jié)構(gòu)與尋址——一維數(shù)組 設(shè)具有M個(gè)元素的一維數(shù)組的下標(biāo)范圍為閉區(qū)間[0,M-1]，每個(gè)數(shù)組元素占用L

個(gè)存儲單元。La0ai-1ai……aM-1a1……Loc(a0)Loc(ai)

ai

的存儲地址：Loc(ai

)＝Loc(a0)＋i×L

85.2數(shù)組的存儲和實(shí)現(xiàn)數(shù)組的存儲結(jié)構(gòu)與尋址——二維數(shù)組常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。按列優(yōu)先：先列后行，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。

二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)95.2數(shù)組的存儲和實(shí)現(xiàn)二維數(shù)組——按行優(yōu)先（M×N）0N-1

0M-1aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=i×N＋j本行中aij

前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)aijLoc(aij)

=Loc(a00)＋(N×i＋j)×L105.2數(shù)組的存儲和實(shí)現(xiàn)二維數(shù)組——按行優(yōu)先的更一般情況l2h2

l1h1aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)aijLoc(aij)＝Loc(al1l2)+((i-l1)×(h2-l2+1)+(j-l2))×L本行中aij

前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)115.2數(shù)組的存儲和實(shí)現(xiàn)三維數(shù)組 三維數(shù)組：A[m1,m2,m3]：Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×L

125.2數(shù)組的存儲和實(shí)現(xiàn)N維數(shù)組 一般的N維數(shù)組：A[b1,b2,…,bn]：

Loc(j1,j2,…,jn)=Loc(0,0,…,0)+(∑ji∏bk+jn)L =Loc(0,0,…,0)+∑ciji 其中：cn=L，ci-1=bi×ci，1＜i≤n。ni=1數(shù)組基址Ci為常數(shù)k=i+1nN-1i=1135.2數(shù)組的存儲和實(shí)現(xiàn)二維數(shù)組——靜態(tài)數(shù)組表示法 typedefElemTypeArray[m*n]; ArrayA;

Amn=a00a01…

a0n-1a10a11…

a1n-1

……am-10am-11…am-1n-1a00….a0n-1a10….a1n-1….am-10….am-1n-1145.2數(shù)組的存儲和實(shí)現(xiàn)數(shù)組的動態(tài)表示法 typedefstruct{ ElemType*base;//動態(tài)空間基址

intdim;//數(shù)組維數(shù)

int*bound；//維界基址

int*constants;//數(shù)組映像函數(shù)常量基址 }Array;A.baseA.dimA.boundsA.constantsb1b2b3c1c2c3a000a0013A[b1][b2][b3]15初始化數(shù)組操作

StatusInitArray(Array2&A,intb1,intb2){//數(shù)組的初始化

if(b1<=0||b2<=0)returnERROR;else{A.bound1=b1;A.bound2=b2;if(!(A.base=(ElemType*)malloc(b1*b2*sizeof(ElemType))))exit(OVERFLOW);returnOK;}}16銷毀數(shù)組操作StatusDestroyArray(Array2&A){/*銷毀數(shù)組A*/if(A.base){free(A.base);A.base=NULL;A.bound1=0;A.bound2=0;returnOK;}elsereturnERROR;}17

讀元素操作StatusValue(Array2A,ElemType&e,intj1,intj2){/*若各下標(biāo)不超界，則將所指定的A的元素值賦值給e，并返回OK*/if((j1<0)||(j1>=A.bound1)||(j2<0)||(j2>=A.bound2))returnERROR;e=*(A.base+A.bound2*j1+j2);returnOK;}18寫元素操作StatusAssign(Array2&A,ElemTypee,intj1,intj2){/*若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。*/if((j1<0)||(j1>=A.bound1)||(j2<0)||(j2>=A.bound2))returnERROR;*(A.base+A.bound2*j1+j2)=e;returnOK;}19n維數(shù)組元素存儲地址的計(jì)算(低下標(biāo)優(yōu)先)

假設(shè)數(shù)組Ab1b2,…,bn

每個(gè)元素占用L個(gè)存儲單元，Loc(j1,j2,…,jn)為元素aj1j2…jn

的存儲地址。Loc(0,0,…,0)是數(shù)組A的基址。Loc(j1,j2,…,jn)=Loc(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)L=Loc(0,…,0)+c1j1+c2j2+…+cn-1jn-1+cnjnintB[4][3][5]a000a001a00b1-1a010a011a01b1-1a020a021a02b1-1205.3矩陣的壓縮存儲

5.3.1特殊矩陣的壓縮存儲

5.3.2稀疏矩陣的壓縮存儲215.3.1特殊矩陣 值相同元素或者非零元素的分布有一定規(guī)律的矩陣，稱為特殊矩陣。對稱矩陣、上（下）三角矩陣。a11a12…

a1na21a22…

a2n……am1am2…

amna11a12…

a1n0

a22…

a2n

……00…

amn225.3.1特殊矩陣對稱矩陣/上（下）三角矩陣 用一維數(shù)組，按行優(yōu)先存儲下三角元素。a11

a12a13a14…

a1na21a22

a23a24…

a2na31a32a33

a34

…a3n…an1an2an3an4

…

anna11a21a22

a31a32a33

…

an1an2…

ann

012345n(n+1)/2-1k=i(i-1)/2+j-1當(dāng)ijj(j-1)/2+i-1當(dāng)ij性質(zhì)：aij=aji1≤i,j≤n對于下標(biāo)i,j，線性地址235.3.2稀疏矩陣含有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。討論含有較多零元素的稀疏矩陣的壓縮存儲。M

=

012900000000000-3000014000240000018000001500-7000M有42（67）個(gè)元素，有8個(gè)非零元素如何進(jìn)行稀疏矩陣的壓縮存儲？？245.3.2稀疏矩陣三元組順序表M

=

012900000000000-3000014000240000018000001500-7000采用三元組存儲：(行,列,值)(

(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ù)和列數(shù)：6,7

255.3.2稀疏矩陣三元組順序表

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

ElemTypee;//非零元值

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

//用于存儲三元組表,data[0]未用

intmu,nu,tu;//行數(shù)、列數(shù)和非零元個(gè)數(shù)

}TSMatrix;265.3.2稀疏矩陣三元組表的順序存儲M

=

012900000000000-3000014000240000018000001500-7000ije12345678M.dataM.muM.nuM.tu31-361151212521813

9432464-73614678

按行（行內(nèi)按列）順序存儲非零元素。275.3.2稀疏矩陣三元組表的順序存儲——轉(zhuǎn)置算法M

=

012900000000000-3000014000240000018000001500-7000

T

=

00-3001512000180900240000000-70000000014000000000

基本算法：交換對應(yīng)行、列位置上的元素。285.3.2稀疏矩陣一般矩陣的轉(zhuǎn)置算法

…

inta[m][n],b[m][n];for(i=0;i<m;++i)

for(j=0;j<n;++j)b[j][i]=a[i][j];

…算法的時(shí)間復(fù)雜度為：O(m*n)295.3.2稀疏矩陣ije12345678M.dataM.muM.nuM.tu31-361151212521813

9432464-7361467821124

6

-713

-33

42416

1531963

142

518ije12345678M.dataM.muM.nuM.tu678305.3.2稀疏矩陣轉(zhuǎn)置運(yùn)算算法TransposeSMatrix(TSMatrixM,TSMatrix&T)基本思想 對M.data從頭至尾掃描：

第一次掃描時(shí)，將M.data中列號為1的三元組賦值到T.data中； 第二次掃描時(shí)，將M.data中列號為2的三元組賦值到T.data中； 依此類推，直至將M.data所有三元組賦值到T.data中。31121213931-3361443245218611564-7ijvijv31-325

1813

-361

1516

5121221

1252

1813931

943

2434

2464

-746

-7361463

14M.dataT.data第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素5.3.2稀疏矩陣第七次掃描查找第7列元素三元組表的順序存儲——轉(zhuǎn)置算法325.3.2稀疏矩陣StatusTranMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu)//非零元素個(gè)數(shù)!=0{q=1;//q為當(dāng)前三元組在T.data[]存儲位置(下標(biāo))

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

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

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;}

}//if

returnOK;}//TranMtrix算法的時(shí)間復(fù)雜度：O(nu*tu)335.3.2稀疏矩陣時(shí)間復(fù)雜度分析轉(zhuǎn)置算法TranMatrix的時(shí)間復(fù)雜度為O(nutu)當(dāng)非零元的個(gè)數(shù)tu和矩陣元素個(gè)數(shù)munu同數(shù)量級時(shí)，轉(zhuǎn)置運(yùn)算算法的時(shí)間復(fù)雜度為O(numunu)算法一般用于tu<<munu的情況345.3.2稀疏矩陣提高算法效率num[col]：存儲M第col列非零元個(gè)數(shù)cpos[col]：存儲M第col列第一個(gè)非零元在T.data中的位置121213931-3361443245218611564-7ijvM.datacpos[col]的計(jì)算方法：

cpos[1]=1cpos[col]=cpos[col-1]+num[col-1]2colncolnum[col]cpot[col]1234567

22811012785319355.3.2稀疏矩陣第3列第二個(gè)非零元在b中的位置121213931-3361443245218611564-7colnum[col]cpot[col]1234567228110135278M.dataT.data12122112第2列第一個(gè)非零元在b中的位置139第3列第一個(gè)非零元在b中的位置31931-313-33614631443243424521825186115161564-746-74第2列第二個(gè)非零元在b中的位置65第4列第二個(gè)非零元在b中的位置第1列第一個(gè)非零元在b中的位置2793第6列第一個(gè)非零元在b中的位置掃描M.data實(shí)現(xiàn)M到T的轉(zhuǎn)置809365.3.2稀疏矩陣StatusFastTransMatrix(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;//求M中每一列非零元個(gè)數(shù)

for(t=1;t<=M.tu;++t)++num[M.data[t].j];

//求第col列中第一個(gè)非零元在T.data中的序號

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];375.3.2稀疏矩陣

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

}//if

returnOK;

}//FastTranMatrix時(shí)間復(fù)雜度分析 算法中有四個(gè)并列的單循環(huán)，循環(huán)次數(shù)分別為nu、tu、nu和tu，時(shí)間復(fù)雜度為：O(nu+tu)385.3.2稀疏矩陣行邏輯鏈接順序表#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXMN+1];

//每行第一個(gè)元素的位置表intmu,nu,tu;}RLSMatrix;121213931-3361443245218611564-7123456M.rpos

M.muM.nuM.tu678103567395.3.2稀疏矩陣?yán)航o定一組下標(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;}//value405.3.2稀疏矩陣稀疏矩陣的鏈?zhǔn)酱鎯Α宙湵聿捎面溄哟鎯Y(jié)構(gòu)存儲三元組表，每個(gè)非零元素對應(yīng)的三元組存儲為一個(gè)鏈表結(jié)點(diǎn)：rowcolitemdownrightrow：存儲非零元素的行號col：存儲非零元素的列號item：存儲非零元素的值right：指針域，指向同一行中的下一個(gè)三元組down：指針域，指向同一列中的下一個(gè)三元組415.3.2稀疏矩陣稀疏矩陣的鏈?zhǔn)酱鎯Α宙湵?0050-1002000M=11331222-1145M.cheadM.rhead425.3.2稀疏矩陣十字鏈表的類型定義typedefstructOLNode{introw,col;//非零元的行下標(biāo)和列下標(biāo)

ElemTypee;//非零元值

structOLNode*right,*down}OLNode,OLink;typedefstruct{OLink*rhead,*chead;//行/列表頭指針數(shù)組

intmu,nu,tu;//行數(shù)、列數(shù)和非零元個(gè)數(shù)}CrossList;43廣義表(generalizedlist)的概念 廣義表是一種不同構(gòu)的線性結(jié)構(gòu)，5.4.1廣義表的定義

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

或?yàn)樵?atom)

或?yàn)閺V義表。廣義表的基本性質(zhì)1.廣義表的定義是一個(gè)遞歸定義，因?yàn)樵诿枋鰪V義表時(shí)又用到了廣義表；2.在線性表中數(shù)據(jù)元素是單個(gè)元素，而在廣義表中，元素可以是單個(gè)元素稱為原子(atom)，也可以是廣義表，稱為廣義表的子表(sublist)；3.當(dāng)每個(gè)元素均為原子且類型相同時(shí)，就是線性表。44廣義表的術(shù)語5.4.1廣義表的定義LS=(1,2,,n)表頭head表名表尾tailn是表長

表頭：LS的第一個(gè)元素稱為表頭

表尾：其余元素組成的表稱為LS的表尾 表長：為最外層包含元素個(gè)數(shù)

深度：所含括弧的重?cái)?shù)。原子的深度為0，“空表”的深度為

1。455.4.1廣義表的定義例：A=()空表

B=(b,c,d)C=(a,B)=(a,(b,c,d))D=(A,B,C)=((),(b,c,d),(a,(b,c,d)))特點(diǎn)有次序有長度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享465.4.1廣義表的定義例：A=()空表

B=(b,c,d)C=(a,B)=(a,(b,c,d))D=(A,B,C)=((),(b,c,d),(a,(b,c,d)))表長：0；深度：1表長：3，深度：1表長：2，深度：2表長：3，深度：3遞歸表共享表E=(a,E)=(a,(a,E))=(a,(a,(a,….)))475.4.1廣義表的定義廣義表的圖形化表示ABDCeabcdA=(a,(b,A))D=(A,B,C)=((),(e),(a,(b,c,d)

))Aab表長：3深度：3表長：2深度：∞深度＝括號的重?cái)?shù)＝○結(jié)點(diǎn)的層數(shù)用○表示子表用□表示原子48 任何一個(gè)非空廣義表LS=(1,2,…,n)均可分解為

表頭

Head(LS)=1和

表尾

Tail(LS)=(2,…,n)兩部分。5.4.1廣義表的定義例如：D=(E,F)=((a,(b,c))，F(xiàn))Head(D

)=

Tail(D)=Head(

E

)=Tail(

E)=Head(

((b,c)))=

Tail(((b,c)))=Head(

(b,c)

)=

Tail((b,c))=Head((c))=

Tail((c))=E(F)a((b,c))(b,c)()b(

c

)c()49廣義表的基本操作教材P1071）創(chuàng)建空的廣義表L；

2）銷毀廣義表L；

3）已有廣義表L，由L復(fù)制得到廣義表T；

4）求廣義表L的長度；

5）求廣義表L的深度；

6）判廣義表L是否為空；

7）取廣義表L的表頭；

8）取廣義表L的表尾；

9）在L中插入元素作為L的第一個(gè)元素；

10）刪除廣義表L的第一個(gè)元素，并e用返回其值；

11）遍歷廣義表L，用函數(shù)visit()處理每個(gè)元素；5.4.1

廣義表的定義50 廣義表中的數(shù)據(jù)元素可能為原子或列表，由此需要兩種結(jié)點(diǎn)：

表結(jié)點(diǎn)：用以表示廣義表；

原子結(jié)點(diǎn)：用以表示原子。5.4.2

廣義表的存儲結(jié)構(gòu)tagptr表結(jié)點(diǎn)1

hptpdata0tagatom原子結(jié)點(diǎn)鏈表存儲方式51結(jié)點(diǎn)的類型定義Typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子，LIST==1:列表TypedefstructGLNode{ElemTagtag;

//標(biāo)志域

union{AtomType

atom;//原子結(jié)點(diǎn)的值域struct{structGLNode*hp,*tp;}

ptr;

//表結(jié)點(diǎn)的指針域：ptr.hp指表頭，ptr.tp指表尾

};}*Glist;5.4.2

廣義表的存儲結(jié)構(gòu)tagptr表結(jié)點(diǎn)1

hptpdata0tagatom原子結(jié)點(diǎn)52廣義表存儲方式5.4.2

廣義表的存儲結(jié)構(gòu)若表頭為原子，則為空表

ls=NULL非空表lstag=1指向表頭的指針指向表尾的指針tag=0data否則，依次類推。tag=1∧

∧

53廣義表(α1,α2…αn)的兩種分解方法5.4.2

廣義表的存儲結(jié)構(gòu)廣義表：表頭+表尾廣義表L=(α1,α2…αn)

表頭:α1

表尾:(α2,

…,αn)廣義表L=(α1,α2…αn)

子表:α1α2α3…αn

廣義表：子表1+子表2+···+子表n

54頭尾表構(gòu)造法5.4.2

廣義表的存儲結(jié)構(gòu)L=(a,(b,c),((d)))1L0a

111111a((b,c),((d)))

(b,c)b(c)c(((d)))((d))

(d)d0b

0c

0d55

bc子表構(gòu)造法5.4.2

廣義表的存儲結(jié)構(gòu)L=(a,(b,c),((d)))

a(b,c)((d))1L1111

(d)11

d0a0b0c0d56

廣義表存儲方式5.4.2

廣義表的存儲結(jié)構(gòu)A=()

B=(e)C=(a,(b,c,d))D=(A,B,C)A=NULL∧1B0eD11∧1∧a((b,c,d))(b,c,d)b(c,d)c(d)d()C1∧111∧0a0b0c0d()157廣義表是遞歸結(jié)構(gòu)，所以廣義表的許多操作可以用遞歸算法實(shí)現(xiàn)。5.4.3

廣義表操作的實(shí)現(xiàn)遞歸函數(shù)一個(gè)含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件：1.在每一次調(diào)用自己時(shí)，必須是（在某種意義上）更接近于解;2.必須有一個(gè)終止條件。58一、分治法(DivideandConquer)(又稱分割求解法)如何設(shè)計(jì)遞歸函數(shù)？二、后置遞歸法(Postponingthework)三、回溯法(Backtracking)59遞歸算法的基本思路——分治法

對于一個(gè)輸入規(guī)模為n

的函數(shù)或問題，用某種方法把輸入分解成k(1<k≤n)個(gè)子集，從而產(chǎn)生h個(gè)子問題，分別求解這h

個(gè)問題，得出h個(gè)問題的子解，再用某種方法把它們組合成原來問題的解。若子問題規(guī)模還相當(dāng)大，則可以反復(fù)使用分治法，直至最后所分得的子問題足夠小，直到可以直接求解為止。60遞歸算法的基本思路——后置法例：單鏈表的遞歸刪除61

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

取值于集合Si。

n

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

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

并檢查之;若對于所有取值于集合Si+1的xi+1都不能得到新的滿足約束條件的部分解(x1,x2,

，xi+1)，則從當(dāng)前子組中刪去xi,回溯到前一個(gè)部分解(x1,x2,

,xi-1)，重新添加那些值集Si中尚未考察過的xi，看是否滿足約束條件。如此反復(fù)進(jìn)行，直至求得滿足約束條件的問題的解，或者證明問題無解。例：皇后問題遞歸算法的基本思路——回溯法625.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)

廣義表L的深度=廣義表L中括號重?cái)?shù)GListDepth(L)=1+MAX(GListDepth(L的元素))

GListDepth(L)例L=(a,(b,c),((d)))

GListDepth((b,c))GListDepth(a)

GListDepth(((d)))=0原子=1線性表=2=3635.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)GListDepth(L)的遞歸描述直接求解空表：深度=1

原子：深度=0分解：將廣義表分解成n個(gè)子表，分別求得每個(gè)子表的深度。組合：廣義表的深度=max{子表的深度}+1645.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)((d))

L=(a,(b,c),((d)))的深度(b,c)a1

L111110d

10c

0b

0a

655.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)

intGListDepth(GListL){//采用頭尾鏈表存儲結(jié)構(gòu)，求廣義表L的深度

if(!L)return1;//空表深度1

if(L->tag==ATOM)return0;//原子深度0

for(max=0,pp=L;pp;pp=pp->ptr.tp)

{dep=GListDepth(pp->ptr.hp);if(dep>max)max=dep;

}returnmax+1;}665.4.3

廣義表操作的實(shí)現(xiàn)復(fù)制廣義表CopyGList(T,L)1

L111110d

10c

0b

0a

L=(a,(b,c),((d)))表頭表尾675.4.3

廣義表操作的實(shí)現(xiàn)voidGListCopy(GList&T,GListL){/*由廣義表L復(fù)制得到廣義表T*/

if(!L)T=NULL;

//復(fù)制空表

else

{T=(GList)malloc(sizeof(GLNode));//建表結(jié)點(diǎn)if(!T)exit(OVERFLOW);T->tag=L->tag;

if(L->tag==ATOM)T->data=L->data;//原子

else{GListCopy(T->ptr.hp,L->ptr.hp);//復(fù)制hpGListCopy(T->ptr.tp,L->ptr.tp);//復(fù)制tp

}

}}685.4.3

廣義表操作的實(shí)現(xiàn)建立廣義表輸入：字符串(1,2,,n)結(jié)果:建立廣義表的頭尾鏈表分解：將廣義表分解成n個(gè)子表1,2,,n，分別建立1,2,,n

對應(yīng)的子表。直接求解：空表:NULL

原子:建立原子結(jié)點(diǎn)

組合：將n個(gè)子表組合成一個(gè)廣義表695.4.3

廣義表操作的實(shí)現(xiàn)建立廣義表子表和廣義表的關(guān)系相鄰兩個(gè)子表之間的關(guān)系((d))(b,c)a子表1

L111110d

10c

0b

0a

705.4.3

廣義表操作的實(shí)現(xiàn)voidCreateGList(GList&L,charstr[]){if(strcmp(str,"()“)==0)L=NULL;//空表

else{if(strlen(str)==1){//建原子結(jié)點(diǎn)

L=(GList)malloc(sizeof(GLNode));L->tag=ATOM;L->atom=str[0];}else{//非空表，建表結(jié)點(diǎn)

L=(GList)malloc(sizeof(GLNode));L->tag=LIST; p=L;SubString(sub,str,2,strlen(str)-2);//脫外層括號

由sub中所含n個(gè)子串建立n個(gè)子表;}}//else}//CreateGList715.4.3

廣義表操作的實(shí)現(xiàn)do{//由sub中所含n個(gè)子串建立n個(gè)子表

sever(sub,hsub);//分離出子表串hsub=i

CreateGList(p->ptr.hp,hsub);

//建hsub對應(yīng)的子表

if(!strempty(sub)){//建下一個(gè)子表的表結(jié)點(diǎn)

p->ptr.tp=(GList)malloc(sizeof(GLNode));p->tag=LIST;p=p->ptr.tp;}//if}while(!strempty(sub));p->ptr.tp=NULL;//最后一個(gè)子表的表結(jié)點(diǎn)725.4.3

廣義表操作的實(shí)現(xiàn)刪除廣義表中所有元素為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)。735.4.3

廣義表操作的實(shí)現(xiàn)voidDelete_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)沒有被刪除的情況

}}//Delete_GL745.4.3

廣義表操作的實(shí)現(xiàn)voidDelete_GL(Glist&L,AtomTypex)p=L;L=L->ptr.tp;//修改指針free(head);//釋放原子結(jié)點(diǎn)free(p);//釋放表結(jié)點(diǎn)Delete_GL(L,x);

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

1L0x

1pL

head755.4.3

廣義表操作的實(shí)現(xiàn)voidDelete_GL(Glist&L,AtomTypex)if(head->tag==LIST)//該項(xiàng)為廣義表

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

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

1L0a

1

1headL->ptr.tp765.4.3

廣義表操作的實(shí)現(xiàn)voidInitGList(GList&L){ L=N