第五章+數(shù)組與廣義表

1、第五章 數(shù)組和廣義表數(shù)組稀疏矩陣廣義表數(shù) 組定義 相同類型的數(shù)據(jù)元素的集合。一維數(shù)組的示例35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9一維數(shù)組一維數(shù)組數(shù)組的定義和初始化main ( ) int a13 = 3, 5, 7 , *elem; for ( int i = 0; i 3; i+ ) printf ( “%d”, a1i, “n” ); /靜態(tài)數(shù)組 elem = a1; for ( int i = 0; i 0 a, i = 0 a+i*la類似于線性表，一個二維數(shù)組的邏輯結構可形式地表示為：2_Array=(D,R)其中D=aij(

2、i=0,1,m-1,j=0,1,n-1), aij是同類型數(shù)據(jù)元素的集合。R=ROW,COL是數(shù)據(jù)元素上關系的集合。ROW=|0=i=m-1,0=j=n-2每一行上的列關系。COL=|0=i=m-2,0=j=n-1每一列上的行關系。 二維數(shù)組二維數(shù)組111101121202111101101000mnananamaaamaaamaaaa行優(yōu)先存放：行優(yōu)先存放： 設數(shù)組開始存放位置設數(shù)組開始存放位置 LOC( 0, 0 ) = a, 每個元每個元素占用素占用 l 個存儲單元個存儲單元 LOC ( i, j ) = a + ( i * m + j ) * l三維數(shù)組各維元素個數(shù)為 m1, m2,

3、m3 下標為 i1, i2, i3的數(shù)組元素的存儲地址： （按頁/行/列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前前i1頁總頁總元素個數(shù)元素個數(shù)第第i1頁的頁的前前i2行行總總元素個數(shù)元素個數(shù)n 維數(shù)組各維元素個數(shù)為 m1, m2, m3, , mn 下標為 i1, i2, i3, , in 的數(shù)組元素的存儲地址： limianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 二維

4、數(shù)組二維數(shù)組 三維數(shù)組三維數(shù)組行向量 下標 i 頁向量 下標 i列向量 下標 j 行向量 下標 j 列向量 下標 k特殊矩陣的壓縮存儲特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。特殊矩陣的壓縮存儲主要是針對階數(shù)很高的特殊矩陣。為節(jié)省存儲空間，對可以不存儲的元素，如零元素或?qū)ΨQ元素，不再存儲。對稱矩陣三對角矩陣對稱矩陣的壓縮存儲設有一個 nn 的對稱矩陣 A。11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaa在矩陣中，在矩陣中，aij = aji為節(jié)約存儲空間，只存對角線及對角線以上的元素，或者只存對角線及對角線以下的元素。

5、前者稱為上三角矩陣，后者稱為下三角矩陣。把它們按行存放于一個一維數(shù)組 B 中，稱之為對稱矩陣 A 的壓縮存儲方式。數(shù)組 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 個元素。上三角矩陣下三角矩陣33323130232221201312111003020100aaaaaaaaaaaaaaaa33323130232221201312111003020100aaaaaaaaaaaaaaaa11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩陣B a00 a10 a11 a20 a21 a22 a30 a3

6、1 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1若若 i j, 數(shù)組元素數(shù)組元素Aij在數(shù)組在數(shù)組B中的存放位置中的存放位置為為 1 + 2 + + i + j = (i + 1)* i / 2 + j前前i行行元素總數(shù)元素總數(shù) 第第i行第行第j個個元素前元素個數(shù)元素前元素個數(shù)若若 i j，數(shù)組元素，數(shù)組元素 Aij 在矩陣的上三角在矩陣的上三角部分部分, 在數(shù)組在數(shù)組 B 中沒有存放，可以找它的對中沒有存放，可以找它的對稱元素稱元素Aji：= j *(j +1) / 2 + i若已知某矩陣元素位于數(shù)組若已知某矩陣元素位于數(shù)組B的第的第k個位置，個位置，可尋

7、找滿足可尋找滿足 i (i + 1) / 2 k (i + 1)*(i + 2) / 2的的 i, , 此即為此即為該元素的行號。該元素的行號。 j = k - i * (i + 1) / 2此即為該元素的列號。此即為該元素的列號。 例，當例，當 k = 8, 3*4 / 2 = 6 k j，數(shù)組元素，數(shù)組元素Aij在矩陣的下三角在矩陣的下三角部分，在數(shù)組部分，在數(shù)組 B 中沒有存放。因此，找它中沒有存放。因此，找它的對稱元素的對稱元素Aji。 Aji在數(shù)組在數(shù)組 B 的第的第 (2*n- -j- -1) * j / 2 + i 的位置中找到。的位置中找到。112112223223222112

8、1110010000000000000000000Annnnnnnnnnaaaaaaaaaaaaa三對角矩陣的壓縮存儲B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10三對角矩陣中除主對角線及在主對角線上 下最臨近的兩條對角線上的元素外，所有其它元素均為0?？偣灿?n-2個非零元素。將三對角矩陣A中三條對角線上的元素按行存放在一維數(shù)組 B 中，且a00存放于B0。在三條對角線上的元素aij 滿足 0 i n-1, i-1 j i+1在一維數(shù)組 B 中 Aij 在第 i 行，它前面有 3*i-1 個非零

9、元素, 在本行中第 j 列前面有 j-i+1 個，所以元素 Aij 在 B 中位置為 k = 2*i + j。若已知三對角矩陣中某元素 Aij 在數(shù)組 B 存放于第 k 個位置，則有 i = (k + 1) / 3 j = k - 2 * i例如，當 k = 8 時， i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 當 k = 10 時， i = (10+1) / 3 = 3, j = 10 - 2*3 = 4 0000280000000091039000000006000017000110150022000A76稀疏矩陣 (Sparse Matrix)非零元素個數(shù)非零元

10、素個數(shù)遠遠少于矩陣元素個數(shù)遠遠少于矩陣元素個數(shù)在上圖中在上圖中, ,矩陣矩陣A A是是6 6* *7 7的矩陣的矩陣, ,它有它有4242個元素個元素, ,但只有但只有8 8個非零個非零元素元素, ,且分布無規(guī)律可循且分布無規(guī)律可循, ,所以可以稱之為稀疏矩陣。所以可以稱之為稀疏矩陣。稀疏矩陣的抽象數(shù)據(jù)類型稀疏矩陣的抽象數(shù)據(jù)類型(三元組順序表）三元組順序表）#define MAXSIZE 12500typedef structint i,j; /非零元素行號非零元素行號/列號列號ElemType e; /非零元素的值非零元素的值Triple; /三元組三元組typedef unionTripl

11、e dataMAXSIZE+1;int mu,nu,tu; /矩陣行數(shù)、列數(shù)、非零元個數(shù)矩陣行數(shù)、列數(shù)、非零元個數(shù)TSMatrix;/稀疏矩陣類定義稀疏矩陣類定義 0000280000000091039000000006000017000110150022000稀疏矩陣稀疏矩陣 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3

12、 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 80000015003901700000000006022280000000001100910000 轉(zhuǎn)置矩陣轉(zhuǎn)置矩陣 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 4 4 9 91 1 1 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 3 3 0 0 2 22 2 4 3 3 2 2 - - - -6 6 5 5 5 1 1 1 17 7 6 5 5 3 3 3 39 9 7 6 6 0

13、 0 1 16 6用三元組表表示的稀疏矩陣及其轉(zhuǎn)置v稀疏矩陣轉(zhuǎn)置算法思想顯然，一個稀疏矩陣的轉(zhuǎn)置仍然是一個稀疏矩陣，方法是：設將矩陣M轉(zhuǎn)置為矩陣T（1）將矩陣的行列值交換（2）將每一個三元組的i和j相互調(diào)換（3）重排三元組之間的次序可以有兩種處理方法：方法一：按照M(m*n)的列序來進行轉(zhuǎn)置設矩陣列數(shù)為nu，對矩陣三元組表掃描nu次。第k次檢測列號為k的項。第k次掃描找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。v稀疏矩陣的轉(zhuǎn)置稀疏矩陣的轉(zhuǎn)置Status TransposeSMatrix(TSMatrix M, TSMatrix &T)T.mu=M.nu;

14、 T.nu=M.mu; T.tu=M.tu;/轉(zhuǎn)置矩陣的列數(shù)轉(zhuǎn)置矩陣的列數(shù), ,行數(shù)和非零元素個數(shù)行數(shù)和非零元素個數(shù)if (T.tu)q=0; /矩陣矩陣T的指針的指針for(col=0;colM.nu;+col)for(p=0;pM.tu;+p)/矩陣矩陣M的指針的指針if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;/TransposeSMatrix該算法主要工作是在該算法主要工作是在p*col的兩重循環(huán)中做的兩重循環(huán)中做的，所以時間復雜度是的，所以時間復雜度是

15、O(nu*tu)。而一。而一般矩陣的轉(zhuǎn)置算法是在般矩陣的轉(zhuǎn)置算法是在nu*mu的兩重循的兩重循環(huán)中做的，時間復雜度是環(huán)中做的，時間復雜度是O(nu*mu)。當。當稀疏矩陣的非零元個數(shù)稀疏矩陣的非零元個數(shù)tu=nu*mu時，其時，其時間復雜度時間復雜度O(nu*tu)=O(nu*nu*mu)=O(nu2*mu)大大大高于一般矩陣的時間復雜度，所以該大高于一般矩陣的時間復雜度，所以該算法僅適用于算法僅適用于tunu*mu的稀疏矩陣。的稀疏矩陣。方法二：快速轉(zhuǎn)置運算方法二：快速轉(zhuǎn)置運算在對在對M M矩陣轉(zhuǎn)置時，矩陣轉(zhuǎn)置時，M M矩陣的三元組中元素按行序排列，矩陣的三元組中元素按行序排列，T T矩陣中

16、的元素按矩陣中的元素按M M矩陣的列序排列，前面的轉(zhuǎn)置算法的矩陣的列序排列，前面的轉(zhuǎn)置算法的特點是以特點是以T T矩陣的三元組為中心，在矩陣的三元組為中心，在M M矩陣的三元組中矩陣的三元組中通盤查找合適的結點置入通盤查找合適的結點置入T T中。如果能預先確定中。如果能預先確定M M的每的每一列第一個非零元在一列第一個非零元在T T中應有的位置，則在轉(zhuǎn)置時就可中應有的位置，則在轉(zhuǎn)置時就可直接放到直接放到T T中去，所以在轉(zhuǎn)置前，應先求得中去，所以在轉(zhuǎn)置前，應先求得M M的的每一列每一列中非零元的個數(shù)中非零元的個數(shù)和每一列的和每一列的第一個非零元在第一個非零元在T T中的位置中的位置。為此，需要

17、兩個輔助數(shù)組為此，需要兩個輔助數(shù)組numnum和和cpot,numcpot,num表示表示M M中第中第colcol列列非零元素的個數(shù)。非零元素的個數(shù)。cpotcpot表示表示M M中第中第colcol列第一個非零元列第一個非零元素在素在T T中的位置。顯然有：中的位置。顯然有：cpot0=0cpotcol=cpotcol-1+numcol-1矩陣M的輔助數(shù)組的值Col012356numcol111221cpotcol012357轉(zhuǎn)置矩陣轉(zhuǎn)置矩陣Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)T.mu=M.nu; T.nu=M.m

18、u; T.tu=M.tu;if(T.tu)for(col=0;colM.nu;+col) numcol=0;/初始化初始化numfor(t=0;tM.tu;+t) +numM.datat.j;/求求M中每列非零元個數(shù)中每列非零元個數(shù)cpot0=0;for(col=1;colM.nu;+col) cpotcol=cpotcol-1+numcol-1;/求第求第col列中第一個非零元在列中第一個非零元在T中的序號中的序號for(p=0;pM.tu;+p)col=M.datap.j; q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.

19、e=M.datap.e; +cpotcol;/該列下一元素位置該列下一元素位置/for /ifreturn OK;/FastTransposeSMatrix行邏輯鏈接的順序表行邏輯鏈接的順序表為便于隨機存取任意一行的非零元，將快速轉(zhuǎn)置為便于隨機存取任意一行的非零元，將快速轉(zhuǎn)置矩陣的算法中的輔助數(shù)組矩陣的算法中的輔助數(shù)組cpot固定在稀疏矩陣固定在稀疏矩陣的存儲結構中。的存儲結構中。typedef structTriple dataMAXSIZE+1;int rposMAXRC+1;int mu,nu,tu;RLSMatrix;該存儲方法便于某些運算如稀疏矩陣的相乘。該存儲方法便于某些運算如稀疏

20、矩陣的相乘。000200105003M00420120N400160NMQ十字鏈表十字鏈表以鏈式存儲結構表示三元組的線性表。以鏈式存儲結構表示三元組的線性表。template class CNode int Row, Col; T Value;CNode *Down, *Right;LeftUpRowColValueRowColValueDownRight例例8000709000040600A2000009010000300B廣義表 (General Lists )廣義表的概念廣義表的概念 n ( 0 )個表元素組成的有個表元素組成的有 限序列，記作限序列，記作 LS = (a0, a1, a

21、2, , an-1) LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表 (稱稱 為子表為子表)，可以是數(shù)據(jù)元素，可以是數(shù)據(jù)元素(稱為原子稱為原子)。 n為表的長度。為表的長度。n = 0 的廣義表為空表。的廣義表為空表。 n 0時，時，表的第一個表元素稱為廣義表表的第一個表元素稱為廣義表 的表頭的表頭(head)，除此之外，其它表元素組，除此之外，其它表元素組 成的表稱為廣義表的表尾成的表稱為廣義表的表尾(tail)。 A=( );/A是一個空表是一個空表B=(e);/表表B有一個原子有一個原子C=(a,(b,c,d);/兩個元素為原子兩個元素為原子a和子表和子表(b,c,d)

22、D=(A,B,C); /有三個元素均為列表有三個元素均為列表E=(a,E);/遞歸的列表遞歸的列表,包含兩個元素包含兩個元素,一個是單元一個是單元素素a,另一個是子表另一個是子表,但該子表是其自身但該子表是其自身.所以所以,E相當相當于一個無限的廣義表于一個無限的廣義表( a,(a,(a,).例如例如表結點表結點Tag=1 hp tp廣義表存儲結構廣義表存儲結構原子結點原子結點Tag=0 atomtypedef struct GLNodeint tag;unionchar atom;struct structGLNode *hp,*tp;ptr;*GList;方法一方法一方法一方法一A=NILE 1 11 D 11 BC1 0 e 0 a 1 1 1 0 b 0 c 0 d 1 10 a 表結點表結點Tag=1 hp tp廣義表存儲結構廣義表存儲結構原子結點原子結點typedef struct GLNodeint tag;unionchar atom;struct GLNode *hp;struct GLNode