《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017數(shù)組和廣義表演示文檔》由會(huì)員分享，可在線閱讀，更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017數(shù)組和廣義表演示文檔（39頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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