濟(jì)南大學(xué)數(shù)據(jù)結(jié)構(gòu)第五章

1、第五章數(shù)組和廣義表數(shù)組和廣義表均是元素為復(fù)合結(jié)構(gòu)的線性結(jié)構(gòu)。5.1數(shù)組的定義以二維數(shù)組為例，二維數(shù)組通?？梢悦枋鰹閮煞N形式:以行序?yàn)橹餍?: PASCAL、 C可以看成 A = ( ， ， . . .， )T01m-1其中 i 是一個(gè)行向量形式的線性表，0i m-1i = ( ai 0， ai 1， . . . ， ai n-1 )以列序?yàn)橹餍?:FORTRAN可以看成 A = ( ， ， )01n-1其中 是一個(gè)列向量形式的線性表，0j n-1jj = ( a0 j， a1 j， am-1j)T5.2數(shù)組的表示和實(shí)現(xiàn)數(shù)組一旦被定義，其維數(shù)和維界就不再改變，故通常采用順序存儲(chǔ)結(jié)構(gòu)。如何將多維數(shù)

2、組結(jié)構(gòu)轉(zhuǎn)換對(duì)應(yīng)一組連續(xù)的存儲(chǔ)單元？以列序?yàn)橹餍蛞孕行驗(yàn)橹餍驅(qū)τ跀?shù)組，一旦規(guī)定了維數(shù)和維界，如何計(jì)算數(shù)組元素的存儲(chǔ)位置?設(shè)數(shù)組以行序?yàn)橹餍?。二維數(shù)組Amn數(shù)組元素aij 的存儲(chǔ)位置為L(zhǎng)OC(i，j) =LOC(0，0) + ( n i +Lj )LOC(0，0)是 a00 的存儲(chǔ)位置；是每個(gè)數(shù)組元素占用的存儲(chǔ)單元數(shù)；例， LOC(1， 1) =LOC(0， 0) + ( n1 + 1 ) L三維數(shù)組A ( b1，b2，b3 )LOC(0， 0， 0)是 a000 的存儲(chǔ)位置；是每個(gè)數(shù)組元素占用的存儲(chǔ)單元數(shù)；LOC(1， 1， 1) = LOC(0，0，0) + ( b2 b3 1 + b3 1

3、+ 1 ) L 數(shù)組元素 aijk 的存儲(chǔ)位置為 :LOC(i，j，k) = LOC(0，0，0) + ( b2 b3 i + b3 j + k ) L維數(shù)組 A ( b1，b2， ， bn )的元素存儲(chǔ)位置可計(jì)算為 : LOC(j1,j2, ,jn)= LOC(0,0, ,0) +( b2 bnj1 + b3 bn j2 + + bnjn-1 + jn ) L 5.3 矩陣的壓縮存儲(chǔ)矩陣元素如何存儲(chǔ)？通常利用二維數(shù)組來(lái)存儲(chǔ)矩陣元素。Bmna i jb i-1,j-1實(shí)際中，存在許多特殊矩陣，例如在矩陣中有許多值相同的元素或者零元素。用定長(zhǎng)數(shù)組存儲(chǔ)造成浪費(fèi)。為了節(jié)省存儲(chǔ)空間，需要對(duì)這類矩陣進(jìn)行

4、壓縮存儲(chǔ)。壓縮存儲(chǔ)是指為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。對(duì)稱矩陣三角矩陣對(duì)角矩陣稀疏矩陣階對(duì)稱矩陣n 階矩陣 A 滿足 :ai j = aj i通常表示為 :n2 個(gè)矩陣元素只需占用n(n+1)/2 個(gè)存儲(chǔ)空間設(shè)計(jì)用一維數(shù)組SAn(n+1)/2 存儲(chǔ) n 階對(duì)稱矩陣A 。關(guān)鍵問(wèn)題 :如何建立數(shù)組元SAk 和矩陣元aij 之間的一一對(duì)應(yīng)關(guān)系。一定是 i ，j 的函數(shù)a i+b j+ca i + j + ca n + 1 + c=a=,b=1 ,c=-1三角矩陣所謂下 (上)三角矩陣是指矩陣的上(下)三角 (不包括對(duì)角線 )中的元均為常數(shù)c 的階矩陣。下三角矩陣和對(duì)稱矩陣基

5、本一樣，只需除存儲(chǔ)其下 (上)三角中的元之外，再增加一個(gè)存儲(chǔ)單元存放 c 。關(guān)鍵問(wèn)題 :如何建立數(shù)組元SAk 和矩陣元aij 之間的一一對(duì)應(yīng)關(guān)系。對(duì)角矩陣所有的非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中。一般情況三對(duì)角矩陣關(guān)鍵問(wèn)題:如何建立數(shù)組元SAk 和矩陣元aij之間的一一對(duì)應(yīng)關(guān)系。一定是 i ，j 的函數(shù) a i + b j + c= a i+j+ca (n-1) + (n-2) + c3n-7代入解得： a=2 ,b=1 , c=-3K = 2i + j - 3(| i - j | 1)作業(yè) :五對(duì)角矩陣稀疏矩陣非零元很少的矩陣。稀疏因子 :設(shè) mn 的矩陣，有t 個(gè)非零元，令通常認(rèn)為

6、 0.05時(shí)稱為稀疏矩陣。稀疏矩陣的壓縮存儲(chǔ)三元組順序表行邏輯鏈接順序表十字鏈表三元組順序表三元組 ( i ，j ， aij )表示非零元素i 行數(shù)， j 列數(shù)， aij 非零元。5.4廣義表的定義廣義表 (列表 )LS= ( a1，a2，an )LS:列表名稱: 列表長(zhǎng)度 (元素的個(gè)數(shù) )ai:可以是單個(gè)數(shù)據(jù)，也可以是子列表，分別稱為原子和子表。a1:LS 的表頭 (第一個(gè)元素 )。( a2，a3， an ) :LS 的表尾 (列表 )。列表的舉例 :(1)A=() A 是一個(gè)空列表，長(zhǎng)度為0 。(2)B = ( e ) B 中只有一個(gè)原子 e ，長(zhǎng)度為 1 。(3)C = ( a ,( b

7、 ,c ,d ) ) C 有兩個(gè)元素， 原子 a 和子表 ( b ,c ,d ) ，長(zhǎng)度為 2 。(4)D = ( ( ) ,( e ) ,( a ,( b ,c ,d ) ) ) D 有三個(gè)元素，都是子表，長(zhǎng)度為3 。(5)E = ( a ,E ) E 為一個(gè)遞歸的表，長(zhǎng)度為2 。例 E = ( a ,( a ,( a , ) ) ) 。列表的性質(zhì) :列表是一個(gè)多層次的結(jié)構(gòu)。例 D = ( ( ) ,( e ) ,( a ,( b ,c ,d ) ) )列表可為其它列表的子表所調(diào)用。例，D=(A,B,C)列表可以是一個(gè)遞歸的表。例， E = ( a ,E )任何一個(gè)非空列表，其表頭可能是原子

8、或列表，而表尾一定是列表。例， B = ( e )表頭為原子 e；表尾為空表 ( ) 。例， B = ( ( a ,b ) ,c )表頭為列表 ( a ,b ) ；表尾為列表 ( c ) 。()=()？( ) 為空表，長(zhǎng)度0；( ( ) ) 長(zhǎng)度為1 的列表，可分解得到表頭、表尾。5.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu) (原子、列表 )，難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。結(jié)點(diǎn)結(jié)構(gòu) :tag :標(biāo)志域， 1 為表結(jié)點(diǎn)， 0 為原子結(jié)點(diǎn)。hp:指向表的表頭元素結(jié)點(diǎn)。atom:原子結(jié)點(diǎn)的值域。tp:指向下一個(gè)元素域。例 D = ( ( ) ,( e ) ,( a

9、,( b ,c ,d ) ) )作業(yè)：求 (a,b),(c,d),(e,f)的表頭和表尾出師表兩漢：諸葛亮先帝創(chuàng)業(yè)未半而中道崩殂， 今天下三分， 益州疲弊， 此誠(chéng)危急存亡之秋也。然侍衛(wèi)之臣不懈于內(nèi)，忠志之士忘身于外者，蓋追先帝之殊遇，欲報(bào)之于陛下也。誠(chéng)宜開張圣聽，以光先帝遺德，恢弘志士之氣，不宜妄自菲薄，引喻失義，以塞忠諫之路也。宮中府中，俱為一體；陟罰臧否，不宜異同。若有作奸犯科及為忠善者，宜付有司論其刑賞，以昭陛下平明之理；不宜偏私，使內(nèi)外異法也。侍中、侍郎郭攸之、費(fèi)祎、董允等，此皆良實(shí)，志慮忠純，是以先帝簡(jiǎn)拔以遺陛下：愚以為宮中之事，事無(wú)大小，悉以咨之，然后施行，必能裨補(bǔ)闕漏，有所廣益。

10、將軍向?qū)?，性行淑均，曉暢軍事，試用于昔日，先帝稱之曰愚以為營(yíng)中之事，悉以咨之，必能使行陣和睦，優(yōu)劣得所?！澳?”，是以眾議舉寵為督：親賢臣， 遠(yuǎn)小人， 此先漢所以興隆也； 親小人， 遠(yuǎn)賢臣， 此后漢所以傾頹也。 先帝在時(shí)，每與臣論此事， 未嘗不嘆息痛恨于桓、 靈也。 侍中、尚書、 長(zhǎng)史、 參軍，此悉貞良死節(jié)之臣，愿陛下親之、信之，則漢室之隆，可計(jì)日而待也。臣本布衣，躬耕于南陽(yáng)，茍全性命于亂世，不求聞達(dá)于諸侯。先帝不以臣卑鄙，猥自枉屈，三顧臣于草廬之中，咨臣以當(dāng)世之事，由是感激，遂許先帝以驅(qū)馳。后值傾覆，受任于敗軍之際，奉命于危難之間，爾來(lái)二十有一年矣。先帝知臣謹(jǐn)慎，故臨崩寄臣以大事也。受命以來(lái)，夙夜憂嘆，恐托付不效，以傷先帝之明；故五月渡瀘，深入不毛。今南方已定，兵甲已足，當(dāng)獎(jiǎng)率三軍，北定中原，