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

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)在表達非線性數(shù)據(jù)結(jié) 構(gòu)中的作用。內(nèi)容：使用二維數(shù)組表示矩陣及運算；三角矩陣、對稱矩 陣、稀疏矩陣等各種壓縮存儲方法實現(xiàn)矩陣運算；廣 義表的概念、雙鏈表示和實現(xiàn)。要求：理解多維數(shù)組的存儲結(jié)構(gòu)；熟悉特殊矩陣的壓縮存 儲方法；掌握稀疏矩陣三元組從順序表、行的單鏈表 到十字鏈表等到多種存儲結(jié)構(gòu)的演變過程；理解廣義 表的概念，熟悉廣義表的存儲結(jié)構(gòu)。重點：討論多種由順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)有機結(jié)合 的存儲結(jié)構(gòu)，以矩陣為例，研究在相同的邏輯結(jié)構(gòu) （矩陣）和操作要求（矩陣運算）情況下，根據(jù)各種 矩陣的不同特性，采用多種存儲結(jié)構(gòu)實現(xiàn)矩陣運算。難點：稀疏矩陣的多種存儲和實現(xiàn)，廣義表的存儲和 實現(xiàn)。實驗：特殊矩陣和廣義表的存儲和運算。4一、教學(xué)內(nèi)容：

1、 數(shù)組的定義和順序存儲方式；

2、 特殊矩陣的壓縮存儲；

3、 稀疏矩陣

4、 廣義表的概念、表示及基本操作；廣義表存儲結(jié)構(gòu)的實現(xiàn)。

二、教學(xué)要求：

1、 了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；

2、 掌握對特殊矩陣進行壓縮存儲時的下標(biāo)變換公式；

3、 了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，理解以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；

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

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

數(shù)組是數(shù)據(jù)結(jié)構(gòu)的基本結(jié)構(gòu)形式，它是一種順序式的結(jié)構(gòu)，數(shù)組是存儲同一類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)使用數(shù)組時需要定義數(shù)組的大小和存儲數(shù)據(jù)的數(shù)據(jù)類型75.1數(shù)組－－數(shù)組定義

數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組的維數(shù)是由數(shù)組的下標(biāo)的個數(shù)確定的：一個下標(biāo)稱為一維數(shù)組一個下標(biāo)以上的數(shù)組稱為多維數(shù)組從這個意義上講，確定了對于數(shù)組的一個下標(biāo)總有一個相應(yīng)的數(shù)值與之對應(yīng)的關(guān)系；或者說數(shù)組是有限個同類型數(shù)據(jù)元素組成的序列數(shù)組是二元組<下標(biāo)，值>的一個集合85.1.1一維數(shù)組一維數(shù)組是指下標(biāo)的個數(shù)只有一個的數(shù)組，有時稱為向量，是最基本的數(shù)據(jù)類型在java中需要事先聲明，程序才能夠在編譯過程中預(yù)留內(nèi)存空間聲明的格式一般是：

<數(shù)據(jù)類型><變量名稱>[]=new<數(shù)據(jù)類型>[<數(shù)組大小>]；一維數(shù)組具有線性表的結(jié)構(gòu)，但操作簡單，一般不進行插入和刪除操作，只定義給定下標(biāo)讀取元素和修改元素的操作9一維數(shù)組的存儲一維數(shù)組的數(shù)據(jù)存儲按照順序存儲，邏輯地址和物理地址都是連續(xù)的。如果已知第一個數(shù)據(jù)元素的地址loc(a0)，則第i個元素的地址loc(ai)為：Loc(ai)=Loc(a0)＋i×c假設(shè)數(shù)組的下標(biāo)從0開始，只要求出第i個元素之前存放了多少個數(shù)據(jù)元素即可（實際上有i個元素），每個元素占有c個存儲單元，再乘以c，就是第i個元素的起始地址。5.1.1一維數(shù)組10一維數(shù)組的存儲由此可見，求數(shù)組中數(shù)據(jù)元素的地址，已知條件必須是知道第一個元素的地址，然后主要是找出該元素之前已經(jīng)存儲了多少個數(shù)據(jù)元素。在一維數(shù)組中，只要知道任何一個元素的地址即可求出其它元素的地址，但在多維數(shù)組中，已知條件必須是第一個數(shù)據(jù)元素地址。5.1.1一維數(shù)組115.1.1一維數(shù)組數(shù)組分配內(nèi)存空間的方式有2種靜態(tài)數(shù)組：聲明時給出數(shù)組元素個數(shù)。當(dāng)程序開始運行時，數(shù)組即獲得系統(tǒng)分配的一塊地址連續(xù)的內(nèi)存空間。靜態(tài)數(shù)組所占用的內(nèi)存空間由系統(tǒng)自動管理。動態(tài)數(shù)組：聲明時不指定數(shù)組長度。當(dāng)程序運行中需要使用數(shù)組時，向系統(tǒng)申請數(shù)組的存儲單元空間，并給出數(shù)組長度。當(dāng)數(shù)組使用完之后，需要向系統(tǒng)歸還所占用的內(nèi)存空間。數(shù)組容量不夠時，不能就地擴容。前面的做法是，申請一個更大容量的數(shù)組并進行數(shù)組元素復(fù)制。在Java中，數(shù)組元素既可以簡單數(shù)據(jù)類型，也可以是引用類型。而且Java中的數(shù)組都是動態(tài)數(shù)組。125.1.2多維數(shù)組多維數(shù)組多維數(shù)組是指下標(biāo)的個數(shù)有兩個以上，我們比較常用的是二維數(shù)組（因為三維以上的數(shù)組存儲可以簡化為二維數(shù)組的存儲）。下面以二維數(shù)組為例說明多維數(shù)組。二維數(shù)組的聲明同一維數(shù)組。格式為：

<數(shù)據(jù)類型><數(shù)組名稱>[][]=new<數(shù)據(jù)類型>[size1][size2];135.1.2多維數(shù)組例如，設(shè)A是一個有m行n列的二維數(shù)組，則A可以表示為：在此，可以將二維數(shù)組A看成是由m個行向量[X0，X1，…，Xm-1]T組成，其中，Xi=(ai0,ai1,….,ain-1)，0≤i≤m-1；也可以將二維數(shù)組A看成是由n個列向量[y0,y1,……,yn-1]組成，其中yi=(a0i,a1i,…..,am-1i)，0≤i≤n-1。145.1.2多維數(shù)組二維數(shù)組中，每個數(shù)據(jù)元素對應(yīng)一對數(shù)組下標(biāo)，在行方向上和列方向上都存在一個線性關(guān)系，即存在兩個前驅(qū)（前件）和兩個后繼（后件）。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個數(shù)據(jù)元素對應(yīng)n個下標(biāo)，受n個關(guān)系的制約，其中任一個關(guān)系都是線性關(guān)系。可看作是數(shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組是對線性表的擴展：線性表中的數(shù)據(jù)元素本身又是一個多層次的線性表。155.1.2多維數(shù)組對于數(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ù)組由于計算機的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。185.1.2多維數(shù)組靜態(tài)多維數(shù)組的順序存儲結(jié)構(gòu)以二維數(shù)組的順序存儲為例說明，二維數(shù)組在順序存儲時一般有兩種：行優(yōu)先順序：存儲時先按行從小到大的順序存儲，在每一行中按列號從小到大存儲。列優(yōu)先順序：存儲時先按列從小到大的順序存儲，在每一列中按行號從小到大存儲。以上的兩種存儲順序中，第一個被存放的元素總是第一行第一列的數(shù)據(jù)元素，所以該元素的地址是我們的已知條件。195.1.2多維數(shù)組以二維數(shù)組arr[2][3]為例：205.1.2多維數(shù)組215.1.2多維數(shù)組以行序為主序（按行存儲）的方法：“左”下標(biāo)優(yōu)先

以列序為主序（按列存儲）的方法：“右”下標(biāo)優(yōu)先225.1.2多維數(shù)組多維數(shù)組同樣在二維數(shù)組中比較典型的是計算數(shù)據(jù)的存儲位置。假設(shè)二維數(shù)組是m*n的二維數(shù)組（共有m行，每行有n列）。第一個數(shù)據(jù)元素的地址是loc(a11)，則第i行第j列的數(shù)據(jù)元素的地址的計算公式應(yīng)為（按照行優(yōu)先順序存儲）：loc(aij)=loc(a11)+[（i-1）*n+j-1]*c假設(shè)下標(biāo)從1開始，我們需要計算出i行前面已經(jīng)存儲了i-1行元素，每行有n個元素，共有（i-1）*n個數(shù)據(jù)元素，在第i行元素中，j列之前有j-1個數(shù)據(jù)元素，共有（i-1）*n+j-1個元素，每個元素占有c個存儲單元，只要乘以c就可以了。其中l(wèi)oc(aij)表示第i行第j列數(shù)據(jù)元素的內(nèi)存的起始位置，loc(a11)表示第一個數(shù)據(jù)元素的內(nèi)存位置，c表示每個數(shù)據(jù)元素所占有的內(nèi)存空間的大小，如果下標(biāo)從0開始，只要不用減1即可。235.1.2多維數(shù)組多維數(shù)組如果按列優(yōu)先順序存儲，則地址的計算為：

loc(aij)=loc(a11)+[（j-1）*m+i-1]*c假設(shè)下標(biāo)從1開始，其中l(wèi)oc(aij)表示第i行第j列的數(shù)據(jù)元素的內(nèi)存起始位置，loc(a11)表示第一個數(shù)據(jù)元素的內(nèi)存位置，c表示每個數(shù)據(jù)元素所占有的內(nèi)存空間的大小；主要還是計算第i行j列元素之前有多少個數(shù)據(jù)元素。如果下標(biāo)從0開始，只要不用減1即可。245.1.2多維數(shù)組多維數(shù)組按此公式可以推廣到多維數(shù)組的數(shù)據(jù)元素的地址計算（假設(shè)按照行優(yōu)先順序存儲）：m行n列縱標(biāo)為k的三維數(shù)組，假設(shè)第一個元素的地址是loc(a111)，如果按行優(yōu)先順序存儲，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開始，只要不用減1即可。讀者可以從以上的地址公式中可以找出一定的地址計算規(guī)律：多維數(shù)組中按行優(yōu)先計算公式用一個下標(biāo)乘以后面的最大值。

《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》5.1數(shù)組（1）靜態(tài)順序存儲行主序列主序《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》（2）動態(tài)二維數(shù)組的存儲結(jié)構(gòu)275.1.2多維數(shù)組【例5.1】矩陣類。本例聲明Matrix類表示矩陣，成員table是一個元素類型為整型的二維數(shù)組。add()方法實現(xiàn)兩個矩陣相加。28矩陣運算主要有矩陣加、矩陣減、矩陣乘、矩陣轉(zhuǎn)置等。矩陣加（C=A+B）定義為publicclassMatrix{privateintvalue[][];}《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》【例5.1】矩陣類。設(shè)，有設(shè)，有設(shè)，有設(shè)，有305.2特殊矩陣的壓縮存儲在科學(xué)與工程計算問題中，矩陣是一種常用的數(shù)學(xué)對象，在高級語言編制程序時，簡單而又自然的方法，就是將一個矩陣描述為一個二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為1。315.2特殊矩陣的壓縮存儲但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲密度仍為1，但實際上占用了許多單元去存儲重復(fù)的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節(jié)省存儲空間，我們可以對這類矩陣進行壓縮存儲：即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。325.2特殊矩陣的壓縮存儲所謂矩陣的壓縮存儲，也就是在存儲數(shù)組時，盡量減少存儲空間，但是數(shù)組中的每個元素必須存儲，所以在矩陣存儲中，如果有規(guī)律可尋，只要存儲其中一部分，而另一部分的存儲地址可以通過相應(yīng)的算法將它計算出來，從而占有比較少的存儲空間達到存儲整個矩陣的目的，稱為矩陣的壓縮存儲。矩陣的壓縮存儲僅是針對特殊矩陣的；而對于沒有規(guī)律可循的二維數(shù)組則不能夠使用壓縮存儲。二維數(shù)組（矩陣）的壓縮存儲一般有三種，它們分別是對稱矩陣、稀疏矩陣和三角矩陣。三種矩陣中以稀疏矩陣比較常見。

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

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

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

5.2矩陣的壓縮存儲34

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

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

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

aij=ajii≥1，j≥1

則稱為n階對稱矩陣。對于對稱矩陣，如果不采用壓縮存儲，占有的存儲單元有n2個，因為是對稱矩陣，所以只要存儲對角的數(shù)據(jù)元素和一半的數(shù)據(jù)元素即可，占有的存儲單元有n（n-1）/2個存儲單元中。如果我們以行序為主序存儲其下三角（包括對角線）的元素，其上三角的元素可以推算出來。415.2矩陣的壓縮存儲對稱矩陣如果用一維數(shù)組存儲一個對稱矩陣，只要將對稱矩陣存儲在一個最大下標(biāo)為n（n-1）/2的一維數(shù)組S中即可。此時按照行優(yōu)先順序存儲，數(shù)據(jù)元素aij與數(shù)組S的下標(biāo)k的對應(yīng)關(guān)系為（why???）：

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

k=j(j-1)/2+i-1當(dāng)i＜j時425.2矩陣的壓縮存儲對稱矩陣對于任意給定的一組下標(biāo)（i，j），均可在S中找到元素aij，反之，對所有元素都能夠確定在S中位置，當(dāng)i＜j時，根據(jù)對稱矩陣的性質(zhì)推算即可。由此可以看出對稱矩陣的存儲可以使用一維數(shù)組S存儲，占用的空間不再是n2，而是n（n-1）/2空間減少了接近一半，實現(xiàn)了二維數(shù)組的壓縮存儲。43

（1）只存放下三角部分由于對稱矩陣關(guān)于主對角線對稱，故我們只需存放主對角線及主對角線以下的元素。這時，a[0][0]存入s[0]，a[1][0]存入s[1]，a[1][1]存入s[2]，…，具體參見圖5-4。這時s[k]與a[i][j]的對應(yīng)關(guān)系為：i(i+1)/2+j當(dāng)i≥jk=j(j+1)/2+i當(dāng)i<j上面的對應(yīng)關(guān)系讀者很容易推出：當(dāng)i≥j時，aij在下三角部分中，aij前面有i行，共有1+2+3+…+i個元素，而aij是第i行的第j個元素，即有k=1+2+3+…-+i+j=i(i+1)/2+j；當(dāng)i<j時，aij在上三角部分中，但與aji對稱，故只需在下三角部分中找aij即可，故只需將i與j交換即可，即k=j(j+1)/2+i。4445(2)只存放上三角部分對于對稱陣，除了用下三角形式存放外，還可以用上三角形式存放，這時a[0][0]存入s[0],a[0][1]存入s[1]，a[0][2]存入s[2]，…，具體參見圖5-5。這時s[k]與a[i][j]的對應(yīng)關(guān)系可以按下面方法推出：當(dāng)i≤j時，aij在上三角部分中，前面共有i行，共有n+n-1+…+n-(i-1)=i*n-個元素，而aij是本行第j-i個元素，故k=i*n-+j-i，當(dāng)i>j時，交換i與j即可。故s[k]與a[i][j]的對應(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.對稱矩陣的壓縮存儲《數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）》3.對角矩陣的壓縮存儲495.2稀疏矩陣稀疏矩陣對稀疏矩陣很難下一個確切的定義，它只是一個憑人們的直覺來理解的概念。一般認(rèn)為，一個較大的矩陣中，零元素的個數(shù)相對于整個矩陣元素的總個數(shù)所占比例較大時，該矩陣就是一個稀疏矩陣。例如，有一個6×6階的矩陣A，其36個元素中只有8個非零元素，那么，可以稱矩陣A為稀疏矩陣。50515.2稀疏矩陣稀疏矩陣稀疏矩陣一般是指矩陣中的大部分元素為零，僅有少量元素非零的矩陣稱為稀疏矩陣；或者說矩陣A（m×n）中有S個非零元素，如果S遠遠小于矩陣的元素總數(shù)，稱A為稀疏矩陣。稀疏矩陣的存儲一般只要保存非零元素即可，對于零元素可以不與保存，這樣可以實現(xiàn)稀疏矩陣的壓縮存儲。

525.2稀疏矩陣稀疏矩陣稀疏矩陣的壓縮存儲采用三元組的方法實現(xiàn)。其存儲規(guī)則如下：每一個非零元素占有一行，每行中包含非零元素所在的行號、列號、非零元素的數(shù)值。53表示稀疏矩陣的三元組{(0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,5,28)，(4,4,50)}行號列號元素值rowcolumnvalue54555.2稀疏矩陣稀疏矩陣如果每個非零元素按照此種方法存儲，雖然能夠完整地描述非零元素，但如果矩陣中有整行（或整列）中沒有非零元素，此時可能不能夠還原成原來的矩陣所以為了完整地描述稀疏矩陣，在以上描述的情況下，如果增加一行的內(nèi)容，該行包括