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

1、2022-3-221 2022-3-222 數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級語言程序設(shè)計中都設(shè)定了數(shù)組類型。語言程序設(shè)計中都設(shè)定了數(shù)組類型。 數(shù)組數(shù)組（ArrayArray）是由是由n(n1)個個相同類型數(shù)據(jù)元素相同類型數(shù)據(jù)元素a0，al，ai，an-1構(gòu)成的構(gòu)成的有限序列有限序列。n是數(shù)組的是數(shù)組的長度長度。其中數(shù)組中。其中數(shù)組中的數(shù)據(jù)元素的數(shù)據(jù)元素ai是一個數(shù)據(jù)結(jié)構(gòu)，即是一個數(shù)據(jù)結(jié)構(gòu)，即ai可以是線性表中的一個元素，可以是線性表中的一個元素，本身也可以是一個線性表本身也可以是一個線性表，而線性子表中的每一個數(shù)據(jù)元素還可，而

2、線性子表中的每一個數(shù)據(jù)元素還可以再分解以再分解 。根據(jù)數(shù)組元素。根據(jù)數(shù)組元素ai的組織形式不同，數(shù)組可以分為的組織形式不同，數(shù)組可以分為一維數(shù)組、二維數(shù)組以及多維（一維數(shù)組、二維數(shù)組以及多維（n維）數(shù)組。維）數(shù)組。 2022-3-2232022-3-2241一維數(shù)組一維數(shù)組 一維數(shù)組可以看成是一個線性表或一個向量，它在計算機(jī)一維數(shù)組可以看成是一個線性表或一個向量，它在計算機(jī)內(nèi)是存放在內(nèi)是存放在一塊連續(xù)的一塊連續(xù)的存儲單元中，存儲單元中，適合適合于隨機(jī)查找。于隨機(jī)查找。 一維數(shù)組中，一旦一維數(shù)組中，一旦a0的存儲地址、一個數(shù)據(jù)元素所占存儲的存儲地址、一個數(shù)據(jù)元素所占存儲單元數(shù)單元數(shù)L確定，則確定

3、，則ai的存儲地址的存儲地址LOC(ai)就可求出：就可求出： LOC(ai)=LOC(a0)+i*L (0in) 2二維數(shù)組二維數(shù)組 二維數(shù)組，又稱二維數(shù)組，又稱矩陣矩陣(matrix)。二維數(shù)組中的每一個元素又二維數(shù)組中的每一個元素又是一個定長的線性表（一維數(shù)組），都要受到是一個定長的線性表（一維數(shù)組），都要受到兩個關(guān)系兩個關(guān)系即行關(guān)即行關(guān)系和列關(guān)系的系和列關(guān)系的約束約束，也就是每個元素都同屬于兩個線性表。，也就是每個元素都同屬于兩個線性表。例例如，設(shè)如，設(shè)A是一個有是一個有m行行n列的二維數(shù)組，則列的二維數(shù)組，則A可以表示為：可以表示為：2022-3-225 a0,0 a0,1 a0,n

4、-1A m n = a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 可以看成由可以看成由m m個個行行向量組成的向量，也可以看由向量組成的向量，也可以看由n n個個列列向向量組成的向量。量組成的向量。 數(shù)組中的每個元素由數(shù)組中的每個元素由元素值元素值a aijij及一組及一組下標(biāo)下標(biāo)（i i，j j）來來確確定定。a aijij既屬于第既屬于第i i行的行向量，又屬于第行的行向量，又屬于第j j列的列向量。列的列向量。 其中，其中，a ai i=( a=( ai,0i,0 a ai,1i,1 a ai,n-1i,n-1) (0) (0i in)n) 可以認(rèn)為可以

5、認(rèn)為A Am m* *n n=A=A，A A是這樣的一維數(shù)組：是這樣的一維數(shù)組： A=( aA=( a0 0，a al l，a ai i，a am-1m-1) ) 2022-3-226 顯然，二維數(shù)組同樣滿足數(shù)組的定義。一個二維數(shù)組可以顯然，二維數(shù)組同樣滿足數(shù)組的定義。一個二維數(shù)組可以看作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組。以此類推，看作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組。以此類推，任任何多維數(shù)組都可以看作一個線性表，何多維數(shù)組都可以看作一個線性表，這時線性表中的每個數(shù)據(jù)這時線性表中的每個數(shù)據(jù)元素也是一個線性表。多維數(shù)組是特殊的線性表，是線性表的元素也是一個線性表。多維數(shù)組是特殊的線性表，

6、是線性表的推廣。推廣。數(shù)組的性質(zhì)：數(shù)組的性質(zhì)：(1)(1) 數(shù)組中的數(shù)據(jù)元素數(shù)目數(shù)組中的數(shù)據(jù)元素數(shù)目固定固定。一旦定義了一個數(shù)組，其數(shù)。一旦定義了一個數(shù)組，其數(shù)據(jù)元素數(shù)目不再有增減變化。它屬于據(jù)元素數(shù)目不再有增減變化。它屬于靜態(tài)分配存儲空間靜態(tài)分配存儲空間的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。結(jié)構(gòu)。(2)(2) 數(shù)組中的數(shù)據(jù)元素必須具有數(shù)組中的數(shù)據(jù)元素必須具有相同相同的數(shù)據(jù)類型。的數(shù)據(jù)類型。(3)(3) 數(shù)組中的每個數(shù)據(jù)元素都有一組數(shù)組中的每個數(shù)據(jù)元素都有一組唯一唯一的下標(biāo)值。的下標(biāo)值。(4)(4) 數(shù)組是一種數(shù)組是一種隨機(jī)存儲隨機(jī)存儲結(jié)構(gòu)?？呻S機(jī)存取數(shù)組中的任意數(shù)據(jù)結(jié)構(gòu)?？呻S機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。元素。

7、2022-3-227 對于對于多維數(shù)組多維數(shù)組，有兩種，有兩種存儲存儲方式：方式：Am,n 以以行序為主序行序為主序的順序存儲；的順序存儲； 數(shù)組元素按行向量排列，即第數(shù)組元素按行向量排列，即第i+1個行向量緊接在第個行向量緊接在第i個個行向量之后行向量之后, 把所有數(shù)組元素順序存放在一塊連續(xù)的存把所有數(shù)組元素順序存放在一塊連續(xù)的存儲單元中。儲單元中。 任一數(shù)據(jù)元素的任一數(shù)據(jù)元素的存儲地址存儲地址可由公式算出：可由公式算出：Loc(a i,j)=loc(a 0,0)+(i*n+j)*L 以以列序為主序列序為主序的順序存儲的順序存儲 在以列序為主序的存儲方式中，數(shù)組元素按列向量排列，在以列序為主

8、序的存儲方式中，數(shù)組元素按列向量排列，即第即第j+1個列向量緊接在第個列向量緊接在第j個列向量之后個列向量之后, 把所有數(shù)組把所有數(shù)組元素順序存放在一塊連續(xù)的存儲單元中。元素順序存放在一塊連續(xù)的存儲單元中。 任一數(shù)據(jù)元素的任一數(shù)據(jù)元素的存儲地址存儲地址可由公式算出可由公式算出Loc(a i,j)=loc(a 0,0)+(j*m+i)*L2022-3-228 推廣推廣到一般到一般 設(shè)二維數(shù)組行下界為設(shè)二維數(shù)組行下界為c1,c1,行上界為行上界為d1,d1,列下界為列下界為c2c2，列上界為列上界為d2,d2,即數(shù)組即數(shù)組Ac1d1,c2d2.Ac1d1,c2d2. - -則以則以行序行序為主序的

9、求元素地址公式可以為：為主序的求元素地址公式可以為：Loc(a Loc(a i,ji,j)=loc(a )=loc(a c1,c2c1,c2)+(i-c1)+(i-c1)* *(d2-c2+1)+(j-c2)(d2-c2+1)+(j-c2)* *L L則以則以列序列序為主序的求元素地址公式可以為：為主序的求元素地址公式可以為：Loc(a Loc(a i,ji,j)=loc(a )=loc(a c1,c2c1,c2)+(j-c1)+(j-c1)* *(d1-c1+1)+(i-c1)(d1-c1+1)+(i-c1)* *L L2022-3-229 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除

10、數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組的基本操作一般數(shù)組的基本操作一般不會不會含有元含有元素的插入或刪除等操作素的插入或刪除等操作, ,數(shù)組數(shù)組只有只有訪問數(shù)組元素訪問數(shù)組元素和修改元素值和修改元素值的操作。的操作。 (1) (1) 取值操作：取值操作：給定一組下標(biāo)，讀其對應(yīng)的數(shù)據(jù)元素。給定一組下標(biāo)，讀其對應(yīng)的數(shù)據(jù)元素。 (2) (2) 賦值操作：賦值操作：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。數(shù)據(jù)元素。 我們著重研究二維和三維數(shù)組，因為它們的應(yīng)用是廣泛的，我們著重研究二維和三維數(shù)組

11、，因為它們的應(yīng)用是廣泛的，尤其是二維數(shù)組。尤其是二維數(shù)組。2022-3-2210 通常，數(shù)組在內(nèi)存中被映象為通常，數(shù)組在內(nèi)存中被映象為向量向量，即用向量作為數(shù)組的，即用向量作為數(shù)組的一種存儲結(jié)構(gòu)，這是因為內(nèi)存的地址空間是一維的，數(shù)組的行一種存儲結(jié)構(gòu)，這是因為內(nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過一個映象函數(shù)，則可根據(jù)數(shù)組元素的下標(biāo)得到列固定后，通過一個映象函數(shù)，則可根據(jù)數(shù)組元素的下標(biāo)得到它的存儲地址。它的存儲地址。 對于對于一維數(shù)組一維數(shù)組按下標(biāo)按下標(biāo)順序分配順序分配即可。即可。 對對多維數(shù)組多維數(shù)組分配時，要把它的元素映象存儲在一維存儲器分配時，要把它的元素映象存儲在一維存儲器中，一

12、般有兩種存儲方式：中，一般有兩種存儲方式：一一是以是以行為主序行為主序（或先行后列）的（或先行后列）的順序存放，如順序存放，如BASICBASIC、PASCALPASCAL、COBOLCOBOL、C C等程序設(shè)計語言中用等程序設(shè)計語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是另一種是以列為主序以列為主序（先列后行）的順序存放，如（先列后行）的順序存放，如FORTRANFORTRAN語語言中，用的是以列為主序的分配順序，即一列一列地分配。言中，用的是以列為主序的分配順序，即一列一列地分配。2022-3-2211 以以行

13、行為主序的為主序的分配規(guī)律分配規(guī)律是：最右邊的下標(biāo)先變化是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個下標(biāo)再變，下標(biāo)再變，從右向左，最后是左下標(biāo)。，從右向左，最后是左下標(biāo)。 以以列列為主序的為主序的分配規(guī)律分配規(guī)律恰好相反：最左邊的下標(biāo)恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個下標(biāo)再變，第二個下標(biāo)再變，從左向右，最后是右下標(biāo)。，從左向右，最后是右下標(biāo)。 2022-3-2212 例例如一個如一個2 23 3的二維數(shù)組，邏輯結(jié)構(gòu)可以用左圖表示。的二維數(shù)組，邏輯結(jié)

14、構(gòu)可以用左圖表示。以行為主序的內(nèi)存映象如右圖（以行為主序的內(nèi)存映象如右圖（a a）所示。）所示。 分配順序為：分配順序為：a a11 11 ，a a12 12 ，a a13 13 ，a a21 21 ，a a2222 ，a a23 23 ；以列為主序的分配順序為：；以列為主序的分配順序為：a a11 11 ，a a21 21 ，a a12 12 ，a a2222 ，a a13 13 ，a a23 23 ；它的內(nèi)存映象如右圖（；它的內(nèi)存映象如右圖（b b）所示。）所示。2022-3-2213 設(shè)有設(shè)有mn二維數(shù)組二維數(shù)組Amn，下面我們看，下面我們看按元素的下標(biāo)按元素的下標(biāo)求求其其地址地址的計算

15、：的計算： 以以“行為主序行為主序”的分配為的分配為例例：設(shè)數(shù)組的基址為：設(shè)數(shù)組的基址為LOC(a11)，每個數(shù)組元素占據(jù)每個數(shù)組元素占據(jù)l個地址單元，那么個地址單元，那么aij 的物理地址可用一的物理地址可用一線性尋址函數(shù)計算：線性尋址函數(shù)計算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在在C語言中，數(shù)組中每一維的語言中，數(shù)組中每一維的下界定義為下界定義為0，則：，則： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推廣推廣到一般的二維數(shù)組：到一般的二維數(shù)組：Ac1.d1 c2.d2，則，則aij的物理地的物理地址

16、計算函數(shù)為：址計算函數(shù)為： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l2022-3-2214 同理對于三維數(shù)組同理對于三維數(shù)組Amnp，即，即mnp數(shù)組，對于數(shù)組元數(shù)組，對于數(shù)組元素素aijk其其物理地址物理地址為：為： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推廣推廣到一般的三維數(shù)組：到一般的三維數(shù)組：Ac1.d1 c2.d2 c3.d3，則，則aijk的物理地址為：的物理地址為： LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *

17、( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*l2022-3-2215三維數(shù)組三維數(shù)組的邏輯結(jié)構(gòu)和以行為主序的分配示意圖如圖所示。的邏輯結(jié)構(gòu)和以行為主序的分配示意圖如圖所示。2022-3-2216 (2)(2)由于由于C C語言采用行序為主序的存儲方式，有：語言采用行序為主序的存儲方式，有： LOC(aLOC(a2,32,3)=LOC(a)=LOC(a0,00,0)+(i)+(i* *n+j)n+j)* *k k =1000+(2 =1000+(2* *4+3)4+3)* *4 4 =1044 =1044【例例1】在】

18、在C語言中，對于給定的二維數(shù)組語言中，對于給定的二維數(shù)組float a34，計算：計算： (1) 數(shù)組數(shù)組a中的數(shù)組元素數(shù)目；中的數(shù)組元素數(shù)目； (2) 若數(shù)組若數(shù)組a的起始地址為的起始地址為1000，且每個數(shù)組元素長度為，且每個數(shù)組元素長度為32位位(即即4個字節(jié)個字節(jié))，數(shù)組元素，數(shù)組元素a23的內(nèi)存地址。的內(nèi)存地址?！窘狻俊窘狻?1)由于由于C語言中數(shù)組的行、列下標(biāo)值的下界均為語言中數(shù)組的行、列下標(biāo)值的下界均為0，該數(shù)，該數(shù)組行上界為組行上界為3-1=2，列上界為，列上界為4-1=3，所以該數(shù)組的元素數(shù)目共有，所以該數(shù)組的元素數(shù)目共有3*4=12個。個。2022-3-2217 【例例2

19、2】有有m m名學(xué)生，每人考名學(xué)生，每人考n n門功課，試寫出求任一學(xué)生總分?jǐn)?shù)門功課，試寫出求任一學(xué)生總分?jǐn)?shù)和任一課程總分?jǐn)?shù)的數(shù)據(jù)結(jié)構(gòu)和算法。和任一課程總分?jǐn)?shù)的數(shù)據(jù)結(jié)構(gòu)和算法?！窘狻堪褜W(xué)生的考試成績存放在【解】把學(xué)生的考試成績存放在m m行行n n列的二維數(shù)組中，則第列的二維數(shù)組中，則第i(0i(0im)im)行第行第j(0j(0jn)jn)列中存放了第列中存放了第i i個學(xué)生的第個學(xué)生的第j j門課程考試門課程考試成績。即數(shù)據(jù)結(jié)構(gòu)為：成績。即數(shù)據(jù)結(jié)構(gòu)為：#define M 10 /假設(shè)假設(shè)為為1010人人#define N 3 /假設(shè)假設(shè)為為3 3int scoreMN; /學(xué)生成績二維數(shù)組

20、學(xué)生成績二維數(shù)組求求第第i i名學(xué)生總分?jǐn)?shù)名學(xué)生總分?jǐn)?shù)的算法為：的算法為：int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); 2022-3-2218 求第求第j j門課程門課程總分?jǐn)?shù)總分?jǐn)?shù)的算法為：的算法為：int course_sum(int scoreMN,int j) int i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); 2022-3-2219 矩陣矩陣是數(shù)值計算程序設(shè)計中經(jīng)常用到的數(shù)學(xué)模型，它

21、是由是數(shù)值計算程序設(shè)計中經(jīng)常用到的數(shù)學(xué)模型，它是由 m m 行和行和 n n 列的數(shù)值構(gòu)成（當(dāng)列的數(shù)值構(gòu)成（當(dāng)m=n m=n 時稱為方陣）。時稱為方陣）。在高級程序設(shè)計在高級程序設(shè)計語言中語言中，通常用，通常用表示矩陣。然而表示矩陣。然而在數(shù)值分析過程中經(jīng)在數(shù)值分析過程中經(jīng)常遇到一些比較特殊的矩陣，它們的階數(shù)很高，常遇到一些比較特殊的矩陣，它們的階數(shù)很高，矩陣中元素數(shù)矩陣中元素數(shù)量很大，而且有很多元素的值相同或是零值元素，量很大，而且有很多元素的值相同或是零值元素，如如對稱矩陣對稱矩陣、三角矩陣三角矩陣、帶狀矩陣帶狀矩陣和和稀疏矩陣稀疏矩陣等。等。為了節(jié)省存儲空間并且加為了節(jié)省存儲空間并且加快

22、處理速度，需要對快處理速度，需要對這類矩陣這類矩陣進(jìn)行壓縮存儲，進(jìn)行壓縮存儲，壓縮存儲的壓縮存儲的原則原則是：是：。 2022-3-2220。 對稱矩陣對稱矩陣是一個是一個n n階階方陣。若一個方陣。若一個n n階矩陣階矩陣A A中的元素滿中的元素滿足足: :a ai,ji,j=a=aj,i j,i (0i(0i，jn-1)jn-1)，則稱則稱A A為為n n階對稱矩陣。階對稱矩陣。 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 a n-1 2 a n-1

23、n-1 對稱矩陣對稱矩陣2022-3-2221 在這個下三角矩陣中，第在這個下三角矩陣中，第i i行恰有行恰有i+1i+1個元素，個元素，元素總數(shù)元素總數(shù)為：為：n*n, , 現(xiàn)把這些元素存儲在現(xiàn)把這些元素存儲在n(n+1)/2n(n+1)/2個元的空間中。個元的空間中。 由于對稱矩陣中的元素關(guān)于由于對稱矩陣中的元素關(guān)于主對角線主對角線對稱對稱，因此，因此可以為每一對對可以為每一對對稱的矩陣元素分配稱的矩陣元素分配 1 1 個存儲空間，個存儲空間，n n階矩陣中的階矩陣中的n nn n個元素就可以被個元素就可以被壓縮到壓縮到 n(n+1)/2n(n+1)/2 個元素的存儲空間中去。個元素的存儲

24、空間中去。 Sak 與aji 的對應(yīng)關(guān)系： 稱一維數(shù)組稱一維數(shù)組Sa0.n(n+1)/2 為為n 階對稱矩陣階對稱矩陣A的壓縮存儲。的壓縮存儲。其存儲對應(yīng)關(guān)系如上圖其存儲對應(yīng)關(guān)系如上圖 : : k 0 1 2 3 4 n(n+1)/2-1a0,0 a1,0 a1,1 a2,0 a2,1 an-1,0 an-1,n-1Sak隱 含 元 素a0,1 a0,2 a0,n-1 對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 2022-3-2222其中，其中，Sbn(n+1)/2中存放常數(shù)中存放常數(shù)c或或0。 2022-3-2223常見的有常見的有三對角矩陣、五對角矩陣、七對三對角矩陣、五對角矩陣、七對角矩陣角矩

25、陣等。等。具有具有3條非零對角線的對角矩陣條非零對角線的對角矩陣 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa2022-3-2224 ：對特殊矩陣的壓縮存儲實質(zhì)上就是將二維矩陣中的對特殊矩陣的壓縮存儲實質(zhì)上就是將二維矩陣中的部分元素按照某種方案排列到一維數(shù)組中，不同的排列方案也部分元素按照某種方案排列到一維數(shù)組中，不同的排列方案也就對應(yīng)不同的存儲方案。就對應(yīng)不同的存儲方案。2022-3-22255.2.2 稀疏矩陣的壓縮存儲方法稀疏矩陣的壓縮存儲方法 如果一個矩陣中

26、非零元較零元少，且分布沒有一定規(guī)律，稱如果一個矩陣中非零元較零元少，且分布沒有一定規(guī)律，稱該矩陣為該矩陣為稀疏矩陣稀疏矩陣。 根據(jù)存儲時所附加信息的不同，稀疏矩陣的根據(jù)存儲時所附加信息的不同，稀疏矩陣的順序存儲方法順序存儲方法包包括：括：三元組表示法三元組表示法、帶輔助行向量的二元組表示法帶輔助行向量的二元組表示法和和偽地址表偽地址表示法示法，其中以三元組表示法，其中以三元組表示法最常用最常用。 三元組表示法三元組表示法就是在存儲非零元的同時，存儲該元素所對就是在存儲非零元的同時，存儲該元素所對應(yīng)的行下標(biāo)和列下標(biāo)。應(yīng)的行下標(biāo)和列下標(biāo)。稀疏矩陣中的每一個非零元素由一個三稀疏矩陣中的每一個非零元素

27、由一個三元組元組( (i i，j j，a aijij) )唯一確定。唯一確定。矩陣中所有非零元素存放在由三元矩陣中所有非零元素存放在由三元組組成的數(shù)組中。組組成的數(shù)組中。 由由線性表的兩種不同存儲結(jié)構(gòu)可以得到稀疏矩陣壓縮的不線性表的兩種不同存儲結(jié)構(gòu)可以得到稀疏矩陣壓縮的不同的存儲方法。同的存儲方法。 2022-3-2226 假設(shè)有一個假設(shè)有一個6 67 7階稀疏矩陣階稀疏矩陣A A，其元素情況以及非零元其元素情況以及非零元對應(yīng)的三元組表（以行序為主序）如圖所示。對應(yīng)的三元組表（以行序為主序）如圖所示。 0 0 1 0 0 0 0 0 2 0 0 0 0 0A67 = 3 0 0 0 0 0 0

28、 0 0 0 5 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 4 0 6 7 71 0 2 12 1 1 23 2 0 34 3 3 55 4 4 66 5 5 77 5 6 4序號 行 列 值 (a) 稀疏矩陣稀疏矩陣 (b) 三元組表示三元組表示 三元組表中的第一行分別表示稀疏矩陣三元組表中的第一行分別表示稀疏矩陣A A的行數(shù)、列數(shù)的行數(shù)、列數(shù)和非零元的個數(shù)。和非零元的個數(shù)。顯然，顯然，非零元素的三元組是按行號遞增的非零元素的三元組是按行號遞增的順序、相同行號的三元組按列號遞增的順序排列的。順序、相同行號的三元組按列號遞增的順序排列的。圖圖5-42022-3-22271

29、 1三元組順序表三元組順序表 假設(shè)以行序為主序，且以假設(shè)以行序為主序，且以一維數(shù)組一維數(shù)組作為三元組表的存儲結(jié)作為三元組表的存儲結(jié)構(gòu)，可以得到稀疏矩陣的一種壓縮存儲方法，稱為構(gòu)，可以得到稀疏矩陣的一種壓縮存儲方法，稱為三元組順序三元組順序表表。三元組順序表的數(shù)據(jù)結(jié)構(gòu)定義如下：。三元組順序表的數(shù)據(jù)結(jié)構(gòu)定義如下：#define NUM 100 /矩陣中非零元素最大個數(shù)矩陣中非零元素最大個數(shù)typedef struct /三元組結(jié)構(gòu)三元組結(jié)構(gòu) int r, c; /行行(列列)號號 ElemType d; /元素值元素值 tupletype; /三元組定義三元組定義typedef struct in

30、t rows; /矩陣行數(shù)值矩陣行數(shù)值 int cols; /矩陣列數(shù)值矩陣列數(shù)值 int nums; /非零元素個數(shù)非零元素個數(shù) tupletype dataNUM; /三元組表三元組表 table; /三元組順序表定義三元組順序表定義 2022-3-2228 1稀疏矩陣的轉(zhuǎn)置運(yùn)算稀疏矩陣的轉(zhuǎn)置運(yùn)算 轉(zhuǎn)置轉(zhuǎn)置是矩陣中最簡單的一種運(yùn)算。是矩陣中最簡單的一種運(yùn)算。 對于一個對于一個m mn n的矩陣其轉(zhuǎn)置矩陣是一個的矩陣其轉(zhuǎn)置矩陣是一個n nm m的矩陣，設(shè)為的矩陣，設(shè)為B Bn nm m 且滿足且滿足a ai ,ji ,j=b=bj,i j,i 即：即：aij=bjiaij=bji，其中：其中

31、：00im-1im-1，0jn-10jn-1 即即A A的行是的行是B B的列，的列，A A的列是的列是B B的行。的行。稀疏矩陣的三元組表稀疏矩陣的三元組表2022-3-2229三元組表示的三元組表示的稀疏矩陣的轉(zhuǎn)置稀疏矩陣的轉(zhuǎn)置常用的算法有以下兩種：常用的算法有以下兩種：1 1）矩陣的列序轉(zhuǎn)置）矩陣的列序轉(zhuǎn)置（傳統(tǒng)的轉(zhuǎn)置算法）（傳統(tǒng)的轉(zhuǎn)置算法） 矩陣矩陣A是按行序為主序存儲的，是按行序為主序存儲的，若按列序為主序進(jìn)行轉(zhuǎn)置就若按列序為主序進(jìn)行轉(zhuǎn)置就可以得到可以得到A陣的轉(zhuǎn)置矩陣陣的轉(zhuǎn)置矩陣B。假設(shè)矩陣假設(shè)矩陣A的三元組存入一維數(shù)組的三元組存入一維數(shù)組中，中，只要在只要在數(shù)組中按三元組的列域數(shù)

32、組中按三元組的列域cols的值開始掃描，從第的值開始掃描，從第0列列至第至第n-1列，依序?qū)⑷M列域與行域值對換，并順次存入數(shù)組列，依序?qū)⑷M列域與行域值對換，并順次存入數(shù)組mb中。算法如下：中。算法如下：int transpose(table ma,table mb) int i,j,k=0,n,t; if(ma.nums=0)return(0)； /矩陣中無非零元素矩陣中無非零元素 m=ma.rows; /m為矩陣為矩陣A的列數(shù)的列數(shù) n=ma.cols; /n為矩陣為矩陣A的行數(shù)的行數(shù) t=ma.nums; /為矩陣中非零元素個數(shù)為矩陣中非零元素個數(shù) mb.rows=n; /轉(zhuǎn)置矩陣

33、轉(zhuǎn)置矩陣B的列數(shù)的列數(shù) 2022-3-2230mb.cols; /轉(zhuǎn)置矩陣轉(zhuǎn)置矩陣B的行數(shù)的行數(shù) mb.nums=t; /轉(zhuǎn)置矩陣中的非零元素個數(shù)轉(zhuǎn)置矩陣中的非零元素個數(shù) for(i=0;in;i+) /按矩陣按矩陣A的列序掃描的列序掃描 for(j=0;jt;j+) if(ma.dataj.c=i) /判斷第判斷第j個三元組是不是第個三元組是不是第i列的列的 mb.datak.r=ma.dataj.c; mb.datak.c=ma.dataj.r; mb.datak+.d=ma.dataj.d; return(1); /成功完成矩陣轉(zhuǎn)置成功完成矩陣轉(zhuǎn)置 以上算法的以上算法的時間復(fù)雜度時間復(fù)雜

34、度分析：分析：若若n n為轉(zhuǎn)置矩陣的列數(shù)，為轉(zhuǎn)置矩陣的列數(shù)，t t為矩陣中非為矩陣中非零元素個數(shù)，則算法的時間花費(fèi)零元素個數(shù)，則算法的時間花費(fèi)主要在兩個循環(huán)上主要在兩個循環(huán)上，所以若時間復(fù)雜，所以若時間復(fù)雜度為度為O(nO(nt)t)。也就是說，時間的花費(fèi)和矩陣也就是說，時間的花費(fèi)和矩陣A A的列數(shù)和非零元素個數(shù)的列數(shù)和非零元素個數(shù)的乘積成正比。若用的乘積成正比。若用m mn n的二維數(shù)組表示矩陣，則相應(yīng)的矩陣轉(zhuǎn)置算的二維數(shù)組表示矩陣，則相應(yīng)的矩陣轉(zhuǎn)置算法的循環(huán)為：法的循環(huán)為：for ( i=0for ( i=0；i in n；i+ )i+ ) for (j=0 for (j=0；j jm m

35、；j+j+ ) bij=aji bij=aji； 此時，時間復(fù)雜度為此時，時間復(fù)雜度為O(mn) 。2022-3-22312 2）快速轉(zhuǎn)置算法：）快速轉(zhuǎn)置算法： 三元組順序表雖然節(jié)省了存儲空間，但時間復(fù)雜度比一般三元組順序表雖然節(jié)省了存儲空間，但時間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，矩陣轉(zhuǎn)置的算法還要復(fù)雜，其效率低的原因其效率低的原因是算法要從是算法要從A A的三的三元組表中尋找第一列、第二列、元組表中尋找第一列、第二列、，要反復(fù)搜索，要反復(fù)搜索A A表，表，若能直若能直接確定接確定A A中每一三元組在中每一三元組在B B中的位置，則對中的位置，則對A A的三元組表掃描一的三元組表掃描一次即

36、可次即可。這是可以做到的，因為。這是可以做到的，因為A A中第一列的第一個非零元素中第一列的第一個非零元素一定存儲在一定存儲在B.data1B.data1，如果還知道第一列的非零元素的個數(shù)，如果還知道第一列的非零元素的個數(shù)，那么第二列的第一個非零元素在那么第二列的第一個非零元素在B.dataB.data中的位置便等于第一中的位置便等于第一列的第一個非零元素在列的第一個非零元素在B.dataB.data中的位置加上第一列的非零元素中的位置加上第一列的非零元素的個數(shù)，的個數(shù)，如此類推，因為如此類推，因為A A中三元組的存放順序是先行后列，中三元組的存放順序是先行后列，對同一行來說，必定先遇到列號小

37、的元素，這樣只需掃描一遍對同一行來說，必定先遇到列號小的元素，這樣只需掃描一遍A.dataA.data即可。即可。 2022-3-2232為此，需要設(shè)置兩個一維數(shù)組為此，需要設(shè)置兩個一維數(shù)組num0.nnum0.n和和rpos0.nrpos0.n：num0.nnum0.n：統(tǒng)計統(tǒng)計M M中每列非零元素的個數(shù)。中每列非零元素的個數(shù)。rpos0.nrpos0.n：M M中的每列第一個非零元素在中的每列第一個非零元素在T T中的位置。中的位置。算法通過算法通過rposrpos數(shù)組建立位置對應(yīng)關(guān)系：數(shù)組建立位置對應(yīng)關(guān)系： rpos0=0 rpos0=0 ； rposcol=rposcol-1+numc

38、ol-1 rposcol=rposcol-1+numcol-1 0 0colcolM.rowsM.rows；例如圖例如圖5-4(5-4(a) a) 所示的稀疏矩陣的三元組表對應(yīng)的所示的稀疏矩陣的三元組表對應(yīng)的num0.n-1num0.n-1和和rpos0.n-1rpos0.n-1如圖如圖5-55-5所示。所示。 （算法（算法5.2見教科書見教科書P100）圖圖5-5 5-5 矩陣的矩陣的numnum和和rpos rpos 數(shù)組值數(shù)組值Col 0 1 2 3 4 5 6numcol 1 1 1 1 1 1 1rposcol 0 1 2 3 4 5 62022-3-2233快速轉(zhuǎn)置快速轉(zhuǎn)置算法如下

39、：算法如下： void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j; cpot0=1; for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1;for(p=1;p=a.t;+p) col=a

40、.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; 2022-3-2234帶行表的三元組帶行表的三元組) ) 有時為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲的三元組中，有時為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲的三元組中，加入一個加入一個行表行表來記錄稀疏矩陣中每行的非零元素在三元組表中來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個新增屬性加以描述的起始位置。當(dāng)將行表作為三元組表的一個新增屬性加以描述時，就得到了稀疏矩陣的另一種順序存

41、儲結(jié)構(gòu)：時，就得到了稀疏矩陣的另一種順序存儲結(jié)構(gòu)：帶行表的三元帶行表的三元組表。組表。稱這種稱這種“帶行鏈接信息帶行鏈接信息”的三元組表為的三元組表為行邏輯鏈接的順行邏輯鏈接的順序表序表。 其類型描述如下：其類型描述如下： #define maxrow 100 typedef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable 2022-3-2235 下面討論兩個下面討論兩個稀疏矩陣相乘稀疏矩陣相乘的例子，容易看出這種表示方的例子，容易看出這種表示方法的優(yōu)越性：法的優(yōu)越性： 若設(shè)若設(shè) Q=M*N 其中，其中，M是

42、是m1*n1矩陣，矩陣，N是是m2*n2矩陣。矩陣。 當(dāng)當(dāng)n1=m2時有：時有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0 for(k=1;ktag=ATOM) return 0; /原子深度為原子深度為0 for(max=0,pp=L;pp;pp=pp-ptr.tp) dep=GListDepth(pp-ptr.hp); /求以求以pp-ptr.hp為頭指針的子表深度為頭指針的子表深度 if(depmax)max=dep; return max+1; /非空表的深度是各元素的深度的最大值加非空表的深度是各元素的深度的最大值加1/GListDepth202

43、2-3-2254 GListNode *GListCopy(GListNode *p)/*p為被被復(fù)制的廣義表的頭結(jié)點(diǎn)指針為被被復(fù)制的廣義表的頭結(jié)點(diǎn)指針*/ GListNode *q; if(p=NULL) return NULL； q=(GListNode*)malloc(sizeof(GListNode); q-tag=p-tag; if(p-tag=1) q-val.sublist= GListCopy(p-val.sublist); else q-val.data=p-val.data; q-link=GListCopy(p-link); return q; 2022-3-2255 假

44、設(shè)廣義表以單鏈表的形式存儲，廣義表的元素類型假設(shè)廣義表以單鏈表的形式存儲，廣義表的元素類型elemtype 為字符型為字符型char，廣義表由鍵盤輸入，假定全部為字廣義表由鍵盤輸入，假定全部為字母，輸入格式為：元素之間用逗號分隔，表元素的起止符號母，輸入格式為：元素之間用逗號分隔，表元素的起止符號分別為左、右圓括號，空表在其圓括號內(nèi)使用一個分別為左、右圓括號，空表在其圓括號內(nèi)使用一個“#”字符字符表示，最后使用一個分號作為整個廣義表的結(jié)束。表示，最后使用一個分號作為整個廣義表的結(jié)束。 例如例如“( (a a，(b(b，c c，d)d)”，就是一個符合上述規(guī)定的廣義表就是一個符合上述規(guī)定的廣義表格式（注意：不包括引號）。格式（注意：不包括引號