1、Data StructureCh Array & Generalized List2021-9-26mayan 第五章 數組和廣義表數組的定義數組的定義數組的順序表示數組的順序表示矩陣的壓縮存儲矩陣的壓縮存儲廣義表的定義廣義表的定義廣義表的存儲結構廣義表的存儲結構Data StructureCh Array & Generalized List2021-9-26mayan 5.1數組的定義數組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數據元素本身也是一種線性表。數組： 由一組名字相同、下標不同的變量構成。數組的處理比其它復雜的結構要簡單-特點 數組中各元素具有統一的類型； 數組元素的

2、下標一般具有固定的上界和下界，即數組一旦被定義，它的維數和維界就不再改變。數組的基本操作比較簡單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的操作。Data StructureCh Array & Generalized List2021-9-26mayan 5.1數組的定義一維數組的特點：1個下標，ai 是ai+1的直接前驅二維數組的特點：2個下標，每個元素ai,j受到兩個關系（行關系和列關系）的約束：N維數組的特點：n個下標，每個元素受到n個關系約束。一個n維數組可以看成是由若干個n1維數組組成的線性表。一個mn的二維數組可以看成是m行的一維數組，或者n列的一維數組。mnmmnn

3、nmaaaaaaaaaA.212222111211Data StructureCh Array & Generalized List2021-9-26mayan 5.2 數組的順序表示問題問題：計算機的存儲結構是一維的，而數組一般是多維的，怎樣存放？解決辦法：解決辦法：事先約定按某種次序將數組元素排成一列序列，然后將這個線性序列存入存儲器中。以行序為主序以列序為主序注意：若規定好了次序，則數組中任意一個元素的存放地址便有規律可尋，可形成地址計算公式；約定的次序不同，則計算元素地址的公式不同；1.C和PASCAL中一般采用行優先順序；FORTRAN采用列優先。Data StructureCh A

4、rray & Generalized List2021-9-26mayan 5.2 數組的順序表示以“行序為主序”的存儲映象a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L二維數組A中任一元素ai,j 的存儲位置 LOC(i,j) = LOC(0,0) + (b2ij)LData StructureCh Array & Generalized List2021-9-26mayan 5.2 數組的順序表示按列序為主序存放按列序為主序存放amn.a2na1n.am2.a22a12am1.a21a11a11a12.a1na21a22.a2nam1am

5、2.amn.Data StructureCh Array & Generalized List2021-9-26mayan 5.2 數組的順序表示推廣到一般情況，可得到 n 維數組數據元素存儲位置的映象關系 稱為 n 維數組的映象函數。數組元素的存儲數組元素的存儲位置是其下標的線性函數位置是其下標的線性函數其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1nData StructureCh Array & Generalized List2021-9-26mayan 5.2 數組的順序表示例

6、：一個二維數組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數組元素用相鄰的6個字節存儲，存儲器按字節編址。那么，這個數組的體積是 個字節。 設數組a160, 170的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a32,58的存儲地址為 。288LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲什么是

7、壓縮存儲？若多個數據元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。什么樣的矩陣具備壓縮條件？ 一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲對稱矩陣 在一個n階方陣A中，若元素滿足下述性質： aij=aji 1i,j n則稱A為對稱矩陣。 對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節約近一半的存儲空間。Data StructureCh Array & G

8、eneralized List2021-9-26mayan 5.3矩陣的壓縮存儲jiijjjijiik, 12/ ) 1(12/ ) 1(，a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲三角矩陣a1100.0a21a220.0an1an2an3.ann.0a11 a21 a22 a31 a32 an1 ann .k

9、=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲對角矩陣a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4按行序為主序：Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲什么叫稀疏矩陣？假

10、設 m 行 n 列的矩陣含 t 個非零元素，則稱 為稀疏因子稀疏因子通常認為 0.05 的矩陣為稀疏矩陣。稀疏矩陣的壓縮存儲方法:三元組順序表行邏輯聯接的順序表1.十字鏈表nmtADT定義p96Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲 -三元組順序表三元組順序表7600070015000001800000240001400003000000000009120M6 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 i j v0 1 2 3

11、 4 5 6 7Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表#define MAXSIZE 12500 typedefstructint i, j; /該非零元的行下標和列下標 ElemType e; / 該非零元的值 Triple; / 三元組類型typedefstruct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型Data StructureCh Array & Generalized List2021-9-26ma

12、yan 5.3矩陣的壓縮存儲-三元組順序表如何求轉置矩陣？028003600070500140005280000007143600Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表用常規的二維數組表示時的算法for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;其時間復雜度為: O(munu)Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的

13、壓縮存儲-三元組順序表用“三元組”表示時如何實現？解決思路：將矩陣行、列維數互換將每個三元組中的i和j相互調換重排三元組次序方法一：對A中的每一列 col(1col n)，通過從頭至尾掃描三元組表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優先的壓縮存儲表示。Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表Status TransposeSMatrix(TSMatrix M, TSMatrix &T) / 采用三元組順序表存儲表

14、示求稀疏矩陣M的轉置矩陣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) for (p=1; p=M.tu; +p) 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算法分析：結論？O(M的列數nu非零元個數tu) 若 tu 與munu同數量級，則時間復雜度為:)(2numuOData S

15、tructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表方法二：快速轉置即按a.data中三元組次序轉置，轉置結果放入b中恰當位置。此法關鍵是要預先確定M中每一列第一個非零元在b.data中位置，為確定這些位置，轉置前應先求得M的每一列中非零元個數實現：設兩個數組numcol：表示矩陣M中第col列中非零元個數cpotcol：指示M中第col列第一個非零元在b.data中位置顯然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col a.nu)Data StructureCh Arra

16、y & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表7600070015000001800000240001400003000000000009120M1357889colnumcolcpotcol12223241506170Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / 算法5.2 T.mu = M.nu; T.nu = M.mu; T

17、.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) / 求 M 中每一列所含非零元的個數 +numM.datat.j; cpot1 = 1; / 求 M 中每一列的第一個非零元在 b.data 中的序號 for (col=2; col=M.nu; +col) cpotcol = cpotcol-1+numcol-1; for (p=1; p=M.tu; +p) col = M.datap.j; q = cpotcol; T.dataq.i =M.datap.j; T.dataq.

18、j =M.datap.i; T.dataq.e =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrixData StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-三元組順序表算法分析：時間復雜度為 : O(M的列數nu+非零元個數tu)若 tu 與munu同數量級，則時間復雜度為：O(munu) 和經典算法的時間復雜度相同。Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣

19、的壓縮存儲-行邏輯聯接的順序表三元組順序表又稱有序的雙下標法，它的特點是，非零元在表中按行序有序存儲，因此便于進行依行順序處理的矩陣運算。然而，若需隨機存取某一行中的非零元，則需從頭開始進行查找。修改前述的稀疏矩陣的結構定義，增加一個數據成員rpos, 其值在稀疏矩陣的初始化函數中確定。#define MAXRC 500 typedefstruct Triple dataMAXSIZE + 1; intrposMAXRC+1; int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類型Data StructureCh Array & Generalized List2021

20、-9-26mayan 5.3矩陣的壓縮存儲-行邏輯聯接的順序表0 0 50 -1 0 02 0 0 0M= 0 2 1 0-2 4 0 0N= 0 6-1 0 0 4Q=則Q=M*N為： 它們的三元組、和分別為： i j e i j e i j e 1 1 3 1 2 2 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 Q.data M.data N.dataData StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-行邏輯聯接的順序表矩陣乘法的精典算法:

21、for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其時間復雜度為: O(m1n2n1)Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-行邏輯聯接的順序表兩個稀疏矩陣相乘QMN 的過程可大致描述如下： Q初始化; if Q是非零矩陣 / 逐行求積for (arow=1; arow=M.mu; +arow) / 處理M的每一行 ctemp = 0; / 累加器清零 計算Q中第arow行的積并

22、存入ctemp 中； 將ctemp 中非零元壓縮存儲到Q.data；/ for arow/ if Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-行邏輯聯接的順序表Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) / 算法5.3，求矩陣乘積Q=M?N，采用行邏輯鏈接存儲表示。 if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; / Q初始化 if (M.tu*

23、N.tu != 0) / Q是非零矩陣 for (arow=1; arow=M.mu; +arow) / 處理M的每一行 for (l=1; l=M.nu; +l) ctempl = 0; / 當前行各元素累加器清零 Q.rposarow = Q.tu+1; if (arowM.mu) tp=M.rposarow+1; else tp=M.tu+1; Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-行邏輯聯接的順序表 for (p=M.rposarow; ptp;+p) / 對當前行中每一個非零元 brow=

24、M.datap.j; / 找到對應元在N中的行號 if (brow N.mu ) t = N.rposbrow+1; else t = N.tu+1; for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘積元素在Q中列號 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲-行邏輯聯接的順序表for (ccol=1; ccol MAX

25、SIZE) return ERROR; Q.dataQ.tu.i=arow; Q.dataQ.tu.j=ccol; Q.dataQ.tu.e=ctempccol; / if / for arow / if return OK; / MultSMatrixData StructureCh Array & Generalized List2021-9-26mayan 累加器ctemp初始化的時間復雜度為(M.muN.nu)，求Q的所有非零元的時間復雜度為(M.tuN.tu/N.mu)，進行壓縮存儲的時間復雜度為(M.muN.nu)，總的時間復雜度就是總的時間復雜度就是 (M.mu N.nu+M.t

26、u N.tu/N.mu)。若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個數 M.tu = Mmn， N中非零元的個數 N.tu = Nnp，相乘算法的時間復雜度就是 (mp(1+nMN) ，當M0.05 和N0.05及 n 1000時，相乘算法的時間復雜度就相當于 (mp)。5.3矩陣的壓縮存儲-行邏輯聯接的順序表Data StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲 -十字鏈表用十字鏈表表示用途：方便稀疏矩陣的加減運算（p105）；方法：每個非0元素占用5個域（p104） 。rightdowne

27、jiData StructureCh Array & Generalized List2021-9-26mayan 5.3矩陣的壓縮存儲 -十字鏈表M.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 Data StructureCh Array & Generalized List2021-9-26mayan 5.4 廣義表的定義定義：廣義表是線性表的推廣，也稱為列表（lists）記為： LS = ( a1 , a2 , ， an ) 在廣義表中約定： 第一個元素是表頭，而其余元素組成的表稱為表尾； 用小寫字母表示原子類型，用大寫字母表示列表。 廣義表名 表頭(Head） 表尾 (Tail)Data StructureCh Array & Generalized List2021-9-26mayan 5.4 廣義表的定義特點：有次序性：一個直接前驅和一個直接后繼有長度表中元素個數有深度表中括號的重數可遞歸：自己可以作為自己的子表可共享：可以為其他廣義表所共享注意：任何一個非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。Data Structu