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

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