數(shù)據(jù)結構(C語言版)(第二版) 第4章 特殊矩陣和廣義表

第4章

特殊矩陣和廣義表教學要求相關知識點稀疏矩陣廣義表的表頭、表尾學習重點稀疏矩陣的存儲與操作廣義表的操作目錄特殊矩陣的壓縮存儲1廣義表2本章小結34.1特殊矩陣的

壓縮存儲4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲本節(jié)將介紹兩種特殊矩陣：對稱矩陣和三角矩陣的壓縮存儲。對于這些特殊矩陣，應該充分利用元素值的分布規(guī)律，將其進行壓縮存儲。選擇壓縮存儲的方法應遵循兩條原則：一是盡可能地壓縮數(shù)據(jù)量，二是壓縮后仍然可以比較容易地進行各項基本操作。1.對稱矩陣及其壓縮存儲在一個n階方陣A中，若元素滿足下述性質：aij=aji 0≤i，j≤n-1則稱A為n階對稱矩陣。如圖4.5(a)為4階對稱矩。4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲1.對稱矩陣及其壓縮存儲對稱矩陣中的元素關于主對角線對稱，若將對稱矩陣中的所有數(shù)據(jù)元素都進行存儲，則所需的存儲空間將會隨著矩陣階數(shù)n的增大而急劇上升。因此，對于順序存儲而言，最好的做法是為每一對對稱元素分配一個存儲空間，即只存放主對角線和下三角(或上三角)區(qū)的元素。012345678910573122017423144.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲1.對稱矩陣及其壓縮存儲為討論方便，假定為每一對對稱元素只分配一個存儲空間，且按行優(yōu)先的次序順序存儲主對角線和下三角區(qū)的元素，那么對于n階對稱矩陣來說，只需要存放第0行的一個元素a00，第1行的兩個元素a10、a11，第2行的3個元素a20，a21，a22，……第n-1行的n個元素an-1,0，an-1,1，an-1,n-1。4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲1.對稱矩陣及其壓縮存儲現(xiàn)在，矩陣中每行要存儲的元素個數(shù)，恰好形成一個等差數(shù)列，該數(shù)列的首項是1，末項是n，項數(shù)是n，公差是1。因此，對稱矩陣要存儲的元素個數(shù)為：n(n+1)/2。這樣，原先存儲整個矩陣需要給n2個元素分配存儲區(qū)，現(xiàn)在由于矩陣的對稱性只需要給n(n+1)/2個元素分配存儲區(qū)，所需存儲區(qū)幾乎節(jié)省了一半，這就是對對稱矩陣進行壓縮存儲的意義所在。對對稱矩陣進行壓縮存儲后，訪問該矩陣元素的位置計算公式如式(4.2)：4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲1.對稱矩陣及其壓縮存儲k=0，1，2，…，n(n+1)/2-1，是對稱矩陣位于(i，j)位置的元素在一維數(shù)組中的存儲序號。4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲1.對稱矩陣及其壓縮存儲以下C語言函數(shù)的功能是將一維數(shù)組a中壓縮存儲的下三角4×4階對稱矩陣按矩陣格式輸出。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特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲2.三角矩陣及其壓縮存儲三角矩陣分為上三角矩陣和下三角矩陣，下三角矩陣的特點是以主對角線為界的上半部分是一個固定的值，下半部分的元素值沒有任何規(guī)律；上三角矩陣的特點是以主對角線為界的下半部分是一個固定的值，上半部分的元素值沒有任何規(guī)律。其中，C表示某個常數(shù)，當然也可以為0。(a)下三角矩陣(b)上三角矩陣4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲2.三角矩陣及其壓縮存儲三角矩陣的存儲除了只存儲其上(下)三角中的元素之外，再加一個存儲常數(shù)C的存儲空間即可，即一個n階方陣中只需要為n(n+1)/2+1個元素分配存儲空間。例如，下三角矩陣圖4.7(a)的壓縮存儲可將上三角部分的常量值存儲在第0個單元，下三角和主對角上的元素從第1個存儲單元開始存放，則以行優(yōu)先的方式存儲。對下三角矩陣進行壓縮存儲后，訪問該矩陣元素的位置計算公式如式k=012345678910C296128103013269204.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲2.三角矩陣及其壓縮存儲k=0，1，2，…，n(n+1)/2，是下三角矩陣位于(i，j)位置的元素在一維數(shù)組中的存儲序號。同理，上三角矩陣的壓縮存儲可將下三角部分的常量值存儲在第0個單元，上三角和主對角上的元素從第1個存儲單元開始存放，則以行優(yōu)先的方式存儲。4.1特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲2.三角矩陣及其壓縮存儲對上三角矩陣進行壓縮存儲后，訪問該矩陣元素的位置計算公式如式k=k=0，1，2，…，(n+1)/2，是上三角矩陣位于(i，j)位置的元素在一維數(shù)組中的存儲序號。012345678910C296813121026309204.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲在特殊矩陣中如果非零元素的分布有明顯的規(guī)律，就可以將其壓縮存儲到一維數(shù)組中，并找到每個非零元素在一維數(shù)組中的對應關系。然而，在實際應用中我們還會經(jīng)常遇到另一類矩陣，其非零元素較零元素少，且分布沒有一定的規(guī)律，我們稱之為稀疏矩陣。對稀疏矩陣人們無法給出確切的定義，它只是一個憑人們的直覺了解的概念。若一個m×n的矩陣含有t個非零元素，且t遠遠小于m×n，則我們將這個矩陣稱為稀疏矩陣。令δ=t/(m*n)，則稱δ為矩陣的稀疏因子。如圖4.10所示為一個5階方陣，共25個元素，其中非零元素6個，零元素19個，零元素占整個元素個數(shù)的76%?？梢哉f它是一個稀疏矩陣。4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲由于稀疏矩陣的零元素很多，非零元素很少，因此完全可以對其進行壓縮存儲。通常采用三元組表示法來對稀疏矩陣進行壓縮存儲：即矩陣中的每個元素都由行序號和列序號唯一確定，需要用三項內(nèi)容表示稀疏矩陣中的每個非零元素，形式為：(i，j，value)。其中，i表示行序號，j表示列序號，value表示非零元素的值。將稀疏矩陣中的所有非零元素用這種三元組的形式表示，并將它們按以行為主的順序存放在一維數(shù)組中，形成一個三元組表。4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲

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

ElemTypee; /*非零元素值*/}Triple;4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲1.三元組表的順序存儲及實現(xiàn)typedefstruct{Tripledata[MAXSIZE+1]; /*非零元素三元組表，data[0]未用*/

intmu,nu,tu; /*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/}TSMatrix;用一個m×n的二維數(shù)組來存放稀疏矩陣A；用變量tu記錄非零元素的個數(shù)；變量mu記錄稀疏矩陣的行數(shù)；變量nu記錄非零元素的列數(shù)；用Triple結構體來存放稀疏矩陣A的非零元素的三元組，其中的i表示行下標，j表示列下標；用data來存放非零三元組表。4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲1.三元組表的順序存儲及實現(xiàn)(1)創(chuàng)建稀疏矩陣MintCreateM(TSMatrix*M,inta[],introw,intcol){inti,k=0;

for(i=0;i<row*col;i++)

if(a[i]!=0)

{

M->data[k].i=i/col;

M->data[k].j=i%col;

M->data[k].e=a[i];

++k;

}

4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲1.三元組表的順序存儲及實現(xiàn)(1)創(chuàng)建稀疏矩陣M

if(k)

{M->tu=k;

M->mu=row;

M->nu=col;

return1;

}

else

return0;}4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲1.三元組表的順序存儲及實現(xiàn)(2)求稀疏矩陣M的轉置矩陣T算法4.7求稀疏矩陣的轉置intTransposeSMatrix(TSMatrixM,TSMatrix*T){intp,q,col;

T->mu=M.nu;

T->nu=M.mu;

T->tu=M.tu;

if(T->tu)

{q=0;

for(col=0;col<M.nu;++col) 4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲1.三元組表的順序存儲及實現(xiàn)(2)求稀疏矩陣M的轉置矩陣T /*先將列轉換成行*/

for(p=0;p<M.tu;++p) /*再將行轉換成列*/

if(M.data[p].j==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;

++q;

}

}

return1;}4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲1.三元組表的順序存儲及實現(xiàn)(2)求稀疏矩陣M的轉置矩陣TM為m×n的矩陣，首先創(chuàng)建一個n×m的T矩陣，然后逐個將M矩陣的非零元素的行值賦給T矩陣的非零元素的列值，同時相應地將非零元素值賦給T矩陣。4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲2.三元組表的鏈式存儲帶行指針的單鏈表存儲法該方法是把稀疏矩陣每行非零元素的三元組連接成一個單鏈表，并為每行的三元組鏈表設置一個表頭指針。為此，要在每一個非零元素的三元組中增添一個指針域，指向本行下一個非零元素的三元組。由于相同的行的三元組節(jié)點中，都包含有相同的行號域，因此也可以把三元組里的行號域提取出來含在表頭節(jié)點里，這時的單鏈表存儲法如圖4.8(b)所示。4.1特殊矩陣的壓縮存儲稀疏矩陣及其壓縮存儲2.三元組表的鏈式存儲(1)帶行指針的單鏈表存儲法

圖4.8帶行指針的單鏈表存儲法(a)帶行指針的單鏈表存儲法(b)行指針集中的單鏈表存儲法4.2廣義表4.2廣義表廣義表的定義廣義表是n（n≥0）個數(shù)據(jù)元素的有限序列，一般記作：LS＝(a0，a1，……，an-1)。其中，LS是廣義表的名稱，ai（0≤i≤n-1）是LS的成員（也稱直接元素），它可以是單個的數(shù)據(jù)元素，也可以是一個廣義表，分別稱為LS的單元素和子表。習慣上，用大寫字母表示廣義表的名稱，用小寫字母表示原子。當廣義表LS為非空時，稱第一個元素a0為LS的表頭（Head），稱其余元素組成的表（a1，……，an-1）為LS的表尾（Tail）。n是廣義表的長度，即廣義表最外層包含元素個數(shù)。廣義表的深度定義為所含括弧的重數(shù)，注意:“原子”的深度為

0，“空表”的深度為

1。

4.2廣義表廣義表的定義廣義表有以下特性（1）廣義表中元素是有次序性的。廣義表表中的元素位置不可以隨意調換，調換后表示的是一個不同的廣義表。通過取表頭，表尾兩個操作我們可以看出，表中元素相同，但位置不同的廣義表，得到的結果是不同，所以是兩個不同的廣義表。（2）廣義表有長度。廣義表最外層包含元素個數(shù)是它的長度，不管這個元素是單元素，還是列表?？毡黹L度為0。，（3）廣義表有深度。為所含括弧的層數(shù)，所以，如果表中元素是列表，要把列表用單元素表示出來，這樣再來計算廣義表的深度。4.2廣義表廣義表的定義廣義表有以下特性（4）廣義表是一種多層次的數(shù)據(jù)結構。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表。（5）廣義表中元素可共享。列表可以為其它列表所共享。（6）廣義表中元素可遞歸。即廣義表中的列表可以是其本身的一個子表。這時，廣義表的深度是個無限值，長度是個有限值。（7）任何一個非空廣義表LS＝(a0，a1，……，an-1)均可分解為：表頭Head(LS)=a0和表尾Tail(LS)=(a1，a2，……，an-1)兩部分。4.2廣義表廣義表的存儲結構及實現(xiàn)1.廣義表的表示(1)廣義表常用表示①E=()E是一個空表，其長度為0。②L=(a,b)L是長度為2的廣義表，它的兩個元素都是原子，因此它是一個線性表。③A=(x,L)=(x,(a,b))A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。4.2廣義表廣義表的存儲結構及實現(xiàn)1.廣義表的表示(1)廣義表常用表示④B=(A,y)=((x,(a,b)),y)B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。⑤C=(A,B)=((x,(a,b)),((x,(a,b)),y))C的長度為2，兩個元素都是子表。⑥D=(a,D)=(a,(a,(a,(…))))D的長度為2，第一個元素是原子，第二個元素是D自身，展開是一個無限的廣義表。4.2廣義表廣義表的存儲結構及實現(xiàn)1.廣義表的表示(2)廣義表的深度一個表的“深度”是指表展開后所含括號的層數(shù)。表L、A、B、C的深度為分別為1、2、3、4，表D的深度為∞。4.2廣義表廣義表的存儲結構及實現(xiàn)1.廣義表的表示(3)帶名稱的廣義表表示如果規(guī)定任何表都是有名稱的，為了既表明每個表的名稱，又說明它的組成，則可以在每個表的前面冠以該表的名稱，于是上例中的各表又可以寫成：①E()②L(a,b)③A(x,L(a,b))