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

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

2、維數(shù)組類(lèi)型可以定義為其數(shù)據(jù)元素為n-1維數(shù)組類(lèi)型的一維數(shù)組類(lèi)型。,數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，數(shù)組只有存取元素和修改元素值的操作。,§5.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è)

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

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

5、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]*L,例如，二維數(shù)組Amn按“行優(yōu)先順序”存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用L個(gè)存儲(chǔ)單元。 元素aij的存儲(chǔ)地址應(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)個(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,一般用m*n表示一個(gè)具有m行n列的矩陣，在這種矩陣中擁有m*n個(gè)元素；在高級(jí)語(yǔ)言中，用二維數(shù)組來(lái)表示矩陣。,然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中有許多值相同的元素或者是零元素。有時(shí)為了節(jié)省存儲(chǔ)空間，可以對(duì)這類(lèi)矩陣進(jìn)行壓縮存儲(chǔ)。,§5.3 矩陣的壓縮存儲(chǔ),所謂壓縮存儲(chǔ)是指：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。,假若值相

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

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

10、+…+(i-1)=i(i-1)/2個(gè)元素，在第i行上，aij之前恰有j-1個(gè)元素（即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，所以只要交換上述對(duì)應(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,對(duì)于任意給定一組下標(biāo)(i,j)，均可在sa[k]中找到矩陣元素aij，反之，對(duì)所有的k=0,1, 2,…n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i,j)。由此，稱(chēng)sa[n(n+1)/2]為n階對(duì)

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

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

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

15、到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。,對(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中的元素sa[k]與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，有j-i+

16、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)地址為k=2*i+j=2*3+4=10，即sa[10]；a21的對(duì)應(yīng)地址為k=2*2+1=5，即sa[5] 由此，我們稱(chēng)sa[0..3*n-2]是n階三對(duì)角帶狀矩陣A的壓縮存儲(chǔ)表示。,5.3.2 稀疏矩陣的存貯,稀疏矩陣的定義

17、,在矩陣A(m*n)中，有s個(gè)非零元素。令e=s/(m*n),稱(chēng)e為矩陣的稀疏因子。 當(dāng)e≤0.05時(shí)，則稱(chēng)該矩陣為稀疏矩陣。,稀疏矩陣的抽象數(shù)據(jù)類(lèi)型 見(jiàn)P96-97,稀疏矩陣的壓縮存儲(chǔ),稀疏矩陣中的非零元素的分布一般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。 一個(gè)三元組(i,j,aij)唯一確定了稀疏矩陣的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(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)這一對(duì)行、列值，便可作為稀疏矩陣M的另一種描述。,三元組順序表,假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法——三元順序表。,//三元組順序表存儲(chǔ)表示#define MAXSIZE 12500 // 假設(shè)非零元個(gè)數(shù)的

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

20、u, nu, tu; // 矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) } TSMatrix; // 稀疏矩陣類(lèi)型,三元組表所需存儲(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

21、 18,6 1 15,6 4 -7,M.mu,M.nu,M.tu分別存放矩陣行列維數(shù)和非零元個(gè)數(shù),用三元組來(lái)表示矩陣M：,用三元組來(lái)表示矩陣M：,下面以矩陣的轉(zhuǎn)置為例，說(shuō)明在這種壓縮存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)矩陣的運(yùn)算。,一個(gè)m×n的矩陣A，它的轉(zhuǎn)置B是一個(gè)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，如果只是簡(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)先存放的。,轉(zhuǎn)置方法1,按以上這種方法設(shè)計(jì)的算法，其基本思想是：對(duì)A中的每一列 c

23、ol(0≦col≦n-1)，通過(guò)從頭至尾掃描三元表a.data，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放入b.data中，即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。 具體算法如下。,,,,,,,,,,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,這個(gè)算法主要的工作是在p和col的兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nu*tu)，即矩陣的列數(shù)和非零元的個(gè)數(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)非零元素的個(gè)

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

28、列后，直接將其寫(xiě)入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各列第一個(gè)非零元三元組在T.data 中的位置就能在對(duì)M.data一次掃描的過(guò)程中，完成M到T的轉(zhuǎn)置

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

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

31、到 col 列的第一個(gè)非零元三元組時(shí)，按cpot[col ]的位置，將其放至 T.data 中，當(dāng)再次遇到各列后續(xù)的非零元三元組時(shí)，只需順序放到對(duì)應(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,各列第一個(gè)非零元三元組按先前求出的位置放到T.data中,各列后續(xù)的非零元三元組，順序放到對(duì)應(yīng)列元素的后面,Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元組順序表存儲(chǔ)表示，求稀疏矩陣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、非零元的個(gè)數(shù) cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; // 求 M 中每一列的第一個(gè)非零元在 b.data 中的序號(hào),// 轉(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ù)雜度分析,這個(gè)算法比普通轉(zhuǎn)置算法多用了兩個(gè)輔助向量。從時(shí)間上看，算法中有四個(gè)并列的單循環(huán)，循環(huán)次數(shù)分別為nu和tu，因而總的時(shí)間復(fù)雜度為O(mu +nu)。 在M的非零元個(gè)數(shù)tu和mu*nu等數(shù)量級(jí)時(shí)，其時(shí)間復(fù)雜度為O(mu * nu)。,三元組順序表又稱(chēng)有序的雙下標(biāo)法，它的特點(diǎn)是，非零

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

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

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

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

41、個(gè)數(shù) s= max(m,n),,Ch4_3.c,,1、初始化頭指針向量2、初始化各行列鏈表3、動(dòng)態(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。采用十字鏈表存儲(chǔ)表示 if (M) free(M); scanf(&m,&n,&t); //輸入M的行數(shù)、列數(shù)和非零元個(gè)數(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è)兩個(gè)矩陣相加后的結(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矩陣的鏈表中插入一個(gè)值為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中行值相同的兩個(gè)結(jié)點(diǎn)，pa == NULL 表明矩陣A在該行中沒(méi)有非零元，則上述四種情況的處理過(guò)程為：,******(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è)一個(gè)指針hl[j]，它的初值和列鏈表的頭指針相同，即h

50、l[j]＝chead[j]。,初始，令pa和pb分別指向A和B的第一行的第一個(gè)非零元素的結(jié)點(diǎn)，即 pa＝A.rhead[1]; pb＝B.rhead[1]; pre = NULL; 且令hl初始化 for (j=1; jj〉pb->j（即A的這一行中非零元素已處理完），則需在A中插入一個(gè)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]開(kāi)始找到新結(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指向本行下一個(gè)非零元結(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指向下一行的第一個(gè)非零元結(jié)點(diǎn)，轉(zhuǎn)(2)；否則結(jié)束。,****

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

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

57、 int n,m,t; //矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) }TSMatrix; 下面討論兩個(gè)稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性。,******,兩個(gè)矩陣相乘的經(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)。,兩個(gè)稀疏矩陣相乘,******,行邏輯鏈接的順序表如何從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) 這就是說(shuō)，為求Q的值，只有M(i,k)與N(k,j)（即M元素的列與N元素的行相等的兩項(xiàng)）才有相乘的機(jī)會(huì)，且當(dāng)兩項(xiàng)都不為零時(shí)，乘積中的這一項(xiàng)才不為零。 即只找到M.data中的j值和N.data中的i值相等的各對(duì)元素相乘即可。,**

60、****,2、相乘的基本操作是：對(duì)于M中每個(gè)元素M.data[p]，找到N中所有滿(mǎ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(列號(hào)與行號(hào)相等)且均不為零（三元組存在）時(shí)才

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

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值,,,******,兩個(gè)稀疏矩陣相乘（Q= M* N）的過(guò)程可大致描

63、述如下： Q初始化; if (Q是非零矩陣) { // 逐行求積 for (arow=1; arow<=M.mu; ++arow) { // 處理M的每一行 ctemp[] = 0; // 累加器清零 計(jì)算Q中第arow行的積并存入ctemp[] 中； 將ctemp[] 中非零元壓縮存儲(chǔ)到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是稀疏矩陣并用三元組表存儲(chǔ)結(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，采用行邏輯鏈接存儲(chǔ)。設(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)前處理的行號(hào) ctemp[] = 0; // 當(dāng)前行各元素累加器清零 while (p<=M.tu && M.data[p].i==crow) { brow=M.data[p].j;

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

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