第5章多維數(shù)組和廣義表課件

1、1第第5 5章章 多維數(shù)組和廣義表多維數(shù)組和廣義表5.1 多維多維數(shù)組數(shù)組5.2 特殊特殊矩陣矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)5.3 稀疏稀疏矩陣矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)5.4 廣義表的概念廣義表的概念25.1 數(shù)組數(shù)組 一、數(shù)組的定義一、數(shù)組的定義數(shù)組：它是數(shù)組：它是n（n1)個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。數(shù)組的下標(biāo)：數(shù)組元素的位置。數(shù)組的下標(biāo)：數(shù)組元素的位置。注意：注意：(1)C語(yǔ)言的數(shù)組定義下標(biāo)從語(yǔ)言的數(shù)組定義下標(biāo)從0開始。開始。(2) 數(shù)組的處理相比其它復(fù)雜的結(jié)構(gòu)

2、要簡(jiǎn)單。數(shù)組的處理相比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單。 數(shù)組中各元素具有數(shù)組中各元素具有統(tǒng)一的類型統(tǒng)一的類型； 數(shù)組元素的下標(biāo)一般具有數(shù)組元素的下標(biāo)一般具有固定的上界和下界固定的上界和下界，即數(shù)組一旦，即數(shù)組一旦被定義，它的維數(shù)和維界被定義，它的維數(shù)和維界(上下界上下界)就不再改變。就不再改變。 數(shù)組的數(shù)組的基本操作比較簡(jiǎn)單基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。只有存取元素和修改元素值的操作。(3)一個(gè)二維數(shù)組可以看作每個(gè)數(shù)據(jù)元素是一個(gè)一維數(shù)組的一維一個(gè)二維數(shù)組可以看作每個(gè)數(shù)據(jù)元素是一個(gè)一維數(shù)組的一維數(shù)組。數(shù)組。二維數(shù)組是兩維的，內(nèi)存單

3、元是一維的，存在向內(nèi)存存儲(chǔ)二維數(shù)組是兩維的，內(nèi)存單元是一維的，存在向內(nèi)存存儲(chǔ)時(shí)二維數(shù)組中數(shù)據(jù)元素的存儲(chǔ)方法問題，時(shí)二維數(shù)組中數(shù)據(jù)元素的存儲(chǔ)方法問題，C語(yǔ)言采用以行序?yàn)橹髡Z(yǔ)言采用以行序?yàn)橹餍虻姆椒ù鎯?chǔ)。序的方法存儲(chǔ)。3問題：數(shù)組與線性表的區(qū)別與聯(lián)系問題：數(shù)組與線性表的區(qū)別與聯(lián)系相同之處：相同之處：它們都是若干個(gè)它們都是若干個(gè)相同數(shù)據(jù)類型相同數(shù)據(jù)類型的數(shù)據(jù)元素的數(shù)據(jù)元素a a0 0,a,a1 1,a,a2 2, ,，a an-1n-1構(gòu)成的有限序列。構(gòu)成的有限序列。不同之處：不同之處：(1)(1)數(shù)組要求其元素占用一塊數(shù)組要求其元素占用一塊地址連續(xù)地址連續(xù)的內(nèi)存單元空間，的內(nèi)存單元空間，而線性表無

4、此要求；而線性表無此要求；(2)(2)線性表的元素是線性表的元素是邏輯意義上不可再分的元素邏輯意義上不可再分的元素，而數(shù)組，而數(shù)組中的每個(gè)中的每個(gè)元素還可以是一個(gè)數(shù)組元素還可以是一個(gè)數(shù)組；(3)(3)數(shù)組的數(shù)組的操作操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存放數(shù)據(jù)主要是向某個(gè)下標(biāo)的數(shù)組元素中存放數(shù)據(jù)和取某個(gè)下標(biāo)的數(shù)組元素，這與線性表的插入和刪除操作和取某個(gè)下標(biāo)的數(shù)組元素，這與線性表的插入和刪除操作不不同同。4二、數(shù)組的實(shí)現(xiàn)機(jī)制二、數(shù)組的實(shí)現(xiàn)機(jī)制、一維數(shù)組（一維數(shù)組（n n個(gè)元素）中任一元素個(gè)元素）中任一元素a ai i LOC(ai)=LOC(a)+i*k (0i n)、一個(gè)、一個(gè)m行行n列的二維數(shù)組

5、列的二維數(shù)組LOC(aij)=LOC(a00)+(i*n+j)*k (0im， 0jn)注：注：C語(yǔ)言中數(shù)組元素采用行主序的存放方法，即語(yǔ)言中數(shù)組元素采用行主序的存放方法，即行優(yōu)先行優(yōu)先順序順序。a的內(nèi)存單元地址的內(nèi)存單元地址每個(gè)元素所需的字節(jié)個(gè)數(shù)每個(gè)元素所需的字節(jié)個(gè)數(shù)每個(gè)元素所需的字節(jié)個(gè)數(shù)每個(gè)元素所需的字節(jié)個(gè)數(shù)a0的內(nèi)存單元地址的內(nèi)存單元地址一個(gè)一個(gè)mn的二維數(shù)組可以的二維數(shù)組可以看成是看成是m行的一維數(shù)組，或行的一維數(shù)組，或者者n列的一維數(shù)組。列的一維數(shù)組。 a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 Amn=5對(duì)于行優(yōu)

6、先順序：先排最右的下標(biāo)，從右往左，對(duì)于行優(yōu)先順序：先排最右的下標(biāo)，從右往左，最后排最左下標(biāo)；最后排最左下標(biāo)；對(duì)于列優(yōu)先順序：先排最左的下標(biāo)，從左往右，對(duì)于列優(yōu)先順序：先排最左的下標(biāo)，從左往右，最后排最右下標(biāo)；最后排最右下標(biāo)；6注：只要知道以下三要素便可隨時(shí)求出任一元素的地址注：只要知道以下三要素便可隨時(shí)求出任一元素的地址（意（意義：數(shù)組中的任一元素可隨機(jī)存取）義：數(shù)組中的任一元素可隨機(jī)存?。╅_始結(jié)點(diǎn)的存放首字節(jié)地址（即基地址）；開始結(jié)點(diǎn)的存放首字節(jié)地址（即基地址）；維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)。每個(gè)數(shù)組元素所占用的單元數(shù)。例例軟考題：軟考題：一個(gè)二維數(shù)

7、組一個(gè)二維數(shù)組A A，行下標(biāo)的范圍是，行下標(biāo)的范圍是1 1到到6 6，列下標(biāo)的范圍是，列下標(biāo)的范圍是0 0到到7 7，每個(gè)數(shù)組元素用相鄰的，每個(gè)數(shù)組元素用相鄰的6 6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是數(shù)組的體積是 個(gè)字節(jié)。個(gè)字節(jié)。答：答： Volume=mVolume=m* *n n* *L=(6-1L=(6-1+1+1) )* *(7- 0 (7- 0 +1+1) )* *6=486=48* *6=2886=288例例 設(shè)數(shù)組設(shè)數(shù)組aa60, 60, 7070的基地址為的基地址為20482048，每個(gè)元素占，每個(gè)元素占2 2個(gè)存儲(chǔ)單元

8、，個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58a32,58的存儲(chǔ)地址的存儲(chǔ)地址為為 。答：答：根據(jù)行優(yōu)先公式根據(jù)行優(yōu)先公式 LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+j)n+j)* *k k (0(0i im，0 0j jn)n)得：得：LOC(aLOC(a32,5832,58)=2048+()=2048+(3232* *71+71+5858) )* *2 22887二維數(shù)組二維數(shù)組Amn按行優(yōu)先順序存儲(chǔ)按行優(yōu)先順序存儲(chǔ)元素元素aij的存儲(chǔ)地址為數(shù)組的基地址加上排在的存儲(chǔ)地址為數(shù)組的基地址加上排在aij前面

9、的元素前面的元素所占用的單元數(shù)。因?yàn)樗加玫膯卧獢?shù)。因?yàn)閍ij位于第位于第i行，第行，第j列列,前面前面i行一共有行一共有i*n個(gè)元素，第個(gè)元素，第i行上行上aij前面又有前面又有j個(gè)元素，故它前面一共有個(gè)元素，故它前面一共有i *n+j個(gè)元素，因此，個(gè)元素，因此，aij的地址計(jì)算函數(shù)為：的地址計(jì)算函數(shù)為： Loc(aij)= Loc(a00)+i *n+j*d8三、三、數(shù)組抽象數(shù)據(jù)類型數(shù)組抽象數(shù)據(jù)類型數(shù)據(jù)集合數(shù)據(jù)集合： a0,a1,a2,an-1 每個(gè)數(shù)據(jù)類型為抽象數(shù)據(jù)元素每個(gè)數(shù)據(jù)類型為抽象數(shù)據(jù)元素類型類型操作集合操作集合: :(1)(1)求求數(shù)組元素個(gè)數(shù)數(shù)組元素個(gè)數(shù) ArrayLength

10、(DArrayLength(D) ) (2) (2)存數(shù)組元素存數(shù)組元素Storage(D,i,x)Storage(D,i,x) (3) (3)取數(shù)組元素取數(shù)組元素Get(D,i,x)Get(D,i,x)95.2 5.2 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ) 特殊矩陣特殊矩陣: :指有許多值相同的元素或有許多零元素、且值相同的元素或零指有許多值相同的元素或有許多零元素、且值相同的元素或零元素的分布有一定規(guī)律的矩陣。元素的分布有一定規(guī)律的矩陣。 下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。1 1、n n階對(duì)稱矩陣階對(duì)稱矩陣 在一個(gè)在一個(gè)n n階方陣階方陣A A中，若元

11、素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： a aijij=a=ajiji （1i,jn1i,jn） 則稱則稱A A為為n n階對(duì)稱矩陣階對(duì)稱矩陣。 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 a nn 圖 5.1 對(duì)稱矩陣 n n階對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三階對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，

12、能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按“行優(yōu)先行優(yōu)先順序順序”存儲(chǔ)主存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素。對(duì)角線（包括對(duì)角線）以下的元素。10 i(i+1)/2+j i(i+1)/2+j 當(dāng)當(dāng)i ij j j(j+1)/2+i j(j+1)/2+i 當(dāng)當(dāng)i ij jk= 在這個(gè)下三角矩陣中，第在這個(gè)下三角矩陣中，第i i行恰有行恰有i i個(gè)元素，元素總數(shù)為個(gè)元素，元素總數(shù)為n(n+1)/2n(n+1)/2，這，這樣就可將樣就可將n n2 2個(gè)數(shù)據(jù)元素壓縮存儲(chǔ)在個(gè)數(shù)據(jù)元素壓縮存儲(chǔ)在n(n+1)/2n(n+1)/2個(gè)存儲(chǔ)單元中。個(gè)存儲(chǔ)單元中。 假設(shè)以一

13、維數(shù)組假設(shè)以一維數(shù)組vava作為作為n n階對(duì)稱矩陣階對(duì)稱矩陣A A的壓縮存儲(chǔ)單元，的壓縮存儲(chǔ)單元，k k為一維數(shù)組為一維數(shù)組vava的下標(biāo)序號(hào)，的下標(biāo)序號(hào)，a aijij為為n n階對(duì)稱矩陣階對(duì)稱矩陣A A中中i i行行j j列的數(shù)據(jù)元素列的數(shù)據(jù)元素( (其中其中1i,jn 1i,jn ），），其數(shù)學(xué)映射關(guān)系為：其數(shù)學(xué)映射關(guān)系為： 令令I(lǐng)=max(i,j), J=min(i,jI=max(i,j), J=min(i,j),),則則k k和和i,ji,j的對(duì)應(yīng)關(guān)系可統(tǒng)一為：的對(duì)應(yīng)關(guān)系可統(tǒng)一為： k=Ik=I* *(I+1)/2+J 0(I+1)/2+J 0kn(n+1)/22 2、n n階三角

14、矩陣階三角矩陣 以主對(duì)角線劃分，以主對(duì)角線劃分， n n階三角矩陣有階三角矩陣有n n階上三角矩陣和階上三角矩陣和n n階下三角矩陣階下三角矩陣兩種。兩種。 n n階上三角矩陣如圖階上三角矩陣如圖5.2(a)5.2(a)所示，它的下三角（不包括主對(duì)角線）所示，它的下三角（不包括主對(duì)角線）中的元素均為中的元素均為0 0（或常數(shù)）。（或常數(shù)）。n n階下三角矩陣正好相反，它的主對(duì)角線上階下三角矩陣正好相反，它的主對(duì)角線上方均為方均為0 0（或常數(shù)），如圖（或常數(shù)），如圖5.2(b)5.2(b)所示。所示。 注：在大多數(shù)情況下，注：在大多數(shù)情況下， n n階三角矩陣常數(shù)為零。階三角矩陣常數(shù)為零。 1

15、1 a11 a12 a 1n a11 c c c a22 a 2n a21 a22 c . c c a nn an1 an2 an n (a)(a)上三角矩陣上三角矩陣 (b)(b)下三角矩陣下三角矩陣 圖圖5.2 5.2 三角矩陣三角矩陣i(i-1)/2+j-1 i(i-1)/2+j-1 當(dāng)當(dāng)i ij jn(n+1)/2n(n+1)/2 （或空）（或空） 當(dāng)當(dāng)i imd = da.nddb-md = da.nd; /; /* *行數(shù)值轉(zhuǎn)為列數(shù)值行數(shù)值轉(zhuǎn)為列數(shù)值* */ /db-nd = da.mddb-nd = da.md; /; /* *列數(shù)值轉(zhuǎn)為行數(shù)值列數(shù)值轉(zhuǎn)為行數(shù)值* */ /db-t

16、d = da.tddb-td = da.td; ;/ /* *非零元個(gè)數(shù)不變非零元個(gè)數(shù)不變* */ /if (da.tdif (da.td=0)=0)return;return;elseelse q = 0;q = 0; / /* *q q為為b-listb-list的下標(biāo)值的下標(biāo)值* */ / for (v=1;v=da.nd;v for (v=1;v=da.nd;v+)+) for(p = 0; p da.td for(p = 0; p listq. b-listq.i i = a.listp. = a.listp.j j; /; /* *列號(hào)轉(zhuǎn)為行號(hào)列號(hào)轉(zhuǎn)為行號(hào)* */ / b-list

17、q. b-listq.j j = a.listp.= a.listp.i i; /; /* *行號(hào)轉(zhuǎn)為列號(hào)行號(hào)轉(zhuǎn)為列號(hào)* */ / b-listq.d = a.listp.d; / b-listq.d = a.listp.d; /* *數(shù)組元素復(fù)制數(shù)組元素復(fù)制* */ / q+; q+; 20三、稀疏矩陣的三元組鏈表三、稀疏矩陣的三元組鏈表1、三元組鏈表、三元組鏈表 用鏈表存儲(chǔ)的三元組線性表。用鏈表存儲(chǔ)的三元組線性表。2、行指針數(shù)組結(jié)構(gòu)的三元組鏈表、行指針數(shù)組結(jié)構(gòu)的三元組鏈表 把每行非零元素三元組組織成一個(gè)單鏈表，再設(shè)計(jì)把每行非零元素三元組組織成一個(gè)單鏈表，再設(shè)計(jì)一個(gè)指針類型的數(shù)組存儲(chǔ)所有單鏈表的頭指針。一個(gè)指針類型的數(shù)組存儲(chǔ)所有單鏈表的頭指針。3、三元組十字鏈表、三元組十字鏈表 把非零元素三元組按行和按列組織成單鏈表，這樣把非零元素三元組按行和按列組織成單鏈表，這樣稀疏矩陣中的每個(gè)非零元素三元組結(jié)點(diǎn)都將既勾鏈稀疏矩陣中的每個(gè)非零元素三元組結(jié)點(diǎn)都將既勾鏈在行單鏈表上，又勾鏈在列單鏈表上，形成十字形在行單鏈表上，又勾鏈在列單鏈表上，形成十字形狀。狀。21廣義表廣義表廣義表是線性表的推廣。線性表的元