數(shù)據(jù)結構ch.5數(shù)組和廣義表

1、數(shù) 據(jù) 結 構 Ch.5數(shù)組和廣義表,計 算 機 學 院 肖明軍Email: xiaomj@ustc.edu.cnhttp://staff.ustc.edu.cn/~xiaomj,,2,§5.1 多維數(shù)組,多維數(shù)組是最易處理的非線性結構。因為各元素類型一致，各維上下界固定，所以它最容易線性化，故可看做是線性表的拓廣。例如：二維數(shù)組可以看做是由列向量組成的線性表。,,3,§5.1 多維數(shù)組,結構特性

2、例：二維數(shù)組 ，它屬于兩個向量；i th行和j th列。除邊界外，每個aij恰有兩個直接前驅和兩個直接后繼。,,4,§5.1 多維數(shù)組,非線性特征i th行：前驅aij-1，后繼aij+1j th列：前驅ai-1j，后繼ai-1j僅有一個開始結點：a11僅有一個終端節(jié)點：amn其他邊界上的結點只有一個直接前驅或一個直接后繼，類似的m維數(shù)組 的每一個元素都屬于

3、m個向量。,,5,§5.1 多維數(shù)組,存儲一般均采用順序方式存儲，原因是結構中的結點不變動，內(nèi)存是一維的，必須將多維數(shù)組線性化。行優(yōu)先（行主序）方式：將(i+1)th行向量緊接在i th行向量之后：特點：列下標變化快。Pascal、C等均是此方法。先排最右下標（多維）。,,6,§5.1 多維數(shù)組,列優(yōu)先（列主序）方法特點行下標變化最快，先排最左下標（可推廣至多維）。Fortan是用此方法。地址

4、計算 一維存儲地址（內(nèi)部實現(xiàn)）?；刂贰_始結點存儲地址Loc(a11).維數(shù)——每維的上下界（若下界固定，則只須知道維長度）每個元素占用的單元數(shù)（元素大?。篖,,7,§5.1 多維數(shù)組,例：行主序 。 A[1..m,1..n]原理：aij的地址=基址+排在aij之前的元素個數(shù)×每 個元素的大小Loc(aij)=Loc(a11)+[(i-1)

5、15;n+(j-1)] ×L 前i-1行結點總數(shù) 第i行上aij之前的結點數(shù)在C語言中， 是A[0..m-1 , 0..n-1]，故有： Loc(aij)=Loc(a00)+[i×n+j] ×L,,8,§5.1 多維數(shù)組,多維推廣：以C為例，行主序。思考：A[c1..d1 , c2..d2]Loc(aij)=Loc(ac1c2

6、)+[(i-c1) ×(d2-c2+1)+(j-c2)] ×L i th行前行數(shù) 第2維長度 i th行aij之前結點數(shù)特點：隨機存取。,,9,§5.2 矩陣的壓縮存儲,用二維數(shù)組表示的特點：隨機存取，存儲密度為1。但對特殊和稀疏矩陣的存儲則浪費空間，尤其是大規(guī)?？茖W與工程計算。§5.2.1 特殊矩陣有規(guī)律：壓縮

7、后可找到地址變換公式，保持隨機存取功能。,,10,§5.2 矩陣的壓縮存儲,對稱陣 n階方陣A，若 則稱A為對稱陣。因為矩陣元素關于主對角線對稱，故只存上三角或下三角元素即可，節(jié)約近一半空間。不失一般性，存儲下三角（包括主對角線），以行主序存儲：元素個數(shù),,11,§5.2 矩陣的壓縮存儲,壓縮存儲：將其存于向量sa[0..

8、n(n+1)/2－1]中。如何訪問aij？必須將其與sa[k]的對應關系找出來。地址計算：下三角中有j ≤ i.aij之前有i行（0 ~ i-1）第i行上aij之前元素個數(shù)為j(0 ~ j-1).,,12,§5.2 矩陣的壓縮存儲,上三角中有i < j ,只需交換上式的j和i即可得：令I=max (i , j)，J=min (i , j)，則

9、k和i，j之關系可統(tǒng)一表示為：三角矩陣 壓縮方式同上，在sa中多增加一個單元： sa[0..n(n+1)/2] 將C存于最后一個分量中。,,13,§5.2 矩陣的壓縮存儲,對角矩陣總結：這類矩陣壓縮存儲后能找到地址計算公式，使其保持隨機存取的功能。,,14,§5.2 矩陣的壓縮存儲,§ 5.2.2 稀疏矩陣定義：設Amn中有t個非零元素

10、，若 ，稱A為稀疏矩陣。稀疏因子： 一般非零元素分布無規(guī)律性壓縮存儲：只存儲非零元，故須存儲輔助信息，才能確定其位置。三元組(i，j，aij)：（行號，列號，非零元的值）唯一確定一個非零元。當用三元組表示非零元時，有兩種壓縮方式：順序和鏈式。,,15,§5.2 矩陣的壓縮存儲,三元組順序表（三元組表）以行主序（或列主序）的順序存儲非零元，

11、跳過零元。得到一個其節(jié)點均是三元組的線性表，稱此順序存儲結構為三元組表。#define MaxSize 10000typedef int DataTypetypedef struct{//三元組int i, j；DataType v;}TripleNode;,,16,§5.2 矩陣的壓縮存儲,typedef struct{//三元組表TripleNode data[MaxSize];int m, n,

12、t; //行數(shù)，列數(shù)，非零元總數(shù)}TripleTable;設a，b是TripleTable型變量。轉置運算,,17,§5.2 矩陣的壓縮存儲,,18,§5.2 矩陣的壓縮存儲,方法一：按B的次序或按A的列序轉置?！逜的列是B的行，故按A的列序轉置，所得B是按行主序存放的?；舅枷耄簩中每列，從頭至尾掃描a.data，找出所有列號為col的三元組(0≤col≤n-1)，將它們的行、列號互換后依次放入

13、b.data，即可得行主序表示的B的三元組。正確性：∵按A的列號遞增序轉置，保證B按行號增序排列，B中同一行號的三元組，掃描A時所得三元組 必有i<j，轉置后保證按B的列號增序排列。例，上圖。,,19,§5.2 矩陣的壓縮存儲,void TransMatrix（TripleTable &a, TripleTable &b) {//A=>B

14、 int p, q, col; if (a.t == 0) Error(“A is empty”); b.m = a.n; b.n = a.m; b.t = a.t ; //行列數(shù)互換 q=0; //指示轉置過的三元組 for( col = 0; col < a.n ; col++)//對A的每一列號 for( p = 0; p < a.t; p++)//掃描A的三元組表

15、 if (a.data[p].j == col) {//找A的列號為col的三元組 b.data[q].i = a.data[p].j ; b.data[q].j = a.data[p].i ; b.data[q].v = a.data[p].v ; q++; }},,20,§5.2 矩陣的壓縮存儲,方法二：按A的行序轉置。

16、若簡單的變換a.data的行和列，則b.data為列主序存儲，要重排。但若預先確定A中每一列（即B中每一行）的第一個非零元在b.data中應有的位置，則可正確轉置。位置向量：,,21,§5.2 矩陣的壓縮存儲,思想 先求出A中每一列的非零元個數(shù)，可將第col列的非零元個數(shù)記入pot[col+1]中。step1：初始化將所有pot中元素清0.//O(n)step2：掃描a.data，將列號為

17、col的非零元個數(shù)累加到pot[col+1]中。//O(t)step3：令pot[col]=pot[col-1]+pot[col] 1≤col≤a.n-1//O(n)step4：掃描a.data，將(i,col,v)轉置后放于b.data[pot[col]]中，pot[col]++.//O(t)時間O(n+t)，快速。key：pot[1..a.n]=第0~a.n-1列的非零元個數(shù)。,,22,§5.2 矩陣的壓

18、縮存儲,void FastTransMatrix(TripleTable &a , Tripletable &b) {//pot[0..a.n]，比n多1if (a.t == 0) Error(“…”);//A全零b.m = a.n; b.n = a.n; b.t = a.t;for ( col = 0; col<=a.n ; col++) pot[col] = 0; //step1初始化 fo

19、r ( p = 0; p < a.t; p++) // step2掃描a.data pot[a.data[p].j + 1]++; //設a.data[p].j = col for ( col = 1; col < a.n; col++)//step3. pot[a.n]無用 pot[col] = pot[col – 1] + pot[col];for ( p = 0; p <

20、; a.t; p++) {//step4 col = a.data[p].j; //當前三元組列號. q = pot[col]++; b.data[q].i = a.data[p].j; b.data[q].j = a.data[p].i; b.data[q].v = a.data[p].v;}},,23,§5.2 矩陣

21、的壓縮存儲,以上圖為例，帶行表的三元組表。（順序方式）在行優(yōu)先存儲的三元組表中，加入一個行表來記錄稀疏矩陣壓縮后每行非零元在三元組表中的起始位置。,,24,§5.2 矩陣的壓縮存儲,十字鏈表上兩種方式是順序存儲，若非零元位置或個數(shù)經(jīng)常發(fā)生變化，會引起結點移動，效率降低。此時宜用鏈式存儲。例：A←A+B稀疏矩陣的鏈接存儲方式有多種，這里僅介紹十字鏈表結點結構存儲結構分別設兩個指針數(shù)

22、組作為各行、列單鏈表的頭指針。,,25,§5.2 矩陣的壓縮存儲,typedef struct CLNode{int i, j ;DataType v;struct CLNode * right, *down;}CLNode;typedef struct {CLNode *rhead[MaxRow]; //行鏈表頭指針，MaxRow在前定義CLNode *chead[MaxCol]; //列…in

23、t m,n, t;}CrossList;CrossList A;,,26,§5.2 矩陣的壓縮存儲,,27,§5.3 廣義表（Lists）,概念是線性表的推廣，如將線性表中元素ai放寬到可以是自身的結構。定義： ，它由n個元素構成的有限序列，其中ai或是原子，或是廣義表（子表）。LS-名字，n-長度，n=0為空表。一般用小寫字母表示原子

24、，大寫字母表示子表。表頭、表尾、深度若 ，則a1成為表頭（首），剩余元素構成的表 為表尾。廣義表是遞歸定義的，展開到每一元素均為原子時括號的最大層數(shù)為深度。,,28,§5.3 廣義表（Lists）,例：E=( ) ——空表，長度n = 0，深度d = 1.L=(a, b) ——n = 2，d = 1. （線性表）A=(x, L)=(x, (a, b

25、)) ——n=2, d=2. a1為原子，a2為子表B=(A, y)=((x, (a, b)), y) ——n = 2, 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 = ∞.若規(guī)定任何表都有名字，則可在每個表前冠名。E( ) L(a, b) A(x,

26、 L(a, b)),,29,§5.3 廣義表（Lists）,圖示各種表之關系,,30,§5.3 廣義表（Lists）,運算求表頭、表尾。head(A) = x, tail(A) = ((a, b)) //表尾是表，表頭不一定head(tail(A)) = (a, b) ——表Note： 和 不同。 為空表n=0，不能求表頭和表尾。

27、 為非空表，n=1. 可求表頭和尾：,,31,§5.3 廣義表（Lists）,存儲結構因為廣義表數(shù)據(jù)元素可具有不同結構，故難以用順序方式存儲。一般用鏈接方式存儲，稱之為廣義鏈表。廣義表的頭尾鏈表表示方法。表結點：原子結點：存儲結構見書上說明,,32,§5.3 廣義表（Lists）,圖示E=NIL,,33,§5.3 廣義表（Lists）,特點除空表的表頭指針為

28、空外，頭指針均指向表結點。任一表結點的hp均指向表頭部（原子結點或表結點）任一表結點的tp均指向表尾部（當表尾部為空表時，tp=NIL，否則必指向表結點）易分清表中原子和子表所在層次。如x、L在第一層，a、b在第二層。最高層的表結點數(shù)即為廣義表的長度。浪費空間，易求表長和表深度。,,34,§5.3 廣義表（Lists）,(2) 單鏈表示法模仿線性表的單鏈表結構，當所有元素為原子時，等價于單鏈表。結點結構

29、：圖示：E=NILC=(A, B)=((x, (a, b)), ((x, (a, b)), y)) =(A(x, L(a, b)), B(A(x, L(a, b)), y)),,35,§5.3 廣義表（Lists）,存儲結構說明typedef struct GLNode{int atom; //亦可定義為枚舉類型，標志域struct GLNode *slink; //指向同層后繼

30、union {struct GLNode *slink; //指向子表的第一個結點DataType data； //原子結點數(shù)據(jù)域}optval; //候選值} *GList;,,36,§5.3 廣義表（Lists）,缺點：若要在某一表中開始處插入或刪除一個結點，則要找出所有指向該結點的指針，逐一加以修改。例如，上圖中，刪除A表中的x，修改A的頭指針外，須修改來自于B、C表的指針，引用來源點不

31、易知道。刪除一個表可能導致錯誤。例如，刪除A表時，A的所有結點釋放后，會引起B(yǎng)、C表的錯誤。,,37,§5.3 廣義表（Lists）,改進引入表頭結點，使子表內(nèi)部的變化不會涉及外部元素的變化，插刪第一個結點方便。頭結點和其他結點結構相同，只是以示區(qū)別：刪除表時，頭結點引用計數(shù)減1，僅當引用計數(shù)為0時，才釋放表中所有結點。,,38,§5.3 廣義表（Lists）,(3)雙鏈表示法該方法類似于

32、第6章的二叉鏈表。結點結構存儲說明typedef struct GLNode{DataType data; //子表名字或原子數(shù)據(jù)struct GLNode *link1, *link2;} *GList;,,39,§5.3 廣義表（Lists）,圖示特點簡潔方便，類似于二叉鏈表，可借助于二叉鏈表表示處理，易求長度深度。在表結點中保存了子表的名字信息，有時子表