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

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版）》目的和要求目的：線性結(jié)構(gòu)到非線性結(jié)構(gòu)的過(guò)渡，了解包含子結(jié)構(gòu) 的線性結(jié)構(gòu)，理解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在表達(dá)非線性數(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é)構(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)和適用范圍，理解以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法；

4、 掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，會(huì)對(duì)非空廣義表進(jìn)行分解。

第5章數(shù)組和廣義表5第5章數(shù)組和廣義表目的：了解包含子結(jié)構(gòu)的線性結(jié)構(gòu)。要求：理解多維數(shù)組的存儲(chǔ)結(jié)構(gòu)，了解 特殊矩陣壓縮存儲(chǔ)，了解廣義表。重點(diǎn)：難點(diǎn)：廣義表的表示和實(shí)現(xiàn)。65.1數(shù)組－－數(shù)組定義

數(shù)組是數(shù)據(jù)結(jié)構(gòu)的基本結(jié)構(gòu)形式，它是一種順序式的結(jié)構(gòu)，數(shù)組是存儲(chǔ)同一類(lèi)型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)使用數(shù)組時(shí)需要定義數(shù)組的大小和存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)類(lèi)型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ù)組是二元組<下標(biāo)，值>的一個(gè)集合85.1.1一維數(shù)組一維數(shù)組是指下標(biāo)的個(gè)數(shù)只有一個(gè)的數(shù)組，有時(shí)稱(chēng)為向量，是最基本的數(shù)據(jù)類(lèi)型在java中需要事先聲明，程序才能夠在編譯過(guò)程中預(yù)留內(nèi)存空間聲明的格式一般是：

<數(shù)據(jù)類(lèi)型><變量名稱(chēng)>[]=new<數(shù)據(jù)類(lèi)型>[<數(shù)組大小>]；一維數(shù)組具有線性表的結(jié)構(gòu)，但操作簡(jiǎn)單，一般不進(jìn)行插入和刪除操作，只定義給定下標(biāo)讀取元素和修改元素的操作9一維數(shù)組的存儲(chǔ)一維數(shù)組的數(shù)據(jù)存儲(chǔ)按照順序存儲(chǔ)，邏輯地址和物理地址都是連續(xù)的。如果已知第一個(gè)數(shù)據(jù)元素的地址loc(a0)，則第i個(gè)元素的地址loc(ai)為：Loc(ai)=Loc(a0)＋i×c假設(shè)數(shù)組的下標(biāo)從0開(kāi)始，只要求出第i個(gè)元素之前存放了多少個(gè)數(shù)據(jù)元素即可（實(shí)際上有i個(gè)元素），每個(gè)元素占有c個(gè)存儲(chǔ)單元，再乘以c，就是第i個(gè)元素的起始地址。5.1.1一維數(shù)組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ù)組元素個(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ù)組為例說(shuō)明多維數(shù)組。二維數(shù)組的聲明同一維數(shù)組。格式為：

<數(shù)據(jù)類(lèi)型><數(shù)組名稱(chēng)>[][]=new<數(shù)據(jù)類(lèi)型>[size1][size2];135.1.2多維數(shù)組例如，設(shè)A是一個(gè)有m行n列的二維數(shù)組，則A可以表示為：在此，可以將二維數(shù)組A看成是由m個(gè)行向量[X0，X1，…，Xm-1]T組成，其中，Xi=(ai0,ai1,….,ain-1)，0≤i≤m-1；也可以將二維數(shù)組A看成是由n個(gè)列向量[y0,y1,……,yn-1]組成，其中yi=(a0i,a1i,…..,am-1i)，0≤i≤n-1。145.1.2多維數(shù)組二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)前驅(qū)（前件）和兩個(gè)后繼（后件）。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系?？煽醋魇菙?shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組是對(duì)線性表的擴(kuò)展：線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。155.1.2多維數(shù)組對(duì)于數(shù)組與線性表的關(guān)系的兩種不同理解，可圖示如下，以三維數(shù)組array[5][3][4]為例：165.1.2多維數(shù)組多維數(shù)組的遍歷（1）行優(yōu)先次序a1,1，a1,2，…，a1,n，a2,1，a2,2，…，a2,n，…，am,1，am,2，…，am,n（2）列優(yōu)先次序a1,1，a2,1，…，am,1，a1,2，a2,2，…，am,2，…，a1,n，a2,n，…，am,n175.1.2多維數(shù)組由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(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è)被存放的元素總是第一行第一列的數(shù)據(jù)元素，所以該元素的地址是我們的已知條件。195.1.2多維數(shù)組以二維數(shù)組arr[2][3]為例：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行前面已經(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即可。235.1.2多維數(shù)組多維數(shù)組如果按列優(yōu)先順序存儲(chǔ)，則地址的計(jì)算為：

loc(aij)=loc(a11)+[（j-1）*m+i-1]*c假設(shè)下標(biāo)從1開(kāi)始，其中l(wèi)oc(aij)表示第i行第j列的數(shù)據(jù)元素的內(nèi)存起始位置，loc(a11)表示第一個(gè)數(shù)據(jù)元素的內(nèi)存位置，c表示每個(gè)數(shù)據(jù)元素所占有的內(nèi)存空間的大小；主要還是計(jì)算第i行j列元素之前有多少個(gè)數(shù)據(jù)元素。如果下標(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的數(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ǔ)行主序列主序《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（2）動(dòng)態(tài)二維數(shù)組的存儲(chǔ)結(jié)構(gòu)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）定義為publicclassMatrix{privateintvalue[][];}《數(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ì)造成極大的浪費(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)矩陣、稀疏矩陣和三角矩陣。三種矩陣中以稀疏矩陣比較常見(jiàn)。

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

a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣

5.2矩陣的壓縮存儲(chǔ)34

三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到數(shù)組sa[0..n(n+1)/2]中，其中c存放在數(shù)組的最后一個(gè)元素中5.2矩陣的壓縮存儲(chǔ)《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》5.2.1三角矩陣的壓縮存儲(chǔ)三角矩陣的壓縮存儲(chǔ)（1）線性壓縮存儲(chǔ)三角矩陣36三角矩陣

（1）下三角矩陣下三角矩陣的壓縮存放與對(duì)稱(chēng)矩陣用下三角形式存放類(lèi)似，但必須多一個(gè)存儲(chǔ)單元存放上三角部分元素，使用的存儲(chǔ)單元數(shù)目為n(n+1)/2+1。故可以將n

n的下三角矩陣壓縮存放到只有n(n+1)/2+1個(gè)存儲(chǔ)單元的數(shù)組中，假設(shè)仍按行優(yōu)先存放，這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i(i+1)/2+ji≥j，i、j≥0k=n(n+1)/2i<j5.2矩陣的壓縮存儲(chǔ)《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（1）線性壓縮存儲(chǔ)上三角矩陣38(2)上三角矩陣和下三角矩陣的存儲(chǔ)類(lèi)似，共需n(n+1)/2+1個(gè)存貯單元，假設(shè)仍按行優(yōu)先順序存放，這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i*n-i(i-1)/2+j-i當(dāng)i≤jk=n(n+1)/2i>j5.2矩陣的壓縮存儲(chǔ)三角矩陣《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（2）使用三角形的二維數(shù)組壓縮存儲(chǔ)三角矩陣405.2矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩陣若n階矩陣A中的元素滿足以下條件：

aij=ajii≥1，j≥1

則稱(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ì)角線）的元素，其上三角的元素可以推算出來(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ù)組S的下標(biāo)k的對(duì)應(yīng)關(guān)系為（why???）：

i(i-1)/2+j-1當(dāng)i≥j時(shí)

k=j(j-1)/2+i-1當(dāng)i＜j時(shí)425.2矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩陣對(duì)于任意給定的一組下標(biāo)（i，j），均可在S中找到元素aij，反之，對(duì)所有元素都能夠確定在S中位置，當(dāng)i＜j時(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ì)角線對(duì)稱(chēng)，故我們只需存放主對(duì)角線及主對(duì)角線以下的元素。這時(shí)，a[0][0]存入s[0]，a[1][0]存入s[1]，a[1][1]存入s[2]，…，具體參見(jiàn)圖5-4。這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i(i+1)/2+j當(dāng)i≥jk=j(j+1)/2+i當(dāng)i<j上面的對(duì)應(yīng)關(guān)系讀者很容易推出：當(dāng)i≥j時(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)i<j時(shí)，aij在上三角部分中，但與aji對(duì)稱(chēng)，故只需在下三角部分中找aij即可，故只需將i與j交換即可，即k=j(j+1)/2+i。4445(2)只存放上三角部分對(duì)于對(duì)稱(chēng)陣，除了用下三角形式存放外，還可以用上三角形式存放，這時(shí)a[0][0]存入s[0],a[0][1]存入s[1]，a[0][2]存入s[2]，…，具體參見(jiàn)圖5-5。這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系可以按下面方法推出：當(dāng)i≤j時(shí)，aij在上三角部分中，前面共有i行，共有n+n-1+…+n-(i-1)=i*n-個(gè)元素，而aij是本行第j-i個(gè)元素，故k=i*n-+j-i，當(dāng)i>j時(shí)，交換i與j即可。故s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i*n-+j-i當(dāng)i≤jk=j*n-+i-j當(dāng)i>j46《數(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è)確切的定義，它只是一個(gè)憑人們的直覺(jué)來(lái)理解的概念。一般認(rèn)為，一個(gè)較大的矩陣中，零元素的個(gè)數(shù)相對(duì)于整個(gè)矩陣元素的總個(gè)數(shù)所占比例較大時(shí)，該矩陣就是一個(gè)稀疏矩陣。例如，有一個(gè)6×6階的矩陣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ī)則如下：每一個(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)容，該行包括