深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017數(shù)組和廣義表演示文檔
《深圳大學(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ù)組元素?cái)?shù)組: n個(gè)相同類型數(shù)據(jù)元素a1,a2,an 構(gòu)成的有限序列 該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中 數(shù)組的定義類似于采用順序存儲(chǔ)結(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ī)存儲(chǔ)結(jié)構(gòu)??呻S機(jī)存取數(shù)組中的任意數(shù)據(jù)元素,5.1.2 數(shù)組的定義 ADT array 數(shù)據(jù)對(duì)象D:具有相同類型的數(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 (0in)一維數(shù)組中任一數(shù)據(jù)元素的存儲(chǔ)地址可直接計(jì)算得到(直接存取).一維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。,二維數(shù)組Amn的存儲(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)mn,若每個(gè)元素占用的存儲(chǔ)單元數(shù)為L(zhǎng)(個(gè)),LOCa00表示元素a00的首地址,即數(shù)組的首地址。1 以“行優(yōu)先順序”存儲(chǔ) 第0行中的每個(gè)元素對(duì)應(yīng)的(首)地址是:LOCa0j=LOCa00+jL j=0,1,2, ,n(2) 第1行中的每個(gè)元素對(duì)應(yīng)的(首)地址是: LOCa1j=LOCa00+nL+jL j=0,1,2, ,n 第m行中的每個(gè)元素對(duì)應(yīng)的(首)地址是:LOCamj=LOCa00+mnL+jL j=0,1,2, ,n,aij存儲(chǔ)位置按行優(yōu)先:address(aij )= address ( a00 ) + ( in+j )L 按列優(yōu)先:address(aij ) = address ( a00 ) + (jm +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ù)組元素長(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ǔ),對(duì)稱矩陣的壓縮存儲(chǔ) 若該矩陣為方陣。nn階的方陣A滿足: aij=aji (0in-1 , 0jn-1)則A為對(duì)稱矩陣。 對(duì)稱矩陣中,幾乎有一半元素的值相等。如存儲(chǔ)所有元素,浪費(fèi)空間,且n值越大,浪費(fèi)越嚴(yán)重。,對(duì)稱矩陣壓縮存儲(chǔ): 只存儲(chǔ)對(duì)角線以上(或?qū)蔷€以下)部分,未存儲(chǔ)的部分利用元素之間的對(duì)稱性訪問。 存儲(chǔ)對(duì)稱矩陣A(對(duì)角線以下部分,下標(biāo)滿足ij的數(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)ijaddress(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(ij)壓縮存儲(chǔ)后的地址為: address(aij)= address(a00)+ (i*(i+1)/2+j)L 當(dāng)ij注: 與對(duì)稱矩陣不同,當(dāng)ij時(shí),aij的值為0,其沒有對(duì)應(yīng)的存儲(chǔ)空間。,稀疏矩陣:矩陣中零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于非零元素的個(gè)數(shù)時(shí),稱該矩陣為稀疏矩陣。 例如一個(gè)100100的矩陣,若其中只有100個(gè)非零元素,就可稱其為稀疏矩陣。疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)非零元素。,5.2.2 稀疏矩陣,稀疏矩陣的三元組表示 稀疏矩陣中非零元素的分布沒有規(guī)律,在存儲(chǔ)非零元素時(shí)必須同時(shí)存儲(chǔ)該非零元素的行和列下標(biāo)。這樣稀疏矩陣中的每一個(gè)非零元素需由一個(gè)三元組 (i,j,ai)惟一確定,稀疏矩陣中的所有非零元素構(gòu)成三元組線性表。,有一個(gè)67階稀疏矩陣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)稱表)是線性表的推廣。廣義表是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ù)元素有相對(duì)次序; 廣義表的長(zhǎng)度為最外層包含的元素個(gè)數(shù); 廣義表的深度為所含括弧的重?cái)?shù)。(原子深度為0,空表深度為1); 廣義表可以共享;稱為再入表; 廣義表可以是一個(gè)遞歸表。即可以是自已的子表。遞歸表的深度是無窮值,長(zhǎng)度是有限值; 任何一個(gè)非空廣義表GL均可分解為表頭head(GL) = a1和表尾tail(GL) = ( a2,an) 兩部分。,廣義表的表示下面討論一般的廣義表。小寫字母表示原子,大寫字母表示廣義表的表名。假定廣義表中的元素為char類型,每個(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)如果把表名寫在表的前面,廣義表可表示如下: 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)酱鎯?chǔ)結(jié)構(gòu) 廣義表是遞歸的數(shù)據(jù)結(jié)構(gòu),很難分配固定大小的存儲(chǔ)空間,所以采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 將一個(gè)廣義表看成一棵樹,為了方便存儲(chǔ),將其轉(zhuǎn)換成一棵二叉樹。 如下圖所示:左邊的圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示轉(zhuǎn)換的最終狀態(tài)(一棵二叉樹)。從二叉樹中看到,有兩類結(jié)點(diǎn),一類為圓圈結(jié)點(diǎn),對(duì)應(yīng)子表;另一類為方形結(jié)點(diǎn),對(duì)應(yīng)原子。,廣義表的存儲(chǔ)結(jié)構(gòu),下左圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示轉(zhuǎn)換的最終狀態(tài)(一棵二叉樹)。從二叉樹中看到,有兩類結(jié)點(diǎn),一類為圓圈結(jié)點(diǎn),對(duì)應(yīng)子表;另一類為方形結(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域鏈接起來的單鏈表。 求廣義表的長(zhǎng)度就是求單鏈表的長(zhǎng)度.,2. 求廣義表的深度 對(duì)于帶頭結(jié)點(diǎn)的廣義表g ,廣義表深度是所有子表中最大深度加1。若g為原子,其深度為0。 求廣義表深度的遞歸模型f()如下:,f(g)=,0 若g為原子,1 若g為空表,MAXf(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)用問題。,數(shù)組習(xí) 題,稀疏矩陣常用的壓縮存儲(chǔ)方法有()和()兩種。設(shè)有一個(gè)1010的對(duì)稱矩陣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ù)組Amn(即m行n列)按列存儲(chǔ)在數(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ù)組元素長(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),- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 深圳大學(xué) 數(shù)據(jù)結(jié)構(gòu) 2017 數(shù)組 廣義 表演 文檔
鏈接地址:http://appdesigncorp.com/p-359906.html