數(shù)組和廣義表課件

第五章數(shù)組和廣義表1第五章數(shù)組和廣義表15.1數(shù)組的類型定義5.3稀疏矩陣的壓縮存儲(chǔ)5.2數(shù)組的順序表示和實(shí)現(xiàn)5.4廣義表的類型定義5.5廣義表的表示方法5.6廣義表操作的遞歸函數(shù)25.1數(shù)組的類型定義5.3稀疏矩陣的壓縮存儲(chǔ)55.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基本操作:35.1數(shù)組的類型定義ADTArray{基本操作:3二維數(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}4二維數(shù)組的定義:數(shù)據(jù)對(duì)象:4基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)5基本操作：InitArray(&A,n,bound1,InitArray(&A,n,bound1,...,boundn)

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

操作結(jié)果：銷(xiāo)毀數(shù)組A。7DestroyArray(&A)

操作結(jié)果：銷(xiāo)毀數(shù)組A

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

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

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

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

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

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。9Assign(&A,e,index1,...,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)先);105.2數(shù)組的順序表示和實(shí)現(xiàn)類型特點(diǎn):例如：

稱為基地址或基址。以“行序?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

11例如：稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維推廣到一般情況，可得到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=1n12推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系課堂練習(xí)假設(shè)c語(yǔ)言中有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置為1000，計(jì)算：（1）數(shù)組A的體積（即存儲(chǔ)量）（2）數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；（3）假設(shè)按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；（4）假設(shè)按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址。13課堂練習(xí)假設(shè)c語(yǔ)言中有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)（1）數(shù)組A的體積（即存儲(chǔ)量）解：存儲(chǔ)量＝6×8×6＝288（2）數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；解：LOC（a57）＝1000＋288－6＝128214（1）數(shù)組A的體積（即存儲(chǔ)量）（2）數(shù)組A的最后一個(gè)元素a5（3）假設(shè)按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；解：LOC(a14)＝LOC(a00)＋(8×1+4)×6＝1000＋72＝1072（4）假設(shè)按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址；解：LOC(a47)＝LOC(a00)＋(6×7+4)×6＝1000＋276＝127615（3）假設(shè)按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；（4）假

以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題:1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇乘法，白乘；遇除法，還需判別除數(shù)是否為零;怎樣才能解決這些問(wèn)題？5.3矩陣的壓縮存儲(chǔ)16以常規(guī)方法，即以二維數(shù)組表示1)零值元素1)盡可能少存或不存零值元素;解決問(wèn)題的原則:2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算;3)操作方便;即:a.能盡可能快地找到與下標(biāo)值(i,j)對(duì)應(yīng)的元素;b.能盡可能快地找到同一行或同一列的非零值元;171)盡可能少存或不存零值元素;解決問(wèn)題的原則:2)盡可能1)特殊矩陣值相同的元素或零元素在矩陣中的分布有一定規(guī)率例如:三角矩陣對(duì)角矩陣2)稀疏矩陣非零元極少且在矩陣中隨機(jī)出現(xiàn)有兩類矩陣：181)特殊矩陣2)稀疏矩陣有兩類矩陣：18三角矩陣k=1+2+…+i+jk=n+(n-1)+…+(n-i)+(j-i)特殊矩陣19三角矩陣k=1+2+…+i+jk=n+(n-1)+…+(n-三角矩陣將A[n][n]，把它的非0元按行優(yōu)先，逐行、逐個(gè)存入B[n*(n+1)/2]中）①下三角矩陣中有A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下：

k=i*(i+1)/2+j0<=(i,j)<n②上三角矩陣中有A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下：

k=i*(2*n-i+1)/2+j-i0<=(i,j)<n

20三角矩陣20對(duì)稱矩陣滿足性質(zhì)：aij＝aji

0<=(i,j)<=n在存儲(chǔ)時(shí)我們可以為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元素壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。我們可以參照下三角以行優(yōu)先存儲(chǔ)。A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下：

i*(i+1)/2+j當(dāng)i>=j,0<=(i,j)<=n（下三角）

j*(j+1)/2+i當(dāng)i<j,0<=(i,j)<=n

（上三角）k＝21對(duì)稱矩陣k＝21三對(duì)角矩陣將其3條對(duì)角線上的元素存于數(shù)組B[3n-2-1]中，使得B[k]＝A[i][j]，A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下(請(qǐng)推導(dǎo)）：

k=f（i,j）=?k＝2i+j|i-j|<=1k＝2+3(i-1)+(j-i+1)＝2i+j22三對(duì)角矩陣k=f（i,j）=?k＝2i+j預(yù)習(xí)題1.特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功能？為什么？2.矩陣的一般轉(zhuǎn)置算法的時(shí)間復(fù)雜度是多少？快速轉(zhuǎn)置算法的時(shí)間復(fù)雜度是多少？3.使用帶行邏輯鏈接的三元組順序表完成矩陣相乘算法的時(shí)間復(fù)雜度是多少？稀疏矩陣壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功能。特殊矩陣由于壓縮存儲(chǔ)時(shí)是將其存儲(chǔ)在一個(gè)線性數(shù)組向量b[k]中，矩陣元素下標(biāo)i，j與它在向量中對(duì)應(yīng)元素b[k]行下標(biāo)k有一一對(duì)應(yīng)關(guān)系，故還是隨機(jī)存取的。而稀疏矩陣其壓縮存儲(chǔ)的方式是將其非零元素存儲(chǔ)在一個(gè)三元組數(shù)組a[k]中，矩陣元素下標(biāo)i，j與數(shù)組中對(duì)應(yīng)元素a[k]行下標(biāo)k無(wú)對(duì)應(yīng)關(guān)系，故失去隨機(jī)存儲(chǔ)功能。一般轉(zhuǎn)置算法：O(nutu)快速轉(zhuǎn)置算法：O(nu+tu)(mp(1+nMN))

，當(dāng)M<0.05和N<0.05及n<1000時(shí)，相當(dāng)于O(mp)。23預(yù)習(xí)題1.特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱為稀疏因子通常認(rèn)為

0.05的矩陣為稀疏矩陣稀疏矩陣24假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱稀疏矩陣2稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表二、行邏輯聯(lián)接的順序表三、十字鏈表25稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表二、行邏輯聯(lián)接的順序

#defineMAXSIZE12500

typedefstruct{

inti,j;

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

ElemTypee;

//該非零元的值

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

Tripledata[MAXSIZE+1];

intmu,nu,tu;

}TSMatrix;//稀疏矩陣類型26#defineMAXSIZE12500一、三元組順121415-522-731363428矩陣M：355三元組表（行優(yōu)先）：27121415-522-731363428矩陣M：355三元組如何求轉(zhuǎn)置矩陣？MT將第i行j列元素變?yōu)榈趈行i列元素28如何求轉(zhuǎn)置矩陣？MT將第i行j列元素變?yōu)榈趈行i列元素28用常規(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];29用常規(guī)的二維數(shù)組表示時(shí)的算法其時(shí)間復(fù)雜度為:O(mu用“三元組”表示時(shí)如何實(shí)現(xiàn)？30用“三元組”表示時(shí)如何實(shí)現(xiàn)？30ijv121415-522-731363428ijv1336211422-7432851-5ijv211451-522-713364328行列值互換按行優(yōu)先重排三元組次序MT思路一31ijv121415-522-731363428ijv1336思路二

按照M.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后置入T中恰當(dāng)?shù)奈恢谩Ｒ业竭@個(gè)恰當(dāng)位置，必須預(yù)先知道M中每一列的非零元在T中的位置。32思路二按照M.data中三元組的次121415-522-731363428211451-522-713364328MT33121415-522-731那么如何確定每一行的第一個(gè)非零元在三元組中的位置？

cpot[1]=1;for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];M的第col列的第一個(gè)非零元轉(zhuǎn)置后在T的位置34那么如何確定每一行的第一個(gè)非零元在三元組中的位置？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){}}//ifreturnOK;}//FastTransposeSMatrix

轉(zhuǎn)置矩陣元素35StatusFastTransposeSMatrix(TSCol=M.data[p].j;q=cpot[col];//轉(zhuǎn)置后的位置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]//第col列下一非零元的位置36Col=M.data[p].j;36分析算法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)……37分析算法FastTransposeSMatrix的時(shí)三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需隨機(jī)存取某一行中的非零元，則需從頭開(kāi)始進(jìn)行查找。二、行邏輯聯(lián)接的順序表38三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，

為了便于隨機(jī)存取任意一行的非零元，則需知道每一行的第一個(gè)非零元在三元組表的位置（位序）。因此，可以將此指示“行”信息的輔助數(shù)組固定在稀疏矩陣的三元組表結(jié)構(gòu)里面。39為了便于隨機(jī)存取任意一行的非零元，則需知#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;}RLSMatrix;//行邏輯鏈接順序表類型修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個(gè)數(shù)據(jù)成員rpos,其值在稀疏矩陣的初始化函數(shù)中確定（目的是增加其隨機(jī)存儲(chǔ)特性）。40#defineMAXMN500圖4-6（矩陣T）41圖4-6（矩陣T）41例如：給定一組下標(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時(shí)間復(fù)雜度為O（c）接近于常數(shù)階，具有一定隨機(jī)存儲(chǔ)特征42例如：給定一組下標(biāo)，求矩陣的元素值ElemTypevalu矩陣相乘43矩陣相乘43矩陣乘法的精典算法: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)44矩陣乘法的精典算法:其時(shí)間復(fù)雜度為:O(m1×n2×n1)ije11314522-1312ije12221131-2324ije12621-1122324211M中的j值和N中的i值相等的各對(duì)元素相乘即可Row1234Rpos[row]1235N45ije11314522-1312ije12221131-23Q初始化;ifQ是非零矩陣{//逐行求積for(arow=1;arow<=M.mu;++arow){//處理M的每一行ctemp[]=0;//累加器清零

計(jì)算Q中第arow行的積并存入ctemp[]中；將ctemp[]中非零元壓縮存儲(chǔ)到Q.data；}//forarow}//if兩個(gè)帶行邏輯三元組存儲(chǔ)的稀疏矩陣相乘（QMN）的過(guò)程可大致描述如下：46Q初始化;兩個(gè)帶行邏輯三元組存儲(chǔ)的稀疏矩陣相乘（QMStatusMultSMatrix

(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;}//MultSMatrix47StatusMultSMatrix47ctemp[]=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;//找到對(duì)應(yīng)元在N中的行號(hào)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]};}//壓縮存儲(chǔ)該行非零元處理的每一行M48ctemp[]=0;分析上述算法的時(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)。49分析上述算法的時(shí)間復(fù)雜度累加器ctemp初始化的時(shí)間復(fù)雜度為三、十字鏈表30050-100200011314522-1312^^^^^^^50三、十字鏈表300511314522-1312預(yù)習(xí)題什么叫廣義表？它和線性表有和相同和不同之處？什么叫廣義表的表頭、表尾、表長(zhǎng)、表深？廣義表LS=(1,2,,n)是遞歸定義的線性結(jié)構(gòu)，其中：i或?yàn)樵踊驗(yàn)閺V義表。而在線性表中i只能為原子。當(dāng)廣義表LS=(1,2,,n)非空，第一個(gè)元素1稱為表頭，剩余元素(2,,n)組成的子表稱為表尾。長(zhǎng)度為最外層包含元素個(gè)數(shù)。深度為所含括弧的重?cái)?shù)。51預(yù)習(xí)題什么叫廣義表？它和線性表有和相同和不同之處？廣義表LS5.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}

基本操作:}ADTGlist525.4廣義表的類型定義ADTGlist{52廣義表是遞歸定義的線性結(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,,)))53廣義表是遞歸定義的線性結(jié)構(gòu)，LS=(1廣義表是一個(gè)多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:

E=(a,(b,c))F=(d,(e))DEFa()d()bce54廣義表是一個(gè)多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:DE廣義表

LS=(1,2,…,n)的結(jié)構(gòu)特點(diǎn):1)廣義表中的數(shù)據(jù)元素有相對(duì)次序;2)廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù);3)廣義表的深度定義為所含括弧的重?cái)?shù);注意:“原子”的深度為0;“空表”的深度為1。4)廣義表可以共享;5)廣義表可以是一個(gè)遞歸的表;遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。55廣義表LS=(1,2,…,n)的結(jié)構(gòu)特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))=()566)任何一個(gè)非空廣義表LS=(1,2

結(jié)構(gòu)的創(chuàng)建和銷(xiāo)毀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());57結(jié)構(gòu)的創(chuàng)建和銷(xiāo)毀基本操作狀態(tài)函數(shù)插入和刪除5.5廣義表的表示方法

頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn):

tag=1hptp原子結(jié)點(diǎn)：tag=0data585.5廣義表的表示方法581)空表ls=NIL非空表

ls1表尾表頭構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法:若表頭為原子，則為0data否則，依次類推。591)空表ls=NIL構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法6060L=(a,(x,y),((x)))L((x,y),((x)))(((x)))11a(x,y)61L=(a,(x,y),((x)))L廣義表的頭尾鏈表存儲(chǔ)表示：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;

union{AtomTypeatom;

struct{structGLNode*hp,*tp;}ptr;};}*GList62廣義表的頭尾鏈表存儲(chǔ)表示：typedefenum{ATO2)空表ls=NIL非空表LS=(1,2,…,n)ls111子表1子表2子表n若子表為原子，則為0data否則，依次類推。632)空表ls=NIL63例如:a(x,y)((x))LS=(a,(x,y),((x)))64例如:a(x,y)廣義表的擴(kuò)展線性鏈表存儲(chǔ)表示：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;

union{AtomTypeatom;

structGLNode*hp;};structGLNode*tp;}*GList65廣義表的擴(kuò)展線性鏈表存儲(chǔ)表示：typedefenum{A課堂練習(xí)1.廣義表C＝((((a),b)),(((),y)))，則C的長(zhǎng)度為_(kāi)____，深度為_(kāi)_____，tail(head(tail(C)))＝______2.head(tail(head(((a，b)，(c，d)))))=______24（）b66課堂練習(xí)1.廣義表C＝((((a),b)3.已知下圖為廣義表的存儲(chǔ)結(jié)構(gòu)圖，其結(jié)點(diǎn)結(jié)構(gòu)如教材P109圖5.8所示，寫(xiě)出下圖表示的廣義表：____________________((x,(y)),(((())),(),(z)))673.已知下圖為廣義表的存儲(chǔ)結(jié)構(gòu)圖，其結(jié)點(diǎn)結(jié)構(gòu)如教材P109圖5.6m元多項(xiàng)式的表示*P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15由于在m元多項(xiàng)式P中每一項(xiàng)的變?cè)獋€(gè)數(shù)不確定及不均勻，因此不適合采用線性表表示。若改寫(xiě)為:P(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15每個(gè)多項(xiàng)式都可看作是由一個(gè)變量加上若干個(gè)系數(shù)指數(shù)偶對(duì)組成。上述三元多項(xiàng)式可用以下廣義表表示：685.6m元多項(xiàng)式的表示*P(x,y,z)由于在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))69P=z((A,2),(B,1),(15,0))695.7廣義表的遞歸算法*遞歸函數(shù)一個(gè)含直接或間接調(diào)用本函數(shù)語(yǔ)句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件:1)在每一次調(diào)用自己時(shí)，必須是(在某種意義上)更接近于解;2)必須有一個(gè)終止處理或計(jì)算的準(zhǔn)則。705.7廣義表的遞歸算法*遞歸函數(shù)1)在每一次調(diào)用自己時(shí)，

這一類問(wèn)題可以借助算法設(shè)計(jì)的一種方法分治法(分割求解)(DivideandConquer)來(lái)求解分治法的設(shè)計(jì)思想為:對(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)題足夠小，以至可以直接求解為止。71這一類問(wèn)題可以借助算法設(shè)計(jì)分治法的設(shè)計(jì)思想為廣義表從結(jié)構(gòu)上可以分解成廣義表=表頭+表尾或者廣義表=子表1+子表2+···+子表n因此常利用分治法求解。72廣義表從結(jié)構(gòu)上可以分解成廣義表=表頭+表尾或下面采用廣義表的頭尾鏈表存儲(chǔ)表示：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;

union{AtomTypeatom;

struct{structGLNode*hp,*tp;}ptr;};}*GList73下面采用廣義表的頭尾鏈表存儲(chǔ)表示：typedefenum例一求廣義表的深度例二復(fù)制廣義表例三創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)74例一求廣義表的深度例二復(fù)制廣義表例三創(chuàng)建廣義表的存廣義表的深度=Max{子表的深度}+1例一求廣義表的深度空表的深度=1原子的深度=075廣義表的深度=Max{子表的深度}+1例一求廣義表的深int

GlistDepth(GlistL){

if(!L)return1;

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

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

}

return

max+1;}//GlistDepth76intGlistDepth(GlistL){76若ls=NIL則newls=NIL否則

由表頭ls^.hp復(fù)制得newhp由表尾ls^.tp復(fù)制得newtp構(gòu)造結(jié)點(diǎn)newls,并使newls^.hp=newhp,newls^.tp=newtp例二復(fù)制廣義表77若ls=NIL則newls=NIL例二復(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;

else{

CopyGList(T->ptr.hp,L->ptr.hp);

CopyGList(T->ptr.tp,

L->ptr.tp);

}//else

}//elsereturnOK;}//CopyGList78StatusCopyGList(Glist&T,Gli例三創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)根據(jù)LS=(1,2,

,n)建廣義表ls若LS=()則ls=NIL否則構(gòu)造表結(jié)點(diǎn)ls^分解出第一個(gè)子串1,對(duì)應(yīng)建廣義表的表頭ls^.hp若剩余串非空，則構(gòu)造表尾結(jié)點(diǎn)ls^.tp分解出第二個(gè)子串2,對(duì)應(yīng)建廣義表

依次類推，直至剩余串為空串止79例三創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu)根據(jù)LS=(1,2void

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);//脫外層括弧do{

重復(fù)建n個(gè)子表}while(!StrEmpty(sub));

p->ptr.tp=NULL;}//else}重復(fù)建n個(gè)子表80voidCreateGList(Glist&L,Strsever(sub,hsub);//分離出子表串hsub=i

if(StrLength(hsub)==1){

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

//遞歸建子表

if(!StrEmpty(sub){

p->ptr.tp=(Glist)malloc(sizeof(GLNode));p=p->ptr.tp;//建表尾結(jié)點(diǎn)*p}81sever(sub,hsub);//分離出子表串hsu綜合幾點(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)致遞歸求解。82綜合幾點(diǎn)：822.實(shí)現(xiàn)遞歸函數(shù)，目前必須利用“?！?。一個(gè)遞歸函數(shù)必定能改寫(xiě)為利用棧實(shí)現(xiàn)的非遞歸函數(shù)；反之，一個(gè)用棧實(shí)現(xiàn)的非遞歸函數(shù)可以改寫(xiě)為遞歸函數(shù)。需要注意的是遞歸函數(shù)遞歸層次的深度決定所需存儲(chǔ)量的大小。832.實(shí)現(xiàn)遞歸函數(shù)，目前必須利用“?！?。一個(gè)遞歸函數(shù)必定能改1.了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。2.掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。3.了解稀疏矩陣的兩類壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。本章小結(jié)841.了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)4.掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，讀者可根據(jù)自己的習(xí)慣熟練掌握任意一種結(jié)構(gòu)的鏈表，學(xué)會(huì)對(duì)非空廣義表進(jìn)行分解的兩種分析方法：即可將一個(gè)非空廣義表分解為表頭和表尾兩部分或者分解為n個(gè)子表。854.掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，讀者可根據(jù)自己的作業(yè)題題集P335.10題集P345.19補(bǔ)充題：1、設(shè)有二維數(shù)組A[10,20],其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按列優(yōu)先順序存儲(chǔ)，則元素A[6,6]存儲(chǔ)地址為多少？2、設(shè)有三對(duì)角矩陣(ai,j)n╳n,將其三條對(duì)角線上的元素逐行的存于數(shù)組B(1:3n-2)中，使得B[k]=ai,j，求：（1）用i,j表示k的下標(biāo)變換公式；（2）若n=103,每個(gè)元素占用L個(gè)單元，則用B[K]方式比常規(guī)存儲(chǔ)節(jié)省多少單元。86作業(yè)題題集P335.10實(shí)驗(yàn)5稀疏矩陣運(yùn)算器[實(shí)驗(yàn)?zāi)康腯深入研究數(shù)組的存儲(chǔ)表示和實(shí)現(xiàn)技術(shù)，熟悉廣義表存儲(chǔ)結(jié)構(gòu)的特性。[實(shí)驗(yàn)內(nèi)容]稀疏矩陣運(yùn)算器（題集P136題4.1）稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。要求以帶“行邏輯鏈接信息”的三元組順序表存儲(chǔ)稀疏矩陣，實(shí)現(xiàn)兩矩陣的相加、相減、相乘等運(yùn)算。輸入以三元組表示，輸出以通常的陣列形式列出。[實(shí)驗(yàn)時(shí)間]5月14日和21日[實(shí)驗(yàn)類型]設(shè)計(jì)87實(shí)驗(yàn)5稀疏矩陣運(yùn)算器[實(shí)驗(yàn)?zāi)康腯深入研究數(shù)組的存儲(chǔ)預(yù)習(xí)題1.樹(shù)的邏輯特征是什么？2.了解以下概念：樹(shù)的度，結(jié)點(diǎn)的度，葉子，雙親，孩子，兄弟，祖先，子孫，堂兄弟，深度。3.二叉樹(shù)的特征是什么？有什么性質(zhì)？只有一個(gè)根結(jié)點(diǎn)(無(wú)前驅(qū))，多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)，多個(gè)其它分支結(jié)點(diǎn)(一個(gè)前驅(qū)、多個(gè)后繼)二叉樹(shù)或?yàn)榭諛?shù)；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成。5個(gè)性質(zhì)，常見(jiàn)P123～125。88預(yù)習(xí)題1.樹(shù)的邏輯特征是什么？只有一個(gè)根結(jié)點(diǎn)(無(wú)前驅(qū))，多個(gè)第五章數(shù)組和廣義表89第五章數(shù)組和廣義表15.1數(shù)組的類型定義5.3稀疏矩陣的壓縮存儲(chǔ)5.2數(shù)組的順序表示和實(shí)現(xiàn)5.4廣義表的類型定義5.5廣義表的表示方法5.6廣義表操作的遞歸函數(shù)905.1數(shù)組的類型定義5.3稀疏矩陣的壓縮存儲(chǔ)55.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基本操作:915.1數(shù)組的類型定義ADTArray{基本操作:3二維數(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}92二維數(shù)組的定義:數(shù)據(jù)對(duì)象:4基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)93基本操作：InitArray(&A,n,bound1,InitArray(&A,n,bound1,...,boundn)

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

操作結(jié)果：銷(xiāo)毀數(shù)組A。95DestroyArray(&A)

操作結(jié)果：銷(xiāo)毀數(shù)組A

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

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

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

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

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

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。97Assign(&A,e,index1,...,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)先);985.2數(shù)組的順序表示和實(shí)現(xiàn)類型特點(diǎn):例如：

稱為基地址或基址。以“行序?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

99例如：稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維推廣到一般情況，可得到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=1n100推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系課堂練習(xí)假設(shè)c語(yǔ)言中有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置為1000，計(jì)算：（1）數(shù)組A的體積（即存儲(chǔ)量）（2）數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；（3）假設(shè)按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；（4）假設(shè)按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址。101課堂練習(xí)假設(shè)c語(yǔ)言中有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)（1）數(shù)組A的體積（即存儲(chǔ)量）解：存儲(chǔ)量＝6×8×6＝288（2）數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；解：LOC（a57）＝1000＋288－6＝1282102（1）數(shù)組A的體積（即存儲(chǔ)量）（2）數(shù)組A的最后一個(gè)元素a5（3）假設(shè)按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；解：LOC(a14)＝LOC(a00)＋(8×1+4)×6＝1000＋72＝1072（4）假設(shè)按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址；解：LOC(a47)＝LOC(a00)＋(6×7+4)×6＝1000＋276＝1276103（3）假設(shè)按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；（4）假

以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題:1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇乘法，白乘；遇除法，還需判別除數(shù)是否為零;怎樣才能解決這些問(wèn)題？5.3矩陣的壓縮存儲(chǔ)104以常規(guī)方法，即以二維數(shù)組表示1)零值元素1)盡可能少存或不存零值元素;解決問(wèn)題的原則:2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算;3)操作方便;即:a.能盡可能快地找到與下標(biāo)值(i,j)對(duì)應(yīng)的元素;b.能盡可能快地找到同一行或同一列的非零值元;1051)盡可能少存或不存零值元素;解決問(wèn)題的原則:2)盡可能1)特殊矩陣值相同的元素或零元素在矩陣中的分布有一定規(guī)率例如:三角矩陣對(duì)角矩陣2)稀疏矩陣非零元極少且在矩陣中隨機(jī)出現(xiàn)有兩類矩陣：1061)特殊矩陣2)稀疏矩陣有兩類矩陣：18三角矩陣k=1+2+…+i+jk=n+(n-1)+…+(n-i)+(j-i)特殊矩陣107三角矩陣k=1+2+…+i+jk=n+(n-1)+…+(n-三角矩陣將A[n][n]，把它的非0元按行優(yōu)先，逐行、逐個(gè)存入B[n*(n+1)/2]中）①下三角矩陣中有A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下：

k=i*(i+1)/2+j0<=(i,j)<n②上三角矩陣中有A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下：

k=i*(2*n-i+1)/2+j-i0<=(i,j)<n

108三角矩陣20對(duì)稱矩陣滿足性質(zhì)：aij＝aji

0<=(i,j)<=n在存儲(chǔ)時(shí)我們可以為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元素壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。我們可以參照下三角以行優(yōu)先存儲(chǔ)。A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下：

i*(i+1)/2+j當(dāng)i>=j,0<=(i,j)<=n（下三角）

j*(j+1)/2+i當(dāng)i<j,0<=(i,j)<=n

（上三角）k＝109對(duì)稱矩陣k＝21三對(duì)角矩陣將其3條對(duì)角線上的元素存于數(shù)組B[3n-2-1]中，使得B[k]＝A[i][j]，A[i][j]與B[k]的對(duì)應(yīng)關(guān)系如下(請(qǐng)推導(dǎo)）：

k=f（i,j）=?k＝2i+j|i-j|<=1k＝2+3(i-1)+(j-i+1)＝2i+j110三對(duì)角矩陣k=f（i,j）=?k＝2i+j預(yù)習(xí)題1.特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功能？為什么？2.矩陣的一般轉(zhuǎn)置算法的時(shí)間復(fù)雜度是多少？快速轉(zhuǎn)置算法的時(shí)間復(fù)雜度是多少？3.使用帶行邏輯鏈接的三元組順序表完成矩陣相乘算法的時(shí)間復(fù)雜度是多少？稀疏矩陣壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功能。特殊矩陣由于壓縮存儲(chǔ)時(shí)是將其存儲(chǔ)在一個(gè)線性數(shù)組向量b[k]中，矩陣元素下標(biāo)i，j與它在向量中對(duì)應(yīng)元素b[k]行下標(biāo)k有一一對(duì)應(yīng)關(guān)系，故還是隨機(jī)存取的。而稀疏矩陣其壓縮存儲(chǔ)的方式是將其非零元素存儲(chǔ)在一個(gè)三元組數(shù)組a[k]中，矩陣元素下標(biāo)i，j與數(shù)組中對(duì)應(yīng)元素a[k]行下標(biāo)k無(wú)對(duì)應(yīng)關(guān)系，故失去隨機(jī)存儲(chǔ)功能。一般轉(zhuǎn)置算法：O(nutu)快速轉(zhuǎn)置算法：O(nu+tu)(mp(1+nMN))

，當(dāng)M<0.05和N<0.05及n<1000時(shí)，相當(dāng)于O(mp)。111預(yù)習(xí)題1.特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱為稀疏因子通常認(rèn)為

0.05的矩陣為稀疏矩陣稀疏矩陣112假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱稀疏矩陣2稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表二、行邏輯聯(lián)接的順序表三、十字鏈表113稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表二、行邏輯聯(lián)接的順序

#defineMAXSIZE12500

typedefstruct{

inti,j;

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

ElemTypee;

//該非零元的值

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

Tripledata[MAXSIZE+1];

intmu,nu,tu;

}TSMatrix;//稀疏矩陣類型114#defineMAXSIZE12500一、三元組順121415-522-731363428矩陣M：355三元組表（行優(yōu)先）：115121415-522-731363428矩陣M：355三元組如何求轉(zhuǎn)置矩陣？MT將第i行j列元素變?yōu)榈趈行i列元素116如何求轉(zhuǎn)置矩陣？MT將第i行j列元素變?yōu)榈趈行i列元素28用常規(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];117用常規(guī)的二維數(shù)組表示時(shí)的算法其時(shí)間復(fù)雜度為:O(mu用“三元組”表示時(shí)如何實(shí)現(xiàn)？118用“三元組”表示時(shí)如何實(shí)現(xiàn)？30ijv121415-522-731363428ijv1336211422-7432851-5ijv211451-522-713364328行列值互換按行優(yōu)先重排三元組次序MT思路一119ijv121415-522-731363428ijv1336思路二

按照M.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后置入T中恰當(dāng)?shù)奈恢?。要找到這個(gè)恰當(dāng)位置，必須預(yù)先知道M中每一列的非零元在T中的位置。120思路二按照M.data中三元組的次121415-522-731363428211451-522-713364328MT121121415-522-731那么如何確定每一行的第一個(gè)非零元在三元組中的位置？

cpot[1]=1;for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];M的第col列的第一個(gè)非零元轉(zhuǎn)置后在T的位置122那么如何確定每一行的第一個(gè)非零元在三元組中的位置？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){}}//ifreturnOK;}//FastTransposeSMatrix

轉(zhuǎn)置矩陣元素123StatusFastTransposeSMatrix(TSCol=M.data[p].j;q=cpot[col];//轉(zhuǎn)置后的位置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]//第col列下一非零元的位置124Col=M.data[p].j;36分析算法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)……125分析算法FastTransposeSMatrix的時(shí)三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需隨機(jī)存取某一行中的非零元，則需從頭開(kāi)始進(jìn)行查找。二、行邏輯聯(lián)接的順序表126三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，

為了便于隨機(jī)存取任意一行的非零元，則需知道每一行的第一個(gè)非零元在三元組表的位置（位序）。因此，可以將此指示“行”信息的輔助數(shù)組固定在稀疏矩陣的三元組表結(jié)構(gòu)里面。127為了便于隨機(jī)存取任意一行的非零元，則需知#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;}RLSMatrix;//行邏輯鏈接順序表類型修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個(gè)數(shù)據(jù)成員rpos,其值在稀疏矩陣的初始化函數(shù)中確定（目的是增加其隨機(jī)存儲(chǔ)特性）。128#defineMAXMN500圖4-6（矩陣T）129圖4-6（矩陣T）41例如：給定一組下標(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時(shí)間復(fù)雜度為O（c）接近于常數(shù)階，具有一定隨機(jī)存儲(chǔ)特征130例如：給定一組下標(biāo)，求矩陣的元素值ElemTypevalu矩陣相乘131矩陣相乘43矩陣乘法的精典算法: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)132矩陣乘法的精典算法:其時(shí)間復(fù)雜度為:O(m1×n2×n1)ije11314522-1312ije12221131-2324ije12621-1122324211M中的j值和N中的i值相等的各對(duì)元素相乘即可Row1234Rpos[row]1235N133ije11314522-1312ije12221131-23Q初始化;ifQ是非零矩陣{//逐行求積for(arow=1;arow<=M.mu;++arow){//處理M的每一行ctemp[]=0;//累加器清零

計(jì)算Q中第arow行的積并存入ctemp[]中；