數(shù)據(jù)結(jié)構(gòu)(第5章)

第五章數(shù)組、特殊矩陣和廣義表⒈教學(xué)內(nèi)容：5.1多維數(shù)組5.2特殊矩陣的壓縮存儲(chǔ)5.3稀疏矩陣5.4廣義表⒉教學(xué)目的：⑴理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式；⑵理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算；⑶領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡(jiǎn)單運(yùn)算；⑷了解廣義表的定義和基本運(yùn)算。⒊教學(xué)重點(diǎn)：⑴多維數(shù)組的邏輯結(jié)構(gòu)；⑵多維組的兩種順序存儲(chǔ)方式，計(jì)算給定元素在存儲(chǔ)區(qū)中的地址；⑶對(duì)稱矩陣、三角矩陣的壓縮存儲(chǔ)方式；⑷稀疏矩陣的三元組表表示方法。⒋教學(xué)難點(diǎn)：

稀疏矩陣的壓縮存儲(chǔ)表示下的運(yùn)算的實(shí)現(xiàn)⒌學(xué)時(shí)安排：4學(xué)時(shí)2/1/20231數(shù)據(jù)結(jié)構(gòu)講義5.1多維數(shù)組數(shù)組的邏輯結(jié)構(gòu)數(shù)組的內(nèi)存映象2/1/20232數(shù)據(jù)結(jié)構(gòu)講義5.1.1數(shù)組的邏輯結(jié)構(gòu)數(shù)組是我們熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。2/1/20233數(shù)據(jù)結(jié)構(gòu)講義數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個(gè)數(shù)據(jù)元素有唯一的一組下標(biāo)來(lái)標(biāo)識(shí)，因此，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級(jí)語(yǔ)言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1) 取值操作：給定一組下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。(2) 賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。我們著重研究二維和三維數(shù)組，因?yàn)樗鼈兊膽?yīng)用是廣泛的，尤其是二維數(shù)組。2/1/20234數(shù)據(jù)結(jié)構(gòu)講義

5.1.2數(shù)組的內(nèi)存映象通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲(chǔ)結(jié)構(gòu)，這是因?yàn)閮?nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過(guò)一個(gè)映象函數(shù)，則可根據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址。對(duì)于一維數(shù)組按下標(biāo)順序分配即可。對(duì)多維數(shù)組分配時(shí)，要把它的元素映象存儲(chǔ)在一維存儲(chǔ)器中，一般有兩種存儲(chǔ)方式：一是以行為主序（或先行后列）的順序存放，如BASIC、PASCAL、COBOL、C等程序設(shè)計(jì)語(yǔ)言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是以列為主序（先列后行）的順序存放，如FORTRAN語(yǔ)言中，用的是以列為主序的分配順序，即一列一列地分配。2/1/20235數(shù)據(jù)結(jié)構(gòu)講義以行為主序的分配規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個(gè)下標(biāo)再變，…，從右向左，最后是左下標(biāo)。以列為主序分配的規(guī)律恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變，…，從左向右，最后是右下標(biāo)。

2/1/20236數(shù)據(jù)結(jié)構(gòu)講義例如一個(gè)2×3二維數(shù)組，邏輯結(jié)構(gòu)可以用左圖表示。以行為主序的內(nèi)存映象如右圖（a）所示。分配順序?yàn)椋篴11，a12，a13，a21，a22，a23；以列為主序的分配順序?yàn)椋篴11，a21，a12，a22，a13，a23；它的內(nèi)存映象如右圖（b）所示。2/1/20237數(shù)據(jù)結(jié)構(gòu)講義設(shè)有m×n二維數(shù)組Amn，下面我們看按元素的下標(biāo)求其地址的計(jì)算：以“以行為主序”的分配為例：設(shè)數(shù)組的基址為L(zhǎng)OC(a11)，每個(gè)數(shù)組元素占據(jù)l個(gè)地址單元，那么aij的物理地址可用一線性尋址函數(shù)計(jì)算：

LOC(aij)=LOC(a11)+((i-1)*n+j-1)*l

在C語(yǔ)言中，數(shù)組中每一維的下界定義為0，則：

LOC(aij)=LOC(a00)+(i*n+j)*l

推廣到一般的二維數(shù)組：A[c1..d1][c2..d2]，則aij的物理地址計(jì)算函數(shù)為：

LOC(aij)=LOC(ac1c2)+((i-c1)*(d2-c2+1)+(j-c2))*l2/1/20238數(shù)據(jù)結(jié)構(gòu)講義同理對(duì)于三維數(shù)組Amnp，即m×n×p數(shù)組，對(duì)于數(shù)組元素aijk其物理地址為：

LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1)*l

推廣到一般的三維數(shù)組：A[c1..d1][c2..d2][c3..d3]，則aijk的物理地址為：

LOC(i,j)=LOC(ac1c2c3)+((i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3))*l2/1/20239數(shù)據(jù)結(jié)構(gòu)講義三維數(shù)組的邏輯結(jié)構(gòu)和以行為主序的分配示意圖如圖所示。2/1/202310數(shù)據(jù)結(jié)構(gòu)講義例5.1若矩陣Am×n中存在某個(gè)元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫一個(gè)算法，找出A中的所有鞍點(diǎn)?；舅枷耄涸诰仃嘇中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個(gè)二維數(shù)組表示。2/1/202311數(shù)據(jù)結(jié)構(gòu)講義voidsaddle(intA[][],intm,intn)/*m,n是矩陣A的行和列*/{inti,j,min;

for(i=0;i<m;i++)/*按行處理*/{min=A[i][0]for(j=1;j<n;j++)if(A[i][j]<min)min=A[i][j];/*找第i行最小值*/

for(j=0;j<n;j++)/*檢測(cè)該行中的每一個(gè)最小值是否是鞍點(diǎn)*/

if(A[i][j]==min){k=j;p=0;

while(p<m&&A[p][j]<=min)

p++;if(p>=m)printf(＂%d,%d,%d\n＂,i,k,min);}}}

算法的時(shí)間性能為O(m*(n+m*n))。2/1/202312數(shù)據(jù)結(jié)構(gòu)講義5.2特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩陣三角矩陣帶狀矩陣2/1/202313數(shù)據(jù)結(jié)構(gòu)講義5.2.1對(duì)稱矩陣對(duì)稱矩陣的特點(diǎn)是：在一個(gè)n階方陣中，有aij=aji，其中1≤i,j≤n，如圖所示是一個(gè)５階對(duì)稱矩陣。2/1/202314數(shù)據(jù)結(jié)構(gòu)講義對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱，因此只需存儲(chǔ)上三角或下三角部分即可。比如，只存儲(chǔ)下三角中的元素aij，其特點(diǎn)是中j≤i且1≤i≤n，對(duì)于上三角中的元素aij，它和對(duì)應(yīng)的aji相等，因此當(dāng)訪問(wèn)的元素在上三角時(shí)，直接去訪問(wèn)和它對(duì)應(yīng)的下三角元素即可，這樣，原來(lái)需要n*n個(gè)存儲(chǔ)單元，現(xiàn)在只需要n(n+1)/2個(gè)存儲(chǔ)單元了，節(jié)約了n(n-1)/2個(gè)存儲(chǔ)單元，當(dāng)n較大時(shí)，這是可觀的一部分存儲(chǔ)資源。2/1/202315數(shù)據(jù)結(jié)構(gòu)講義如何只存儲(chǔ)下三角部分？對(duì)下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n*(n+1)/2個(gè)元素，因此，不失一般性，設(shè)存儲(chǔ)到向量SA[n(n+1)/2]中，存儲(chǔ)順序可用下圖示意，這樣，原矩陣下三角中的某一個(gè)元素aij則具體對(duì)應(yīng)一個(gè)sak，下面的問(wèn)題是要找到k與i、j之間的關(guān)系。2/1/202316數(shù)據(jù)結(jié)構(gòu)講義對(duì)于下三角中的元素aij，其特點(diǎn)是：i≥j且1≤i≤n，存儲(chǔ)到SA中后，根據(jù)存儲(chǔ)原則，它前面有i-1行，共有1+2+…+i-1=i*(i-1)/2個(gè)元素，而aij又是它所在的行中的第j個(gè)，所以在上面的排列順序中，aij是第i*(i-1)/2+j個(gè)元素，因此它在SA中的下標(biāo)k與i、j的關(guān)系為：

k=i*(i-1)/2+j-1(０≤k<n*(n+1)/2)

若i<j，則aij是上三角中的元素，因?yàn)閍ij=aji，這樣，訪問(wèn)上三角中的元素aij時(shí)則去訪問(wèn)和它對(duì)應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的元素在SA中的對(duì)應(yīng)關(guān)系：

k=j*(j-1)/2+i-1(０≤k<n*(n+1)/2)

綜上所述，對(duì)于對(duì)稱矩陣中的任意元素aij，若令I(lǐng)=max(i,j)，J=min(i,j)，則將上面兩個(gè)式子綜合起來(lái)得到：

k=I*(I-1)/2+J-1。2/1/202317數(shù)據(jù)結(jié)構(gòu)講義5.2.2三角矩陣形如下圖的矩陣稱為三角矩陣，其中c為某個(gè)常數(shù)。其中(a)為下三角矩陣：主對(duì)角線以上均為同一個(gè)常數(shù)；(b)為上三角矩陣，主對(duì)角線以下均為同一個(gè)常數(shù)；下面討論它們的壓縮存儲(chǔ)方法。2/1/202318數(shù)據(jù)結(jié)構(gòu)講義1.下三角矩陣與對(duì)稱矩陣類似，不同之處在于存完下三角中的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量，因?yàn)槭峭粋€(gè)常數(shù)，所以存一個(gè)即可，這樣一共存儲(chǔ)了n*(n+1)+1個(gè)元素，設(shè)存入向量：SA[n*(n+1)+1]中，這種的存儲(chǔ)方式可節(jié)約n*(n-1)-1個(gè)存儲(chǔ)單元，sak

與aji

的對(duì)應(yīng)關(guān)系為：2/1/202319數(shù)據(jù)結(jié)構(gòu)講義2.上三角矩陣對(duì)于上三角矩陣，存儲(chǔ)思想與下三角類似，以行為主序順序存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線下方的常量。對(duì)于第1行，存儲(chǔ)n個(gè)元素，第2行存儲(chǔ)n-1個(gè)元素，…，第p行存儲(chǔ)(n-p+1)個(gè)元素，aij的前面有i-1行，共存儲(chǔ)：個(gè)元素，aij

是它所在的行中要存儲(chǔ)的第（j-i+1）個(gè)也就是上三角存儲(chǔ)順序中的第(i-1)*(2n-i+2)/2+(j-i+1)個(gè)，因此它在SA中的下標(biāo)為：k=(i-1)*(2n-i+2)/2+j-i。

綜上，sak

與aji

的對(duì)應(yīng)關(guān)系為：2/1/202320數(shù)據(jù)結(jié)構(gòu)講義5.2.3帶狀矩陣

n階矩陣A稱為帶狀矩陣，如果存在最小正數(shù)m，滿足當(dāng)∣i-j∣≥m時(shí)，aij=0，這時(shí)稱w=2m-1為矩陣A的帶寬。下圖是一個(gè)w=3(m=2)的帶狀矩陣。帶狀矩陣也稱為對(duì)角矩陣。由下圖可看出，在這種矩陣中，所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零(或同一個(gè)常數(shù)c)。2/1/202321數(shù)據(jù)結(jié)構(gòu)講義一種壓縮方法是將A壓縮到一個(gè)n行w列的二維數(shù)組B中，如下圖所示，當(dāng)某行非零元素的個(gè)數(shù)小于帶寬w時(shí)，先存放非零元素后補(bǔ)零。那么aij

映射為bi′j′，映射關(guān)系為：2/1/202322數(shù)據(jù)結(jié)構(gòu)講義另一種壓縮方法是將帶狀矩陣壓縮到向量C中去，按以行為主序，順序的存儲(chǔ)其非零元素，如下圖所示，按其壓縮規(guī)律，找到相應(yīng)的映象函數(shù)。如當(dāng)w=3時(shí)，映象函數(shù)為：

k=2*i+j-32/1/202323數(shù)據(jù)結(jié)構(gòu)講義5.3稀疏矩陣稀疏矩陣的三元組表存儲(chǔ)稀疏矩陣的十字鏈表存儲(chǔ)2/1/202324數(shù)據(jù)結(jié)構(gòu)講義5.3.1稀疏矩陣的三元組表存儲(chǔ)將三元組按行優(yōu)先的順序，同一行中列號(hào)從小到大的規(guī)律排列成一個(gè)線性表，稱為三元組表，采用順序存儲(chǔ)方法存儲(chǔ)該表。如圖(a)稀疏矩陣對(duì)應(yīng)的三元組表為圖(b)。2/1/202325數(shù)據(jù)結(jié)構(gòu)講義#defineSMAX1024/*一個(gè)足夠大的數(shù)*/typedefstruct

{inti,j;

/*非零元素的行、列*/

datatypev;/*非零元素值*/}SPNode;/*三元組類型*/typedefstruct

{intmu,nu,tu;/*矩陣的行、列及非零元素的個(gè)數(shù)*/

SPNodedata[SMAX];/*三元組表*/}SPMatrix;

/*三元組表的存儲(chǔ)類型*/這樣的存儲(chǔ)方法確實(shí)節(jié)約了存儲(chǔ)空間，但矩陣的運(yùn)算從算法上可能變的復(fù)雜些。2/1/202326數(shù)據(jù)結(jié)構(gòu)講義1.稀疏矩陣的轉(zhuǎn)置設(shè)SPMatrixA;表示一m*n的稀疏矩陣，其轉(zhuǎn)置B則是一個(gè)n*m的稀疏矩陣，因此有SPMatrixB;。由A求B需：⑴A的行、列轉(zhuǎn)化成B的列、行；⑵將A.data中每一三元組的行列交換后轉(zhuǎn)到B.data中；以上兩點(diǎn)完成之后，并沒(méi)有完成B。因?yàn)槲覀兦懊嬉?guī)定三元組的是按一行一行且每行中的元素是按列號(hào)從小到大的規(guī)律順序存放的，因此B也必須按此規(guī)律實(shí)現(xiàn)，A的轉(zhuǎn)置B如圖(a)所示，圖(b)是它對(duì)應(yīng)的三元組存儲(chǔ)，就是說(shuō)，在A的三元組存儲(chǔ)基礎(chǔ)上得到B的三元組表存儲(chǔ)（為了運(yùn)算方便，矩陣的行列都從1算起，三元組表data也從1單元用起）。2/1/202327數(shù)據(jù)結(jié)構(gòu)講義算法思路：①A的行、列轉(zhuǎn)化成B的列、行；②在A.data中依次找第一列的、第二列的、直到最后一列，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B.data中即可。2/1/202328數(shù)據(jù)結(jié)構(gòu)講義voidTransM1(SPMatrix*A){SPMatrix*B;

intp,q,col;B=malloc(sizeof(SPMatrix));/*申請(qǐng)存儲(chǔ)空間*/

B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;/*稀疏矩陣的行、列、元素個(gè)數(shù)*/

if(B->tu>0)/*有非零元素則轉(zhuǎn)換*/{q=1;for(col=1;col<=(A->nu);col++)/*按A的列序轉(zhuǎn)換*/

for(p=1;p<=(A->tu);p++)/*掃描整個(gè)三元組表*/

if(A->data[p].j==col){B->data[q].i=A->data[p].j;

B->data[q].j=A->data[p].i;B->data[q].v=A->data[p].v;q++;

}returnB;/*返回的是轉(zhuǎn)置矩陣的指針*/}2/1/202329數(shù)據(jù)結(jié)構(gòu)講義分析該算法，其時(shí)間主要耗費(fèi)在col和p的二重循環(huán)上，所以時(shí)間復(fù)雜性為O(n*t)，(設(shè)m、n是原矩陣的行、列，t是稀疏矩陣的非零元素個(gè)數(shù))，顯然當(dāng)非零元素的個(gè)數(shù)t和m*n同數(shù)量級(jí)時(shí)，算法的時(shí)間復(fù)雜度為O(m*n2)，和通常存儲(chǔ)方式下矩陣轉(zhuǎn)置算法相比，可能節(jié)約了一定量的存儲(chǔ)空間，但算法的時(shí)間性能更差一些。2/1/202330數(shù)據(jù)結(jié)構(gòu)講義上述算法效率低的原因是算法要從A的三元組表中尋找第一列、第二列、…，要反復(fù)搜索A表，若能直接確定A中每一三元組在B中的位置，則對(duì)A的三元組表掃描一次即可。這是可以做到的，因?yàn)锳中第一列的第一個(gè)非零元素一定存儲(chǔ)在B.data[1]，如果還知道第一列的非零元素的個(gè)數(shù)，那么第二列的第一個(gè)非零元素在B.data中的位置便等于第一列的第一個(gè)非零元素在B.data中的位置加上第一列的非零元素的個(gè)數(shù)，如此類推，因?yàn)锳中三元組的存放順序是先行后列，對(duì)同一行來(lái)說(shuō)，必定先遇到列號(hào)小的元素，這樣只需掃描一遍A.data即可。2/1/202331數(shù)據(jù)結(jié)構(gòu)講義根據(jù)這個(gè)想法，需引入兩個(gè)向量來(lái)實(shí)現(xiàn)：num[n+1]和cpot[n+1]，num[col]表示矩陣A中第col列的非零元素的個(gè)數(shù)（為了方便均從1單元用起），cpot［col］初始值表示矩陣A中的第col列的第一個(gè)非零元素在B.data中的位置。于是cpot的初始值為：

cpot[1]=1；

cpot[col]=cpot[col-1]+num[col-1]；2≤col≤n2/1/202332數(shù)據(jù)結(jié)構(gòu)講義依次掃描A.data，當(dāng)掃描到一個(gè)col列元素時(shí)，直接將其存放在B.data的cpot[col]位置上，cpot[col]加１，cpot[col]中始終是下一個(gè)col列元素在B.data中的位置。例如對(duì)于矩陣A的num和cpot的值如下：2/1/202333數(shù)據(jù)結(jié)構(gòu)講義SPMatrix*TransM2(SPMatrix*A){SPMatrix*B;inti,j,k;intnum[n+1],cpot[n+1];

B=malloc(sizeof(SPMatrix));/*申請(qǐng)存儲(chǔ)空間*/

B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;

if(B->tu>0)/*有非零元素則轉(zhuǎn)換*/{for(i=1;i<=A->nu;i++)num[i]=0;for(i=1;i<=A->tu;i++)/*求矩陣A中每一列非零元素的個(gè)數(shù)*/{j=A->data[i].j;num[j]++;}

cpot[1]=1;/*求矩陣A中每一列第一個(gè)非零元素在B.data中的位置*/

for(i=2;i<=A->nu;i++)

cpot[i]=cpot[i-1]+num[i-1];for(i=1;i<=(A->tu);i++)/*掃描三元組表*/{j=A->data[i].j;/*當(dāng)前三元組的列號(hào)*/

k=cpot[j];/*當(dāng)前三元組在B.data中的位置*/

B->data[k].i=A->data[i].j;B->data[k].j=A->data[i].i;B->data[k].v=A->data[i].v;cpot[j]++;}}returnB;/*返回的是轉(zhuǎn)置矩陣的指針*/}2/1/202334數(shù)據(jù)結(jié)構(gòu)講義分析這個(gè)算法的時(shí)間復(fù)雜度：這個(gè)算法中有四個(gè)循環(huán)，分別執(zhí)行n，t，n-1，t次，在每個(gè)循環(huán)中，每次迭代的時(shí)間是一常量，因此總的計(jì)算量是O（n+t）。當(dāng)然它所需要的存儲(chǔ)空間比前一個(gè)算法多了兩個(gè)向量。2/1/202335數(shù)據(jù)結(jié)構(gòu)講義2．稀疏矩陣的乘積已知稀疏矩陣A(m1×n1)和B(m2×n2)，n1=m2，求乘積C(m1×n2)。稀疏矩陣A、B、C及它們對(duì)應(yīng)的三元組表A.data、B.data、C.data如圖所示。2/1/202336數(shù)據(jù)結(jié)構(gòu)講義由矩陣乘法規(guī)則知：C（i，j）=A(i,1)×B(1,j)+A(i,2)×B(2,j)+…+A(i,n)×B(n,j)

矩陣用二維數(shù)組表示時(shí)，傳統(tǒng)的矩陣乘法是：A的第一行與B的第一列對(duì)應(yīng)相乘累加后得到c11，A的第一行再與B的第二列對(duì)應(yīng)相乘累加后得到c12，…，因?yàn)楝F(xiàn)在按三元組表存儲(chǔ)，三元組表是按行為主序存儲(chǔ)的，在B.data中，同一行的非零元素其三元組是相鄰存放的，同一列的非零元素其三元組并未相鄰存放，因此在B.data中反復(fù)搜索某一列的元素是很費(fèi)時(shí)的，因此改變一下求值的順序。2/1/202337數(shù)據(jù)結(jié)構(gòu)講義以求c11和c12為例，因?yàn)椋杭碼11只有可能和B中第1行的非零元素相乘，a12只有可能和B中第2行的非零元素相乘，…，而同一行的非零元是相鄰存放的，所以求c11和c12同時(shí)進(jìn)行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22.，…，當(dāng)然只有aik和bkj(列號(hào)與行號(hào)相等)且均不為零（三元組存在）時(shí)才相乘，并且累加到cij當(dāng)中去。2/1/202338數(shù)據(jù)結(jié)構(gòu)講義為了運(yùn)算方便，設(shè)一個(gè)累加器：datatypetemp[n+1]；用來(lái)存放當(dāng)前行中cij的值，當(dāng)前行中所有元素全部算出之后，再存放到C.data中去。為了便于B.data中尋找B中的第k行第一個(gè)非零元素，與前面類似，在此需引入num和rpot兩個(gè)向量。num[k]表示矩陣B中第k行的非零元素的個(gè)數(shù)；rpot[k]表示第k行的第一個(gè)非零元素在B.data中的位置。于是有

rpot[1]=1rpot[k]=rpot[k-1]+num[k-1]2≤k≤n2/1/202339數(shù)據(jù)結(jié)構(gòu)講義例如，對(duì)于矩陣B的num和rpot如圖所示。2/1/202340數(shù)據(jù)結(jié)構(gòu)講義根據(jù)以上分析，稀疏矩陣的乘法運(yùn)算的粗略步驟如下：⑴初始化。清理一些單元，準(zhǔn)備按行順序存放乘積矩陣;⑵求B的num，rpot;⑶做矩陣乘法。將A.data中三元組的列值與B.data中三元組的行值相等的非零元素相乘，并將具有相同下標(biāo)的乘積元素相加。2/1/202341數(shù)據(jù)結(jié)構(gòu)講義SPMatrix*MulSMatrix(SPMatrix*A,SPMatrix*B)/*稀疏矩陣A(m1×n1)和B(m2×n2)用三元組表存儲(chǔ)，求A×B*/

{SPMatrix*C;/*乘積矩陣的指針*/

intp,q,i,j,k,r;datatypetemp[n+1];intnum[B->nu+1],rpot[B->nu+1];if(A->nu!=B->mu)

returnNULL;/*A的列與B的行不相等*/

C=malloc(sizeof(SPMatrix));/*申請(qǐng)C矩陣的存儲(chǔ)空間*/

C->mu=A->mu;C->nu=B->nu;

if(A->tu*B->tu==0){C->tu=0;returnC;}

for(i=1;i<=B->mu;i++)num[i]=0;

for(k=1;k<=B->tu;k++){i=B->data[k].i;num[i]++;

}

/*求矩陣B中每一行非零元素的個(gè)數(shù)*/

rpot[1]=1;/*求矩陣B中每一行第一個(gè)非零元素在B.data中的位置*/

for(i=2;i<=B->mu;i++)

rpot[i]=rpot[i-1]+num[i-1];2/1/202342數(shù)據(jù)結(jié)構(gòu)講義

r=0;/*當(dāng)前C中非零元素的個(gè)數(shù)*/

p=1;/*指示A.data中當(dāng)前非零元素的位置*/

for(i=1;i<=A->mu;i++){for(j=1;j<=B->nu;j++)temp[j]=0;/*cij的累加器初始化*/

while(A->data[p].i==i)./*求第i行的*/{k=A->data[p].j;/*A中當(dāng)前非零元的列號(hào)*/

if(k<B->mu)t=rpot[k+1];elset=B->tu+1;

/*確定B中第k行的非零元素在B.data中的下限位置*/

for(q=rpot[k];q<t;q++;){j=B->data[q].j;temp[j]+=A->data[p].v*B->data[q].v}/*B中第k行的每一個(gè)非零元素*/

p++;}for(j=1;j<=B->nu;j++)if(temp[j]){r++;C->data[r]={i,j,temp[j]};}}C->tu=r;returnC;}2/1/202343數(shù)據(jù)結(jié)構(gòu)講義分析上述算法的時(shí)間性能如下：（1）求num的時(shí)間復(fù)雜度為O(B->nu+B->tu)；（2）求rpot時(shí)間復(fù)雜度為O(B->mu)；（3）求temp時(shí)間復(fù)雜度為O(A->mu*B->nu)；（4）求C的所有非零元素的時(shí)間復(fù)雜度為O(A->tu*B->tu/B->mu)；（5）壓縮存儲(chǔ)時(shí)間復(fù)雜度為O(A->mu*B->nu)；所以總的時(shí)間復(fù)雜度為O(A->mu*B->nu+(A->tu*B->tu)/B->nu)。2/1/202344數(shù)據(jù)結(jié)構(gòu)講義5.3.2稀疏矩陣的十字鏈表存儲(chǔ)三元組表可以看作稀疏矩陣順序存儲(chǔ)，但是在做一些操作（如加法、乘法）時(shí)，非零項(xiàng)數(shù)目及非零元素的位置會(huì)發(fā)生變化，這時(shí)這種表示就十分不便。在這節(jié)中，我們介紹稀疏矩陣的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——十字鏈表，它同樣具備鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)，因此，在某些情況下，采用十字鏈表表示稀疏矩陣是很方便的。2/1/202345數(shù)據(jù)結(jié)構(gòu)講義下圖是一個(gè)稀疏矩陣的十字鏈表。2/1/202346數(shù)據(jù)結(jié)構(gòu)講義用十字鏈表表示稀疏矩陣的基本思想是：對(duì)每個(gè)非零元素存儲(chǔ)為一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)由5個(gè)域組成，其結(jié)構(gòu)如圖表示，其中：row域存儲(chǔ)非零元素的行號(hào)，col域存儲(chǔ)非零元素的列號(hào)，v域存儲(chǔ)本元素的值，right，down是兩個(gè)指針域。2/1/202347數(shù)據(jù)結(jié)構(gòu)講義結(jié)點(diǎn)的結(jié)構(gòu)定義如下:

typedefstructnode{introw,col;structnode*down,*right;unionv_next{datatypev;structnode*next;}}MNode，*MLink;2/1/202348數(shù)據(jù)結(jié)構(gòu)講義5.4廣義表

顧名思義，廣義表是線性表的推廣。也有人稱其為列表（Lists，用復(fù)數(shù)形式以示與統(tǒng)稱的表List的區(qū)別）。廣義表的定義和基本運(yùn)算廣義表的存儲(chǔ)廣義表基本操作的實(shí)現(xiàn)2/1/202349數(shù)據(jù)結(jié)構(gòu)講義5.4.1 廣義表的定義和基本運(yùn)算⒈廣義表的定義和性質(zhì)我們知道，線性表是由n個(gè)數(shù)據(jù)元素組成的有限序列。其中每個(gè)組成元素被限定為單元素，有時(shí)這種限制需要拓寬。例如，中國(guó)舉辦的某體育項(xiàng)目國(guó)際邀請(qǐng)賽，參賽隊(duì)清單可采用如下的表示形式：（俄羅斯，巴西，（國(guó)家，河北，四川），古巴，美國(guó)，（），日本）在這個(gè)拓寬了的線性表中，韓國(guó)隊(duì)?wèi)?yīng)排在美國(guó)隊(duì)的后面，但由于某種原因未參加，成為空表。國(guó)家隊(duì)、河北隊(duì)、四川隊(duì)均作為東道主的參賽隊(duì)參加，構(gòu)成一個(gè)小的線性表，成為原線性表的一個(gè)數(shù)據(jù)項(xiàng)。這種拓寬了的線性表就是廣義表。2/1/202350數(shù)據(jù)結(jié)構(gòu)講義

廣義表（GeneralizedLists）是n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an的有序序列，一般記作：ls＝（a1，a2，…，ai，…，an）

其中：ls是廣義表的名稱，n是它的長(zhǎng)度。每個(gè)ai（1≤i≤n）是ls的成員，它可以是單個(gè)元素，也可以是一個(gè)廣義表，分別稱為廣義表ls的單元素和子表。當(dāng)廣義表ls非空時(shí)，稱第一個(gè)元素a1為ls的表頭（head），稱其余元素組成的表（a2，…，ai，…，an）為ls的表尾（tail）。

顯然，廣義表的定義是遞歸的。2/1/202351數(shù)據(jù)結(jié)構(gòu)講義為書寫清楚起見，通常用大寫字母表示廣義表，用小寫字母表示單個(gè)數(shù)據(jù)元素，廣義表用括號(hào)括起來(lái)，括號(hào)內(nèi)的數(shù)據(jù)元素用逗號(hào)分隔開。下面是一些廣義表的例子：

A＝（）B＝（e）C＝（a，（b，c，d））D＝（A，B，C）E＝（a，E）

F＝（（））2/1/202352數(shù)據(jù)結(jié)構(gòu)講義⒉廣義表的性質(zhì)從上述廣義表的定義和例子可以得到廣義表的下列重要性質(zhì)：⑴廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，…。⑵廣義表可以是遞歸的表。廣義表的定義并沒(méi)有限制元素的遞歸，即廣義表也可以是其自身的子表。例如表E就是一個(gè)遞歸的表。⑶廣義表可以為其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名稱來(lái)引用。2/1/202353數(shù)據(jù)結(jié)構(gòu)講義廣義表的上述特性對(duì)于它的使用價(jià)值和應(yīng)用效果起到了很大的作用。廣義表可以看成是線性表的推廣，線性表是廣義表的特例。廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下，它可以兼容線性表、數(shù)組、樹和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。當(dāng)二維數(shù)組的每行（或每列）作為子表處理時(shí)，二維數(shù)組即為一個(gè)廣義表。另外，樹和有向圖也可以用廣義表來(lái)表示。由于廣義表不僅集中了線性表、數(shù)組、樹和有向圖等常見數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可有效地利用存儲(chǔ)空間，因此在計(jì)算機(jī)的許多應(yīng)用領(lǐng)域都有成功使用廣義表的實(shí)例。2/1/202354數(shù)據(jù)結(jié)構(gòu)講義⒊廣義表基本運(yùn)算廣義表有兩個(gè)重要的基本操作，即取頭操作（Head）和取尾操作（Tail）。

根據(jù)廣義表的表頭、表尾的定義可知，對(duì)于任意一個(gè)非空的列表，其表頭可能是單元素也可能是列表，而表尾必為列表。例如：Head（B）＝eTail（B）＝（）Head（C）＝aTail（C）＝（（b，c，d））Head（D）＝ATail（D）＝（B，C）Head（E）＝aTail（E）＝（E）Head（F）＝（）Tail（F）＝（）

此外，在廣義表上可以定義與線性表類似的一些操作，如建立、插入、刪除、拆開、連接、復(fù)制、遍歷等。2/1/202355數(shù)據(jù)結(jié)構(gòu)講義CreateLists(ls)：根據(jù)廣義表的書寫形式創(chuàng)建一個(gè)廣義表ls。IsEmpty(ls)：若廣義表ls空，則返回True；否則返回False。Length(ls)：求廣義表ls的長(zhǎng)度。Depth(ls)：求廣義表ls的深度。Locate(ls，x)：在廣義表ls中查找數(shù)據(jù)元素x。Merge(ls1，ls2)：以ls1為頭、ls2為尾建立廣義表。CopyGList(ls1，ls2)：復(fù)制廣義表，即按ls1建立廣義表ls2。Head(ls)：返回廣義表ls的頭部。Tail(ls)：返回廣義表的尾部?！?/1/202356數(shù)據(jù)結(jié)構(gòu)講義5.4.2廣義表的存儲(chǔ)由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，因此難以用順序的存儲(chǔ)結(jié)構(gòu)來(lái)表示。而鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)分配較為靈活，易于解決廣義表的共享與遞歸問(wèn)題，所以通常都采用鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)廣義表。在這種表示方式下，每個(gè)數(shù)據(jù)元素可用一個(gè)結(jié)點(diǎn)表示。按結(jié)點(diǎn)形式的不同，廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又可以分為不同的兩種存儲(chǔ)方式。一種稱為頭尾表示法，另一種稱為孩子兄弟表示法。2/1/202357數(shù)據(jù)結(jié)構(gòu)講義⒈頭尾表示法若廣義表不空，則可分解成表頭和表尾；反之，一對(duì)確定的表頭和表尾可惟一地確定一個(gè)廣義表。頭尾表示法就是根據(jù)這一性質(zhì)設(shè)計(jì)而成的一種存儲(chǔ)方法。由于廣義表中的數(shù)據(jù)元素既可能是列表也可能是單元素，相應(yīng)地在頭尾表示法中結(jié)點(diǎn)的結(jié)構(gòu)形式有兩種：一種是表結(jié)點(diǎn)，用以表示列表；另一種是元素結(jié)點(diǎn)，用以表示單元素。在表結(jié)點(diǎn)中應(yīng)該包括一個(gè)指向表頭的指針和指向表尾的指針；而在元素結(jié)點(diǎn)中應(yīng)該包括所表示單元素的元素值。為了區(qū)分這兩類結(jié)點(diǎn)，在結(jié)點(diǎn)中還要設(shè)置一個(gè)標(biāo)志域，如果標(biāo)志為1，則表示該結(jié)點(diǎn)為表結(jié)點(diǎn)；如果標(biāo)志為0，則表示該結(jié)點(diǎn)為元素結(jié)點(diǎn)。2/1/202358數(shù)據(jù)結(jié)構(gòu)講義其形式定義說(shuō)明如下：typedefenum{ATOM,LIST}Elemtag;/*ATOM=0：?jiǎn)卧?；LIST=1：子表*/typedefstructGLNode{Elemtagtag;/*標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn)*/

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

datatypedata;/*data是元素結(jié)點(diǎn)的值域*/

struct{structGLNode*hp,*tp

}ptr;/*ptr是表結(jié)點(diǎn)的指針域，ptr.hp和ptr.tp分別指向表頭和表尾*/};}*GList;/*廣義表類型*/2/1/202359數(shù)據(jù)結(jié)構(gòu)講義頭尾表示法的結(jié)點(diǎn)形式如圖所示。2/1/202360數(shù)據(jù)結(jié)構(gòu)講義對(duì)于5.5.1所列舉的廣義表A、B、C、D、E、F，若采用頭尾表示法的存儲(chǔ)方式，其存儲(chǔ)結(jié)構(gòu)如圖所示。2/1/202361數(shù)據(jù)結(jié)構(gòu)講義從上述存儲(chǔ)結(jié)構(gòu)示例中可以看出，采用頭尾表示法容易分清列表中單元素或子表所在的層次。例如，在廣義表D中，單元素a和e在同一層次上，而單元素b、c、d在同一層次上且比a和e低一層，子表B和C在同一層次上。另外，最高層的表結(jié)點(diǎn)的個(gè)數(shù)即為廣義表的長(zhǎng)度。例如，在廣義表D的最高層有三個(gè)表結(jié)點(diǎn)，其廣義表的長(zhǎng)度為3。2/1/202362數(shù)據(jù)結(jié)構(gòu)講義⒉孩子兄弟表示法廣義表的另一種表示法稱為孩子兄弟表示法。在孩子兄弟表示法中，也有兩種結(jié)點(diǎn)形式：一種是有孩子結(jié)點(diǎn)，用以表示列表；另一種是無(wú)孩子結(jié)點(diǎn)，用以表示單元素。在有孩子結(jié)點(diǎn)中包括一個(gè)指向第一個(gè)孩子（長(zhǎng)子）的指針和一個(gè)指向兄弟的指針；而在無(wú)孩子結(jié)點(diǎn)中包括一個(gè)指向兄弟的指針和該元素的元素值。為了能區(qū)分這兩類結(jié)點(diǎn)，在結(jié)點(diǎn)中還要設(shè)置一個(gè)標(biāo)志域。如果標(biāo)志為1，則表示該結(jié)點(diǎn)為有孩子結(jié)點(diǎn)；如果標(biāo)志為0，則表示該結(jié)點(diǎn)為無(wú)孩子結(jié)點(diǎn)。2/1/202363數(shù)據(jù)結(jié)構(gòu)講義其形式定義說(shuō)明如下：typedefenum{ATOM,LIST}Elemtag;

/*ATOM=0：?jiǎn)卧?；LIST=1：子表*/typedefstructGLENode{Elemtagtag;/*標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn)*/

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

datatypedata;/*元素結(jié)點(diǎn)的值域*/

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

structGLENode*tp;/*指向下一個(gè)結(jié)點(diǎn)*/}*EGList;/*廣義表類型*/2/1/202364數(shù)據(jù)結(jié)構(gòu)講義孩子兄弟表示法的結(jié)點(diǎn)形式如圖所示。2/1/202365數(shù)據(jù)結(jié)構(gòu)講義對(duì)于5.5.1節(jié)中所列舉的廣義表A、B、C、D、E、F，若采用孩子兄弟表示法的存儲(chǔ)方式，其存儲(chǔ)結(jié)構(gòu)如圖所示。2/1/202366數(shù)據(jù)結(jié)構(gòu)講義從圖的存儲(chǔ)結(jié)構(gòu)示例中可以看出，采用孩子兄弟表示法時(shí)，表達(dá)式中的左括號(hào)“（”對(duì)應(yīng)存儲(chǔ)表示中的tag=1的結(jié)點(diǎn)，且最高層結(jié)點(diǎn)的tp域必為NULL。2/1/202367數(shù)據(jù)結(jié)構(gòu)講義5.5.3廣義表基本操作的實(shí)現(xiàn)我們以頭尾表示法存儲(chǔ)廣義表，討論廣義表的有關(guān)操作的實(shí)現(xiàn)。由于廣義表的定義是遞歸的，因此相應(yīng)的算法一般也都是遞歸的。2/1/202368數(shù)據(jù)結(jié)構(gòu)講義⒈廣義表的取頭、取尾GListHead(GListls){ifls->tag==1

thenp=ls->hp;returnp;}GListTail(GListls){ifls->tag==1

thenp=ls->tp;returnp;}2/1/202369數(shù)據(jù)結(jié)構(gòu)講義⒉建立廣義表的存儲(chǔ)結(jié)構(gòu)intCreate(GList*ls,char*S){Glistp;char*sub;ifStrEmpty(S)*ls=NULL;else{if(!(*ls=(GList)malloc(sizeof(GLNode))))return0;if(StrLength(S)==1){

(*ls)->tag=0;(*ls)->data=S;}else{(*ls)->tag=1;p=*ls;hsub=SubStr(S,2,StrLength(S)-2);

do{

sever(sub,hsub);

Create(&(p->ptr.hp),sub);