數(shù)據(jù)結(jié)構(gòu)數(shù)組課件

1、1第5章 數(shù)組和廣義表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）第5章 數(shù)組和廣義表5.1 數(shù)組5.2 特殊矩陣的壓縮存儲(chǔ)5.3 廣義表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）目的和要求目的：線(xiàn)性結(jié)構(gòu)到非線(xiàn)性結(jié)構(gòu)的過(guò)渡，了解包含子結(jié)構(gòu)的線(xiàn)性結(jié)構(gòu)，理解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在表達(dá)非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)中的作用。內(nèi)容：使用二維數(shù)組表示矩陣及運(yùn)算；三角矩陣、對(duì)稱(chēng)矩陣、稀疏矩陣等各種壓縮存儲(chǔ)方法實(shí)現(xiàn)矩陣運(yùn)算；廣義表的概念、雙鏈表示和實(shí)現(xiàn)。要求：理解多維數(shù)組的存儲(chǔ)結(jié)構(gòu)；熟悉特殊矩陣的壓縮存儲(chǔ)方法；掌握稀疏矩陣三元組從順序表、行的單鏈表到十字鏈表等到多種存儲(chǔ)結(jié)構(gòu)的演變過(guò)程；理解廣義表的概念，熟悉廣義表的存儲(chǔ)結(jié)構(gòu)。重點(diǎn)：討論多種由順序存儲(chǔ)結(jié)

2、構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有機(jī)結(jié)合的存儲(chǔ)結(jié)構(gòu)，以矩陣為例，研究在相同的邏輯結(jié)構(gòu)（矩陣）和操作要求（矩陣運(yùn)算）情況下，根據(jù)各種矩陣的不同特性，采用多種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)矩陣運(yùn)算。 難點(diǎn)：稀疏矩陣的多種存儲(chǔ)和實(shí)現(xiàn)，廣義表的存儲(chǔ)和 實(shí)現(xiàn)。 實(shí)驗(yàn)：特殊矩陣和廣義表的存儲(chǔ)和運(yùn)算。4一、教學(xué)內(nèi)容：1、數(shù)組的定義和順序存儲(chǔ)方式；2、特殊矩陣的壓縮存儲(chǔ)；3、稀疏矩陣4、廣義表的概念、表示及基本操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)。二、教學(xué)要求：1、了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；2、掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；3、了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，理解以三元組表

3、示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法；4、掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，會(huì)對(duì)非空廣義表進(jìn)行分解。 第5章 數(shù)組和廣義表5第5章 數(shù)組和廣義表目的：了解包含子結(jié)構(gòu)的線(xiàn)性結(jié)構(gòu)。要求：理解多維數(shù)組的存儲(chǔ)結(jié)構(gòu)，了解 特殊矩陣壓縮存儲(chǔ)，了解廣義表。重點(diǎn)：難點(diǎn)：廣義表的表示和實(shí)現(xiàn)。75.1 數(shù)組數(shù)組定義 數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組的維數(shù)是由數(shù)組的下標(biāo)的個(gè)數(shù)確定的：一個(gè)下標(biāo)稱(chēng)為一維數(shù)組一個(gè)下標(biāo)以上的數(shù)組稱(chēng)為多維數(shù)組從這個(gè)意義上講，確定了對(duì)于數(shù)組的一個(gè)下標(biāo)總有一個(gè)相應(yīng)的數(shù)值與之對(duì)應(yīng)的關(guān)系；或者說(shuō)數(shù)組是有限個(gè)同類(lèi)型數(shù)據(jù)元素組成的序列數(shù)組是二元組的一個(gè)集合85.1.1 一維數(shù)組一維數(shù)組是指下標(biāo)的個(gè)

4、數(shù)只有一個(gè)的數(shù)組，有時(shí)稱(chēng)為向量，是最基本的數(shù)據(jù)類(lèi)型在java 中需要事先聲明，程序才能夠在編譯過(guò)程中預(yù)留內(nèi)存空間聲明的格式一般是： = new ；一維數(shù)組具有線(xiàn)性表的結(jié)構(gòu)，但操作簡(jiǎn)單，一般不進(jìn)行插入和刪除操作，只定義給定下標(biāo)讀取元素和修改元素的操作10一維數(shù)組的存儲(chǔ)由此可見(jiàn)，求數(shù)組中數(shù)據(jù)元素的地址，已知條件必須是知道第一個(gè)元素的地址，然后主要是找出該元素之前已經(jīng)存儲(chǔ)了多少個(gè)數(shù)據(jù)元素。在一維數(shù)組中，只要知道任何一個(gè)元素的地址即可求出其它元素的地址，但在多維數(shù)組中，已知條件必須是第一個(gè)數(shù)據(jù)元素地址。 5.1.1 一維數(shù)組115.1.1 一維數(shù)組數(shù)組分配內(nèi)存空間的方式有2種靜態(tài)數(shù)組：聲明時(shí)給出數(shù)組元

5、素個(gè)數(shù)。當(dāng)程序開(kāi)始運(yùn)行時(shí)，數(shù)組即獲得系統(tǒng)分配的一塊地址連續(xù)的內(nèi)存空間。靜態(tài)數(shù)組所占用的內(nèi)存空間由系統(tǒng)自動(dòng)管理。動(dòng)態(tài)數(shù)組：聲明時(shí)不指定數(shù)組長(zhǎng)度。當(dāng)程序運(yùn)行中需要使用數(shù)組時(shí)，向系統(tǒng)申請(qǐng)數(shù)組的存儲(chǔ)單元空間，并給出數(shù)組長(zhǎng)度。當(dāng)數(shù)組使用完之后，需要向系統(tǒng)歸還所占用的內(nèi)存空間。數(shù)組容量不夠時(shí)，不能就地?cái)U(kuò)容。前面的做法是，申請(qǐng)一個(gè)更大容量的數(shù)組并進(jìn)行數(shù)組元素復(fù)制。在Java中，數(shù)組元素既可以簡(jiǎn)單數(shù)據(jù)類(lèi)型，也可以是引用類(lèi)型。而且Java中的數(shù)組都是動(dòng)態(tài)數(shù)組。125.1.2 多維數(shù)組多維數(shù)組多維數(shù)組是指下標(biāo)的個(gè)數(shù)有兩個(gè)以上，我們比較常用的是二維數(shù)組（因?yàn)槿S以上的數(shù)組存儲(chǔ)可以簡(jiǎn)化為二維數(shù)組的存儲(chǔ)）。下面以二維數(shù)

6、組為例說(shuō)明多維數(shù)組。二維數(shù)組的聲明同一維數(shù)組。格式為： =new size1 size2;145.1.2 多維數(shù)組二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線(xiàn)性關(guān)系，即存在兩個(gè)前驅(qū)（前件）和兩個(gè)后繼（后件）。也可看作是以線(xiàn)性表為數(shù)據(jù)元素的線(xiàn)性表。n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線(xiàn)性關(guān)系。可看作是數(shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組是對(duì)線(xiàn)性表的擴(kuò)展：線(xiàn)性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線(xiàn)性表。155.1.2 多維數(shù)組對(duì)于數(shù)組與線(xiàn)性表的關(guān)系的兩種不同理解，可圖示如下，以三維數(shù)組array534為例：175.1.2

7、 多維數(shù)組由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線(xiàn)性序列存放在存儲(chǔ)器中。又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說(shuō)，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法來(lái)表示數(shù)組。185.1.2 多維數(shù)組靜態(tài)多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)以二維數(shù)組的順序存儲(chǔ)為例說(shuō)明，二維數(shù)組在順序存儲(chǔ)時(shí)一般有兩種：行優(yōu)先順序：存儲(chǔ)時(shí)先按行從小到大的順序存儲(chǔ)，在每一行中按列號(hào)從小到大存儲(chǔ)。列優(yōu)先順序：存儲(chǔ)時(shí)先按列從小到大的順序存儲(chǔ)，在每一列中按行號(hào)從小到大存儲(chǔ)。以上的兩種存儲(chǔ)順序中，第一個(gè)被存放的元素總是第

8、一行第一列的數(shù)據(jù)元素，所以該元素的地址是我們的已知條件。195.1.2 多維數(shù)組以二維數(shù)組arr23為例：205.1.2 多維數(shù)組215.1.2 多維數(shù)組以行序?yàn)橹餍颍ò葱写鎯?chǔ)）的方法： “左”下標(biāo)優(yōu)先 以列序?yàn)橹餍颍ò戳写鎯?chǔ)）的方法： “右”下標(biāo)優(yōu)先225.1.2 多維數(shù)組多維數(shù)組同樣在二維數(shù)組中比較典型的是計(jì)算數(shù)據(jù)的存儲(chǔ)位置。假設(shè)二維數(shù)組是m*n的二維數(shù)組（共有m行，每行有n列）。第一個(gè)數(shù)據(jù)元素的地址是loc(a11)，則第i行第j列的數(shù)據(jù)元素的地址的計(jì)算公式應(yīng)為（按照行優(yōu)先順序存儲(chǔ)）：loc(aij)=loc(a11)+（i-1）*n+j-1*c假設(shè)下標(biāo)從1開(kāi)始，我們需要計(jì)算出i行前面已

9、經(jīng)存儲(chǔ)了i-1行元素，每行有n個(gè)元素，共有（i-1）*n個(gè)數(shù)據(jù)元素，在第i行元素中，j列之前有j-1個(gè)數(shù)據(jù)元素，共有（i-1）*n+j-1個(gè)元素，每個(gè)元素占有c個(gè)存儲(chǔ)單元，只要乘以c就可以了。其中l(wèi)oc(aij)表示第i 行第j列數(shù)據(jù)元素的內(nèi)存的起始位置，loc(a11)表示第一個(gè)數(shù)據(jù)元素的內(nèi)存位置，c表示每個(gè)數(shù)據(jù)元素所占有的內(nèi)存空間的大小，如果下標(biāo)從0開(kāi)始，只要不用減1即可。 245.1.2 多維數(shù)組多維數(shù)組按此公式可以推廣到多維數(shù)組的數(shù)據(jù)元素的地址計(jì)算（假設(shè)按照行優(yōu)先順序存儲(chǔ)）： m行n 列縱標(biāo)為k的三維數(shù)組，假設(shè)第一個(gè)元素的地址是loc(a111)，如果按行優(yōu)先順序存儲(chǔ)，i行j列縱標(biāo)為p

10、的數(shù)據(jù)元素的地址為（可以將它分解為二維數(shù)組）： loc(aijp)=loc(a111)+(i-1)*n*k+(j-1)*k +p-1*c;如果下標(biāo)從0開(kāi)始，只要不用減1即可。讀者可以從以上的地址公式中可以找出一定的地址計(jì)算規(guī)律：多維數(shù)組中按行優(yōu)先計(jì)算公式用一個(gè)下標(biāo)乘以后面的最大值。 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.1 數(shù)組（1）靜態(tài)順序存儲(chǔ) 行主序列主序 275.1.2 多維數(shù)組【例5.1】 矩陣類(lèi)。本例聲明Matrix類(lèi)表示矩陣，成員table是一個(gè)元素類(lèi)型為整型的二維數(shù)組。add()方法實(shí)現(xiàn)兩個(gè)矩陣相加。28矩陣運(yùn)算主要有矩陣加、矩陣減、矩陣乘、矩陣轉(zhuǎn)置等。矩陣加（C=A+B）定義為

11、public class Matrix private int value;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）【例5.1】 矩陣類(lèi)。設(shè) ，有設(shè) ，有設(shè) ，有設(shè) ，有305.2 特殊矩陣的壓縮存儲(chǔ)在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1。315.2特殊矩陣的壓縮存儲(chǔ)但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來(lái)存儲(chǔ)密度仍為1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造

12、成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間， 我們可以對(duì)這類(lèi)矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。325.2特殊矩陣的壓縮存儲(chǔ)所謂矩陣的壓縮存儲(chǔ)，也就是在存儲(chǔ)數(shù)組時(shí)，盡量減少存儲(chǔ)空間，但是數(shù)組中的每個(gè)元素必須存儲(chǔ)，所以在矩陣存儲(chǔ)中，如果有規(guī)律可尋，只要存儲(chǔ)其中一部分，而另一部分的存儲(chǔ)地址可以通過(guò)相應(yīng)的算法將它計(jì)算出來(lái)，從而占有比較少的存儲(chǔ)空間達(dá)到存儲(chǔ)整個(gè)矩陣的目的，稱(chēng)為矩陣的壓縮存儲(chǔ)。矩陣的壓縮存儲(chǔ)僅是針對(duì)特殊矩陣的；而對(duì)于沒(méi)有規(guī)律可循的二維數(shù)組則不能夠使用壓縮存儲(chǔ)。二維數(shù)組（矩陣）的壓縮存儲(chǔ)一般有三種，它們分別是對(duì)稱(chēng)矩陣、稀疏矩陣和三角矩陣。三種矩陣中以稀疏矩陣

13、比較常見(jiàn)。 33三角矩陣 以主對(duì)角線(xiàn)劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線(xiàn)）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)角線(xiàn)上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩陣 (b)下三角矩陣 5.2 矩陣的壓縮存儲(chǔ) 34 三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到數(shù)組sa0.n(n+1

14、)/2中，其中c存放在數(shù)組的最后一個(gè)元素中5.2 矩陣的壓縮存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.2.1 三角矩陣的壓縮存儲(chǔ)三角矩陣的壓縮存儲(chǔ)（1）線(xiàn)性壓縮存儲(chǔ)三角矩陣 36三角矩陣 （1）下三角矩陣下三角矩陣的壓縮存放與對(duì)稱(chēng)矩陣用下三角形式存放類(lèi)似，但必須多一個(gè)存儲(chǔ)單元存放上三角部分元素，使用的存儲(chǔ)單元數(shù)目為n(n+1)/2+1。故可以將nn的下三角矩陣壓縮存放到只有n(n+1)/2+1個(gè)存儲(chǔ)單元的數(shù)組中，假設(shè)仍按行優(yōu)先存放，這時(shí)sk與aij的對(duì)應(yīng)關(guān)系為： i(i+1)/2+j ij，i 、j0 k= n(n+1)/2 ij 5.2 矩陣的壓縮存儲(chǔ) 三角矩陣 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3

15、版）（2）使用三角形的二維數(shù)組壓縮存儲(chǔ)三角矩陣 405.2 矩陣的壓縮存儲(chǔ) 對(duì)稱(chēng)矩陣若n 階矩陣A中的元素滿(mǎn)足以下條件： aij=aji i1，j1 則稱(chēng)為n階對(duì)稱(chēng)矩陣。對(duì)于對(duì)稱(chēng)矩陣，如果不采用壓縮存儲(chǔ)，占有的存儲(chǔ)單元有n2個(gè)，因?yàn)槭菍?duì)稱(chēng)矩陣，所以只要存儲(chǔ)對(duì)角的數(shù)據(jù)元素和一半的數(shù)據(jù)元素即可，占有的存儲(chǔ)單元有n（n-1）/2個(gè)存儲(chǔ)單元中。如果我們以行序?yàn)橹餍虼鎯?chǔ)其下三角（包括對(duì)角線(xiàn)）的元素，其上三角的元素可以推算出來(lái)。415.2 矩陣的壓縮存儲(chǔ) 對(duì)稱(chēng)矩陣如果用一維數(shù)組存儲(chǔ)一個(gè)對(duì)稱(chēng)矩陣，只要將對(duì)稱(chēng)矩陣存儲(chǔ)在一個(gè)最大下標(biāo)為n（n-1）/2的一維數(shù)組S中即可。此時(shí)按照行優(yōu)先順序存儲(chǔ)，數(shù)據(jù)元素aij與數(shù)

16、組S的下標(biāo)k的對(duì)應(yīng)關(guān)系為（why?）： i(i-1)/2 +j-1 當(dāng)ij時(shí) k= j(j-1)/2 + i-1 當(dāng)ij時(shí)425.2 矩陣的壓縮存儲(chǔ) 對(duì)稱(chēng)矩陣對(duì)于任意給定的一組下標(biāo)（i，j），均可在S中找到元素aij，反之，對(duì)所有元素都能夠確定在S中位置，當(dāng)ij時(shí)，根據(jù)對(duì)稱(chēng)矩陣的性質(zhì)推算即可。由此可以看出對(duì)稱(chēng)矩陣的存儲(chǔ)可以使用一維數(shù)組S存儲(chǔ)，占用的空間不再是n2，而是n（n-1）/2空間減少了接近一半，實(shí)現(xiàn)了二維數(shù)組的壓縮存儲(chǔ)。43 （1）只存放下三角部分由于對(duì)稱(chēng)矩陣關(guān)于主對(duì)角線(xiàn)對(duì)稱(chēng)，故我們只需存放主對(duì)角線(xiàn)及主對(duì)角線(xiàn)以下的元素。這時(shí)， a00存入s0，a10 存入s1，a11存入 s2，具體參

17、見(jiàn)圖5-4。這時(shí)sk與aij的對(duì)應(yīng)關(guān)系為： i(i+1)/2+j 當(dāng) ij k= j(j+1)/2+i 當(dāng) ij 上面的對(duì)應(yīng)關(guān)系讀者很容易推出：當(dāng)ij 時(shí)，aij在下三角部分中，aij前面有i行，共有1+2+3+i個(gè)元素，而aij是第i行的第j個(gè)元素，即有k=1+2+3+i+j=i(i+1)/2+j；當(dāng)ij時(shí)，交換i與j即可。故sk與aij的對(duì)應(yīng)關(guān)系為： i*n- +j-i 當(dāng)ij k= j*n- +i-j 當(dāng)ij46數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.對(duì)稱(chēng)矩陣的壓縮存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）3.對(duì)角矩陣的壓縮存儲(chǔ) 495.2 稀疏矩陣稀疏矩陣對(duì)稀疏矩陣很難下一個(gè)確切的定義，它只是

18、一個(gè)憑人們的直覺(jué)來(lái)理解的概念。一般認(rèn)為，一個(gè)較大的矩陣中，零元素的個(gè)數(shù)相對(duì)于整個(gè)矩陣元素的總個(gè)數(shù)所占比例較大時(shí)，該矩陣就是一個(gè)稀疏矩陣。例如，有一個(gè)66階的矩陣A，其36個(gè)元素中只有8個(gè)非零元素，那么，可以稱(chēng)矩陣A為稀疏矩陣。50515.2 稀疏矩陣稀疏矩陣稀疏矩陣一般是指矩陣中的大部分元素為零，僅有少量元素非零的矩陣稱(chēng)為稀疏矩陣；或者說(shuō)矩陣A（m n）中有S個(gè)非零元素，如果S遠(yuǎn)遠(yuǎn)小于矩陣的元素總數(shù)，稱(chēng)A為稀疏矩陣。稀疏矩陣的存儲(chǔ)一般只要保存非零元素即可，對(duì)于零元素可以不與保存，這樣可以實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)。 525.2 稀疏矩陣稀疏矩陣稀疏矩陣的壓縮存儲(chǔ)采用三元組的方法實(shí)現(xiàn)。其存儲(chǔ)規(guī)則如下

19、：每一個(gè)非零元素占有一行，每行中包含非零元素所在的行號(hào)、列號(hào)、非零元素的數(shù)值。53表示稀疏矩陣的三元組 (0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,5,28)，(4,4,50)行號(hào)列號(hào)元素值rowcolumnvalue54555.2 稀疏矩陣稀疏矩陣如果每個(gè)非零元素按照此種方法存儲(chǔ)，雖然能夠完整地描述非零元素，但如果矩陣中有整行（或整列）中沒(méi)有非零元素，此時(shí)可能不能夠還原成原來(lái)的矩陣所以為了完整地描述稀疏矩陣，在以上描述的情況下，如果增加一行的內(nèi)容，該行包括矩陣的總的行數(shù)、矩陣的總的列數(shù)，矩陣中非零元素的個(gè)數(shù)，就可以還原為原來(lái)的矩陣描述了。 56例如，下列三元

20、組表(6,7，8),(1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7) 加上(6,7，8)這一對(duì)行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0

21、 0 0 0 0 0 0 0 0 0 0 0 0 0M=T=5.2 稀疏矩陣575.2 稀疏矩陣稀疏矩陣歸納起來(lái)，若一個(gè)稀疏矩陣有t個(gè)非零元素，則需要用t+1行的三元組來(lái)表示稀疏矩陣。到底矩陣何時(shí)使用三元組存儲(chǔ)呢？一般對(duì)mn的矩陣來(lái)說(shuō)，只要滿(mǎn)足（t+1）*3m*n這個(gè)條件，使用三元組存儲(chǔ)可以節(jié)省空間，否則更加浪費(fèi)空間，也就沒(méi)有必要使用三元組存儲(chǔ)，所以稀疏矩陣中的非零元素的個(gè)數(shù)t是能否使用三元組存儲(chǔ)的關(guān)鍵。 585.2 稀疏矩陣稀疏矩陣轉(zhuǎn)換為三元組存儲(chǔ) 首先應(yīng)該將稀疏矩陣轉(zhuǎn)換為三元組存儲(chǔ)，然后才利用三元組的存儲(chǔ)，實(shí)現(xiàn)對(duì)矩陣的各種運(yùn)算。595.2 稀疏矩陣表5.1 稀疏矩陣三元組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組

22、下標(biāo)行下標(biāo)列下標(biāo)數(shù)據(jù)元素值01111312233734384449數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.稀疏矩陣三元組順序表 （1）稀疏矩陣三元組順序表類(lèi) public class SeqSparseMatrix int rows, columns; /矩陣行數(shù)、列數(shù) SeqList list; /三元組順序表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.稀疏矩陣三元組順序表（2）獲得或設(shè)置稀疏矩陣元素值（3）稀疏矩陣描述字符串 （4）稀疏矩陣相加 【例5.2】三元組順序表表示的稀疏矩陣及其加法運(yùn)算。625.2 稀疏矩陣三元組的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1三元組單鏈表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）4.稀疏矩陣行的單

23、鏈表 （1）稀疏矩陣三元組行的單鏈表類(lèi)public class LinkedSparseMatrix int rows, columns; /矩陣行數(shù)、列數(shù) SeqListPolySLinkedList list; /行指針順序表，元素是多項(xiàng)式排序單鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）4.稀疏矩陣行的單鏈表（2）獲得或設(shè)置稀疏矩陣元素值（3）稀疏矩陣描述字符串 （4）稀疏矩陣相加 （5）深度拷貝及應(yīng)用 655.2 稀疏矩陣三元組的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3十字鏈表示數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）（6）比較兩個(gè)矩陣是否相等數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.十字鏈表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）十字鏈

24、表存儲(chǔ)的稀疏矩陣類(lèi)public class CrossNode /十字鏈表結(jié)點(diǎn)類(lèi) Triple data; /數(shù)據(jù)域表示三元組 CrossNode right, down; /right指向行的下一個(gè)結(jié)點(diǎn)，down指向列的下一個(gè)結(jié)點(diǎn)public class CrossLinkedSparseMatrix int rows, columns; /矩陣行數(shù)、列數(shù) CrossNode rowheads,columnheads; /行、列指針數(shù)組 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.3 廣義表5.3.1 廣義表抽象數(shù)據(jù)類(lèi)型5.3.2 廣義表的存儲(chǔ)結(jié)構(gòu)5.3.3 廣義表雙鏈表示的實(shí)現(xiàn) 5.3.4 m元多項(xiàng)式的廣義表表示705.3 廣義表 廣義表的定義廣義表是線(xiàn)性表的擴(kuò)展，具體定義為n（n0）個(gè)元素的有限集合。其中元素有以下兩種類(lèi)型：1）一個(gè)原子元素（指不可再分的元素）；2）一個(gè)可以再分的元素（或稱(chēng)為一個(gè)子表）。如果所有元素都是原子元素，則稱(chēng)為線(xiàn)性表，如果含有子表則是廣義表。N的值是廣義表的長(zhǎng)度，如果n=0，稱(chēng)為空表。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.3.1 廣義表抽象數(shù)據(jù)類(lèi)型廣義表定義 GList = (a0, a1, an-1)中國(guó)(北京, 上海, 江蘇(南京, 蘇州), 浙江(杭州), 廣東(廣州) L(a,