數(shù)據(jù)結(jié)構(gòu)第05章 數(shù)組和廣義表

1、§5.1 數(shù)組的定義,5.1.1 數(shù)組的抽象數(shù)據(jù)類型定義,見 P90,在C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說， typedef elemtype array2[m][n]; 等價(jià)于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一個n

2、維數(shù)組類型可以定義為其數(shù)據(jù)元素為n-1維數(shù)組類型的一維數(shù)組類型。,數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。,§5.2 數(shù)組的順序表示和實(shí)現(xiàn),由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。 又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個

3、數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。,兩種常見的順序存儲方式：,行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。 以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,… a2n, …,am1,am2,…,amn 列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按列

4、優(yōu)先順序存儲的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,a1n,a2n,…,amn,多維→一維,按上述兩種方式順序存儲的序組，只要知道開始結(jié)點(diǎn)的存放地址（即基地址），維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲的數(shù)組是一個隨機(jī)存取結(jié)構(gòu)。,因?yàn)閍ij位于第i行、第j列，前面i-1行一共有(i-

5、1)×n個元素，第i行上aij前面又有j-1個元素，故它前面一共有(i-1)×n+j-1個元素，因此，aij的地址計(jì)算函數(shù)為： LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*L,例如，二維數(shù)組Amn按“行優(yōu)先順序”存儲在內(nèi)存中，假設(shè)每個元素占用L個存儲單元。 元素aij的存儲地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。,上述討論均是假設(shè)數(shù)組各維的下界是1，更一般的二維數(shù)組

6、是A[c1..d1,c2..d2]，這里c1,c2不一定是1。aij前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-c1行共有(i-c1)*(d2-c2+1)個元素，第i行上aij前一共有j-c2個元素。,因此，aij的地址計(jì)算函數(shù)為： LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d 例如，在C語言中，數(shù)組各維下標(biāo)的下界是0，因此在C語言中，二維數(shù)組的地址計(jì)算公式為：

7、 LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,一般用m*n表示一個具有m行n列的矩陣，在這種矩陣中擁有m*n個元素；在高級語言中，用二維數(shù)組來表示矩陣。,然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中有許多值相同的元素或者是零元素。有時(shí)為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。,§5.3 矩陣的壓縮存儲,所謂壓縮存儲是指：為多個值相同的元素只分配一個存儲空間；對零元素不分配空間。,假若值相

8、同的元素或者零元素在矩陣中的分布有一定規(guī)律，則我們稱此類矩陣為特殊矩陣，反之，稱為稀疏矩陣。,對稱矩陣、三角矩陣、三對角矩陣都屬于特殊矩陣。這些矩陣的共同特點(diǎn)：非零元素的分布有明顯的規(guī)律。 因此可將非零元素壓縮到一維數(shù)組中，并找到每個非零元素在一維數(shù)組中的對應(yīng)關(guān)系。,5.3.1 特殊矩陣的壓縮存貯,對稱矩陣,對于矩陣 A=(aij)n,n ，若有aij=aji(i,j≤n)，則稱該矩陣為對稱矩陣。,矩陣中的元素關(guān)于主對角線對稱，故

9、只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，就可將n2個元素存儲到n(n+1)/2個空間中。,我們按“行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，則其存儲形式如下圖所示：,可以將這些元素存放在向量sa[0..n(n+1)/2-1] 中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個對應(yīng)關(guān)系。,若i≥j，則aij在下三角形中。aij之前的i-1行（從第1行到第i-1行）共有1+2

10、+…+(i-1)=i(i-1)/2個元素，在第i行上，aij之前恰有j-1個元素（即ai1, ai2, ai3,…,aij-1），因此有： k=i*(i-1)/2+j-1 0≤k<n(n+1)/2 若i<j，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對應(yīng)關(guān)系式中的i和j即可得到： k=j*(j-1)/2+i-1 0≤k

11、<n(n+1)/2 可統(tǒng)一為：,因此，aij的地址可用下列式計(jì)算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*d=LOC(sa[0])+[i*(i-1)/2+j-1]*L,對于任意給定一組下標(biāo)(i,j)，均可在sa[k]中找到矩陣元素aij，反之，對所有的k=0,1, 2,…n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i,j)。由此，稱sa[n(n+1)/2]為n階對

12、稱矩陣A的壓縮存儲。,三角矩陣,以主對角線劃分，三角矩陣有上三角矩陣和下三角矩陣兩種。 上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)（一般常數(shù)為零）,三角矩陣中的重復(fù)元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中。,上三角矩陣中，主對角線之上的第p行(1

13、≤p≤n)恰有n-p+1個元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時(shí)，aij之前的i-1行一共有:(2n-i+2)(i-1)/2個元素，在第i行上，aij前恰好有j-i個元素：aii,aii+1,…aij-1。因此，sa[k]和aij的對應(yīng)關(guān)系是：,下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應(yīng)關(guān)系是：,對角矩陣,對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角

14、線上的元素之外，其余元素皆為零。,三對角矩陣：非零元素僅出現(xiàn)在主對角線上(aii ,0≤i≤n-1)，和緊鄰主對角線上、下方的對角線上(ai i+1和ai+1 i, 0≤i≤n-2)。顯然，當(dāng)|i-j|>1時(shí)，元素aij=0。 由此可知，一個k對角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2 ，則元素 aij=0。 對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找

15、到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。,對這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺泶鎯?。除?行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(shù)為3n-2。,K=0 1 2 3 4 5 … … 3n-2 3n-1,數(shù)組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+

16、1個非零元素，這樣，非零元素aij的地址為：,LOC(i,j)= LOC(0,0)+[3*i-1+(j-i+1)]*d = LOC(0,0)+(2i+j)*d,上例中，a34的對應(yīng)地址為k=2*i+j=2*3+4=10，即sa[10]；a21的對應(yīng)地址為k=2*2+1=5，即sa[5] 由此，我們稱sa[0..3*n-2]是n階三對角帶狀矩陣A的壓縮存儲表示。,5.3.2 稀疏矩陣的存貯,稀疏矩陣的定義

17、,在矩陣A(m*n)中，有s個非零元素。令e=s/(m*n),稱e為矩陣的稀疏因子。 當(dāng)e≤0.05時(shí)，則稱該矩陣為稀疏矩陣。,稀疏矩陣的抽象數(shù)據(jù)類型 見P96-97,稀疏矩陣的壓縮存儲,稀疏矩陣中的非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。 一個三元組(i,j,aij)唯一確定了稀疏矩陣的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確

18、定。,,三元組表((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,7)這一對行、列值，便可作為稀疏矩陣M的另一種描述。,三元組順序表,假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元順序表。,//三元組順序表存儲表示#define MAXSIZE 12500 // 假設(shè)非零元個數(shù)的

19、最大值為12500typedef struct { int i, j; // 該非零元的行下標(biāo)和列下標(biāo) ElemType e; } Triple; // 三元組類型typedef union { Triple data[MAXSIZE + 1]; // 非零元三元組表，data[0]未用 int m

20、u, nu, tu; // 矩陣的行數(shù)、列數(shù)和非零元個數(shù) } TSMatrix; // 稀疏矩陣類型,三元組表所需存儲單元個數(shù)為3(t+1)其中t為非零元個數(shù),6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2

21、 18,6 1 15,6 4 -7,M.mu,M.nu,M.tu分別存放矩陣行列維數(shù)和非零元個數(shù),用三元組來表示矩陣M：,用三元組來表示矩陣M：,下面以矩陣的轉(zhuǎn)置為例，說明在這種壓縮存儲結(jié)構(gòu)上如何實(shí)現(xiàn)矩陣的運(yùn)算。,一個m×n的矩陣A，它的轉(zhuǎn)置B是一個n×m的矩陣，且a[i][j]=b[j][i]，0≤i≤m，0≤j≤n，即A的行是B的列，A的列是B的行。,將矩陣A轉(zhuǎn)置為

22、矩陣B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個按列優(yōu)先順序存儲的稀疏矩陣B，要得到按行優(yōu)先順序存儲的b.data，就必須重新排列三元組的順序。 由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。,轉(zhuǎn)置方法1,按以上這種方法設(shè)計(jì)的算法，其基本思想是：對A中的每一列 c

23、ol(0≦col≦n-1)，通過從頭至尾掃描三元表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優(yōu)先的壓縮存儲表示。 具體算法如下。,,,,,,,,,,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3

24、 4 24,4 6 -7,6 3 14,col=1,col=2,Status TransposeSMatrix(TSMatrix M,TSMatrix &T){ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) { q=1; for(col=1; col<=M.nu; ++col) fo

25、r(p=1; 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; } } return OK; } //TransposeSMatri

26、x,這個算法主要的工作是在p和col的兩個循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nu*tu)，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。 而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為： for(col=0;col<=n-1;++col) for(row=0;row<=m;++row) t[col][row]=m[row][col]; 其時(shí)間復(fù)雜度為O(n*m) 當(dāng)非零元素的個

27、數(shù)tu和mu*nn同數(shù)量級時(shí)，算法transmatrix的時(shí)間復(fù)雜度為O(mu*nu2)。,算法復(fù)雜度分析,轉(zhuǎn)置方法2 ——快速轉(zhuǎn)置算法,算法思想： 對矩陣A掃描一次，按A第二列提供的列號一次確定位置裝入矩陣B的一個三元組。具體做法： 第一次掃描先確定三元組的位置關(guān)系，第二次掃描由位置關(guān)系裝入三元組?？梢?，位置關(guān)系是此種算法的關(guān)鍵。,算法思想是：以M矩陣的三元組為中心, 依次取出 M.data 中的每一個三元組，交換行

28、列后，直接將其寫入T.data合適的位置中。,i j e,0 1 2 3 4 5 6 7 8,M.data,i j e,0 1 2 3 4 5 6 7 8,T.data,7 6 8,2 1 12,如果能先求得M各列第一個非零元三元組在T.data 中的位置就能在對M.data一次掃描的過程中，完成M到T的轉(zhuǎn)置

29、,,,為了預(yù)先確定矩陣M中的每一列的第一個非零元素在b.data中應(yīng)有的位置，需要先求得矩陣M中的每一列中非零元素的個數(shù)。,因?yàn)榫仃嘙中每一列的第一個非零元素在b.data中應(yīng)有的位置等于前一列第一個非零元素的位置加上前列非零元素的個數(shù)。 因此需要設(shè)置一維數(shù)組num[0..n]和cpot[0..n]。num[0..n]：用于統(tǒng)計(jì)M中每列非零元素的個數(shù)num[col]表示M中第col列中非零元素的個數(shù)。cpot[0..n]：由

30、遞推關(guān)系得出M中的每列第一個非零元素在B中的位置。,實(shí)現(xiàn)：引入兩輔助數(shù)組num[col]：存儲矩陣M中第col列中非零元個數(shù)cpot[col]：存儲M中第col列第一個非零元在T.data中位置顯然有：,1,3,5,7,8,8,9,,快速轉(zhuǎn)置算法主要步驟：1、 求 M 中各列非零元個數(shù)num[ col];2、 求 M中各列第一個非零元在T.data 中的位置 cpot[col ];3、 對 M.data 進(jìn)行一次掃描， 遇

31、到 col 列的第一個非零元三元組時(shí)，按cpot[col ]的位置，將其放至 T.data 中，當(dāng)再次遇到各列后續(xù)的非零元三元組時(shí)，只需順序放到對應(yīng)列元素的后面；,,,,,,,,,,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6

32、 -7,6 3 14,4,6,2,9,7,5,3,各列第一個非零元三元組按先前求出的位置放到T.data中,各列后續(xù)的非零元三元組，順序放到對應(yīng)列元素的后面,Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元組順序表存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T T.mu = M.nu; T.nu = M.mu;

33、 T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; //{col =M.data[ t ] .j ; ++num [col] ;} // 求 M 中每一列所含

34、非零元的個數(shù) cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; // 求 M 中每一列的第一個非零元在 b.data 中的序號,// 轉(zhuǎn)置矩陣元素 for (p=1; p<=M.tu; ++p) {

35、 col = M.data[p].j; q = cpot[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; ++cpot[col];

36、 } // for } // if return OK;} // FastTransposeSMatrix00,算法復(fù)雜度分析,這個算法比普通轉(zhuǎn)置算法多用了兩個輔助向量。從時(shí)間上看，算法中有四個并列的單循環(huán)，循環(huán)次數(shù)分別為nu和tu，因而總的時(shí)間復(fù)雜度為O(mu +nu)。 在M的非零元個數(shù)tu和mu*nu等數(shù)量級時(shí)，其時(shí)間復(fù)雜度為O(mu * nu)。,三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零

37、元在表中按行序有序存儲，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需按行號存取某一行的非零元，則需從頭開始進(jìn)行查找。,十字鏈表,當(dāng)矩陣的非零元個數(shù)和位置在操作過程中變化較大時(shí)，就不宜采用順序存儲結(jié)構(gòu)來表示三元組的線性表。 例如，在作“將矩陣B加到矩陣A上”的操作時(shí)，由于非零元的插入或刪除將會引起A.data中元素的移動。為此，對這種類型的矩陣，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示三元組的線性表更為恰當(dāng)。,在十字鏈表中，稀疏矩陣的每一行用一個帶有

38、表頭結(jié)點(diǎn)的循環(huán)表表示，每一列也用一個帶表頭結(jié)點(diǎn)的循環(huán)表表示。在鏈表中除表頭結(jié)點(diǎn)外，每個結(jié)點(diǎn)都表示矩陣中的一個非零元素。,十字鏈表的結(jié)點(diǎn)由5個域組成：行域row、列域col、值域val、向下域down、向右域right。,row 用于存儲非零元素的行號；,col 用于存儲非零元素的列號；,val 用于存儲非零元素的元素值；,down 用來存儲指向同一列下一個結(jié)點(diǎn)的指針；,right 用來存儲指向同一行下一個結(jié)點(diǎn)的指針；,注：若不存在下

39、一個結(jié)點(diǎn)，則相應(yīng)的指針域?yàn)榭罩怠?,,^,^,^,^,^,^,^,,,,M.chead,M.rhead,//稀疏矩陣的十字鏈表存儲表示//結(jié)點(diǎn)類型定義typedef struct OLNode{ int i,j; //元素行、列號 ElemType e; //元素值 struct OLNode *right,*down; //非零元所在的行表和列表的后繼 }OLNode, *OLin

40、k;//鏈表類型定義typedef struct{ OLink *rhead,*chead; //行、列的鏈表頭指針基址 int mu,nu,tu; //矩陣總行數(shù),列數(shù),中非零元素總個數(shù) }CrossList,******從鍵盤接收信息建立十字鏈表算法,******算法分析：此算法對非零元輸入的先后次序沒任何要求 T(n)=o(t?s) 其中：t——非零元

41、個數(shù) s= max(m,n),,Ch4_3.c,,1、初始化頭指針向量2、初始化各行列鏈表3、動態(tài)生成結(jié)點(diǎn)，輸入非零元4、將結(jié)點(diǎn)插入行5、將結(jié)點(diǎn)插入列,,,******m=4,n=31,1,32,2,52,3,44,1,82,1,7,,,,,Ch4_3.c,****** Status CreateSMatrix_OL(CrossList &M) {//創(chuàng)

42、建稀疏矩陣M。采用十字鏈表存儲表示 if (M) free(M); scanf(&m,&n,&t); //輸入M的行數(shù)、列數(shù)和非零元個數(shù) M.mu=m; M.nu=n; M.tu=t; if (!(M.rhead=(Olink *) malloc ((m+1)*sizeof(Olink)))) exit (overflow); if (!(M.chead=(Olink *)

43、 malloc ((n+1)*sizeof(Olink)))) exit (overflow); M.rhead[ ]=M.chead[ ]=NULL;//初始化行列頭指針向量； //各行列鏈表為空鏈表 for (scanf(&i,&j,&e); i!=0;scanf(&i,&

44、;j,&e)) {//按任意次序輸入非零元 if (!(p=(OLNode *) malloc (sizeof(OLNode)))) exit (overflow); p->i=i; p->j=j; p->e=e; //生成結(jié)點(diǎn),****** If (M.rhead[i]==NULL || M.rhead[i]->j>j) {p->righ

45、t=M.rhead[i];M.rhead[i]=p;}Else{ //尋查在行表中的插入位置 for (q=M.rhead[i]; (q->right)&&q->right->jright); p->right=q->right; q->right=p; } //完成行插入If (M.chead[j]==NULL || M.chead[j]->

46、;i>i) {p->down=M.chead[j];M.chead[j]=p;}Else{ //尋查在列表中的插入位置 for (q=M.chead[j]; (q->down)&&q->down->idown); p->down=q->down; q->down=p; } //完成列插入Return OK;}//Crea

47、teSMatrix_OL,******算法：將矩陣B加到矩陣A上,假設(shè)兩個矩陣相加后的結(jié)果為A’，則A’的非零元aij’只可能有三種情況：,aij’= aij+ bij aij’= aij (bij=0 時(shí)） aij’= bij (aij=0 時(shí)）,(1) 若pa==NULL或pa->j 〉pb->j，則需要在A矩陣的鏈表中插入一個值為bi,j的結(jié)點(diǎn)。此時(shí)，需改變同一行中前一結(jié)點(diǎn)的right域值，以及同一列中前一結(jié)點(diǎn)的

48、down域值。(2) 若pa->j〈 pb->j，則只要將pa指針往右推進(jìn)一步。,******假設(shè)非空指針 pa和 pb分別指向矩陣A和B中行值相同的兩個結(jié)點(diǎn)，pa == NULL 表明矩陣A在該行中沒有非零元，則上述四種情況的處理過程為：,******(3) 若pa->j == pb->j且pa->e＋pb->e !=0，則只要將ai,j＋bi,j 的值送到pa所指結(jié)點(diǎn)的e域即可，其它所有域的值都

49、不變。(4) 若pa->j == pb->j且pa->e＋pb->e == 0，則需要在A矩陣的鏈表中刪除pa所指的結(jié)點(diǎn)。此時(shí)，需改變同一行中前一結(jié)點(diǎn)的right域值，以及同一列中前一結(jié)點(diǎn)的down域值。,******為了便于插入和刪除結(jié)點(diǎn)，還需要設(shè)立一些輔助指針。其一是，在A的行鏈表上設(shè)pre指針，指示pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；其二是，在A的每一列的鏈表上設(shè)一個指針hl[j]，它的初值和列鏈表的頭指針相同，即h

50、l[j]＝chead[j]。,初始，令pa和pb分別指向A和B的第一行的第一個非零元素的結(jié)點(diǎn)，即 pa＝A.rhead[1]; pb＝B.rhead[1]; pre = NULL; 且令hl初始化 for (j=1; jj〉pb->j（即A的這一行中非零元素已處理完），則需在A中插入一個pb所指結(jié)點(diǎn)的復(fù)制結(jié)點(diǎn)。假設(shè)新結(jié)點(diǎn)的地址為p，則A的行表中的指針作如下變化：if (pre == NUL

51、L) rhead[p->i]=p;else { pre->right＝p; }p->right＝pa; pre = p;,******,A的列鏈表中的指針也要作相應(yīng)的改變。首先需從hl[p->j]開始找到新結(jié)點(diǎn)在同一列中的前驅(qū)結(jié)點(diǎn)，并讓hl[p->j]指向它，然后在列鏈表中插入新結(jié)點(diǎn)：if chead[p->j] == NULL { chead[p->j] = p;

52、 p->down = NULL; }else { p->down＝hl[p->j]->down; hl[p->j]->down＝p; }hl[p->j] = p;,******,② 若pa->j〈pb->j且pa->j!=0，則令pa指向本行下一個非零元結(jié)點(diǎn)，即 pre＝pa; pa＝pa->right;③ 若pa->j == pb->j，則將B中當(dāng)前

53、結(jié)點(diǎn)的值加到A中當(dāng)前結(jié)點(diǎn)上，即 pa->e＋＝pb->e;此時(shí)若pa->e!=0，則指針不變，否則刪除A中該結(jié)點(diǎn)，即行表中指針變?yōu)?if pre == NULL rhead[pa->i] = pa->right; else { pre->right＝pa->right; } p=pa; pa=pa->right; 同時(shí)，為了改變列表中的指針，需要先找到同一

54、列中的前驅(qū)結(jié)點(diǎn)，且讓hl[pa->j]指 向該結(jié)點(diǎn)，然后如下修改相應(yīng)指針：if chead[p->j] == pchead[p->j] = hl[p->j] = p->down; else { hl[p->j]->down＝p->down; }free (p);,******,(3) 若本行不是最后一行，則令pa和pb指向下一行的第一個非零元結(jié)點(diǎn)，轉(zhuǎn)(2)；否則結(jié)束。,****

55、**,,小 結(jié) 1 矩陣壓縮存儲是指為多個值相同的元素分配一個存儲空間，對零元素不分配存儲空間； 2 特殊矩陣的壓縮存儲是根據(jù)元素的分布規(guī)律，確定元素的存儲位置與元素在矩陣中的位置的對應(yīng)關(guān)系； 3 稀疏矩陣的壓縮存儲除了要保存非零元素的值外，還要保存非零元素在矩陣中的位置；,,5．3 矩陣的壓縮存儲,行邏輯鏈接的順序表 有時(shí)為了方便某些矩陣運(yùn)算，我們在按行優(yōu)先存儲的三元組中，加入一個行表來記錄

56、稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個新增屬性加以描述時(shí)，我們就得到了稀疏矩陣的另一種順序存儲結(jié)構(gòu)：“帶行鏈接信息”的三元組表。 其類型描述如下：,******,#define maxsize 100 typedef struct{ triple data[maxsize+1];//非零元三元組表 int rpos[maxrc+1]; //各行第一個非零元的位置表

57、 int n,m,t; //矩陣的行數(shù)、列數(shù)和非零元個數(shù) }TSMatrix; 下面討論兩個稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性。,******,兩個矩陣相乘的經(jīng)典算法也是大家所熟悉的。 若設(shè) Q=M*N 其中，M是m1*n1矩陣，N是m2*n2矩陣。 常規(guī)的二維數(shù)組表示時(shí)轉(zhuǎn)置的算法： 當(dāng)n1=m2時(shí), 有： for(i

58、=1;i<=m1;++i) for(j=1;j<=n2;++j){ q[i][j]=0 for(k=1;k<=n1;++k) q[i][j]+=m[i][k]*n[k][j]; } 此算法的復(fù)雜度為O(m1*n1*n2)。,兩個稀疏矩陣相乘,******,行邏輯鏈接的順序表如何從M和N求得Q呢？

59、,1、求乘積矩陣Q中元素 由矩陣乘法規(guī)則知： Q（i，j）=M(i,1)×N(1,j)+M(i,2)×N(2,j)+…+M(i,n)×N(n,j) 這就是說，為求Q的值，只有M(i,k)與N(k,j)（即M元素的列與N元素的行相等的兩項(xiàng)）才有相乘的機(jī)會，且當(dāng)兩項(xiàng)都不為零時(shí)，乘積中的這一項(xiàng)才不為零。 即只找到M.data中的j值和N.data中的i值相等的各對元素相乘即可。,**

60、****,2、相乘的基本操作是：對于M中每個元素M.data[p]，找到N中所有滿足條件M.data[p].j=N.data[q].i的 元素N.data[q]，求得M.data[p].e和M.data[q].e的乘積。,即M11只有可能和N中第1行的非零元素相乘，M12只有可能和N中第2行的非零元素相乘，…，而同一行的非零元是相鄰存放的，所以求Q11和Q12同時(shí)進(jìn)行，當(dāng)然只有Mik和Nkj(列號與行號相等)且均不為零（三元組存在）時(shí)才

61、相乘，并且累加到Qij當(dāng)中去。,******,,為了便于N.data中尋找N中的第row行第一個非零元素，與前面類似，在此需引入num和rpos兩個向量。num[row]表示矩陣N中第row行的非零元素的個數(shù)；rpos[row]表示第row行的第一個非零元素在N.data中的位置。于是有 rpos[1]=1 rpos[row]=rpos[row-1]+num[row-1] 2≤row≤n,例如 ，對

62、于矩陣N的num和rpos如圖所示。 row 1 2 3 4   num[row] 1 1 2 0 rpos[row] 1 2 3 5 圖5.17 矩陣N的num與rpos值,,,******,兩個稀疏矩陣相乘（Q= M* N）的過程可大致描

63、述如下： Q初始化; if (Q是非零矩陣) { // 逐行求積 for (arow=1; arow<=M.mu; ++arow) { // 處理M的每一行 ctemp[] = 0; // 累加器清零 計(jì)算Q中第arow行的積并存入ctemp[] 中； 將ctemp[] 中非零元壓縮存儲到Q.data；

64、 } // for arow } // if,3、根據(jù)以上分析，稀疏矩陣的乘法運(yùn)算的粗略步驟如下：⑴初始化。清理一些單元，準(zhǔn)備按行順序存放乘積矩陣;⑵求N的num，rpos;⑶做矩陣乘法。將M.data中三元組的列值與N.data中三元組的行值相等的非零元素相乘，并將具有相同下標(biāo)的乘積元素相加。,******,當(dāng)M和N是稀疏矩陣并用三元組表存儲結(jié)構(gòu)時(shí)，假設(shè)M和N分別為：,0 0 50 -1 0 02 0

65、 0 0,M=,,,0 2 1 0-2 4 0 0,N=,,,則Q=M*N為：,0 6-1 0 0 4,Q=,,,算法描述：,算法分析：T(n)=O(m?p),******,它們的三元組、積分別為： i j e i j e i j e 1 1 3 1 2 2

66、 1 2 6 1 4 5 2 1 1 2 1 -1 2 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 m.data n.data q.data,,,,,,,,,

67、,******,Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) {//求矩陣乘積Q=M* N，采用行邏輯鏈接存儲。設(shè)M.nu=N.mu if (M.nu != N.mu) return ERROR; if (M.tu*N.tu != 0) { // Q是非零矩陣 {Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0

68、; p=1// Q初始化 do { crow=M.data[p].i; //crow指示當(dāng)前處理的行號 ctemp[] = 0; // 當(dāng)前行各元素累加器清零 while (p<=M.tu && M.data[p].i==crow) { brow=M.data[p].j;

69、 //找到對應(yīng)元在N中的行號 for (q=N.rpos[brow]; q<rpos[brow+1]; ++q) {ccol = N.data[q].j; // 乘積元素在Q中列號 ctemp[ccol] += M.data[p].e * N.data[q].e; } // for q ++p

70、; }//求得Q中第crow行的非零元,******,for (ccol=1; ccol<=Q.nu; ++ccol) // 壓縮存儲該行非零元 if (ctemp[ccol]) { ++Q.tu; Q.data[Q.tu] = (crow, ccol, ctemp[ccol]); } // if } // do while