深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017數(shù)組和廣義表演示文檔

第5章數(shù)組和廣義表,5.1.1 數(shù)組和數(shù)組元素?cái)?shù)組: n個(gè)相同類型數(shù)據(jù)元素a1,a2,an 構(gòu)成的有限序列 該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中 數(shù)組的定義類似于采用順序存儲結(jié)構(gòu)的線性表,5.1 數(shù) 組,數(shù)組的特性: 數(shù)組中的數(shù)據(jù)元素?cái)?shù)固定 數(shù)組中的數(shù)據(jù)元素具有相同數(shù)據(jù)類型 數(shù)組中的每個(gè)數(shù)據(jù)元素都有一組惟一的下標(biāo)值。 數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)?？呻S機(jī)存取數(shù)組中的任意數(shù)據(jù)元素,5.1.2 數(shù)組的定義 ADT array 數(shù)據(jù)對象D：具有相同類型的數(shù)據(jù)元素構(gòu)成的有序集合； 數(shù)據(jù)關(guān)系R：對于n維數(shù)組，其每一個(gè)元素均位于n個(gè)向量中，每個(gè)元素最多具有n個(gè)前驅(qū)結(jié)點(diǎn)和n個(gè)后繼結(jié)點(diǎn)； 基本運(yùn)算: ADT array,5.1.3 數(shù)組的順序存儲及實(shí)現(xiàn) 數(shù)組是線性表的一種存儲方式 多維數(shù)組數(shù)據(jù)元素的順序存儲有兩種方式： 按行優(yōu)先存儲 按列優(yōu)先存儲,一維數(shù)組的存儲:若a0的存儲地址LOC(a0)確定,每個(gè)數(shù)據(jù)元素占用k個(gè)存儲單元,則: LOC(ai)=LOC(a0)+i*k (0in)一維數(shù)組中任一數(shù)據(jù)元素的存儲地址可直接計(jì)算得到(直接存取).一維數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)。,二維數(shù)組Amn的存儲： a00 a01 a0( n-1) a10 a11 a1( n-1) A = a(m-1)0 a(m-1)1 a(m-1) (n-1)按行優(yōu)先存儲順序：a00， a01， a0(n-1) , a10, a11， a1(n-1) ， a(m-1)0,a(m-1)1,a(m-1) (n-1) 按列優(yōu)先存儲順序：a00，a10， a(m-1)0 , a01, a11, a(m-1)1， a0(n-1) ,.a1(n-1)，a(m-1) (n-1),二維數(shù)組及其順序存儲圖例形式,(b) 行優(yōu)先順序存儲,(c) 列優(yōu)先順序存儲,設(shè)有二維數(shù)組A=(aij)mn，若每個(gè)元素占用的存儲單元數(shù)為L(個(gè))，LOCa00表示元素a00的首地址，即數(shù)組的首地址。1 以“行優(yōu)先順序”存儲 第0行中的每個(gè)元素對應(yīng)的(首)地址是：LOCa0j=LOCa00+jL j=0,1,2, ,n(2) 第1行中的每個(gè)元素對應(yīng)的(首)地址是： LOCa1j=LOCa00+nL+jL j=0,1,2, ,n 第m行中的每個(gè)元素對應(yīng)的(首)地址是：LOCamj=LOCa00+mnL+jL j=0,1,2, ,n,aij存儲位置按行優(yōu)先：address(aij )= address ( a00 ) + ( i×n+j )×L 按列優(yōu)先：address(aij ) = address ( a00 ) + (j×m +i )×L,二維數(shù)組可以看作是每個(gè)數(shù)據(jù)元素都是相同類型的一維數(shù)組的一維數(shù)組。以此類推,任何多維數(shù)組都可以看作一個(gè)線性表,這時(shí)線性表中的每個(gè)數(shù)據(jù)元素也是一個(gè)線性表。多維數(shù)組是線性表的推廣。,例5.1 有二維數(shù)組float a54,計(jì)算a32的內(nèi)存地址.(a起始地址為2000,數(shù)組元素長度4字節(jié)) LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056,壓縮存儲：多個(gè)相同值的結(jié)點(diǎn)只分配一個(gè)存儲空間，值為零的結(jié)點(diǎn)不分配空間。,5.2 矩陣的壓縮存儲,5.2.1 特殊矩陣主要討論對稱矩陣和三角矩陣的壓縮存儲,對稱矩陣的壓縮存儲 若該矩陣為方陣。n×n階的方陣A滿足： aij=aji (0in-1 , 0jn-1)則A為對稱矩陣。 對稱矩陣中，幾乎有一半元素的值相等。如存儲所有元素，浪費(fèi)空間，且n值越大，浪費(fèi)越嚴(yán)重。,對稱矩陣壓縮存儲: 只存儲對角線以上(或?qū)蔷€以下)部分，未存儲的部分利用元素之間的對稱性訪問。 存儲對稱矩陣A(對角線以下部分,下標(biāo)滿足ij的數(shù)組元素aij）： a00 a10 a11 A = a20 a21 a22 a(n-1)0 .a(n-1) (n-1),按行優(yōu)先存儲，A壓縮存儲后元素aij的地址：  address(a00)+(i*(i+1)/2+j)×L 當(dāng)ijaddress(aij)= address(a00)+(j*(j+1)/2+i)×L 當(dāng)i< j,三角矩陣的壓縮存儲 1、下三角矩陣 a00 0 0 0 a10 a11 0 . 0 A = a20 a21 a22 . 0 a(n-1)0 a(n-1) (n-1) 按行優(yōu)先， aij(ij)壓縮存儲后的地址為： address(aij)= address(a00)+ (i*(i+1)/2+j)×L 當(dāng)ij注: 與對稱矩陣不同，當(dāng)i<j時(shí)，aij的值為0，沒有對應(yīng)的存儲單元。,2、 上三角矩陣 a00 a01 a02 a0(n-1) 0 a11 a12 .a1(n-1) A = 0 0 a22 .a2(n-1) 0 0 0 a(n-1)(n-1) 只存儲對角線以上部分。按行優(yōu)先存儲，aij (ij)壓縮存儲的地址為： address(aij)=address(a00)+(n+(n-1)+(n-2)+(n- (i-1) +j-i×L =address(a00)+(i*n-(i-1)*i/2+j-i)*L 注:當(dāng)i>j時(shí)，aij的值為0，其沒有對應(yīng)的存儲空間。,稀疏矩陣:矩陣中零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于非零元素的個(gè)數(shù)時(shí)，稱該矩陣為稀疏矩陣。 例如一個(gè)100×100的矩陣,若其中只有100個(gè)非零元素,就可稱其為稀疏矩陣。疏矩陣的壓縮存儲方法是只存儲非零元素。,5.2.2 稀疏矩陣,稀疏矩陣的三元組表示 稀疏矩陣中非零元素的分布沒有規(guī)律,在存儲非零元素時(shí)必須同時(shí)存儲該非零元素的行和列下標(biāo)。這樣稀疏矩陣中的每一個(gè)非零元素需由一個(gè)三元組 (i,j,ai)惟一確定,稀疏矩陣中的所有非零元素構(gòu)成三元組線性表。,有一個(gè)6×7階稀疏矩陣A, 對應(yīng)的三元組線性表為： (0,2,1),(1,1,2),(2,0,3),(3,3,5), (4,4,6),(5,5,7),(5,6,4),5.3 廣義表,廣義表(簡稱表)是線性表的推廣。廣義表是n(n0)個(gè)元素的一個(gè)序列(n=0,空表)。設(shè)ai為廣義表的第i個(gè)元素,則廣義表GL的一般表示與線性表相同： GL=(a1,a2,ai,an)如果ai是單個(gè)數(shù)據(jù)元素,則ai是廣義表GL的原子；如果ai是一個(gè)廣義表,則ai是廣義表GL的子表。,廣義表的特性： 廣義表中的數(shù)據(jù)元素有相對次序； 廣義表的長度為最外層包含的元素個(gè)數(shù)； 廣義表的深度為所含括弧的重?cái)?shù)。(原子深度為0,空表深度為1)； 廣義表可以共享；稱為再入表； 廣義表可以是一個(gè)遞歸表。即可以是自已的子表。遞歸表的深度是無窮值,長度是有限值； 任何一個(gè)非空廣義表GL均可分解為表頭head(GL) = a1和表尾tail(GL) = ( a2,an) 兩部分。,廣義表的表示下面討論一般的廣義表。小寫字母表示原子,大寫字母表示廣義表的表名。假定廣義表中的元素為char類型,每個(gè)原子的值被限定為英文字母。假定廣義表是表達(dá)式,元素之間用逗號分隔,表元素的起止符號分別為左、右圓括號,空表在其圓括號內(nèi)不包含任何字符。例如“(a,(b,c,d)” 符合廣義表格式。,例如： A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c)如果把表名寫在表的前面,廣義表可表示如下： A() B(e) C(a, (b,c,d) ) D( A() , B(e) , C( a, ( b,c,d ) ) ) E( ( a, ( a, b ) , ( ( a, b ) , c ) ) ),廣義表的圖形表示:用圓圈和方框分別表示表和單元素,用線段把表和元素(元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的下方)連接起來.例如:A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c),廣義表舉例:,廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 廣義表是遞歸的數(shù)據(jù)結(jié)構(gòu),很難分配固定大小的存儲空間,所以采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 將一個(gè)廣義表看成一棵樹,為了方便存儲,將其轉(zhuǎn)換成一棵二叉樹。 如下圖所示:左邊的圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示轉(zhuǎn)換的最終狀態(tài)(一棵二叉樹)。從二叉樹中看到,有兩類結(jié)點(diǎn),一類為圓圈結(jié)點(diǎn),對應(yīng)子表；另一類為方形結(jié)點(diǎn),對應(yīng)原子。,廣義表的存儲結(jié)構(gòu),下左圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示轉(zhuǎn)換的最終狀態(tài)(一棵二叉樹)。從二叉樹中看到,有兩類結(jié)點(diǎn),一類為圓圈結(jié)點(diǎn),對應(yīng)子表；另一類為方形結(jié)點(diǎn),對應(yīng)原子。,廣義表的兩種基本情況 ：(原子),例：廣義表A=(),B=(e),C=(a, (b, c, d) )，D=(A, B, C)，E=(a, E)的存儲結(jié)構(gòu)如圖所示。,廣義表的運(yùn)算1. 求廣義表的長度 在廣義表中,同一層次的每個(gè)結(jié)點(diǎn)是由link域鏈接起來的單鏈表。 求廣義表的長度就是求單鏈表的長度.,2. 求廣義表的深度 對于帶頭結(jié)點(diǎn)的廣義表g ,廣義表深度是所有子表中最大深度加1。若g為原子,其深度為0。 求廣義表深度的遞歸模型f()如下：,f(g)=,0 若g為原子,1 若g為空表,MAXf(subg)+1 其他情況,subg為g的子表,4. 輸出廣義表 打印輸出廣義表時(shí),需要對子表進(jìn)行遞歸調(diào)用。,本章小結(jié)學(xué)習(xí)要點(diǎn)： (1)掌握廣義表的定義。 (2)掌握廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 (3)掌握廣義表的基本運(yùn)算,包括創(chuàng)建廣義表、輸出廣義表、求廣義表的長度和深度。 (4)靈活運(yùn)用廣義表這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問題。,數(shù)組習(xí) 題,稀疏矩陣常用的壓縮存儲方法有（）和（）兩種。設(shè)有一個(gè)10  10的對稱矩陣A采用壓縮方式進(jìn)行存儲，存儲時(shí)以按行優(yōu)先的順序存儲其下三角陣，假設(shè)其起始元素a00的地址為1，每個(gè)數(shù)據(jù)元素占2個(gè)字節(jié)，則a65的地址為（）。 address(aij)= address(a00)+(i*(i+1)/2+j)×L 3.常對數(shù)組進(jìn)行的兩種基本操作為（）和（）。4.數(shù)組的存儲結(jié)構(gòu)采用( )存儲方式；對矩陣壓縮是為了節(jié)省( )。,5.設(shè)二維數(shù)組Amn（即m行n列）按列存儲在數(shù)組Bm*n中，則二維數(shù)組元素Aij在一維數(shù)組B中的下標(biāo)為（ ） A、i*n+j B、i+j*m C、i*jD、j*n+i6.有二維數(shù)組int a56,計(jì)算a25的內(nèi)存地址.(a起始地址為1000,數(shù)組元素長度4字節(jié))按行:LOC(a2,5)=LOC(a0,0)+(i*n+j)*k =1000+(2*6+5)*4=1068按列: LOC(a2,5)=LOC(a0,0)+(j*m +i )*k =1000+(5*5+2)*4=1108,1. 求廣義表的表頭與表尾.廣義表L=( (x,y,z), a ,(u,t,w) )求Head( head( tail (tail(L) ) ) )的結(jié)果.2. 廣義表(a,b,c)的表頭是( ),表尾是( ).3. 一個(gè)廣義表的表頭一定是廣義表( ) 一個(gè)廣義表的表尾一定是廣義表( ),廣義表 習(xí) 題,4、廣義表L=（a，（b, c），進(jìn)行GetTail（L）操作后的結(jié)果為（ ） A、c B、b, c C、(b, c)D、(b, c),