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

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

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

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

4、數(shù)只有一個(gè)的數(shù)組，有時(shí)稱為向量，是最基本的數(shù)據(jù)類型在java 中需要事先聲明，程序才能夠在編譯過程中預(yù)留內(nèi)存空間聲明的格式一般是： = new ；一維數(shù)組具有線性表的結(jié)構(gòu)，但操作簡單，一般不進(jìn)行插入和刪除操作，只定義給定下標(biāo)讀取元素和修改元素的操作10一維數(shù)組的存儲由此可見，求數(shù)組中數(shù)據(jù)元素的地址，已知條件必須是知道第一個(gè)元素的地址，然后主要是找出該元素之前已經(jīng)存儲了多少個(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)程序開始運(yùn)行時(shí)，數(shù)組即獲得系統(tǒng)分配的一塊地址連續(xù)的內(nèi)存空間。靜態(tài)數(shù)組所占用的內(nèi)存空間由系統(tǒng)自動管理。動態(tài)數(shù)組：聲明時(shí)不指定數(shù)組長度。當(dāng)程序運(yùn)行中需要使用數(shù)組時(shí)，向系統(tǒng)申請數(shù)組的存儲單元空間，并給出數(shù)組長度。當(dāng)數(shù)組使用完之后，需要向系統(tǒng)歸還所占用的內(nèi)存空間。數(shù)組容量不夠時(shí)，不能就地?cái)U(kuò)容。前面的做法是，申請一個(gè)更大容量的數(shù)組并進(jìn)行數(shù)組元素復(fù)制。在Java中，數(shù)組元素既可以簡單數(shù)據(jù)類型，也可以是引用類型。而且Java中的數(shù)組都是動態(tài)數(shù)組。125.1.2 多維數(shù)組多維數(shù)組多維數(shù)組是指下標(biāo)的個(gè)數(shù)有兩個(gè)以上，我們比較常用的是二維數(shù)組（因?yàn)槿S以上的數(shù)組存儲可以簡化為二維數(shù)組的存儲）。下面以二維數(shù)

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

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

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

9、經(jīng)存儲了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è)存儲單元，只要乘以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開始，只要不用減1即可。 245.1.2 多維數(shù)組多維數(shù)組按此公式可以推廣到多維數(shù)組的數(shù)據(jù)元素的地址計(jì)算（假設(shè)按照行優(yōu)先順序存儲）： m行n 列縱標(biāo)為k的三維數(shù)組，假設(shè)第一個(gè)元素的地址是loc(a111)，如果按行優(yōu)先順序存儲，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開始，只要不用減1即可。讀者可以從以上的地址公式中可以找出一定的地址計(jì)算規(guī)律：多維數(shù)組中按行優(yōu)先計(jì)算公式用一個(gè)下標(biāo)乘以后面的最大值。 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.1 數(shù)組（1）靜態(tài)順序存儲 行主序列主序 275.1.2 多維數(shù)組【例5.1】 矩陣類。本例聲明Matrix類表示矩陣，成員table是一個(gè)元素類型為整型的二維數(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】 矩陣類。設(shè) ，有設(shè) ，有設(shè) ，有設(shè) ，有305.2 特殊矩陣的壓縮存儲在科學(xué)與工程計(jì)算問題中，矩陣是一種常用的數(shù)學(xué)對象，在高級語言編制程序時(shí)，簡單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單，并且存儲的密度為1。315.2特殊矩陣的壓縮存儲但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲密度仍為1，但實(shí)際上占用了許多單元去存儲重復(fù)的非零元素或零元素，這對高階矩陣會造

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

13、比較常見。 33三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(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 矩陣的壓縮存儲 34 三角矩陣中的重復(fù)元素c可共享一個(gè)存儲空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲到數(shù)組sa0.n(n+1

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

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

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

17、見圖5-4。這時(shí)sk與aij的對應(yīng)關(guān)系為： i(i+1)/2+j 當(dāng) ij k= j(j+1)/2+i 當(dāng) ij 上面的對應(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的對應(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.對稱矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）3.對角矩陣的壓縮存儲 495.2 稀疏矩陣稀疏矩陣對稀疏矩陣很難下一個(gè)確切的定義，它只是

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

19、：每一個(gè)非零元素占有一行，每行中包含非零元素所在的行號、列號、非零元素的數(shù)值。53表示稀疏矩陣的三元組 (0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,5,28)，(4,4,50)行號列號元素值rowcolumnvalue54555.2 稀疏矩陣稀疏矩陣如果每個(gè)非零元素按照此種方法存儲，雖然能夠完整地描述非零元素，但如果矩陣中有整行（或整列）中沒有非零元素，此時(shí)可能不能夠還原成原來的矩陣所以為了完整地描述稀疏矩陣，在以上描述的情況下，如果增加一行的內(nèi)容，該行包括矩陣的總的行數(shù)、矩陣的總的列數(shù)，矩陣中非零元素的個(gè)數(shù)，就可以還原為原來的矩陣描述了。 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)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。 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 稀疏矩陣稀疏矩陣歸納起來，若一個(gè)稀疏矩陣有t個(gè)非零元素，則需要用t+1行的三元組來表示稀疏矩陣。到底矩陣何時(shí)使用三元組存儲呢？一般對mn的矩陣來說，只要滿足（t+1）*3m*n這個(gè)條件，使用三元組存儲可以節(jié)省空間，否則更加浪費(fèi)空間，也就沒有必要使用三元組存儲，所以稀疏矩陣中的非零元素的個(gè)數(shù)t是能否使用三元組存儲的關(guān)鍵。 585.2 稀疏矩陣稀疏矩陣轉(zhuǎn)換為三元組存儲 首先應(yīng)該將稀疏矩陣轉(zhuǎn)換為三元組存儲，然后才利用三元組的存儲，實(shí)現(xiàn)對矩陣的各種運(yùn)算。595.2 稀疏矩陣表5.1 稀疏矩陣三元組的順序存儲結(jié)構(gòu)數(shù)組

22、下標(biāo)行下標(biāo)列下標(biāo)數(shù)據(jù)元素值01111312233734384449數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.稀疏矩陣三元組順序表 （1）稀疏矩陣三元組順序表類 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)酱鎯Y(jié)構(gòu)1三元組單鏈表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）4.稀疏矩陣行的單

23、鏈表 （1）稀疏矩陣三元組行的單鏈表類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)酱鎯Y(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、表存儲的稀疏矩陣類public class CrossNode /十字鏈表結(jié)點(diǎn)類 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ù)類型5.3.2 廣義表的存儲結(jié)構(gòu)5.3.3 廣義表雙鏈表示的實(shí)現(xiàn) 5.3.4 m元多項(xiàng)式的廣義表表示705.3 廣義表 廣義表的定義廣義表是線性表的擴(kuò)展，具體定義為n（n0）個(gè)元素的有限集合。其中元素有以下兩種類型：1）一個(gè)原子元素（指不可再分的元素）；2）一個(gè)可以再分的元素（或稱為一個(gè)子表）。如果所有元素都是原子元素，則稱為線性表，如果含有子表則是廣義表。N的值是廣義表的長度，如果n=0，稱為空表。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.3.1 廣義表抽象數(shù)據(jù)類型廣義表定義 GList = (a0, a1, an-1)中國(北京, 上海, 江蘇(南京, 蘇州), 浙江(杭州), 廣東(廣州) L(a,