(1.6)-第五章 數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表新

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

廣義表的存儲(chǔ)結(jié)構(gòu)5.7廣義表操作的遞歸函數(shù)5.6

m元多項(xiàng)式的表示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>|0

jk

bk-1,1

k

n且k

i,0

ji

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和各維長度合法，則構(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)只有引用型操作，沒有加工型操作；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

推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。其中cn=L，ci-1=bi×ci

,1<i

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

ji

i=1n//－－－－數(shù)組的順序存儲(chǔ)表示－－－－#include<stdarg.h>//標(biāo)準(zhǔn)頭文件，提供宏va_start、va_arg和va_end,用于存取變長參數(shù)表#defineMAX_ARRAY_DIM8//假設(shè)數(shù)組維數(shù)的最大值為8typedef

struct{

ElemType*base;//數(shù)組元素地址，由InitArray分配

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

int*bounds;//數(shù)組維界基址，由InitArray分配

int*constants;//數(shù)組映像函數(shù)常量基址，由InitArray分配}Array;//－－－－基本操作的算法描述－－－－StatusInitArray(Array&A,intdim,…);

//若維數(shù)dim和隨后的各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。if(dim<1||dim>MAX.ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)

exit(OVERFLOW);

//若各維長度合法，則存入A.bounds，并求出A的元素總數(shù)elemtotalelemtotal=1;

va_start(ap,dim);//ap為va_list類型，是存放變長參數(shù)表信息的數(shù)組

for(i=0;i<dim;++i){A.bounds[i]=va.arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;

elemtotal*=A.bounds[i];}va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);//求映像函數(shù)的常數(shù)ci,并存入A.constants[i-1],i=1,…,dimA.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;//L=1,指針的增減以元素的大小為單位for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}Status

DestroyArray(Array&A){//銷毀數(shù)組A

if(!A.base)returnERROR;

free(A.base);A.base=NULL;

if(!A.bounds)returnERROR;

free(A.bounds);A.bounds=NULL;

if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;

returnOK;}

StatusLocate(ArrayA,va_listap,int&off){

//若ap指示的各下標(biāo)值合法，則求出該元素在A中相對(duì)地址offoff=0;

for(i=0;i<A.dim;++i){

ind=va_arg(ap,int);if(ind<0||ind>=A.bounds[i])returnOVREFLOW;

off+=A.constants[i]*ind;}

return

OK;}

StatusValue(ArrayA,ElemType&e,…){

//A是n維數(shù)組，e為元素變量，隨后是n各下標(biāo)值。//若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK

va_start(ap,e);if((result=Loate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}

StatusAssign(Array&A,ElemTypee,…){

//A是n維數(shù)組，e為元素變量，隨后是n各下標(biāo)值。//若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK

va_start(ap,e);if((result=Loate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱為稀疏因子。通常認(rèn)為

0.05的矩陣為稀疏矩陣。5.3矩陣的壓縮存儲(chǔ)何謂稀疏矩陣？以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問題:1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。1)盡可能少存或不存零值元素；解決問題的原則: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

typedef

struct{

int

i,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];Status

FastTransposeSMatrix(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)置矩陣元素算法5.2Col=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]

轉(zhuǎn)置矩陣元素：分析算法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ī)存取某一行中的非零元，則需從頭開始進(jìn)行查找。為便于隨機(jī)存取某一行中的非零元，則需知道每一行的第一個(gè)非零元在三元組表中的位置。為此，可將上節(jié)快速轉(zhuǎn)置矩陣算法中建立的，指示‘行’信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。稱這種‘帶行鏈接信息’的三元組表為行邏輯鏈接的順序表。二、行邏輯聯(lián)接的順序表

#defineMAXMN500

typedef

struct{

Tripledata[MAXSIZE+1];//非零元三元組表

intrpos[MAXRC+1];//各行第一個(gè)非零元的位置表

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

RLSMatrix;//行邏輯鏈接順序表類型行邏輯鏈接的順序表的類型描述如下：例如：給定一組下標(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)

兩個(gè)矩陣相乘的經(jīng)典算法。若設(shè)Q=M*N其中，M是m1*n1矩陣，N是n1*m2矩陣，則

Q初始化；

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

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

//處理M的每一行

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

}//forarow

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

M

N）

的過程可大致描述如下：

Status

MultSMatrix

(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算法5.3

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分析上述算法的時(shí)間復(fù)雜度累加器ctemp初始化的時(shí)間復(fù)雜度為

(M.mu

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

(M.tu

N.tu/N.mu)，進(jìn)行壓縮存儲(chǔ)的時(shí)間復(fù)雜度為

(M.mu

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

(M.mu

N.nu+M.tu

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

M

m

n，N中非零元的個(gè)數(shù)

N.tu=

N

n

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

(m

p

(1+n

M

N))，當(dāng)

M<0.05和

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

(m

p)。三、十字鏈表對(duì)稀疏矩陣的每個(gè)非零元，建立一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)形式如下：ijvdownright其中：i、j和v分別表示該非零元所在的行、列和非零元的值。向右域right指向同一行中下一個(gè)非零元，向下域down指向同一列中下一個(gè)非零元。每個(gè)非零元既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)，整個(gè)矩陣構(gòu)成一個(gè)十字交叉的鏈表。例如：30050-100200011314522-1312^^^^^^^typedef

struct

OLNode{

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

ElemTypee;

struct

OLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域}OLNode;*OLink;typedef

struct{

OLink*rhead,*chead;//行和列鏈表頭指針向量基址由CreateSMatrix分配

intmu,nu,tu;//稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)}CrossList;

Status

CreateSMatrix_OL(CrossList&M){//創(chuàng)建稀疏矩陣M。采用十字鏈表存儲(chǔ)表示。

if(M)free(M);

scanf(&m,&n,&t);//輸入M的行數(shù)、列數(shù)和非零元個(gè)數(shù)

M.mu:=m;M.nu=n;M.tu:=t;

if(!(M.rhead)=(OLink*)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);if(!(M.chead)=(OLink*)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);

M.rhead[]=M.chead[]=NULL;

//初始化行列頭指針向量，各行列鏈表為空鏈表

for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)

){//按任意次序輸入非零元算法5.4

if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->i=i;p->j=j;p->e=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.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}else{//尋查在行表中的插入位置

for(q=M.chead[i];(q->down)&&q->down->j<j;q=q->down);p->down=q->down;q->down=p;}//完成列插入}

returnOK;}//CreateSMatrix_OL5.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}}ADT

Glist基本操作:顧名思義，廣義表是線性表的推廣，也稱其為列表。廣義表是遞歸定義的線性結(jié)構(gòu)，廣義表一般記作：

LS=(

1,

2,

,

n)

其中：n是它的長度，

i

或?yàn)樵踊驗(yàn)閺V義表。習(xí)慣上，用大寫字母表示廣義表的名稱，用小寫字母表示原子。稱

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

2,

,

n)是LS的表尾。例如:

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)廣義表的長度定義為最外層包含元素個(gè)數(shù)；3)廣義表的深度定義為所含括弧的重?cái)?shù)；注意：“原子”的深度為0

“空表”的深度為14)廣義表可以共享；5)廣義表可以是一個(gè)遞歸的表。遞歸表的深度是無窮值，長度是有限值。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廣義表的存儲(chǔ)結(jié)構(gòu)通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn):原子結(jié)點(diǎn)：tag=1hptptag=0data1)表頭、表尾分析法：構(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

10x

()x((x,y),((x)))(((x)))(x,y)((x))(x)//－－－－廣義表的頭尾鏈表存儲(chǔ)表示－－－－typedef

enum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1:子表typedef

struct

GLNode{

ElemTagtag;//公共部分，用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;//atom是原子結(jié)點(diǎn)的值域，AtomType由用戶定義

struct{struct

GLNode*hp,*tp;}ptr;//ptr是表結(jié)點(diǎn)的指針域，ptr.hp和ptr.tp分別指向表頭和表尾};}*GList;//廣義表類型A=NILBCDE∧1e0∧11a01b0∧1d01c01a01∧1∧1∧1圖5.9廣義表的存儲(chǔ)結(jié)構(gòu)示例2)子表分析法：若子表為原子，則為空表

ls=NIL非空表1指向子表1第一個(gè)元素的指針tag=0datatp否則，依次類推。1指向子表2第一個(gè)元素的指針1指向子表n第一個(gè)元素的指針ls…

例如:LS=(a,(x,y),((x)))lsa0x01y0

11

x0

//－－－廣義表的擴(kuò)展線性鏈表存儲(chǔ)表示－－－typedef

enum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1:子表typedef

struct

GLNode{

ElemTagtag;//公共部分，用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;//是原子結(jié)點(diǎn)的值域

struct

GLNode*hp;//表結(jié)點(diǎn)的表頭指針};

struct

GLNode*tp;//相當(dāng)于線性鏈表的next，指向下一個(gè)元素結(jié)點(diǎn)}*GList;//廣義表類型GList是一種擴(kuò)展的線性鏈表ABCDE1c0∧1∧1圖5.11列表的另一種鏈表表示∧∧1∧1∧e0∧1∧1∧1a0∧1b0∧1a0∧d0

一個(gè)m元多項(xiàng)式的表示就是廣義表應(yīng)用的典型實(shí)例。例如三元多項(xiàng)式

p(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15,可以改寫為：

p(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15

即p(x,y,z)=Az2+Bz+15其中

A=((x10+2x6)y3+3x5y2)B=((x4+6x3)y4+2y)A、B又是關(guān)于x、y的多項(xiàng)式，依次類推，上述多項(xiàng)式可以表示為：5.6m元多項(xiàng)式的表示

p=z((A,2),(B,1),(15,0))其中：A=y((C,3),(D,2))C=x((1,10),(2,6))D=x((3,5))B=y((E,4),(F,1))E=x((1,4),(6,3))F=x((2,0))

可類似于廣義表的第二種存儲(chǔ)結(jié)構(gòu)來定義表示m元多項(xiàng)式的廣義表的存儲(chǔ)結(jié)構(gòu)。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：

其中exp為指數(shù)域,coef為系數(shù)域,hp指向其系數(shù)子表,tp指向同一層的下一結(jié)點(diǎn)。其形式定義說明如下：tag=1exphptp表結(jié)點(diǎn)tag=0expcoeftp原子結(jié)點(diǎn)typedef

struct

MPNode{

ElemTagtag;//區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

intexp;//指數(shù)域

union{floatcoef;//系數(shù)域

struct

MPNode*hp;//表結(jié)點(diǎn)的表頭指針};

struct

MPNode*tp;//相當(dāng)于線性鏈表的next，指向下一個(gè)元素結(jié)點(diǎn)}*MPList;//m元多項(xiàng)式廣義表類型P圖5.12三元多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)示意圖3∧1211111111113∧10∧0153121410∧025∧0310016∧024013∧06xyz5.7廣義表操作的遞歸函數(shù)遞歸函數(shù)一個(gè)含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件：

1)在每一次調(diào)用自己時(shí)，必須是(在某種意義上)更接近于解;

2)必須有一個(gè)終止處理或計(jì)算的準(zhǔn)則。例如:

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

n,

charx,chary,charz){if

(n==1)move(x,1,z);//遞歸終止

else{

hanoi(n-1,x,z,y);//遞歸調(diào)用

move(x,n,z);

hanoi(n-1,

y,x,z);//遞歸調(diào)用}}二叉樹的前序遍歷

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ù)或問題，用某種方法把輸入分割成k(1<k≤n)個(gè)子集，從而產(chǎn)生l

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

l

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

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

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

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

Traverse(BT)

可遞歸求解Traverse(LBT)

將n個(gè)結(jié)點(diǎn)分成三個(gè)子集(根結(jié)點(diǎn)、左子樹

和右子樹)，從而產(chǎn)生下列三個(gè)子問題：1)訪問根結(jié)點(diǎn)；3)遍歷右子樹;2)遍歷左子樹；可遞歸求解Traverse(RBT)廣義表從結(jié)構(gòu)上可以分解成廣義表=表頭+表尾或者廣義表=子表1+子表2+···+子表n因此常利用分治法求解之。算法設(shè)計(jì)中的關(guān)鍵問題是，如何將l

個(gè)子問題的解組合成原問題的解。廣義表的頭尾鏈表存儲(chǔ)表示：typedef

enum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedef

struct

GLNode

{

ElemTagtag;//標(biāo)志域

union{

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

struct{struct

GLNode*hp,*tp;}ptr;

};}*GListtag=1

hp

tpptr表結(jié)點(diǎn)廣義表的深度=Max{子表的深度}+15.7.1求廣義表的深度可以直接求解的兩種簡單情況為：

空表的深度=1

原子的深度=0廣義表的深度定義為廣義表中括弧的層數(shù)。

將廣義表分解成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;算法5.5111L…

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具體例子，講義P114圖5.135.7.2復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡單情況為：

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

原子結(jié)點(diǎn)可以直接復(fù)制求得。前面提到，任何一個(gè)非空廣義表均可分解成表頭和表尾；反之，一對(duì)確定的表頭和表尾可惟一確定一個(gè)廣義表。

將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(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ù)制表頭和表尾算法5.6CopyGList(T->ptr.hp,

L->ptr.hp);

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

L->ptr.tp);//復(fù)制求得表尾L->ptr.tp

的一個(gè)副本T->ptr.tp語句

CopyGList(T->ptr.hp,

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

CopyGList(newhp,

L->ptr.tp);

T->ptr.hp=newhp;復(fù)制表頭和表尾為：5.7.3建立廣義表的存儲(chǔ)結(jié)構(gòu)

對(duì)應(yīng)廣義表的不同定義方法相應(yīng)地有不同的創(chuàng)建存儲(chǔ)結(jié)構(gòu)的算法。從上述兩種廣義表操作的遞歸算法中可以發(fā)現(xiàn)：在對(duì)廣義表進(jìn)行操作的遞歸定義時(shí)，可有兩種分析方法：一種是把廣義表分解成表頭和表尾；另一種是把廣義表看成是含有n個(gè)并列子表（假設(shè)原子也作為子表）的表。假設(shè)以字符串S=

(

1,

2,

,

n)

的形式定義廣義表L，建立相應(yīng)的存儲(chǔ)結(jié)構(gòu)。由于S中的每個(gè)子串

i定義L的一個(gè)子表，從而產(chǎn)生n個(gè)子問題，即分別由這n個(gè)子串(遞歸)建立n個(gè)子表，再組合成一個(gè)廣義表。可以直接求解的兩種簡單情況為：由串

(

)

建立的廣義表是空表；由單字符建立的子表只是一個(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é)點(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,SStringS){if(strcompare(S,emp))L=NULL;//創(chuàng)建空表

else{if(!(L=(Glist)malloc(sizeof(GLNode))))exit(overflow);//建表結(jié)點(diǎn)

if(Strlength(s)==1){L->tag=ATOM;L->atom=s;}else{//創(chuàng)建單原子廣義表

L->tag=List;

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

}//elsereturnOK}

由sub中所含n個(gè)子串建立n個(gè)子表;算法5.7do{//重復(fù)建n個(gè)子表

sever(sub,

hsub);//從sub中分離出表頭串hsub

CreateGlist(p->ptr.hp,hsub);q=p;if(!StrEmpty(sub){//表尾不空

if(!(p=(GLNode*)malloc(sizeof(GLNode))))exit(overflow);p->tag=LIST;q->ptr.tp=p;

}//if}while(!StrEmpty(sub));q->ptr.tp=NULL;//表尾為空表}//elseStatusserver(Sstring

&str,

SString&hstr)

{//將非空串str分割成兩部分：hsub為第一個(gè)‘，’之前的子串，str為之后的子串

n=Strlength(str);i=0;k=0;//k記尚未配對(duì)的左括號(hào)個(gè)數(shù)

Do{//搜索最外層的第一個(gè)逗號(hào)

++i；

SubString（ch，str，i，1);

if(ch==‘(‘)++k;elseif(ch==‘)‘)--k;}while(i<n&&(ch!=‘,’||k!=0));if(i<n)

{

SubString(hstr,str,1,i-1);SubString(str,str,i+1,n-i)}

else{strcopy(hstr,str);clearstring(str)}}server算法5.8后置遞歸的設(shè)計(jì)思想為:

遞歸的終結(jié)狀態(tài)是，當(dāng)前的問題可以直接求解，對(duì)原問題而言，則是已走到了求解的最后一步。鏈表是可以如此求解的一個(gè)典型例子。例如：編寫“刪除單鏈表中所有值為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”，則余下問題是考慮以L->next為頭指針的鏈表……

a1

L->nextL->next=p->nextp=L->nextvoid

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)沒有被刪除的情況

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

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

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

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

1L0a

1

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

假設(shè)問題的解為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

并檢查之。例一、皇后問題求解設(shè)四皇后問題的解為(x1,x2,x3,x4),

其中：xi(i=1,2,3,4)

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

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

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