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

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

稀疏矩陣的壓縮存儲表示下的運算的實現(xiàn)⒌學時安排：4學時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)其特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。2/1/20233數(shù)據(jù)結(jié)構(gòu)講義數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標來標識，因此，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1) 取值操作：給定一組下標，讀其對應的數(shù)據(jù)元素。(2) 賦值操作：給定一組下標，存儲或修改與其相對應的數(shù)據(jù)元素。我們著重研究二維和三維數(shù)組，因為它們的應用是廣泛的，尤其是二維數(shù)組。2/1/20234數(shù)據(jù)結(jié)構(gòu)講義

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

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

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

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

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

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

LOC(aij)=LOC(ac1c2)+((i-c1)*(d2-c2+1)+(j-c2))*l2/1/20238數(shù)據(jù)結(jié)構(gòu)講義同理對于三維數(shù)組Amnp，即m×n×p數(shù)組，對于數(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中存在某個元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點?；舅枷耄涸诰仃嘇中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個二維數(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++)/*檢測該行中的每一個最小值是否是鞍點*/

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

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

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

若i<j，則aij是上三角中的元素，因為aij=aji，這樣，訪問上三角中的元素aij時則去訪問和它對應的下三角中的aji即可，因此將上式中的行列下標交換就是上三角中的元素在SA中的對應關(guān)系：

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

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

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

與aji

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

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

綜上，sak

與aji

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

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

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

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

{inti,j;

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

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

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

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

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

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

B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;/*稀疏矩陣的行、列、元素個數(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++)/*掃描整個三元組表*/

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

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中每一列非零元素的個數(shù)*/{j=A->data[i].j;num[j]++;}

cpot[1]=1;/*求矩陣A中每一列第一個非零元素在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;/*當前三元組的列號*/

k=cpot[j];/*當前三元組在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)講義分析這個算法的時間復雜度：這個算法中有四個循環(huán)，分別執(zhí)行n，t，n-1，t次，在每個循環(huán)中，每次迭代的時間是一常量，因此總的計算量是O（n+t）。當然它所需要的存儲空間比前一個算法多了兩個向量。2/1/202335數(shù)據(jù)結(jié)構(gòu)講義2．稀疏矩陣的乘積已知稀疏矩陣A(m1×n1)和B(m2×n2)，n1=m2，求乘積C(m1×n2)。稀疏矩陣A、B、C及它們對應的三元組表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ù)組表示時，傳統(tǒng)的矩陣乘法是：A的第一行與B的第一列對應相乘累加后得到c11，A的第一行再與B的第二列對應相乘累加后得到c12，…，因為現(xiàn)在按三元組表存儲，三元組表是按行為主序存儲的，在B.data中，同一行的非零元素其三元組是相鄰存放的，同一列的非零元素其三元組并未相鄰存放，因此在B.data中反復搜索某一列的元素是很費時的，因此改變一下求值的順序。2/1/202337數(shù)據(jù)結(jié)構(gòu)講義以求c11和c12為例，因為：即a11只有可能和B中第1行的非零元素相乘，a12只有可能和B中第2行的非零元素相乘，…，而同一行的非零元是相鄰存放的，所以求c11和c12同時進行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22.，…，當然只有aik和bkj(列號與行號相等)且均不為零（三元組存在）時才相乘，并且累加到cij當中去。2/1/202338數(shù)據(jù)結(jié)構(gòu)講義為了運算方便，設一個累加器：datatypetemp[n+1]；用來存放當前行中cij的值，當前行中所有元素全部算出之后，再存放到C.data中去。為了便于B.data中尋找B中的第k行第一個非零元素，與前面類似，在此需引入num和rpot兩個向量。num[k]表示矩陣B中第k行的非零元素的個數(shù)；rpot[k]表示第k行的第一個非零元素在B.data中的位置。于是有

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

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中每一行非零元素的個數(shù)*/

rpot[1]=1;/*求矩陣B中每一行第一個非零元素在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;/*當前C中非零元素的個數(shù)*/

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

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中當前非零元的列號*/

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行的每一個非零元素*/

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)講義分析上述算法的時間性能如下：（1）求num的時間復雜度為O(B->nu+B->tu)；（2）求rpot時間復雜度為O(B->mu)；（3）求temp時間復雜度為O(A->mu*B->nu)；（4）求C的所有非零元素的時間復雜度為O(A->tu*B->tu/B->mu)；（5）壓縮存儲時間復雜度為O(A->mu*B->nu)；所以總的時間復雜度為O(A->mu*B->nu+(A->tu*B->tu)/B->nu)。2/1/202344數(shù)據(jù)結(jié)構(gòu)講義5.3.2稀疏矩陣的十字鏈表存儲三元組表可以看作稀疏矩陣順序存儲，但是在做一些操作（如加法、乘法）時，非零項數(shù)目及非零元素的位置會發(fā)生變化，這時這種表示就十分不便。在這節(jié)中，我們介紹稀疏矩陣的一種鏈式存儲結(jié)構(gòu)——十字鏈表，它同樣具備鏈式存儲的特點，因此，在某些情況下，采用十字鏈表表示稀疏矩陣是很方便的。2/1/202345數(shù)據(jù)結(jié)構(gòu)講義下圖是一個稀疏矩陣的十字鏈表。2/1/202346數(shù)據(jù)結(jié)構(gòu)講義用十字鏈表表示稀疏矩陣的基本思想是：對每個非零元素存儲為一個結(jié)點，結(jié)點由5個域組成，其結(jié)構(gòu)如圖表示，其中：row域存儲非零元素的行號，col域存儲非零元素的列號，v域存儲本元素的值，right，down是兩個指針域。2/1/202347數(shù)據(jù)結(jié)構(gòu)講義結(jié)點的結(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，用復數(shù)形式以示與統(tǒng)稱的表List的區(qū)別）。廣義表的定義和基本運算廣義表的存儲廣義表基本操作的實現(xiàn)2/1/202349數(shù)據(jù)結(jié)構(gòu)講義5.4.1 廣義表的定義和基本運算⒈廣義表的定義和性質(zhì)我們知道，線性表是由n個數(shù)據(jù)元素組成的有限序列。其中每個組成元素被限定為單元素，有時這種限制需要拓寬。例如，中國舉辦的某體育項目國際邀請賽，參賽隊清單可采用如下的表示形式：（俄羅斯，巴西，（國家，河北，四川），古巴，美國，（），日本）在這個拓寬了的線性表中，韓國隊應排在美國隊的后面，但由于某種原因未參加，成為空表。國家隊、河北隊、四川隊均作為東道主的參賽隊參加，構(gòu)成一個小的線性表，成為原線性表的一個數(shù)據(jù)項。這種拓寬了的線性表就是廣義表。2/1/202350數(shù)據(jù)結(jié)構(gòu)講義

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

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

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

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

根據(jù)廣義表的表頭、表尾的定義可知，對于任意一個非空的列表，其表頭可能是單元素也可能是列表，而表尾必為列表。例如：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）＝（）

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

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

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

struct{structGLNode*hp,*tp

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

/*ATOM=0：單元素；LIST=1：子表*/typedefstructGLENode{Elemtagtag;/*標志域，用于區(qū)分元素結(jié)點和表結(jié)點*/

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

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

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

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