第五章 數(shù)組與廣義表

1、|第第1章章 緒論緒論|第第2章章 線性表線性表|第第3章章 串串|第第4章章 棧與隊(duì)列棧與隊(duì)列第第5章章 數(shù)組和廣義表數(shù)組和廣義表|第第6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)|第第7章章 圖圖|第第8章章 查找查找|第第9章章 排序排序|5.1 5.1 數(shù)組數(shù)組|5.2 5.2 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)|5.3 5.3 廣義表廣義表|5.1.1 一維數(shù)組一維數(shù)組|5.1.2 多維數(shù)組多維數(shù)組|數(shù)組是一組相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合，數(shù)組元素?cái)?shù)組是一組相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合，數(shù)組元素按次序存儲(chǔ)于一個(gè)地址連續(xù)的內(nèi)存空間中。按次序存儲(chǔ)于一個(gè)地址連續(xù)的內(nèi)存空間中。|數(shù)組元素在數(shù)組中的位置通常

2、稱為數(shù)組的下標(biāo)。數(shù)組元素在數(shù)組中的位置通常稱為數(shù)組的下標(biāo)。5.1 數(shù)組的定義數(shù)組的定義|數(shù)組分配內(nèi)存空間的方式有數(shù)組分配內(nèi)存空間的方式有2種種z靜態(tài)數(shù)組靜態(tài)數(shù)組：聲明時(shí)給出數(shù)組元素個(gè)數(shù)。當(dāng)程序開(kāi)始運(yùn)行時(shí)，：聲明時(shí)給出數(shù)組元素個(gè)數(shù)。當(dāng)程序開(kāi)始運(yùn)行時(shí)，數(shù)組即獲得系統(tǒng)分配的一塊地址連續(xù)的內(nèi)存空間。靜態(tài)數(shù)數(shù)組即獲得系統(tǒng)分配的一塊地址連續(xù)的內(nèi)存空間。靜態(tài)數(shù)組所占用的內(nèi)存空間由系統(tǒng)自動(dòng)管理。組所占用的內(nèi)存空間由系統(tǒng)自動(dòng)管理。z動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組：聲明時(shí)不指定數(shù)組長(zhǎng)度。當(dāng)程序運(yùn)行中需要使：聲明時(shí)不指定數(shù)組長(zhǎng)度。當(dāng)程序運(yùn)行中需要使用數(shù)組時(shí)，向系統(tǒng)申請(qǐng)數(shù)組的存儲(chǔ)單元空間，并給出數(shù)組用數(shù)組時(shí)，向系統(tǒng)申請(qǐng)數(shù)組的存儲(chǔ)單

3、元空間，并給出數(shù)組長(zhǎng)度。當(dāng)數(shù)組使用完之后，需要向系統(tǒng)歸還所占用的內(nèi)存長(zhǎng)度。當(dāng)數(shù)組使用完之后，需要向系統(tǒng)歸還所占用的內(nèi)存空間?？臻g。|在在Java中，數(shù)組元素既可以是簡(jiǎn)單數(shù)據(jù)類型，也可以是中，數(shù)組元素既可以是簡(jiǎn)單數(shù)據(jù)類型，也可以是引用類型。而且引用類型。而且Java中的數(shù)組都是動(dòng)態(tài)數(shù)組。中的數(shù)組都是動(dòng)態(tài)數(shù)組。5.1.1 一維數(shù)組一維數(shù)組5.1.2 多維數(shù)組多維數(shù)組a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =以二維數(shù)組為例，以二維數(shù)組為例，數(shù)組和廣義表均

4、是元素為復(fù)合結(jié)構(gòu)的線性結(jié)構(gòu)。數(shù)組和廣義表均是元素為復(fù)合結(jié)構(gòu)的線性結(jié)構(gòu)。1 多維數(shù)組的概念多維數(shù)組的概念2. 多維數(shù)組的遍歷多維數(shù)組的遍歷 :以以行序行序?yàn)橹餍驗(yàn)橹餍?可以看成可以看成 A = ( 1， 2， ， m )T. . .其中其中 i 是一個(gè)是一個(gè)行向量行向量形式的線性表，形式的線性表，1im i = ( ai 1，ai 2， ，ai n ). . .a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =PASCAL、C按照某種次序訪問(wèn)一個(gè)數(shù)據(jù)結(jié)構(gòu)中的

5、所有元素，并且每按照某種次序訪問(wèn)一個(gè)數(shù)據(jù)結(jié)構(gòu)中的所有元素，并且每個(gè)數(shù)據(jù)元素恰好訪問(wèn)一次，稱為對(duì)該數(shù)據(jù)結(jié)構(gòu)的遍歷。個(gè)數(shù)據(jù)元素恰好訪問(wèn)一次，稱為對(duì)該數(shù)據(jù)結(jié)構(gòu)的遍歷?？梢钥闯煽梢钥闯?A = ( 1， 2， ， n ). . .其中其中 j 是一個(gè)是一個(gè)列向量列向量形式的線性表，形式的線性表，1jn j = ( a1 j，a2 j， ，amj )T. . .a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =以以列序列序?yàn)橹餍驗(yàn)橹餍?FORTRAN3. 多維數(shù)組的

6、順序存儲(chǔ)結(jié)構(gòu)多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組一旦被定義，其數(shù)組一旦被定義，其維數(shù)維數(shù)和和維界維界就不再改變，故通常就不再改變，故通常采用采用 。如何將多維數(shù)組結(jié)構(gòu)轉(zhuǎn)換對(duì)應(yīng)一組連續(xù)的存儲(chǔ)單元？如何將多維數(shù)組結(jié)構(gòu)轉(zhuǎn)換對(duì)應(yīng)一組連續(xù)的存儲(chǔ)單元？順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)以列序?yàn)橹餍蛞粤行驗(yàn)橹餍騛11a21 am,1a12a22 am,2 2a1,n am,na2 2,n 1 2 na11 a12 a13 a1,na21 a22 a23 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn 1 2 . . . n以行序?yàn)橹餍蛞孕行驗(yàn)橹餍騛11a1

7、2 a1,na21a22 a2 2,n am,1 1 am,n am,2 2 1 2 ma11 a12 a13 a1,na21 a22 a23 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn 1 2 m. . .對(duì)于數(shù)組，一旦規(guī)定了維數(shù)和維界，如何計(jì)算數(shù)組元素的存儲(chǔ)位置對(duì)于數(shù)組，一旦規(guī)定了維數(shù)和維界，如何計(jì)算數(shù)組元素的存儲(chǔ)位置?a11a12 a1,na21a22 a2 2,n am,1 1 am,n am,2 2 1 2 m 設(shè)數(shù)組以設(shè)數(shù)組以行序行序?yàn)橹餍?。為主序。二維數(shù)組二維數(shù)組 Amn 數(shù)組元素?cái)?shù)組元素 aij 的存儲(chǔ)

8、位置為的存儲(chǔ)位置為L(zhǎng)oc(ai,j) =Loc(a1,1)是是a1,1的存儲(chǔ)位置；的存儲(chǔ)位置；存儲(chǔ)密度為存儲(chǔ)密度為1；1例，例，Loc(a2,2) =+ ( i-1)n + (j-1)Loc(a1,1)Loc(a1,1) + n +1例例1:一個(gè)二維數(shù)組一個(gè)二維數(shù)組A,行下標(biāo)的范圍是行下標(biāo)的范圍是1到到6,列下標(biāo)的范圍是列下標(biāo)的范圍是0到到7,每每個(gè)數(shù)組元素用相鄰的個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)個(gè)字節(jié)存儲(chǔ),存儲(chǔ)器按字節(jié)編址存儲(chǔ)器按字節(jié)編址;那么那么,這個(gè)這個(gè)數(shù)組占數(shù)組占 個(gè)字節(jié)。個(gè)字節(jié)。例例2:已知二維數(shù)組已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：按行存儲(chǔ)的元素地址公式是：Loc(aij)

9、=Loc(a11)+(i-1)*m+(j-1)*K , 按列存儲(chǔ)的公式是？按列存儲(chǔ)的公式是？例例3計(jì)算機(jī)系考研題計(jì)算機(jī)系考研題：設(shè)數(shù)組設(shè)數(shù)組a160, 170的基地址為的基地址為2048，每個(gè)元素占每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58的的 存儲(chǔ)地址為存儲(chǔ)地址為 。答：答：Volume=m*n*L= 6 * (7+1) * 6=48*6 =288288答答:Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 盡管是方陣,公式仍不同答答:Loc(aij) = Loc(a11) + (m (j-1) + i-1

10、) lLoc(a32,58)=2048+(60*(58-1)+32-1)*28950注意審題注意審題,以列為主序以列為主序!|設(shè)二維數(shù)組中的每一個(gè)數(shù)組元素設(shè)二維數(shù)組中的每一個(gè)數(shù)組元素Aij占用占用6個(gè)字節(jié)個(gè)字節(jié),行下行下標(biāo)標(biāo)i從從0到到8,列下標(biāo)列下標(biāo)j從從2到到5,1)則二維數(shù)組則二維數(shù)組A共占用共占用_(1)_個(gè)字節(jié)個(gè)字節(jié);2)A中中6行和行和4列的數(shù)組元素共占用列的數(shù)組元素共占用_(2)_個(gè)字節(jié)個(gè)字節(jié);3)若按行優(yōu)先順序存放二維數(shù)組若按行優(yōu)先順序存放二維數(shù)組A,其第一個(gè)數(shù)組元素存放其第一個(gè)數(shù)組元素存放的首字節(jié)號(hào)為的首字節(jié)號(hào)為1000(十進(jìn)制十進(jìn)制),則最后一個(gè)數(shù)組元素存放則最后一個(gè)數(shù)組元

11、素存放的首字節(jié)為的首字節(jié)為_(kāi)(3)_4)數(shù)組元素?cái)?shù)組元素A34的首字節(jié)號(hào)為的首字節(jié)號(hào)為_(kāi)(4)_9行行4列列 36*6 2.（9+4-1）*63.1000+216-6 4. 1000+（3*4+（4-2）*61. 數(shù)組數(shù)組A中中,每個(gè)元素每個(gè)元素A的長(zhǎng)度為的長(zhǎng)度為3個(gè)字節(jié)個(gè)字節(jié),行下標(biāo)行下標(biāo)i從從1到到8,列列下標(biāo)下標(biāo)j從從1到到10,從首地址從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),存存放該數(shù)組至少需要的單元數(shù)是放該數(shù)組至少需要的單元數(shù)是?2. 數(shù)組數(shù)組A中中,每個(gè)元素每個(gè)元素A的長(zhǎng)度為的長(zhǎng)度為3個(gè)字節(jié)個(gè)字節(jié),行下標(biāo)行下標(biāo)i從從1到到8,列列下標(biāo)下標(biāo)j從從1到到10,從首地址

12、從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),該該數(shù)組按行存放時(shí)數(shù)組按行存放時(shí),元素元素A85的起始地址為的起始地址為?3. 數(shù)組數(shù)組A中中,每個(gè)元素每個(gè)元素A的長(zhǎng)度為的長(zhǎng)度為3個(gè)字節(jié)個(gè)字節(jié),行下標(biāo)行下標(biāo)i從從1到到8,列列下標(biāo)下標(biāo)j從從1到到10,從首地址從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),該該數(shù)組按列存放時(shí)數(shù)組按列存放時(shí),元素元素A58的起始地址為的起始地址為?240SA+222 SA+(8-1)*10+(5-1)*3SA+180 SA+(8-1)*8+(5-1)*3實(shí)際中，存在許多特殊矩陣，例如在矩陣中有許多實(shí)際中，存在許多特殊矩陣，例如在矩陣中有許多值

13、相值相同同的元素或者的元素或者零元素零元素。 10 0 10 0 10 0 10 0 0. . . . . . . . . . . . .用定長(zhǎng)數(shù)組存儲(chǔ)造成浪費(fèi)。用定長(zhǎng)數(shù)組存儲(chǔ)造成浪費(fèi)。5.2 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)為了節(jié)省存儲(chǔ)空間，需要對(duì)這類矩陣進(jìn)行為了節(jié)省存儲(chǔ)空間，需要對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)壓縮存儲(chǔ)。壓縮存儲(chǔ)壓縮存儲(chǔ)是指為是指為多個(gè)值相同多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；的元素只分配一個(gè)存儲(chǔ)空間；對(duì)對(duì)零元素零元素不分配空間。不分配空間。 對(duì)稱矩陣對(duì)稱矩陣 對(duì)角矩陣對(duì)角矩陣 稀疏矩陣稀疏矩陣 三角矩陣三角矩陣對(duì)稱矩陣是滿足 aij= aji 性質(zhì)的n階矩陣(1i,jn)?？梢?/p>

14、看出可以看出:對(duì)稱矩陣中的元素對(duì)稱矩陣中的元素，故只要，故只要存儲(chǔ)矩陣中存儲(chǔ)矩陣中或或中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，共享一個(gè)存儲(chǔ)空間，的空間。能節(jié)約近的空間。能節(jié)約近一半的存儲(chǔ)空間。一半的存儲(chǔ)空間。1 5 1 3 75 0 8 0 01 8 9 2 63 0 2 5 17 0 6 1 3 a11 a21 a22 a31 a32 a33 an,1 an,2 an,3 an,nK= 0 1 2 3 4 5 n(n-1)/2 n(n+1)/2-1a11a21 a22a31 a32 a33 an,1 an,2 an,3 an,na11 a12 a13 a1n

15、a21 a22 a23 a2na31 a32 a33 a3n an1 an2 an3 annv當(dāng)當(dāng)ij時(shí)時(shí),aij 在矩陣的在矩陣的下三角下三角中。中。在在aij 之前的之前的i-1行行(從第從第1行到第行到第i-1行行)共共有有1+2+i-1=i*(i-1)/2個(gè)元素個(gè)元素,在第在第i行行上上,aij 之前有之前有ai1,ai2,ai3,ai(j-1) 即即j-1個(gè)元個(gè)元素素,因此存儲(chǔ)單元的下標(biāo)因此存儲(chǔ)單元的下標(biāo)k有有: k = i(i-1)/2+( j-1)v當(dāng)當(dāng)ij 時(shí)時(shí)aij 在矩陣的在矩陣的上三角上三角中。中。由于由于aij=aji 所以交換上式所以交換上式i,j可得可得: k =

16、j( j-1)/2+( i-1)a11 a12 a13 a1na21 a22 a23 a2na31 a32 a33 a3n an1 an2 an3 ann公式不要死記硬背公式不要死記硬背應(yīng)掌握其推導(dǎo)過(guò)程應(yīng)掌握其推導(dǎo)過(guò)程二、三角矩陣二、三角矩陣所謂所謂下下(上上)三角矩陣三角矩陣是指矩陣的上是指矩陣的上(下下)三角三角(不包括對(duì)不包括對(duì)角線角線)中的元均為常數(shù)中的元均為常數(shù) c 的的 n 階矩陣。階矩陣。a11a21 a22an1 1 an2 ann. . . . . . .C下三角矩陣下三角矩陣和對(duì)稱矩陣基本一樣，只需除存儲(chǔ)其下和對(duì)稱矩陣基本一樣，只需除存儲(chǔ)其下(上上)三角中的元三角中的元之外

17、，再增加一個(gè)存儲(chǔ)單元存放之外，再增加一個(gè)存儲(chǔ)單元存放 c 。k = i (i 1)2+ j - - 1當(dāng)當(dāng) i j關(guān)鍵問(wèn)題關(guān)鍵問(wèn)題: 如何建立數(shù)組元如何建立數(shù)組元 SAk 和矩陣元和矩陣元 aij 之間的之間的一一對(duì)應(yīng)關(guān)系。一一對(duì)應(yīng)關(guān)系。k = 0123n(n+1)2- - 1n(n+1)2當(dāng)當(dāng) i jn(n+1)2a11a21a22a31annca12 , ,a13 所有非所有非0元素都集元素都集中在以主對(duì)角線為中中在以主對(duì)角線為中心的帶狀區(qū)域。心的帶狀區(qū)域。它可以行為主它可以行為主,或或以對(duì)角線的順序以對(duì)角線的順序,將將其壓縮到一維數(shù)組上。其壓縮到一維數(shù)組上。a00 a01 a02 0 0

18、 0 0 0 0 0a10 a11 a12 a13 0 0 0 0 0 0a20 a21 a22 a23 a24 0 0 0 0 0 0 a31 a32 a33 a34 a35 0 0 0 0 0 0 a42 a43 a44 a45 a46 0 0 0 0 0 0 a53 a54 a55 a56 a57 0 0 0 0 0 0 a64 a65 a66 a67 a68 0 0 0 0 0 0 a75 a76 a77 a78 a79 0 0 0 0 0 0 a86 a87 a88 a89 0 0 0 0 0 0 0 a97 a98 a99oo一般情況一般情況oa11 a12a21 a22 a23a

19、32 a33 a34an,n-1-1 ann an-1-1,no三對(duì)角矩陣三對(duì)角矩陣關(guān)鍵問(wèn)題關(guān)鍵問(wèn)題: 如何建立數(shù)組元如何建立數(shù)組元 SAk 和矩陣元和矩陣元 aij 之間的一一之間的一一對(duì)應(yīng)關(guān)系。對(duì)應(yīng)關(guān)系。k=(3(i-1)-1)+(j-i+2)-1=2i + j - 3(| | i - - j | | 1)a11 a12a21 a22 a23 a32 a33 a34an,n-1-1 ann an-1-1, n-2-2 an-1-1, n-1 -1 an-1-1,n a43 a44 a450aij因因?qū)菙?shù)對(duì)角數(shù)不不同而不同同而不同第第i(i1)行的第行的第j-i+2個(gè)非零元素個(gè)非零元素|1

20、 稀疏矩陣的三元組稀疏矩陣的三元組|2 三元組的順序存儲(chǔ)結(jié)構(gòu)三元組的順序存儲(chǔ)結(jié)構(gòu)|3 三元組的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)三元組的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稀疏矩陣稀疏矩陣非零元很少的矩陣。非零元很少的矩陣。稀疏因子稀疏因子: 設(shè)設(shè) mn 的矩陣，有的矩陣，有 t 個(gè)非零元，令個(gè)非零元，令mnt= ，稱，稱為矩陣的稀疏因子。為矩陣的稀疏因子。通常認(rèn)為通常認(rèn)為 0.05 時(shí)稱為時(shí)稱為稀疏矩陣稀疏矩陣。|稀疏矩陣的非零元素由三部分組成：行下標(biāo)、列下標(biāo)稀疏矩陣的非零元素由三部分組成：行下標(biāo)、列下標(biāo)和矩陣元素值，這稱為稀疏矩陣的三元組。和矩陣元素值，這稱為稀疏矩陣的三元組。|用稀疏矩陣的三元組用稀疏矩陣的三元組序列序列表示為：表示

21、為：1,1,1,3,1,2,3,3,7,4,3,8,4,4,9。 9800070200000001A（2） 三元組的順序存儲(chǔ)結(jié)構(gòu)三元組的順序存儲(chǔ)結(jié)構(gòu)三元組三元組( i ，j ，aij )表示非零元素表示非零元素i 行數(shù)，行數(shù)，j 列數(shù)，列數(shù)，aij 非零元。非零元。M67 = 0 12 9 0 0 0 00 0 0 0 0 0 0- -3 0 0 0 0 14 00 0 0 24 0 0 0 00 0 18 0 0 0 0 01515 0 0 - -7 0 0 0i j aij1 2 121 3 93 1 - -33 6 14144 3 24245 2 18186 1 15156 4 -7-7

22、 SparseNode1類的一個(gè)對(duì)象表示稀疏矩陣的一個(gè)三元組，它類的一個(gè)對(duì)象表示稀疏矩陣的一個(gè)三元組，它只記錄了稀疏矩陣中的一個(gè)元素的位置和值。只記錄了稀疏矩陣中的一個(gè)元素的位置和值。public class SparseNode1 /稀疏矩陣的三元組表示的結(jié)點(diǎn)結(jié)構(gòu) public int row; /行下標(biāo) public int column; /列下標(biāo) public int data; /值 public SparseNode1(int i,int j,int k) row=i; column=j; data=k; public SparseNode1() this(0,0,0); publ

23、ic void output() /輸出一個(gè)元素的三元組值 下面聲明的下面聲明的Sparse1類的一個(gè)對(duì)象則表示一個(gè)稀疏矩陣，類的一個(gè)對(duì)象則表示一個(gè)稀疏矩陣，成員成員table是一個(gè)數(shù)組表示的線性表，元素類型為是一個(gè)數(shù)組表示的線性表，元素類型為SparseNode1類。構(gòu)造方法將一個(gè)稀疏矩陣轉(zhuǎn)換成三元組表示法。類。構(gòu)造方法將一個(gè)稀疏矩陣轉(zhuǎn)換成三元組表示法。public class Sparse1 /稀疏矩陣的三元組順序存儲(chǔ)結(jié)構(gòu) protected SparseNode1 table; /數(shù)組，元素為三元組 public Sparse1(int mat1) /建立三元組表示 System.out

24、.println(稀疏矩陣:); int n=mat1.length; table=new SparseNode1 n*2; /估計(jì)數(shù)組長(zhǎng)度 int i,j,k=0; for(i=0;imat1.length;i+) for(j=0;jmat1i.length;j+) public class Sparse1_ex public static void main(String args) int mat1=1,0,0,0, /稀疏矩陣稀疏矩陣 0,0,0,0, 2,0,7,0, 0,0,8,9; Sparse1 s1=new Sparse1(mat1); /一個(gè)對(duì)象表示一個(gè)稀疏一個(gè)對(duì)象表示一個(gè)

25、稀疏矩陣矩陣 s1.output(); 程序運(yùn)行結(jié)果如下：程序運(yùn)行結(jié)果如下：稀疏矩陣稀疏矩陣: 1 0 0 0 0 0 0 0 2 0 7 0 0 0 8 9稀疏矩陣三元組的順序表示稀疏矩陣三元組的順序表示: 行下標(biāo)行下標(biāo) 列下標(biāo)列下標(biāo) 值值table0 = 111table1 = 312table2 = 337table3 = 438table4 = 449table5 = nulltable6 = nulltable7 = null|數(shù)組長(zhǎng)度不易設(shè)定，可能存在溢出與浪費(fèi)問(wèn)題。數(shù)組長(zhǎng)度不易設(shè)定，可能存在溢出與浪費(fèi)問(wèn)題。|插入、刪除操作不方便。若矩陣元素的值發(fā)生變化，一插入、刪除操作不方便。若

26、矩陣元素的值發(fā)生變化，一個(gè)為零的元素變成非零元素，就要向線性表中插入一個(gè)個(gè)為零的元素變成非零元素，就要向線性表中插入一個(gè)三元組；若非零元素變成零元素，就要從線性表中刪除三元組；若非零元素變成零元素，就要從線性表中刪除一個(gè)三元組。為了保持線性表元素間的相對(duì)次序，進(jìn)行一個(gè)三元組。為了保持線性表元素間的相對(duì)次序，進(jìn)行插入和刪除操作時(shí)，就必須移動(dòng)元素。插入和刪除操作時(shí)，就必須移動(dòng)元素。1行的單鏈表示行的單鏈表示 將稀疏矩陣每行上的若干個(gè)非零元素作為結(jié)點(diǎn)鏈接成一個(gè)將稀疏矩陣每行上的若干個(gè)非零元素作為結(jié)點(diǎn)鏈接成一個(gè)單向鏈表，每條鏈表第單向鏈表，每條鏈表第1個(gè)結(jié)點(diǎn)的引用存放在數(shù)組中。個(gè)結(jié)點(diǎn)的引用存放在數(shù)組中

27、。 常用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有兩種：行（列）的單鏈表示和常用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有兩種：行（列）的單鏈表示和十字鏈表示。十字鏈表示。table1234column data next1112383749圖圖5.1 稀疏矩陣的行的單鏈表示稀疏矩陣的行的單鏈表示 其中，鏈表的每個(gè)結(jié)點(diǎn)由其中，鏈表的每個(gè)結(jié)點(diǎn)由3個(gè)成員組成：個(gè)成員組成：column（列下標(biāo)），（列下標(biāo)），data（值）和（值）和next（后繼結(jié)點(diǎn)的引用）。（后繼結(jié)點(diǎn)的引用）。Table數(shù)組元素存放每數(shù)組元素存放每條鏈表第條鏈表第1個(gè)結(jié)點(diǎn)的引用。個(gè)結(jié)點(diǎn)的引用。 聲明稀疏矩陣以行的單鏈表示為如下的聲明稀疏矩陣以行的單鏈表示為如下的SparseNode

28、2類：類：public class SparseNode2 /稀疏矩陣行的單鏈表示public int column; /列下標(biāo)public int data; /值public SparseNode2 next; /后繼結(jié)點(diǎn)的引用public SparseNode2(int i,int j)column=i;data=j;next=null;public SparseNode2() 下面的下面的Sparse2類實(shí)現(xiàn)稀疏矩陣的行的單鏈表示，成員類實(shí)現(xiàn)稀疏矩陣的行的單鏈表示，成員table是是一個(gè)數(shù)組，元素類型為一個(gè)數(shù)組，元素類型為SparseNode2類。構(gòu)造方法是將一個(gè)稀疏類。構(gòu)造方法是將一

29、個(gè)稀疏矩陣轉(zhuǎn)換成行的單鏈表示。矩陣轉(zhuǎn)換成行的單鏈表示。public class Sparse2 /稀疏矩陣行的單鏈表示protected SparseNode2 table; /數(shù)組元素引用鏈表的第1個(gè)結(jié)點(diǎn)public Sparse2(int mat1) /建立稀疏矩陣行的單鏈表示int n=mat1.length;table=new SparseNode2n+1;int i,j,k=0;SparseNode2 p=null,q;for(i=0;in;i+)p=tablei+1;for(j=0;j null table2=null table3= 1 2 - 3 7 - null table4

30、= 3 8 - 4 9 - null 按行的單鏈表示的稀疏矩陣，每個(gè)結(jié)點(diǎn)可以很容易地按行的單鏈表示的稀疏矩陣，每個(gè)結(jié)點(diǎn)可以很容易地找到行的后繼結(jié)點(diǎn)，但很難找到列的后繼結(jié)點(diǎn)。為充分表找到行的后繼結(jié)點(diǎn)，但很難找到列的后繼結(jié)點(diǎn)。為充分表示行和列的后繼結(jié)點(diǎn)，可以采用十字鏈表示。示行和列的后繼結(jié)點(diǎn)，可以采用十字鏈表示。 將行的單鏈表示和列的單鏈表示結(jié)合起來(lái)存儲(chǔ)稀疏矩將行的單鏈表示和列的單鏈表示結(jié)合起來(lái)存儲(chǔ)稀疏矩陣稱為十字鏈表示。陣稱為十字鏈表示。 1 2 3 412341 1 1 3 3 7 4 3 8 4 4 9 3 1 2 | 每個(gè)結(jié)點(diǎn)表示一個(gè)非零元素。每個(gè)結(jié)點(diǎn)有每個(gè)結(jié)點(diǎn)表示一個(gè)非零元素。每個(gè)結(jié)點(diǎn)有

31、5個(gè)成員：行個(gè)成員：行下標(biāo)，列下標(biāo)，值，行后繼引用以及列后繼引用。下標(biāo)，列下標(biāo)，值，行后繼引用以及列后繼引用。| 從行的角度看，需要一個(gè)數(shù)組存放行的單鏈的第從行的角度看，需要一個(gè)數(shù)組存放行的單鏈的第1個(gè)結(jié)個(gè)結(jié)點(diǎn)；同樣，從列的角度看，還需要一個(gè)數(shù)組存放列的單鏈點(diǎn)；同樣，從列的角度看，還需要一個(gè)數(shù)組存放列的單鏈的第的第1個(gè)結(jié)點(diǎn)。使用這種表示，各行的非零元素和各列的個(gè)結(jié)點(diǎn)。使用這種表示，各行的非零元素和各列的非零元素都分別鏈接在一起，最多有非零元素都分別鏈接在一起，最多有m+n條鏈。條鏈。| 對(duì)元素的查找可順著所在行的鏈進(jìn)行，也可以順著所對(duì)元素的查找可順著所在行的鏈進(jìn)行，也可以順著所在列的鏈進(jìn)行。在列的鏈進(jìn)行。|5.3.1 廣義表的概