《深圳大學-數據結構-2017數組和廣義表演示文檔》由會員分享，可在線閱讀，更多相關《深圳大學-數據結構-2017數組和廣義表演示文檔（39頁珍藏版）》請在裝配圖網上搜索。

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