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

1、第五章第五章數(shù)組和廣義表數(shù)組和廣義表25.1 多維數(shù)組多維數(shù)組n多維數(shù)組多維數(shù)組是最易處理的非線性結(jié)構(gòu)。因為各元素類型一是最易處理的非線性結(jié)構(gòu)。因為各元素類型一致，各維上下界固定，所以它最容易線性化，致，各維上下界固定，所以它最容易線性化，故可看做是線性表的拓廣。例如：二維數(shù)組可故可看做是線性表的拓廣。例如：二維數(shù)組可以看做是由列向量組成的線性表。以看做是由列向量組成的線性表。n注意注意認(rèn)真研讀數(shù)據(jù)結(jié)構(gòu)書中的抽象數(shù)據(jù)類型定義，認(rèn)真研讀數(shù)據(jù)結(jié)構(gòu)書中的抽象數(shù)據(jù)類型定義，思考其嚴(yán)密性。思考其嚴(yán)密性。35.1 多維數(shù)組多維數(shù)組1. 結(jié)構(gòu)特性結(jié)構(gòu)特性例：二維數(shù)組 ，它屬于兩個向量；i th行和j th列

2、。除邊界外，每個aij恰有兩個直接前驅(qū)和兩個直接后繼。111212122212nnmnmmmnaaaaaaAaaaijmnaA45.1 多維數(shù)組多維數(shù)組n 非線性特征i th行：前驅(qū)aij-1，后繼aij+1j th列：前驅(qū)ai-1j，后繼ai+1j僅有一個開始結(jié)點：a11僅有一個終端節(jié)點：amn其他邊界上的結(jié)點只有一個直接前驅(qū)或一個直接后繼，類似的m維數(shù)組 的每一個元素都屬于m個向量。1 2mnnnA55.1 多維數(shù)組多維數(shù)組2. 存儲一般均采用順序方式存儲，原因是結(jié)構(gòu)中的結(jié)點不變動，內(nèi)存是一維的，必須將多維數(shù)組線性化。 行優(yōu)先（行主序）方式：將(i+1)th行向量緊接在i th行向量之后：

3、特點：列下標(biāo)變化快。Pascal、C等均是此方法。先排最右下標(biāo)（多維）。11 12121 22212 , , , nnmmmna aaa aaa aa65.1 多維數(shù)組多維數(shù)組 列優(yōu)先（列主序）方法特點行下標(biāo)變化最快，先排最左下標(biāo)（可推廣至多維）。Fortan是用此方法。 地址計算 一維存儲地址（內(nèi)部實現(xiàn)）。n基地址開始結(jié)點存儲地址Loc(a11).n維數(shù)每維的上下界（若下界固定，則只須知道維長度）n每個元素占用的單元數(shù)（元素大?。篖11 21112 22212 , , , mmnnmna aaa aaa aa i ja 75.1 多維數(shù)組多維數(shù)組例：行主序 。 A1.m,1.n原理：aij

4、的地址=基址+排在aij之前的元素個數(shù)每 個元素的大小Loc(aij)=Loc(a11)+(i-1)n+(j-1) L 前i-1行結(jié)點總數(shù) 第i行上aij之前的結(jié)點數(shù)在C語言中， 是A0.m-1 , 0.n-1，故有： Loc(aij)=Loc(a00)+in+j LmnAmnA85.1 多維數(shù)組多維數(shù)組n多維推廣：以C為例，行主序。n思考：Ac1.d1 , c2.d2Loc(aij)=Loc(ac1c2)+(i-c1) (d2-c2+1)+(j-c2) L i th行前行數(shù) 第2維長度 i th行aij之前結(jié)點數(shù)1 2n12n0.1,0.1,0.1d ddAAadd1 2.00.012323

5、1()()(.)nj jjnnnnnLoc aLoc ajdddjddjdjL 95.2 矩陣的壓縮存儲矩陣的壓縮存儲n用二維數(shù)組表示的特點：用二維數(shù)組表示的特點：隨機(jī)存取，存儲密隨機(jī)存取，存儲密度為度為1。但對特殊和稀疏矩陣的存儲則浪費空。但對特殊和稀疏矩陣的存儲則浪費空間，尤其是大規(guī)模科學(xué)與工程計算。間，尤其是大規(guī)模科學(xué)與工程計算。5.2.1 特殊矩陣特殊矩陣n有規(guī)律有規(guī)律：壓縮后可找到地址變換公式，保持壓縮后可找到地址變換公式，保持隨機(jī)存取功能。隨機(jī)存取功能。重復(fù)元素分布有規(guī)律零元素105.2 矩陣的壓縮存儲矩陣的壓縮存儲1.對稱陣對稱陣 n階方陣A，若 則稱A為對稱陣。因為矩陣元素關(guān)于

6、主對角線對稱，故只存上三角或下三角元素即可，節(jié)約近一半空間。不失一般性，存儲下三角（包括主對角線），以行主序存儲：元素個數(shù) 0,1,ijjiaai jna00a10a11a20a21a22. an-10an-11.an-1n-110(1)(1)/2niin n115.2 矩陣的壓縮存儲矩陣的壓縮存儲n壓縮存儲：壓縮存儲：將其存于向量sa0.n(n+1)/21中。如何訪問aij？必須將其與sak的對應(yīng)關(guān)系找出來。n地址計算：地址計算： 下三角中有j i.aij之前有i行（0 i-1）第i行上aij之前元素個數(shù)為j(0 j-1). 10(1)(1)/2itti i元素個數(shù)(1)/2ki ij125

7、.2 矩陣的壓縮存儲矩陣的壓縮存儲 上三角中有i j ,只需交換上式的j和i即可得：令I(lǐng)=max (i , j)，J=min (i , j)，則k和i，j之關(guān)系可統(tǒng)一表示為：2.三角矩陣三角矩陣 壓縮方式同上，在sa中多增加一個單元： sa0.n(n+1)/2 將C存于最后一個分量中。(1)/2kj jijiijaa(1)/2kI IJC135.2 矩陣的壓縮存儲矩陣的壓縮存儲3.對角矩陣對角矩陣總結(jié)：這類矩陣壓縮存儲后能找到地址計算公式，使其保持隨機(jī)存取的功能。145.2 矩陣的壓縮存儲矩陣的壓縮存儲 5.2.2 稀疏矩陣稀疏矩陣n定義：定義：設(shè)Amn中有t個非零元素，若 ，稱A為稀疏矩陣。

8、n稀疏因子： 一般非零元素分布無規(guī)律性n壓縮存儲：只存儲非零元，故須存儲輔助信息，才能確定其位置。三元組(i，j，aij)：（行號，列號，非零元的值）唯一確定一個非零元。當(dāng)用三元組表示非零元時，有兩種壓縮方式：順序和鏈?zhǔn)?。tmn0.05tm n155.2 矩陣的壓縮存儲矩陣的壓縮存儲1.三元組順序表（三元組表）三元組順序表（三元組表）以行主序（或列主序）的順序存儲非零元，跳以行主序（或列主序）的順序存儲非零元，跳過零元。得到一個其節(jié)點均是三元組的線性表，過零元。得到一個其節(jié)點均是三元組的線性表，稱此順序存儲結(jié)構(gòu)為三元組表。稱此順序存儲結(jié)構(gòu)為三元組表。#define MaxSize 10000t

9、ypedef int DataTypetypedef struct/三元組int i, j；DataType v;TripleNode;165.2 矩陣的壓縮存儲矩陣的壓縮存儲typedef struct/三元組表TripleNode dataMaxSize;int m, n, t; /行數(shù)，列數(shù)，非零元總數(shù)TripleTable;設(shè)設(shè)a，b是是TripleTable型變量。型變量。n轉(zhuǎn)置運算轉(zhuǎn)置運算4 505008103000200060000A5 401065020030000008000BmnnmAB A ijB ji01,01imjn175.2 矩陣的壓縮存儲矩陣的壓縮存儲4 5050

10、08103000200060000A5 401065020030000008000Bijvo12345a.tMaxSize-1.a.data01504810112321-2306185.2 矩陣的壓縮存儲矩陣的壓縮存儲 方法一：方法一：按A的列序轉(zhuǎn)置。A的列是B的行，故按A的列序轉(zhuǎn)置，所得B是按行主序存放的。基本思想：對A中每列，從頭至尾掃描a.data，找出所有列號為col的三元組(0coln-1)，將它們的行、列號互換后依次放入b.data，即可得行主序表示的B的三元組。正確性：按A的列號遞增序轉(zhuǎn)置，保證B按行號增序排列，B中同一行號的三元組，掃描A時所得三元組 必有iB int p, q

11、, col; if (a.t = 0) Error(“A is empty”); b.m = a.n; b.n = a.m; b.t = a.t ; /行列數(shù)互換 q=0; /指示轉(zhuǎn)置過的三元組 for( col = 0; col a.n ; col+)/對A的每一列號 O(n) for( p = 0; p a.t; p+)/掃描A的三元組表 O(t) if (a.datap.j = col) /找A的列號為col的三元組 b.dataq.i = a.datap.j ; b.dataq.j = a.datap.i ; b.dataq.v = a.datap.v ; q+; 時間復(fù)雜度為O(n*

12、t)，若tmn，則時間復(fù)雜度為O(mn2)205.2 矩陣的壓縮存儲矩陣的壓縮存儲 方法二：按A的行序轉(zhuǎn)置。若簡單的變換a.data的行和列，則b.data為列主序存儲，要重排。但若預(yù)先確定A中每一列（即B中每一行）的第一個非零元在b.data中應(yīng)有的位置，則可正確轉(zhuǎn)置。位置向量：00 /0 110.1potApot colpot colcolcolan的第 列起址第列非零元個數(shù)215.2 矩陣的壓縮存儲矩陣的壓縮存儲n思想 先求出A中每一列的非零元個數(shù)，可將第col列的非零元個數(shù)記入potcol+1中。step1：初始化將所有pot中元素清0./O(n)step2：掃描a.data，將列號為

13、col的非零元個數(shù)累加到potcol+1中。/O(t)step3：令potcol=potcol-1+potcol 1cola.n-1/O(n)step4：掃描a.data，將(i,col,v)轉(zhuǎn)置后放于b.datapotcol中，potcol+./O(t)key：pot1.a.n=第0a.n-1列的非零元個數(shù)。時間復(fù)雜度為O(n+t)，若tmn，則時間復(fù)雜度為O(mn)225.2 矩陣的壓縮存儲矩陣的壓縮存儲void FastTransMatrix(TripleTable &a , Tripletable &b) /pot0.a.n，比n多1if (a.t = 0) Error

14、(“”);/A全零b.m = a.n; b.n = a.n; b.t = a.t;for ( col = 0; col=a.n ; col+) potcol = 0; /step1初始化 for ( p = 0; p a.t; p+) / step2掃描a.data pota.datap.j + 1+; /設(shè)a.datap.j = col pota.n是哨兵for ( col = 1; col a.n; col+)/step3. pota.n無用，但第二個循環(huán)須統(tǒng)計 potcol = potcol 1 + potcol;for ( p = 0; p a.t; p+) /step4 col =

15、a.datap.j; /當(dāng)前三元組列號. q = potcol+; b.dataq.i = a.datap.j; b.dataq.j = a.datap.i; b.dataq.v = a.datap.v;235.2 矩陣的壓縮存儲矩陣的壓縮存儲以上圖為例，2.帶行表的三元組表。（順序方式）在行優(yōu)先存儲的三元組表中，加入一個行表來記錄稀疏矩陣壓縮后每行非零元在三元組表中的起始位置。4 5A245.2 矩陣的壓縮存儲矩陣的壓縮存儲3.十字鏈表上兩種方式是順序存儲，若非零元位置或個數(shù)經(jīng)常發(fā)生變化，會引起結(jié)點移動，效率降低。此時宜用鏈?zhǔn)酱鎯?。例：矩陣相加操?AA+B稀疏矩陣的鏈接存儲方式有多種，這里

16、僅介紹十字鏈表n結(jié)點結(jié)構(gòu)n存儲結(jié)構(gòu)分別設(shè)兩個指針數(shù)組作為各行、列單鏈表的頭指針。255.2 矩陣的壓縮存儲矩陣的壓縮存儲typedef struct CLNodeint i, j ;DataType v;struct CLNode * right, *down;CLNode;typedef struct CLNode *rheadMaxRow; /行鏈表頭指針，MaxRow在前定義CLNode *cheadMaxCol; /列int m,n, t;CrossList;CrossList A;265.2 矩陣的壓縮存儲矩陣的壓縮存儲每個結(jié)點是在“十字”路口，可鏈成循環(huán)鏈表。稀疏矩陣壓縮后失去“隨

17、機(jī)存取”的功能。01510112321-230604801234A.cheadA.rhead275.3 廣義表（廣義表（Lists）1.概念概念是線性表的推廣，如將線性表中元素是線性表的推廣，如將線性表中元素ai放寬到可以是自放寬到可以是自身的結(jié)構(gòu)。身的結(jié)構(gòu)。n定義：定義： ，它由，它由n個元素構(gòu)成的有限個元素構(gòu)成的有限序列，其中序列，其中ai或是原子，或是廣義表（子表）。或是原子，或是廣義表（子表）。LS-名字，名字，n-長度長度，n=0為空表。為空表。一般用小寫字母表示原子，大寫字母表示子表。一般用小寫字母表示原子，大寫字母表示子表。n表頭、表尾、深度表頭、表尾、深度若若 ，則，則a1成為

18、成為表頭表頭（首），剩余元素構(gòu)成的表（首），剩余元素構(gòu)成的表 為為表尾表尾。廣義表是遞歸定義的，展開到每一。廣義表是遞歸定義的，展開到每一元素均為原子時括號的最大層數(shù)為元素均為原子時括號的最大層數(shù)為深度深度。 12( ,),0nLSa aanLS 2(,)naa285.3 廣義表（廣義表（Lists）n例：例：E=( ) 空表，長度空表，長度n = 0，深度，深度d = 1.L=(a, b) n = 2，d = 1. （線性表）（線性表）A=(x, L)=(x, (a, b) n=2, d=2. a1為原子，為原子，a2為子表為子表B=(A, y)=(x, (a, b), y) n = 2,

19、d = 3.C=(A, B)=(x, (a, b), (x, (a, b), y) n = 2, d = 4.D=(a, D)=(a, (a, (a, () n = 2, d = .n若規(guī)定任何表都有名字，則可在每個表前冠名。若規(guī)定任何表都有名字，則可在每個表前冠名。E( ) L(a, b) A(x, L(a, b)295.3 廣義表（廣義表（Lists）n運算求表頭、表尾。head(A) = x, tail(A) = (a, b) /表尾是表，表頭不一定表尾是表，表頭不一定head(tail(A) = (a, b) 表表, tail(tail(A) = ( )Note： 和和 不同。不同。

20、為空表為空表n=0n=0，不能求表頭和表尾。，不能求表頭和表尾。 為非空表，為非空表，n=1. n=1. 可求表頭和尾：可求表頭和尾： head( head( tail(A) = atail( head( tail(A) = (b) 原子表head( tail( head( tail(A) = btail( tail( head( tail(A) = ( ) 原子表( )( )( )( )head ( ) ( ), tail ( ) ( )305.3 廣義表（廣義表（Lists）2.存儲結(jié)構(gòu)因為廣義表數(shù)據(jù)元素可具有不同結(jié)構(gòu)，故難以用順序方式存儲。一般用鏈接方式存儲，稱之為廣義鏈表。(1) 廣義

21、表的頭尾鏈表表示方法。n表結(jié)點：n原子結(jié)點：1hptptag0atom表結(jié)點，使用和原子結(jié)點，使用315.3 廣義表（廣義表（Lists）n圖示E=NIL325.3 廣義表（廣義表（Lists）n特點 除空表的表頭指針為空外，頭指針均指向表結(jié)點。 任一表結(jié)點的hp均指向表頭部（原子結(jié)點或表結(jié)點）任一表結(jié)點的tp均指向表尾部（當(dāng)表尾部為空表時，tp=NIL，否則必指向表結(jié)點） 易分清表中原子和子表所在層次。如x、L在第一層，a、b在第二層。 最高層的表結(jié)點數(shù)即為廣義表的長度。 浪費空間，易求表長和表深度。335.3 廣義表（廣義表（Lists）(2) 單鏈表示法模仿線性表的單鏈表結(jié)構(gòu)，當(dāng)所有元素

22、為原子時，等價于單鏈表模仿線性表的單鏈表結(jié)構(gòu)，當(dāng)所有元素為原子時，等價于單鏈表。n結(jié)點結(jié)構(gòu)：n圖示：圖示：E=NILC=(A, B)=(x, (a, b), (x, (a, b), y) =(A(x, L(a, b), B(A(x, L(a, b), y)0slinkatom1data 本 結(jié) 點 為 子 表 （指 向 子 表 的 第 一 個 結(jié) 點 ）本 結(jié) 點 為 原 子 （）345.3 廣義表（廣義表（Lists）n存儲結(jié)構(gòu)說明typedef struct GLNodeint atom; /亦可定義為枚舉類型，標(biāo)志域struct GLNode *slink; /指向同層后繼union struct GLNode *slink; /指向子表的第一個結(jié)點DataType data； /原子結(jié)點數(shù)據(jù)域optval; /候選值 *GList;355.3 廣義表（廣義表（Lists）n缺點： 若要在某一表中開始處插入或刪除一個結(jié)點，則要找出所有指向該結(jié)點的指針，逐一加以修改。例如，上圖中，刪除A表中的x，修改A的頭指針外，須修改來自于B、C表的指針，引用來源點不