稀疏矩陣與廣義表

1、數(shù) 據(jù) 結(jié) 構(gòu)一、數(shù)據(jù)結(jié)構(gòu)：（1）定義：數(shù)據(jù)之間的關(guān)系（2）邏輯結(jié)構(gòu)：數(shù)據(jù)之間的形式上的關(guān)系（3）物理結(jié)構(gòu)：數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)采用不同的存儲結(jié)構(gòu)，將引起不同的處理方法，即算法也不相同。1二、數(shù)據(jù)結(jié)構(gòu)的描述：1、描述方法：用二元組表示，B=( K, R ) 其含義是：B是一種數(shù)據(jù)結(jié)構(gòu)，K表示K個數(shù)據(jù)元素，R表示元素之間的關(guān)系。 這里R可以是多個關(guān)系，我們主要研究 R1 的關(guān)系2、例如：一種數(shù)據(jù)結(jié)構(gòu)表示如下： LLL（K , R） K= 01, 02 , 03, 04, 05 , 06 ,07 , 08 , 09 ,10 R= r r = , , , , , , 2例題2、一種數(shù)據(jù)結(jié)構(gòu)tree=

2、( K , R ) K= 01, 02 , 03, 04, 05 , 06 ,07 , 08 , 09 ,10 R= r r = , , , , , , , 三、算法的時間復雜性和空間復雜性1、時間復雜性 ：取決于循環(huán)次數(shù)和循環(huán)嵌套層數(shù)O(log2n) O ( n) O(n log2n ) O(n2 ) O(2n) O( n! ) 2、空間復雜性計算：存儲單元的多少，主要在于數(shù)組單元3 數(shù)據(jù)之間的關(guān)系 一 、線性關(guān)系： 1、L1=（ a, b, c , f , h , x , z ) ; 2、L2=（ 34，56，12，78，45，86 ， 100 ） L= （ a1, a2 ,a3, a4

3、, , an ) 二、非線性關(guān)系 4三、線性表 1、線性表、線性鏈表 2、棧、鏈接棧 3、隊列、鏈接隊列 5 四、關(guān)于線性鏈表的幾點說明：（1）結(jié)點 ： 數(shù)據(jù)域 指針域 （2）線性鏈表的幾種形式： 單向鏈表、雙向鏈表、循環(huán)鏈表其特點如下：6 在循環(huán)鏈表中，為了方便插入和刪除操作，一般加入頭結(jié)點 線性表的基本操作： （1）建立線性表 （2）插入結(jié)點、刪除結(jié)點 （3）求線性表的長度 （4）查找 （5）線性表的排序 （6）線性表的歸并運算7插入結(jié)點的操作：插入到頭結(jié)點: 插入到某一個結(jié)點 ： 插入到尾部:P.next:=head; P.next:=q.next; r.next :=p; head:=

4、 p; q.next:=p ; r := p ; q:= x ;8 刪除操作 ： 刪除頭結(jié)點 刪除某一個結(jié)點 P：=head ; q.next := p.next ; Head:=head.next; dispose ( p ) ; Dispose (p);9 五、棧的操作： 1、進棧 （壓棧） 2、出棧 （彈棧） 3、主要應用于：遞歸、回溯算法、深度搜索等算法 六、隊列操作： 1、進隊 2、出隊 3、主要應用于：搜索算法（寬度搜索）、進程管理等 10第五節(jié) 稀疏矩陣與廣義表一、稀疏矩陣 1、矩陣： 由一組行列組成的數(shù)字陣列，稱為矩陣。如下圖： 1 2 3 4 5 3 -10 6 1 2 1

5、7 9 4 -3 7 2 1 0 2 5 -1 3 -1 8 0 -2 2 4 2、矩陣的存儲方法： （1）一般用二維數(shù)組，數(shù)據(jù)之間的關(guān)系：行、列線性， 存儲結(jié)構(gòu)：由行、列唯一確定一個元素的位置 （2）用線性鏈接表的結(jié)構(gòu)存儲矩陣11一般矩陣存儲都采用順序存儲結(jié)構(gòu)，便于訪問和操作。123、稀疏矩陣：（1）定義： 矩陣中非零元素的個數(shù)遠遠少于零元素的個數(shù)，這樣的矩陣稱為非零矩陣。 如下圖所示： 1 2 3 4 5 6 3 0 0 5 0 0 1 0 0 -2 0 0 0 2 1 0 4 0 6 0 3 0 0 0 0 0 0 4 0 0 -1 0 0 0 5 13二、稀疏矩陣1、矩陣中非零元素的個

6、數(shù)遠遠少于零元素的個數(shù)，這樣的矩陣稱為非零矩陣。2、存儲方法：三元組存儲法，設稀疏矩陣按行、列號從小到大順序排列。如書圖（3-16），變?yōu)橐粋€線性表 順序存儲(1) 用一個二維數(shù)組A0.m ,1.3 : integer (2) 存儲方法：a0,1存放非零元素個數(shù)，a0,2總行數(shù) a0,3存放總列數(shù) (3) 按行存放：每個非零元素所在行、列數(shù)以及值（p.72) 鏈接存儲：設定一個一維的指針記錄數(shù)組每個單元是一個鏈表，鏈接是本行的非零元素（p.73）143、稀疏矩陣運算：轉(zhuǎn)置運算（p.75) 轉(zhuǎn)置運算優(yōu)化（快速轉(zhuǎn)置, p.75）加法運算(p.76)15 A 1 2 3 0 1 2 3 4 5 6

7、7 用順序存儲結(jié)構(gòu)表示三元組存儲非零元素的個數(shù) A0，1=5，A0，2=6， A0，3=7 A1，1=1 ，A1，2=1，A1，3=3 A2，1=1 ，A2，2=4，A2，3=556711314523-231133435633-1存儲方法： A0,1存放整個矩陣的非零元素個數(shù)， A0,2總行數(shù)， A0,3存放總列數(shù) 按行存放：每個非零元素所在行、列數(shù)以及本身值16鏈接存儲：設定一個數(shù)組，其類型為指針，該指針類型有4個域： type matnode =record row ,col :integer ; val : integer ; next : matnode ; end ; var A :

8、array 1.5 of matnode數(shù)組的每個單元是一個結(jié)點，它將鏈接本行的非零元素。因此，這是一種將順序存儲與動態(tài)存儲有機結(jié)合的存儲方法。 存儲結(jié)構(gòu)圖如下：17 A 數(shù)組1234514522-235653-118 三、稀疏矩陣運算： 1、轉(zhuǎn)置運算 所謂矩陣轉(zhuǎn)置是指將矩陣的行、列數(shù)據(jù)進行轉(zhuǎn)換即第一行變?yōu)榈谝涣?，第二行變?yōu)榈诙小?一般的轉(zhuǎn)置方法是通過雙重循環(huán)，將行列值交換。稀疏矩陣的轉(zhuǎn)換方法是： 1 2 3 4 5 1 2 3 4 5 6 3 0 1 0 0 3 0 0 5 0 0 1 0 0 0 0 0 0 0 -2 0 0 0 2 0 -2 4 0 -1 1 0 4 0 6 0 3 5

9、 0 0 0 0 0 0 0 0 0 0 4 0 0 6 0 0 0 0 -1 0 0 0 5 0 0 0 0 0 19（1）用三元組方法存儲原稀疏矩陣A數(shù)組（設m行、n列），t個非零元素（2）轉(zhuǎn)換后的矩陣為B數(shù)組（T行，N列）： B0，1=n，B0，2=m，B0，3=t （3）對A數(shù)組進行T次掃描，其方法是： 第一次掃描，將A數(shù)組中非零元素的列值為1所有單元，按照從上到下（行號從小到大）順序?qū)懭隑數(shù)組中。第二次掃描，將A數(shù)組中非零元素的列值為2的所有單元，按照同樣方法，再寫入B數(shù)組。寫入的方法是：將A數(shù)組的行、列、本身值依次賦給B數(shù)組的列、行、本身值算法如下：20Procedure tran

10、smat( A,B) ; 本題的時間復雜性 ：？ begin m:=a0,1 ; n:=a0,2 ; t:= a0,3 ; b0,1:=n ; b0,2 := m ; b0,3:= t ; if t=0 then return ; q:=1 ; for col := 1 to n do for p:= 1 to t do if ap,2 = col then begin bq,1 :=ap,2 ; bq,2:=ap,1; bq,3:=ap,3 ; q:=q+1 ; end; end; 21方法二：（1）對數(shù)組A進行兩次掃描，首先掃描A數(shù)組中的每一列非零元素的個數(shù)，并得到每一列的第一個非零元素在

11、B數(shù)組中的位置；（2）第二次掃描，將A數(shù)組的每個三元組寫入到B數(shù)組的相應位置。（3）細化： 用num 數(shù)組統(tǒng)計原矩陣中每列的非零元素的個數(shù)，用pot 數(shù)組記錄下一個非零元素在B數(shù)組中的存儲位置（B的行號） 計算式： pot1:=1 ; potcol:=potcol-1 + numcol-1 ; 由數(shù)組A 可以得到num 數(shù)組與pot數(shù)組的初始值： 22其算法如下： procedure fasttrans(A, B ) ; begin (1) m:=a0,1 ; n:=a0,2 ; t:= a0,3 ; (2) b0,1:=n ; b0,2 := m ; b0,3:= t ; (3) if t=

12、0 then return ; (4) for col:=1 to n do numcol:= 0 ; (5) for I:=1 to t do numaI,2 := numaI,2+1 ; (6) pot1:=1 ; for col:=2 to n do potcol:=potcol-1 + numcol-1 ; 23For I:=1 to t do begin col:=AI,2; q:= pot col ; Bq,1:=AI,2 ; Bq,2:=AI,1 ; Bq,3:=AI,3; potcol:=potcol+1 ; end;End;2、矩陣加法運算： （1）一般矩陣加法運算的方法：將

13、兩個矩陣中對應的行、列元素進行加法運算一一對應，求和。(A:=A+B ) （2）稀疏矩陣加法（用順序存儲的三元組方法） （3）用線性鏈接表的方法，進行矩陣加法計算 24其算法：Procedure juzhenjiafa(a ,b , n) ; type point= node ; node=record da : integer ; x,y : integer ; next :point ; end ; var a,b : array1.100 of point ; p,q,r : point ; begin (1) 建立兩個稀疏矩陣（鏈式）(2) For I:=1 to n do q:=AI

14、 ; p:= q.next ; r:=BI.next ; ( 原先的兩個鏈表都帶有頭結(jié)點）25 (3) while (p nil) and ( r nil ) do begin if q.x r.x then q:=p; p:=p.next ; if q.x= r.x then if p .da+r.da 0 then p.da:= p.da+r.da ; q:=p ; p:=p.next else q.next :=p.next ; p:=p.next ; r:=r.next if p.colr.col then s:=r.next ; q.next:=r ; r.next:=p ;q:=r

15、; r:=s end ; (4) if p=nil then p.next:= r ;End; 26矩陣乘法：矩陣乘法 ：A M，N* BN，T = CM，T例如： 27一般矩陣乘法的運算方法：（1）A、B兩矩陣必須滿足如下條件： A矩陣的列數(shù)與B矩陣的行數(shù)相同，即：A K，T，BT，X 得到新的矩陣：CK，X（2）乘法方法：將A矩陣的一行的每個元素，對應乘以B矩陣的每一列的元素，其代數(shù)和為當前新矩陣的一個元素值。（3）程序?qū)崿F(xiàn)的方法： 建立三個數(shù)組 ，其行列個數(shù)，根據(jù)需要設定 輸入兩個矩陣，并輸出 利用三重循環(huán)語句完成矩陣乘法運算。 稀疏矩陣的乘法運算：用三元組存儲方法，計算兩個矩陣相乘28

16、廣義表一、廣義表1、定義：線性表的推廣。廣義表是指一個表或者是空表或是一個非空元素組成的表。其元素可以是某個確定類型的元素，也可以是子表組成。（a1, a2, a3, B4, a5 , a6 , B7 an) 其中B4、B7分別為一個子表。B4=（b1, b2, b3,bi) , B7=( d1,d2,dj)例如：A=（ ），B=（e）， C=( a, ( b, c, d ) ) D=(A ,B , C )=( ( ), (e), ( a,( b, c, d ) ) )29E=(a, (a ,b),(a,b),c ) )注意： 廣義表通常用圓括號括起來，用逗號分隔其中的元素。 為了區(qū)分原子和子

17、表，書寫時用大寫字母表示廣義表的子表，用小寫字母表示原子。 若廣義表 L 非空(n1)，則al是L的表頭，其余元素組成的表(a1，a2，an)稱為L的表尾。 廣義表是遞歸定義的 30 2、 廣義表常用表示 E=( )E是一個空表，其長度為0。 L=(a，b)L是長度為2的廣義表，它的兩個元素都是原子，因此它是一個線性表 A=(x，L)=(x，(a，b)A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。 B=(A，y)=(x，(a，b)，y) B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。31 C=(A，B)=(x，(a，b)，(x，(a，b)，y) C的長度為2，兩

18、個元素都是子表。 D=(a，D)=(a，(a，(a，()D的長度為2，第一個元素是原子，第二個元素是D自身，展開后它是一個無限的廣義表。 3、 廣義表的深度一個表的深度是指表展開后所含括號的層數(shù)。 【例】表L、A、B、C的深度為分別為1、2、3、4，表D的深度為。 32 4、廣義表的結(jié)構(gòu)圖：A=（ ），B=（e）， C=( a, ( b, c, d ) ) D=(A ,B , C )=( ( ), (e), ( a,( b, c, d ) ) )樹形結(jié)構(gòu)335、廣義表的運算： （ p. 80) (1) 計算廣義表的長度 (2) 廣義表的輸入和輸出 (3) 建立廣義表6、廣義表的應用：建立廣義表

19、輸入廣義表，輸出廣義表34二、廣義表的存儲結(jié)構(gòu) 由于廣義表中元素及子表中的元素多少不固定，所以一般用動態(tài)鏈接結(jié)構(gòu)。 結(jié)點表示 ： A= NIL ， B C Tag(0,1) da(或link)Next 0ed035練習：畫出下列廣義表的鏈接存儲結(jié)構(gòu) A=（a,b,c ) ; B=(a,(b,(c) ; C=(a,b),(c,d) ; D=(a ,(b,(c,d),(e) ； E=(a,(b,( ) ,c),(d) ,e)。三、 廣義表類型定義方法及操作： 1. 定義： type node=record tag : 0.1; 0： 表示元素，1 ：表示子表 next :node; case ta

20、g of 0: da:integer ; char 1: link: node ; end;36 2. 廣義表的操作： 建立廣義表、 輸出廣義表 求廣義表的表頭和表尾 (3) 計算廣義表的深度:所有子表中最大深度加 1例題1：建立廣義表的算法 元素之間用“，”分開，表元素的開始結(jié)束符號用“（）”，空表用（ ）表示。設用“；”號作為表的結(jié)束符號。（加一個表頭結(jié)點） E=(a,( b, ( ) , c), ( d ) , e) ；37Procedure creat ( var po: node) ; begin (1) read(ch); (2) case ch of : po = nil ; (

21、: new(po) ;po.tag:=1; creat(po.link); a.z: new(po); po.tag:=0; po.da:=ch; end ; (3) read(ch); (4) if po nil then if ch:=, then creat ( po.next ) else po.next:=nil end ; 38例題2 輸出廣義表的算法用“（”表示廣義表的開始，用“）”表示結(jié)束Procedure print (p : node); begin (1) if p.tag=1 then begin write() ; if p.link=nil then print(

22、) else print(p.link) else write(p.da); (2) if p.tag=1 then write() (3) if p.next nil then write(,);print(p.next) end ; 39例題3 求廣義表的表頭和表尾。 表頭： head ( ) , 表尾 :tail( ) 表頭是指表中的第一個元素 ，表尾是指除表頭以外的元素。 任何一個非空廣義表的表頭是表中第一個元素，它可以是原子，也可以是子表，而其表尾必定是子表。 例如 ： (1) HEAD(TAIL(HEAD(a,b),(c,d) (2) TAIL(HEAD(TAIL(a,b),(c,

23、d) 40(3) . 廣義表( (A , B, E, F , G)的表尾是( )。 A.(B, E , F, G) B.( ) C.（A，B， E，F(xiàn)，G) D. 不存在(4) . 廣義表（ ( ( ) ，( ) ) , (a , b, c) , (e , d)）的表頭是( )，表尾是( )。A.(e , d ) B.( ( ) ) C.( ( ) , ( ) ) D.（(a , b , c ）, ( e , d) ) (5) 對廣義表( (a),(b) )進行下面的操作head(head(a),(b)后的結(jié)果是( )。 A.a B.(a) C.( ) D.不確定 (6) 廣義表(A,B,E,F,G)的表尾是( )。A.(B, E , F, G) B.( ) C.（A，B， E，F(xiàn)，G) D.（G）41(7) 利用廣義表的head和tail操作寫出函數(shù)表達式，把以下各題中的單元素banana從廣義表中分離出來： (1) L1(apple, pear, banana, orange) (2) L2(apple, pear), (banana, orange) (3) L3(apple), (pear), (banana), (orange) (4) L4(apple), (pear)