數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組第2講1本章分為（2～3）講第1講

5.1

數(shù)組的基本概念

5.2

特殊矩陣

第2講5.3稀疏矩陣5.3.1數(shù)組元素的三元組

5.3.2三元組順序表供教師參考第2講5.3.3十字鏈表5.5廣義表

25.3稀疏矩陣

矩陣中大多數(shù)元素值為零，只有很少非零元素，這些非零元素的分布又沒(méi)有明顯的規(guī)律，這種矩陣稱為稀疏矩陣。假設(shè)矩陣的行數(shù)為m，列數(shù)為n，非零元素個(gè)數(shù)為t，則t<m或t<n或t<<m*n的情況都可以視作稀疏矩陣。有一個(gè)100*100的矩陣，僅有20個(gè)非零元素，它就是稀疏矩陣。如圖稀疏矩陣:3稀疏矩陣的主要運(yùn)算：（1）稀疏矩陣的輸入建立；（2）稀疏矩陣的輸出；（3）稀疏矩陣的轉(zhuǎn)置、求逆矩陣；（4）兩個(gè)稀疏矩陣求和、求差、求乘積。為了壓縮存儲(chǔ)稀疏矩陣，僅保存非零元素，而不存儲(chǔ)零元素。一個(gè)非零元素往往需要3個(gè)參數(shù)：行號(hào)、列號(hào)和數(shù)據(jù)值。45.3.1數(shù)組元素的三元組一個(gè)三元組(i,j,aij)能唯一確定矩陣中的一個(gè)非零元素。例如：a11用(1,1,15)表示；a14用(1,4,22)表示；……；a51用（5,1,91）表示；a63用（6,3,28）表示。

對(duì)于某m行n列且有t個(gè)非零元素的稀疏矩陣，還需一個(gè)表示矩陣特征的三元組（m,n,t）。

5

一個(gè)稀疏矩陣所有非零元素的三元組（i,j,aij）再加上（m,n,t），就能唯一地確定稀疏矩陣。一個(gè)稀疏矩陣所對(duì)應(yīng)的若干三元組的集合，可以采用順序結(jié)構(gòu)存儲(chǔ)，也可以采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)。下面首先介紹稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)。

struct

Thrinode//定義三元組結(jié)構(gòu)

{inti;//非零元素的行號(hào)

intj;//非零元素的列號(hào)

ElemTypev;//非零元素?cái)?shù)據(jù)值

}65.3.2三元組順序表矩陣M的三元組順序表如(a)圖。矩陣N的三元組順序表如(b)圖。

采用按行優(yōu)先原則。71．稀疏矩陣三元組表的類定義constintMAXSIZE=50; //定義常量typedef

int

ElemType; //假設(shè)數(shù)據(jù)元素是整型//定義Thrinode為三元組結(jié)構(gòu)體struct

Thrinode{inti;intj; //非零元素的行號(hào)列號(hào)

ElemTypev; //非零元素的數(shù)據(jù)值

};//三元組表SqMatrix

類定義classSqMatrix{………};

8三元組表的類定義classSqMatrix{private:

intm;

//矩陣的總行數(shù)

intn;

//矩陣的總列數(shù)

intt;

//非零元素的總個(gè)數(shù)

Thrinode

data[MAXSIZE]; //三元組表

public:

SqMatrix(); //構(gòu)造函數(shù)

voidCreat(); //輸入建立一個(gè)矩陣

SqMatrix

TransmatOne(); //矩陣轉(zhuǎn)置方法1

SqMatrix

TransmatTwo(); //矩陣轉(zhuǎn)置方法2voidShowMatrix(); //矩陣的輸出顯示};92．稀疏矩陣的主要算法

矩陣運(yùn)算有矩陣轉(zhuǎn)置、求逆矩陣、兩個(gè)矩陣相加（減）等。重點(diǎn)討論矩陣轉(zhuǎn)置?？从颐鎴D示：怎樣由(a)生成(b)？都是按行優(yōu)先原則。

教師應(yīng)將圖表(a)am和,(b)bn畫(huà)在黑板上，與算法對(duì)照10（1）按原矩陣M的列序進(jìn)行轉(zhuǎn)置

若要按照待求解的轉(zhuǎn)置矩陣N的行序優(yōu)先排放非零元素。就需按照矩陣M的列序進(jìn)行轉(zhuǎn)置。首先從圖（a）am表中找出第1列的所有的非零元素，逐一存入bn表。然后再?gòu)腶m表中找出第2列的所有的非零元素，逐一存入bn表。直到從am表中找出第n列的非零元素逐一存入bn表。具體實(shí)現(xiàn)見(jiàn)算法5.1。類的數(shù)據(jù)成員data[]表示原矩陣M，b.data[]表示轉(zhuǎn)置后的矩陣N。11//按原矩陣列序轉(zhuǎn)置-算法5.1

SqMatrix

qMatrix::TransmatOne() {SqMatrixb;

cout<<“\n按原矩陣的列序轉(zhuǎn)置："<<endl;

b.m=n;

b.n=m;

b.t=t;if(t!=0)//非零元素個(gè)數(shù)t為零，不執(zhí)行操作

{intq=0; //設(shè)q為b.data[]表的下標(biāo)

for(int

col=1;col<=n;col++)

//矩陣M的列循環(huán)

for(intp=0;p<t;p++)//掃描data[](矩陣M)的所有非零元素

12for(int

col=1;col<=n;col++)//M列循環(huán),b排一行

for(intp=0;p<t;p++)//掃描data[]所有非零元素

{if(data[p].j==col){b.data[q].j=data[p].i;

b.data[q].i=data[p].j;

b.data[q].v=data[p].v;q++;}}//forp}//if

cout<<"\n矩陣轉(zhuǎn)置已完成!"<<endl;returnb;//返回轉(zhuǎn)置后的三元組表b}13算法的時(shí)間復(fù)雜度

因算法的主要工作是在col和p的二重循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(n*t)。當(dāng)非零元素個(gè)數(shù)t比較多，其數(shù)量級(jí)接近m*n時(shí)，其時(shí)間復(fù)雜度就接近O(m*n*n)，這比直接用二維數(shù)組表示矩陣的轉(zhuǎn)置算法的時(shí)間量級(jí)O(m*n)要差，此時(shí)的空間占用也很大為3*m*n。14（2）按原矩陣M的行序進(jìn)行轉(zhuǎn)置

按原矩陣M的行序轉(zhuǎn)置，就是按照data[]三元組的次序進(jìn)行轉(zhuǎn)置。這樣只需對(duì)data[]掃描一趟。轉(zhuǎn)置后的元素在b.data[]中一般不能連續(xù)存放，而應(yīng)直接放到b.data[]中應(yīng)有的位置上。為了確定矩陣M中的每一列（col）的第1個(gè)非零元素（即N中每一行的第1個(gè)非零元素）在b.data[]中應(yīng)有的位置，需要先求矩陣M中的每一列中非零元素的個(gè)數(shù)。需設(shè)置兩個(gè)數(shù)組num[1..n]和pot[1..n]：num[col]表示矩陣M第col列非零元素的個(gè)數(shù)；pot[col]表示M中第col列第1個(gè)非零元素在b.data[]中位置。15設(shè)置兩個(gè)數(shù)組num[1..n]和pot[1..n]

掃描data[]一趟求出num[col]。然后：pot[1]=0;

pot[col]=pot[col-1]+num[col-1]，見(jiàn)下表2。col123456num[col]212201pot[col]023577對(duì)照板書(shū)圖表講解16//按矩陣M行序轉(zhuǎn)置-算法5.2

SqMatrix

SqMatrix::TransmatTwo() {SqMatrixb;

int

num[MAXSIZE]; //M每列非零元素的個(gè)數(shù)

int

pot[MAXSIZE];//每列首個(gè)非零元素在b中位置

intcol,q;b.m=n;b.n=m;b.t=t;if(t!=0) //非零元素個(gè)數(shù)為零，不操作

{for(col=1;col<=n;col++)num[col]=0;//清零for(intp=0;p<t;p++)num[data[p].j]++;//統(tǒng)計(jì)

pot[1]=0;for(col=2;col<=n;col++)//計(jì)算

pot[col]=pot[col-1]+num[col-1];

17//按矩陣M行序轉(zhuǎn)置算法5.2-續(xù)

for(intp=0;p<t;p++) //進(jìn)行轉(zhuǎn)置

{col=data[p].j;//取M的非零元素列號(hào)

q=pot[col];

//確定該元素在b.data[]中位置

b.data[q].i=data[p].j;

b.data[q].j=data[p].i;

b.data[q].v=data[p].v;

pot[col]++;//修改pot[col]值

}//forp}//ift

cout<<"\n矩陣轉(zhuǎn)置已完成!"<<endl;returnb; //返回轉(zhuǎn)置后的三元組表b對(duì)象}18算法時(shí)間復(fù)雜度

算法5.2僅比算法5.1多用了兩個(gè)輔助數(shù)組num[MAXSIZE]和pot[MAXSIZE]。算法有4個(gè)并列的for循環(huán)語(yǔ)句，它們分別執(zhí)行n,t,n?1和t次。因此，算法的時(shí)間復(fù)雜度為O(n+t)。在t比較大和m*n等數(shù)量級(jí)時(shí)，該算法的執(zhí)行時(shí)間上升到O(m*n)?；仡櫵惴?.1時(shí)間復(fù)雜度為O(n*t)，顯然算法5.2更加優(yōu)化。195.3.3十字鏈表當(dāng)矩陣非零元素的位置或個(gè)數(shù)經(jīng)常變動(dòng)時(shí)，為了避免大量移動(dòng)數(shù)據(jù)元素，三元組順序表表就不適合作為稀疏矩陣的存儲(chǔ)結(jié)構(gòu)。此時(shí)，采用鏈表存儲(chǔ)結(jié)構(gòu)更為恰當(dāng)。由于稀疏矩陣元素具有二維定位特征，因此單鏈表不適用，本節(jié)將介紹十字鏈表的存儲(chǔ)方法。20稀疏矩陣A與它的十字鏈表存儲(chǔ)圖

教師應(yīng)將圖表(a)am和,(b)bn畫(huà)在黑板上，與算法對(duì)照211．十字鏈表的組成（1）總表頭結(jié)點(diǎn)

有一個(gè)指針hm指向總表頭結(jié)點(diǎn)。該結(jié)點(diǎn)存放矩陣的總行數(shù)m、總列數(shù)n，next指針域指向第一個(gè)行列表頭結(jié)點(diǎn)。down和right閑置不用。

（2）行列表頭結(jié)點(diǎn)（3）非零元素結(jié)點(diǎn)22（2）行列表頭結(jié)點(diǎn)

①結(jié)構(gòu)與總表頭結(jié)點(diǎn)相同。其十字鏈表須設(shè)置S（S取m，n之較大值）個(gè)行列表頭結(jié)點(diǎn)，首地址用一維數(shù)組h來(lái)存儲(chǔ)，h[1]，h[2]，…，h[S]。每個(gè)結(jié)點(diǎn)中的row和col域被置為0；它的next指向下一個(gè)行列表頭結(jié)點(diǎn)；

right指向本行第1個(gè)非零元素結(jié)點(diǎn)；

down指向本列第1個(gè)非零元素結(jié)點(diǎn)。②行列表頭的循環(huán)鏈表。最后一個(gè)行列表頭結(jié)點(diǎn)的next域要求指向總表頭結(jié)點(diǎn)hm，形成一個(gè)行列表頭的循環(huán)鏈表。對(duì)照十字鏈表講解23（3）非零元素結(jié)點(diǎn)①結(jié)構(gòu)與其他結(jié)點(diǎn)域結(jié)構(gòu)相似。只是next域變?yōu)関al域存放