數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版）（微課版）第4章 特殊矩陣和廣義表

第4章

特殊矩陣和廣義表教學(xué)要求相關(guān)知識(shí)點(diǎn)稀疏矩陣廣義表的表頭、表尾學(xué)習(xí)重點(diǎn)稀疏矩陣的存儲(chǔ)與操作廣義表的操作目錄特殊矩陣的壓縮存儲(chǔ)1廣義表2本章小結(jié)34.1特殊矩陣的

壓縮存儲(chǔ)4.1特殊矩陣的壓縮存儲(chǔ)規(guī)律分布特殊矩陣的壓縮存儲(chǔ)兩種規(guī)律分布特殊矩陣：對(duì)稱矩陣和三角矩陣。充分利用元素值的分布規(guī)律，將特殊矩陣進(jìn)行壓縮存儲(chǔ)。兩條原則：一是盡可能地壓縮數(shù)據(jù)量，二是壓縮后仍然可以比較容易地進(jìn)行各項(xiàng)基本操作。1.對(duì)稱矩陣及其壓縮存儲(chǔ)在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：aij=aji 0≤i，j≤n-1則稱A為n階對(duì)稱矩陣。如圖4.5(a)為4階對(duì)稱矩。4.1特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，因此，順序存儲(chǔ)時(shí)為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間，即只存放主對(duì)角線和下三角(或上三角)區(qū)的元素。對(duì)稱矩陣下標(biāo)i,j0,01,01,12,02,12,23,03,13,23,3一維數(shù)組下標(biāo)k0123456789a[i][j]a[j][i]b[k]1057312201742314元素存儲(chǔ)位置：4.1特殊矩陣的壓縮存儲(chǔ)為每一對(duì)對(duì)稱元素只分配一個(gè)存儲(chǔ)空間，且按行優(yōu)先的次序順序存儲(chǔ)主對(duì)角線和下三角區(qū)的元素，那么對(duì)于n階對(duì)稱矩陣來(lái)說(shuō)，只需要存放第0行的一個(gè)元素a00，第1行的兩個(gè)元素a10、a11，第n-1行的n個(gè)元素an-1,0，an-1,1，an-1,n-1。4.1特殊矩陣的壓縮存儲(chǔ)矩陣每行存儲(chǔ)的元素個(gè)數(shù)形成一個(gè)等差數(shù)列，該數(shù)列的首項(xiàng)是1，末項(xiàng)是n，項(xiàng)數(shù)是n，公差是1。因此，對(duì)稱矩陣要存儲(chǔ)的元素個(gè)數(shù)為：n(n+1)/2。非壓縮存儲(chǔ)矩陣需分配n2個(gè)存儲(chǔ)區(qū)，由于對(duì)稱矩陣的對(duì)稱性，壓縮存儲(chǔ)后只需分配n(n+1)/2個(gè)存儲(chǔ)區(qū)，幾乎節(jié)省一半。對(duì)稱矩陣進(jìn)行壓縮存儲(chǔ)后，訪問(wèn)該矩陣元素的位置計(jì)算公式如式：

其中k(0≤k≤n(n+1)/2)對(duì)稱矩陣位于(i，j)位置的元素在一維數(shù)組中的存儲(chǔ)序號(hào)。4.1特殊矩陣的壓縮存儲(chǔ)將一維數(shù)組a中壓縮存儲(chǔ)的下三角4×4階對(duì)稱矩陣按矩陣格式輸出。print(inta[]){inti,j;for(i=0;i<4;i++){for(j=0;j<4;j++)if(i>=j)printf("%4d",a[i*(i+1)/2+j]);elseprintf("%4d",a[j*(j+1)/2+i]);printf(“\n”);}}4.1特殊矩陣的壓縮存儲(chǔ)2.三角矩陣及其壓縮存儲(chǔ)三角矩陣分為上三角矩陣和下三角矩陣。下三角矩陣以主對(duì)角線為界的上半部分是一個(gè)固定值，下半部分的元素值沒(méi)有規(guī)律；上三角矩陣以主對(duì)角線為界的下半部分是一個(gè)固定值，上半部分的元素值沒(méi)有規(guī)律。(a)下三角矩陣(b)上三角矩陣4.1特殊矩陣的壓縮存儲(chǔ)三角矩陣的存儲(chǔ)除了存儲(chǔ)其上(下)三角中的元素之外，再加一個(gè)存儲(chǔ)常數(shù)C的存儲(chǔ)空間，即一個(gè)n階方陣只需為n(n+1)/2+1個(gè)元素分配存儲(chǔ)空間。4.1特殊矩陣的壓縮存儲(chǔ)下三角矩陣圖4.7(a)的壓縮存儲(chǔ)可將上三角部分的常量值存儲(chǔ)在第0個(gè)單元，下三角和主對(duì)角上的元素從第1個(gè)存儲(chǔ)單元開始存放，則以行優(yōu)先的方式存儲(chǔ)如下：012345678910C29612810301326920對(duì)下三角矩陣進(jìn)行壓縮存儲(chǔ)后，訪問(wèn)該矩陣元素的位置計(jì)算公式如式k=k(0≤k≤n(n+1)/2)是下三角矩陣位于(i，j)位置的元素在一維數(shù)組中的存儲(chǔ)序號(hào)。4.1特殊矩陣的壓縮存儲(chǔ)上三角矩陣的壓縮存儲(chǔ)可將下三角部分的常量值存儲(chǔ)在第0個(gè)單元，上三角和主對(duì)角上的元素從第1個(gè)存儲(chǔ)單元開始存放，則以行優(yōu)先的方式存儲(chǔ)如下：012345678910C29681312102630920對(duì)上三角矩陣進(jìn)行壓縮存儲(chǔ)后，訪問(wèn)該矩陣元素的位置計(jì)算公式如式k=k(0≤k≤n(n+1)/2)是上三角矩陣位于(i，j)位置的元素在一維數(shù)組中的存儲(chǔ)序號(hào)。4.1特殊矩陣的壓縮存儲(chǔ)稀疏矩陣及其壓縮存儲(chǔ)稱非零元素較零元素少，且分布沒(méi)有規(guī)律的矩陣為稀疏矩陣。若m×n的矩陣含有t個(gè)非零元素，且t遠(yuǎn)遠(yuǎn)小于m×n，則將這個(gè)矩陣稱為稀疏矩陣。令δ=t/(m*n)，稱δ為矩陣的稀疏因子。一個(gè)5階方陣，共25個(gè)元素，其中非零元素6個(gè)，零元素19個(gè)，零元素占整個(gè)元素個(gè)數(shù)的76%，它是一個(gè)稀疏矩陣。4.1特殊矩陣的壓縮存儲(chǔ)稀疏矩陣及其壓縮存儲(chǔ)用三元組法對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)：用三項(xiàng)內(nèi)容表示稀疏矩陣中的每個(gè)非零元素，形式為：(i，j，value)。其中，i表示行序號(hào)，j表示列序號(hào)，value表示非零元素的值。將稀疏矩陣中的所有非零元素用這種三元組的形式表示，并將它們按以行為主的順序存放在一維數(shù)組中，形成一個(gè)三元組表。4.1特殊矩陣的壓縮存儲(chǔ)

三元組ijvalue00031047212-1320-1421-254324.1特殊矩陣的壓縮存儲(chǔ)1.稀疏矩陣的三元組表的順序存儲(chǔ)及實(shí)現(xiàn)(1)稀疏矩陣的三元組表的順序存儲(chǔ)稀疏矩陣的三元組表的順序存儲(chǔ)結(jié)構(gòu)定義如下：typedefintElemType; #defineMAXSIZE100//非零元素個(gè)數(shù)的最大值typedefstruct{inti,j; /*行下標(biāo)，列下標(biāo)*/

ElemTypee; /*非零元素值*/}Triple;4.1特殊矩陣的壓縮存儲(chǔ)typedefstruct{Tripledata[MAXSIZE+1]; /*非零元素三元組表，data[0]未用*/

intmu,nu,tu; /*矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}TSMatrix;用一個(gè)m×n的二維數(shù)組來(lái)存放稀疏矩陣A；用變量tu記錄非零元素的個(gè)數(shù)；變量mu記錄稀疏矩陣的行數(shù)；變量nu記錄非零元素的列數(shù)；用Triple結(jié)構(gòu)體來(lái)存放稀疏矩陣A的非零元素的三元組，其中的i表示行下標(biāo)，j表示列下標(biāo)；用data來(lái)存放非零三元組表。4.1特殊矩陣的壓縮存儲(chǔ)(2)創(chuàng)建稀疏矩陣M根據(jù)一維數(shù)組a及要?jiǎng)?chuàng)建的順序存儲(chǔ)三元組表實(shí)現(xiàn)的稀疏矩陣M所要求的行數(shù)、列數(shù)創(chuàng)建稀疏矩陣M。intCreateM(TSMatrix*M,inta[],introw,intcol){intt,k=0;

for(t=0;t<row*col;t++) if(a[t]!=0)//對(duì)數(shù)組中的非零元素創(chuàng)建三元組

{(*M).data[k].i=t/col;//三元組行號(hào)

(*M).data[k].j=t%col;//三元組列號(hào)

(*M).data[k].e=a[t];//三元組的非零元素值

++k;

}

4.1特殊矩陣的壓縮存儲(chǔ)

if(k)//如果三元組表中有元素，則創(chuàng)建三元組成功

{ (*M).tu=k;//矩陣的非零元素個(gè)數(shù)

(*M).mu=row;//矩陣的行數(shù)

(*M).nu=col;//矩陣的列數(shù)return1;

}

elsereturn0;}4.1特殊矩陣的壓縮存儲(chǔ)2.三元組表的鏈?zhǔn)酱鎯?chǔ)(1)帶行指針的單鏈表存儲(chǔ)法稀疏矩陣每行非零元素的三元組連成一個(gè)單鏈表，每行三元組鏈表設(shè)置一個(gè)表頭指針。每個(gè)非零元素的三元組中增添一個(gè)指針域，指向本行下個(gè)非零元素的三元組。4.1特殊矩陣的壓縮存儲(chǔ)由于相同的行的三元組節(jié)點(diǎn)中，都包含有相同的行號(hào)域，因此可以把三元組里的行號(hào)域提取出來(lái)放在表頭節(jié)點(diǎn)里，這時(shí)的單鏈表存儲(chǔ)法如圖4.8(b)所示。4.2廣義表4.2廣義表廣義表的定義廣義表是n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，一般記作：LS＝(a0，a1，……，an-1)。LS是廣義表的名稱，ai（0≤i≤n-1）是LS的成員（也稱直接元素），它可以是單個(gè)的數(shù)據(jù)元素(也稱原子)，也可以是一個(gè)廣義表，分別稱為L(zhǎng)S的單元素和子表。習(xí)慣上，用大寫字母表示廣義表的名稱，用小寫字母表示原子。當(dāng)廣義表LS為非空時(shí)，稱第一個(gè)元素a0為L(zhǎng)S的表頭（Head），稱其余元素組成的表（a1，……，an-1）為L(zhǎng)S的表尾（Tail）。n是廣義表的長(zhǎng)度，即廣義表最外層包含元素個(gè)數(shù)。廣義表的深度定義為所含括弧的重?cái)?shù)，注意：“原子”的深度為

0，“空表”的深度為

1。

4.2廣義表廣義表的特性（1）廣義表中元素是有次序性的。表中的元素位置不可以隨意調(diào)換，調(diào)換后表示的是一個(gè)不同的廣義表。（2）廣義表有長(zhǎng)度。廣義表最外層包含元素個(gè)數(shù)是它的長(zhǎng)度，不管這個(gè)元素是原子，還是子表?？毡黹L(zhǎng)度為0。（3）廣義表有深度。為所含括弧的層數(shù)，如果表中元素是子表，要把子表用原子表示出來(lái)，再計(jì)算廣義表的深度。（4）廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表。（5）廣義表中元素可共享。子表可以為其它子表所共享。4.2廣義表（6）廣義表中元素可遞歸。即廣義表中的子表可以是其本身的一個(gè)子表。這時(shí)，廣義表的深度是個(gè)無(wú)限值，長(zhǎng)度是個(gè)有限值。（7）任何一個(gè)非空廣義表LS＝(a0，a1，……，an-1)均可分解為：表頭Head(LS)=a0和表尾Tail(LS)=(a1，a2，……，an-1)兩部分。4.2廣義表廣義表的常用表示及基本運(yùn)算1.廣義表的表示(1)廣義表存儲(chǔ)數(shù)據(jù)的常用表示形式①E=()E是一個(gè)空表，其長(zhǎng)度為0。②L=(a,b)L是長(zhǎng)度為2的廣義表，它的兩個(gè)元素都是原子，因此它是一個(gè)線性表。③A=(x,L)=(x,(a,b))A是長(zhǎng)度為2的廣義表，第一個(gè)元素是原子x，第二個(gè)元素是子表L。4.2廣義表④B=(A,y)=((x,(a,b)),y)B是長(zhǎng)度為2的廣義表，第一個(gè)元素是子表A，第二個(gè)元素是原子y。⑤C=(A,B)=((x,(a,b)),((x,(a,b)),y))C的長(zhǎng)度為2，兩個(gè)元素都是子表。⑥D(zhuǎn)=(a,D)=(a,(a,(a,(…))))D的長(zhǎng)度為2，第一個(gè)元素是原子，第二個(gè)元素是D自身，展開是一個(gè)無(wú)限的廣義表。4.2廣義表(2)廣義表的深度一個(gè)表的“深度”是指表展開后所含括號(hào)的層數(shù)。表L、A、B、C的深度為分別為1、2、3、4，表D的深度為∞。4.2廣義表(3)帶名稱的廣義表表示如果規(guī)定任何表都是有名稱的，為了既表明每個(gè)表的名稱，又說(shuō)明它的組成，則可以在每個(gè)表的前面冠以該表的名稱，于是上例中的各表又可以寫成：①E()②L(a,b)③A(x,L(a,b))④B(A(x,L(a,b)),y)⑤C(A(x,l(a,b)),B(A(x,L(a,b)),y))⑥D(zhuǎn)(a,D(a,D(…)))4.2廣義表2.廣義表的基本運(yùn)算由于廣義表是對(duì)線性表和樹的推廣，并且具有共享和遞歸特性的廣義表可以和有向圖建立對(duì)應(yīng)，因此廣義表的大部分運(yùn)算與這些數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算類似。只討論廣義表的兩種特殊的基本運(yùn)算：取表頭head(Ls)和取表尾tail(Ls)。任何一個(gè)非空廣義表的表頭是表中的第一個(gè)元素，它可以是原子，也可以是子表，而其表尾必定是子表。廣義表的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)【例4.1】取廣義表的表頭及表尾假設(shè)廣義表L=(a,(b)),B=(A,(y))，則有：head(L)=a，tail(L)=((b))head(B