1、第四章 數(shù)組,數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表 4.1 數(shù)組的定義和特點(diǎn) 定義,數(shù)組特點(diǎn) 數(shù)組結(jié)構(gòu)固定 數(shù)據(jù)元素同構(gòu) 數(shù)組運(yùn)算 給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素 給定一組下標(biāo)，修改數(shù)據(jù)元素的值,4.2 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 次序約定 以行序?yàn)橹餍?以列序?yàn)橹餍?4.3 矩陣的壓縮存儲(chǔ) 對(duì)稱矩陣,三角矩陣,對(duì)角矩陣,Loc(aij)=Loc(a11)+2(i-1)+(j-1),數(shù)組可看成是一種特殊的線性表，其特殊在于，表中的數(shù)所元素本身也是一種線性表。 數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級(jí)語(yǔ)言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，

2、并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。多維數(shù)組是向量的推廣。例如，二維數(shù)組： a11 a12 a1n a21 a22 a2n am1 am2 amn,Amn=,4.1 數(shù)組的定義,可以看成是由個(gè)行向量組成的向量，也可以看成是個(gè)列向量組成的向量。 在C語(yǔ)言中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說(shuō)， typedef elemtype array2mn; 等價(jià)于： typedef elemtype array1n; typedef array1 array2m; 同理，一個(gè)維數(shù)組類型可以定義為其數(shù)據(jù)元素為維數(shù)組類型

3、的一維序組類型。 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。,2 數(shù)組的順序表示和實(shí)現(xiàn) 由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。 又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說(shuō)，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法來(lái)表示數(shù)組。,通常有兩種順序存儲(chǔ)方式： 行優(yōu)先順序?qū)?shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為： a11,a

4、12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。 列優(yōu)先順序?qū)?shù)組元素按列向量排列，第j+1個(gè)列向量緊接在第j個(gè)列向量之后，A的m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為： a11,a21,am1,a12,a22,am2,an1,an2,anm 在FORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。,以上規(guī)則可以推廣到多維數(shù)組的情況：優(yōu)先順序可規(guī)定為先排最右的下標(biāo)，從右到左，最后排最左下標(biāo)：列優(yōu)先順序與此相反，先排最左下標(biāo)，從左向右，最后排最右下標(biāo)。 按上述兩種方式順序存儲(chǔ)的序組，只要知道開(kāi)始結(jié)點(diǎn)的存放地址（即基地址），維數(shù)和每維

5、的上、下界，以及每個(gè)數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。,例如，二維數(shù)組Amn按“行優(yōu)先順序”存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用d個(gè)存儲(chǔ)單元。 元素aij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因?yàn)閍ij位于第i行、第j列，前面i-1行一共有(i-1) n個(gè)元素，第i行上aij前面又有j-1個(gè)元素，故它前面一共有(i-1) n+j-1個(gè)元素，因此，aij的地址計(jì)算函數(shù)為： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d 同樣，三維數(shù)組Ai

6、jk按“行優(yōu)先順序”存儲(chǔ)，其地址計(jì)算函數(shù)為： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p +(k-1)*d,上述討論均是假設(shè)數(shù)組各維的下界是不是1，更一般的二維數(shù)組是Ac1.d1,c2.d2，這里c1,c2不一定是1。aij前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-c1行共有(i-c1)*(d2-c2+1)個(gè)元素，第i行上aij前一共有j-c2個(gè)元素，因此，aij的地址計(jì)算函數(shù)為： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C語(yǔ)言中，數(shù)組各維下標(biāo)的下界是0，因此在C語(yǔ)言中，二維數(shù)組的地址計(jì)

7、算公式為： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來(lái)存儲(chǔ)密度仍為1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間，可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。,4.2 矩陣的壓縮

8、存儲(chǔ),所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。 1、對(duì)稱矩陣 在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)： aij=aji 0i,jn-1 則稱A為對(duì)稱矩陣。對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素。,1 特殊矩陣,存儲(chǔ)形式如圖所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1

9、a n-1 2 a n-1 n-1 在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素，元 素總數(shù)為：(i+1)=n(n+1)/2 可以將這些元素存放在一個(gè)向量sa0.n(n+1)/2-1中。為了便于訪問(wèn)對(duì)稱矩陣A中的元素，我們必須在aij和sak之間找一個(gè)對(duì)應(yīng)關(guān)系。,若ij，則ai j在下三角形中。 ai j之前的i行（從第0行到第i-1行）一共有1+2+i=i(i+1)/2個(gè)元素，在第i行上， ai j之前恰有j個(gè)元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式

10、中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，則k和 i, j的對(duì)應(yīng)關(guān)系可統(tǒng)一為： k=I*(I+1)/2+J 0 kn(n+1)/2,因此，aij的地址可用下列式計(jì)算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下標(biāo)交換關(guān)系，對(duì)于任意給定一組下標(biāo) (i，j)，均可在sak中找到矩陣元素aij，反之，對(duì)所有 的k=0,1,2,n(n-1)/2-1，都能確定sak中的元素在矩陣中的位置(i,j)。由此，稱san(n+1)/2為階對(duì)稱矩陣A的壓縮

11、存儲(chǔ)，見(jiàn)下圖： k=0 1 2 3 n(n-1)/2 n(n-1)/2-1 例如a21和a12均存儲(chǔ)在 sa4中，這是因?yàn)?k=I*(I+1)/2+J=2*(2+1)/2+1=4,以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。 上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線） 中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì) 角線上方均為常數(shù)。在大多數(shù)情況下， 三角矩陣常數(shù)為零。 a00 a01 a 0 n-1 a00 0 0 0 a11 a 1 n-1 a10 a11 0 . . 0 0 a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩陣 (b)下三角矩陣,2、

12、三角矩陣,三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量sa0.n(n+1)/2中，其中c存放在向量的最后一個(gè)分量中， 上三角矩陣中，主對(duì)角線之上的第p行(0pj,k=,下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，sak和aij對(duì)應(yīng)關(guān)系是： i(i+1)/2+j ij n(n+1)/2 ij 3、對(duì)角矩陣 對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線為了中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)三對(duì)角矩陣， a00 a01 a10 a11 a12 a21 a22 a23 . . .

13、 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1,k=,非零元素僅出現(xiàn)在主對(duì)角(aii,0in-1上，緊鄰主對(duì)角線上面的那條對(duì)角線上(aii+1,0in-2)和緊鄰主對(duì)角線下面的那條對(duì)角線上(ai+1 i,0in-2)。顯然，當(dāng)i-j1時(shí)，元素aij=0。 由此可知，一個(gè)k對(duì)角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若i-j(k-1)/2 ，則元素 aij=0。 對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。,在三對(duì)角矩陣?yán)锔綕M足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1i

14、n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺?lái)存儲(chǔ)。除第0行和第n-1行是2個(gè)元素外，每行的非零元素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。,K=0 1 2 3 4 5 3n-2 3n-1 數(shù)組sa中的元素sak與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，有j-i+1個(gè)非零元素，這樣，非零元素aij的地址為：,LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34對(duì)應(yīng)著sa10。 k=2*i+j=2*3+4=1

15、0 a21對(duì)應(yīng)著sa5 k=2*2+1=5 由此，我們稱sa0.3*n-2是階三對(duì)角帶狀矩陣A的壓縮存儲(chǔ)表示。,上述的各種特殊矩陣非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。 什么是稀疏矩陣？簡(jiǎn)單說(shuō)，設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即smn），則稱A為稀疏矩陣。,4.3 稀疏矩陣,例如，下列三元組表 (1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7) 加上(6

16、,7)這一對(duì)行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 稀疏矩陣M和T,M=,T=,假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法三元順序表。 #defin

17、e maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple;,一、三元組順序表 轉(zhuǎn)置,typedef struct triple datamaxsize; int m,n,t; tripletable; 設(shè)A為tripletable型的結(jié)構(gòu)變量，圖5.4中所示的稀疏矩陣的三元組的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,以矩陣的轉(zhuǎn)置為例，說(shuō)明在這種壓縮存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)矩陣的運(yùn)算。 一個(gè)mn的矩陣A，它

18、的轉(zhuǎn)置B是一個(gè)nm的矩陣，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡(jiǎn)單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B，要得到按行優(yōu)先順序存儲(chǔ)的b.data，就必須重新排列三元組的順序。 由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。,按這種方法設(shè)計(jì)的算法，其基本思想是：對(duì)A中的每一列 col(0coln-1)，通過(guò)從頭至尾掃描三元表a.data，找出所有列號(hào)等于col

19、的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放入b.data中，即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14,Void transmatrix(tripletable a,tripletable b) int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0;,for(col=1;col=a.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.

20、datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; ,分析這個(gè)算法，主要的工作是在p和col的兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(n*t)，即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為： for(col=0;col=n-1;+col) for(row=0;row=m;+row) tcolrow=mrowcol; 其時(shí)間復(fù)雜度為O(n*m)。當(dāng)非零元素的個(gè)數(shù)t和m*n同數(shù)量級(jí)時(shí)，算法transmatrix的時(shí)間復(fù)雜度為O(n*n2)。,三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同

21、時(shí)還有可能增加算是法的難度。因此，此算法僅適用于t=m*n的情況。 下面給出一種快速轉(zhuǎn)置的算法，其算法思想為：對(duì)A掃描一次，按A第二列提供的列號(hào)一次確定位置裝入B的一個(gè)三元組。具體實(shí)施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？梢?jiàn)，位置關(guān)系是此種算法的關(guān)鍵。,為了預(yù)先確定矩陣M中的每一列的第一個(gè)非零元素在數(shù)組B中應(yīng)有的位置，需要先求得矩陣M中的每一列中非零元素的個(gè)數(shù)。因?yàn)椋壕仃嘙中第一列的第一個(gè)非零元素在數(shù)組B中應(yīng)有的位置等于前一列第一個(gè)非零元素的位置加上前列非零元素的個(gè)數(shù)。 為此，需要設(shè)置兩個(gè)一維數(shù)組num0.n和cpot0.n num0.n：統(tǒng)計(jì)M中每列非零元素的

22、個(gè)數(shù)，numcol的值可以由A的第二列求得。,cpot0.n：由遞推關(guān)系得出M中的每列第一個(gè)非零元素在B中的位置。 算法通過(guò)cpot數(shù)組建立位置對(duì)應(yīng)關(guān)系： cpot1=1 cpoti=cpoti-1+numi-1 2=i=a.n 例如：圖中的矩陣M和相應(yīng)的三元組A可以求得numi和 cpoti的值如下： i 1 2 3 4 5 6 7 numi 2 2 2 1 0 1 0 cpoti 1 3 5 7 8 8 9,A i j v,第一列元素個(gè)數(shù) 第二列元素個(gè)數(shù) 第三列元素個(gè)數(shù),num,cpot,q=cpoti,p,q,快速轉(zhuǎn)置算法如下： void fasttranstri(tritupletab

23、le b,tritupletable a) int p,q,l,k; int numa.n,copta.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(l=1;l=a.n;+l) numl=0; for(k=1;k=a.t;+k) +numa.datak.j;,cpot0=1; for(l=2; l=a.t;+l) cpotl=cpotl-1+numl-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotl; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i;

24、 b.dataq.v=a.datap.v;+cpotl; ,有時(shí)為了方便某些矩陣運(yùn)算，我們?cè)诎葱袃?yōu)先存儲(chǔ)的三元組中，加入一個(gè)行表來(lái)記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個(gè)新增屬性加以描述時(shí)，我們就得到了稀疏矩陣的另一種順序存儲(chǔ)結(jié)構(gòu)：帶行表的三元組表。其類型描述如下：,二、帶行表的三元組 乘法,#define maxrow 100 typedef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable; 下面討論兩個(gè)稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性。,兩個(gè)矩陣相乘的

25、經(jīng)典算法也是大家所熟悉的。設(shè) Q=M*N 其中，M是m1*n1矩陣，N是m2*n2矩陣。 當(dāng)n1=m2時(shí)有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0; for(k=1;k=n1;+k) qij+=mik*nkj; 此算法的復(fù)雜度為O(m1*n1*n2)。,當(dāng)M和N是稀疏矩陣并用三元組表存儲(chǔ)結(jié)構(gòu)時(shí)，就不能套用上述算法。假設(shè)M和N分別為：,0 0 5 0 -1 0 0 2 0 0 0,M=,0 2 1 0 -2 4 0 0,N=,則Q=M*N為：,0 6 -1 0 0 4,Q=,它們的三元組分別為： i j v i j v i j v 1 1 3 1 2 2

26、 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data,稀疏矩陣相乘的基本思想是：對(duì)于M中每個(gè)元素M，找到N 中所有滿足條件的元素，求得和的乘積，而從式得知，乘積矩陣Q中每個(gè)元素的值是個(gè)累加和，這個(gè)乘積只是中的一部分。為了便于操作，應(yīng)對(duì)每個(gè)元素設(shè)一累加和的變量，其初值為零，然后掃描數(shù)組M，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)那罄塾?jì)和的變量上。,void multsmatrix(rtripletable a, rtripletable b, rtripletable c) if(a.n!=b.m)

27、/不能相乘 printf(“errorn”); exit(0); c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0) for(arow=1;arow=a.m;+arow) ctemparow=0;,c.rposarow=c.t+1; for(p=a.ropsarow;pa.rposarow+1;+p) brow=a.datap.j; if(browb.t) t=b.rposbrow+1 else t=b.t+1; for(q=b.rposbrow; qt;+q) ccol=n.dataq.j; ctempccol+=a.datap.v*b.dataq.v; ,for

28、(ccol=1;ccolmaxsize) exit(0); c.datac.t=arow,ccol,ctempccol; ,M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩陣維數(shù)（6,7）唯一確定,稀疏矩陣 定義：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣 壓縮存儲(chǔ)原則：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值,稀疏矩陣(其他講解方式),稀疏矩陣的壓縮存儲(chǔ)方法 順序存儲(chǔ)結(jié)構(gòu) 三元組表,#define M 20 typedef struct node int i,j; int

29、v; JD; JD maM;,三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1) 其中t為非零元個(gè)數(shù),6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,ma0.i,ma0.j,ma0.v分別存放 矩陣行列維數(shù)和非零元個(gè)數(shù),帶輔助行向量的二元組表,增加一個(gè)輔助數(shù)組NRAm+1,其物理意義是第i行第一個(gè)非零元 在二元組表中的起始地址（m為行數(shù)） 顯然有：,6,POS0不用或 存矩陣行數(shù),二元組表需存儲(chǔ)單元個(gè)數(shù)為2(t+1)+m+1,偽地址表示法,偽地址：本元素在矩陣中（包括零元素） 按行優(yōu)先順序的相對(duì)位置,偽地址表示法需存儲(chǔ)單元個(gè)數(shù) 為2

30、(t+1),求轉(zhuǎn)置矩陣 問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表 問(wèn)題分析 一般矩陣轉(zhuǎn)置算法：,for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol; T(n)=O(mn),解決思路：只要做到 將矩陣行、列維數(shù)互換 將每個(gè)三元組中的i和j相互調(diào)換 重排三元組次序，使mb中元素以N的行(M的列)為主序,方法一：按M的列序轉(zhuǎn)置 即按mb中三元組次序依次在ma中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。 為找到M中每一列所有非零元素，需對(duì)其三元組表ma從第一行 起掃描一遍。由于ma中以M行序?yàn)橹餍?所以由此得到的恰是mb 中應(yīng)有的順序,算法描述：,算法分析：T(