第五章數(shù)組和廣義表

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

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

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

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ù)對象:

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個下標(biāo)值。

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

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

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

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

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

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

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

稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j

的存儲位置

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ù)元素存儲位置的映象關(guān)系

稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)。其中cn=L，ci-1=bi×ci,1<i

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

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

0.05的矩陣為稀疏矩陣。5.3稀疏矩陣的壓縮存儲何謂稀疏矩陣？

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

非零元在矩陣中的分布有一定規(guī)則例如:三角矩陣對角矩陣2)隨機稀疏矩陣非零元在矩陣中隨機出現(xiàn)有兩類稀疏矩陣：特殊矩陣

這類矩陣由于零元素或重復(fù)元素的分布很有規(guī)律，可以很容易地把矩陣壓縮存儲在一個一維數(shù)數(shù)組中。An×nBm，即B[k]=A[i,j]，需求出下標(biāo)映射函數(shù)k=f(i,j)。上三角矩陣0對角矩陣000下三角矩陣ajiaij對稱矩陣

如下三角矩陣有映射Aij=Bk，則有a11a21a22a31．．．a(chǎn)ni．．．a(chǎn)nnk=0123n(n-1)/2n(n+1)/2-1K=i(i-1)/2+j-1(i≥j)n(n+1)/2(i<j)0下三角矩陣隨機稀疏矩陣的壓縮存儲方法:一、三元組順序表二、行邏輯聯(lián)接的順序表三、十字鏈表

#defineMAXSIZE12500

typedefstruct{

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

ElemTypee;//該非零元的值

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

Tripledata[MAXSIZE+1];

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

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

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

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

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];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的時間復(fù)雜度：時間復(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)法，它的特點是，非零元在表中按行序有序存儲，因此便于進(jìn)行依行順序處理的矩陣運算。然而，若需隨機存取某一行中的非零元，則需從頭開始進(jìn)行查找。二、行邏輯聯(lián)接的順序表#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

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

修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個數(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];

}其時間復(fù)雜度為:O(m1×n2×n1)Q初始化；

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

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

//處理M的每一行

ctemp[]=0;//累加器清零

計算Q中第arow行的積并存入ctemp[]中；將ctemp[]中非零元壓縮存儲到Q.data；

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

M

N）的過程可大致描述如下：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;}//MultSMatrixctemp[]=0;//當(dāng)前行各元素累加器清零

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

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處理的每一行M三、十字鏈表30050-100200011314522-1312^^^^^^^作業(yè)1.設(shè)有上三角矩陣（aij)n×n

，將其上三角元素逐行存于數(shù)組B(0:m-1)中，使得B[k]=aij，且k=f1(i)+f2(j)+c。試推導(dǎo)函數(shù)f1、f2和常數(shù)項c，其中1≤i，j≤n。上三角矩陣05.4廣義表的類型定義ADTGlist{

數(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基本操作:廣義表是遞歸定義的線性結(jié)構(gòu)，LS=(

1,

2,

,

n)其中：

i

或為原子或為廣義表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,

,)))廣義表是一個多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:

E=(a,

(b,

c))

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

LS=(

1,

2,…,

n)的結(jié)構(gòu)特點:1)廣義表中的數(shù)據(jù)元素有相對次序；2)廣義表的長度定義為最外層包含元素個數(shù)；3)廣義表的深度定義為所含括弧的重數(shù)；注意：“原子”的深度為0

“空表”的深度為14)廣義表可以共享；5)廣義表可以是一個遞歸的表。遞歸表的深度是無窮值，長度是有限值。6)任何一個非空廣義表

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é)點:原子結(jié)點：tag=1hptptag=0data1)表頭、表尾分析法：構(gòu)造存儲結(jié)構(gòu)的兩種分析方法:若表頭為原子，則為空表

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

)

1LL=()0a

1

1

1

1

10x

()x2)子表分析法：若子表為原子，則為空表

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

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

的指針1指向子表n

的指針ls…

例如:

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

一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個條件：1)在每一次調(diào)用自己時，必須是(在某種意義上)更接近于解;2)必須有一個終止處理或計算的準(zhǔn)則。一、分治法(DivideandConquer)(又稱分割求解法)如何設(shè)計遞歸函數(shù)？二、后置遞歸法(Postponingthework)三、回溯法(Backtracking)

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

個子問題，分別求解這l個問題，得出

l

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

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

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

將n個盤分成兩個子集(1至n-1和n)，從而產(chǎn)生下列三個子問題：1)將1至n-1號盤從x軸移動至y軸；3)將1至n-1號盤從y軸移動至z軸；2)將n號盤從x軸移動至z軸；可遞歸求解Hanoi(n-1,x,z,y)梵塔的遞歸函數(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);}}又如:遍歷二叉樹:

Traverse(BT)

可遞歸求解Traverse(LBT)

將n個結(jié)點分成三個子集(根結(jié)點、左子樹和右子樹)，從而產(chǎn)生下列三個子問題：1)訪問根結(jié)點；3)遍歷右子樹;2)遍歷左子樹；可遞歸求解Traverse(RBT)二叉樹的遍歷void

PreOrderTraverse(

BiTree

T,void(Visit)(BiTreeP))

{

if(T)

{Visit(T->data);

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

}}

//PreOrderTraverse廣義表從結(jié)構(gòu)上可以分解成廣義表=表頭+表尾或者廣義表=

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

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

個子問題的解組合成原問題的解。廣義表的頭尾鏈表存儲表示：typedefenum{ATOM,LIST}ElemTag;

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

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

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

};}*GListtag=1

hp

tpptr表結(jié)點例一求廣義表的深度例二復(fù)制廣義表廣義表的深度=Max{子表的深度}+1例一求廣義表的深度可以直接求解的兩種簡單情況為：

空表的深度=1

原子的深度=0

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

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簡單情況為：

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

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

將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，若ls=NIL則newls=NIL否則構(gòu)造結(jié)點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é)點

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

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

else{}

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

L->ptr.hp);

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

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

CopyGList(T->ptr.hp,

L->ptr.hp);等價于

CopyGList(newhp,

L->ptr.tp);

T->ptr.hp=newhp;二、后置遞歸的設(shè)計思想為:

遞歸的終結(jié)狀態(tài)是，當(dāng)前的問題可以直接求解，對原問題而言，則是已走到了求解的最后一步。鏈表是可以如此求解的一個典型例子。例如：編寫“刪除單鏈表中所有值為x的數(shù)據(jù)元素”的算法。1)單鏈表是一種順序結(jié)構(gòu)，必須從第一個結(jié)點起，逐個檢查每個結(jié)點的數(shù)據(jù)元素；分析:2)從另一角度看，鏈表又是一個遞歸結(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é)點的單鏈表中

//所有值為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é)點分析:

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

2)刪除時，不僅要刪除原子結(jié)點，還需要刪除相應(yīng)的表結(jié)點。void

Delete_GL(Glist&L,AtomTypex)

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

if(L){

head=L->ptr.hp;

//考察第一個子表

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

(head->atom==x))

{}//刪除原子項x的情況

else{}//第一項沒有被刪除的情況

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

1L0x

1pL

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

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

//遞歸處理剩余表項

1L0a

1

1headL->ptr.tp三、回溯法是一種“窮舉”方法。其基本

思想為：

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

取值于集合Si。

n

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

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

并檢查之。綜合幾點：1.

對于含有遞歸特性的問題，最好設(shè)計遞歸形式的算法。但也不要單純追求形式，應(yīng)在算法設(shè)計的分析過程中“就事論事”。例如，在利用分割求解設(shè)計算法時，子問題和原問題的性質(zhì)相同；或者，問題的當(dāng)前一步解決之后，余下的問題和原問題性質(zhì)相同，則自然導(dǎo)致遞歸求解。2.實現(xiàn)遞歸函數(shù)，目前必須利用“?！?。一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函