數據結構(Java)-第5章

1、基本內容1.數組的定義和運算數組的定義和運算 第第5章章 數組和廣義表數組和廣義表 2.數組順序存儲結構數組順序存儲結構 3.矩陣的壓縮存儲矩陣的壓縮存儲 4.廣義表廣義表5.數組項目實踐數組項目實踐 NEXT Neusoft1、數組（、數組（array）的定義）的定義數組數組是由是由n個（個（n1）具有相同數據類型的數據元素（）具有相同數據類型的數據元素（a0，a1，ai-1，ai，ai+1，an-1）構成的有限序列，并且這些數據元素占用）構成的有限序列，并且這些數據元素占用一片地址連續(xù)的內存單元。在一片地址連續(xù)的內存單元。在Java語言中，數組的本身是堆中的對語言中，數組的本身是堆中的對象

2、，它能保存基本類型變量或其他對象的引用。在使用數組之前，象，它能保存基本類型變量或其他對象的引用。在使用數組之前，需要聲明并構造數組。需要聲明并構造數組。例如：聲明一個用于保存學生考試成績的一維數組例如：聲明一個用于保存學生考試成績的一維數組scores，即，即double scores;然后構造數組，然后構造數組，scores = new double5;一一. 數組的定義和運算數組的定義和運算NEXT Neusoft2、數組的運算、數組的運算數組的基本操作主要有以下數組的基本操作主要有以下3種，以一維數組為例：種，以一維數組為例：（1）求數組的長度：）求數組的長度：length（）（）初始

3、條件：數組已存在。初始條件：數組已存在。操作結果：返回數組中數據元素的個數。操作結果：返回數組中數據元素的個數。（2）取值：）取值：getValue（index）初始條件：數組已存在。初始條件：數組已存在。操作結果：返回數組下標為操作結果：返回數組下標為index的數組元素的值。的數組元素的值。（3）賦值：）賦值：setValue（index，newValue）初始條件：數組已存在。初始條件：數組已存在。操作結果：將數組下標為操作結果：將數組下標為index的數組元素的值設置為的數組元素的值設置為newValue。NEXT Neusoft 二、二、數組順序存儲結構數組順序存儲結構 1、一維數組

4、、一維數組一維數組一維數組占用一片地址連續(xù)的內存單元，設數組第一個元素占用一片地址連續(xù)的內存單元，設數組第一個元素a0 的存儲地的存儲地址為，每個元素占用址為，每個元素占用c字節(jié)，則數組任意一個元素字節(jié)，則數組任意一個元素ai的存儲地址為：的存儲地址為：2、多維數組、多維數組以以二維數組二維數組為例，一個為例，一個m行行n列的二維數組如下所示：列的二維數組如下所示：0()()iLoc aLoc aic 0001020,11011121,11,01,11,21,1nnm nmmmmnaaaaaaaaAaaaaNEXT Neusoft二維數組的兩種存儲方式二維數組的兩種存儲方式NEXT Neuso

5、ft【例例5.1】有二維數組有二維數組double arr=new double45，試問：，試問：（1）數組）數組arr中存放多少個數據元素？數組中存放多少個數據元素？數組arr總共占用多少字節(jié)的存儲總共占用多少字節(jié)的存儲空間？空間？（2）假設數組）假設數組arr的首地址（數組一個元素的地址）為的首地址（數組一個元素的地址）為8000，如果采用，如果采用按行為主序的存儲方式，則數組元素按行為主序的存儲方式，則數組元素arr23的存儲地址是多少？的存儲地址是多少？NEXT Neusoft 三、三、矩陣的壓縮存儲矩陣的壓縮存儲 1、三角矩陣、三角矩陣三角矩陣分為上三角矩陣和下三角矩陣。三角矩陣分

6、為上三角矩陣和下三角矩陣。上三角矩陣上三角矩陣是指矩陣的主對角是指矩陣的主對角線（不包括主對角線）下方的元素均為常數線（不包括主對角線）下方的元素均為常數c或零的或零的n階方陣；階方陣；下三角矩下三角矩陣陣是指矩陣的主對角線（不包括主對角線）上方的元素均為常數是指矩陣的主對角線（不包括主對角線）上方的元素均為常數c或零或零的的n階方陣。階方陣。 （a）上三角矩陣）上三角矩陣 （b）下三角矩陣）下三角矩陣0001020,111121,11,1nnn nnnaaaacaaaAccca 0010111,01,11,21,1n nnnnnnacccaaccAaaaa NEXT Neusoft（1）下三

7、角矩陣）下三角矩陣以下三角矩陣為例，第以下三角矩陣為例，第1行有行有1個非零元素個非零元素a00，第，第2行有行有2個非零元素個非零元素a10和和a11。依次類推，第。依次類推，第i行有行有i+1個非零元素。矩陣中非零元素總數為：個非零元素。矩陣中非零元素總數為：利用下三角矩陣的規(guī)律，可以采用長度為（）的一維數組利用下三角矩陣的規(guī)律，可以采用長度為（）的一維數組B，行優(yōu)先壓，行優(yōu)先壓縮存儲下三角矩陣中的元素，其中縮存儲下三角矩陣中的元素，其中B 用于存放下三角矩陣中重復的常用于存放下三角矩陣中重復的常數數c。得出矩陣。得出矩陣 中任意一個元素中任意一個元素aij與一維數組與一維數組B的下標的下

8、標k( )之間的關系如下：之間的關系如下：10(1)(1)2ninni0(1)/2knnn nA(1)()2(1)()2iijijknnij NEXT Neusoft其中，其中，i為行下標，為行下標，j為列下標。假設每個元素占用為列下標。假設每個元素占用L個字節(jié)，當個字節(jié)，當 時時，元素，元素aij的地址為：的地址為：當當 時，元素時，元素aij的地址為：的地址為：下三角矩陣的壓縮存儲如下圖所示：下三角矩陣的壓縮存儲如下圖所示：ij()( 0)(1)/ 2)ijLoc aLoc BiijLij()( 0)(1)/ 2)ijLoc aLoc BnnLNEXT Neusoft（2）上三角矩陣）上三

9、角矩陣與下三角矩陣類似，上三角矩陣也可以采用壓縮存儲，上三角矩陣采用與下三角矩陣類似，上三角矩陣也可以采用壓縮存儲，上三角矩陣采用以列為主序存放矩陣元素較為方便。上三角矩陣中任意一個元素以列為主序存放矩陣元素較為方便。上三角矩陣中任意一個元素aij與一與一維數組維數組B的下標的下標k( )之間的關系如下：之間的關系如下：0(1)/ 2knn(1)()2(1)()2jjiijknnij NEXT Neusoft其中，其中，i為行下標，為行下標，j為列下標。假設每個元素占用為列下標。假設每個元素占用L個字節(jié)，當個字節(jié)，當 時時，元素，元素aij的地址為：的地址為：當當 時，元素時，元素aij的地址

10、為：的地址為：ijij()( 0)(1)ijLoc aLoc BjjiL()( 0)(1)/ 2)ijLoc aLoc BnnLNEXT Neusoft2、對稱矩陣、對稱矩陣在在n階方陣中，若任意一個矩陣元素滿足下述性質：階方陣中，若任意一個矩陣元素滿足下述性質：則稱則稱 為為n階階對稱矩陣對稱矩陣。在對稱矩陣中，以主對角線。在對稱矩陣中，以主對角線 為軸線的對稱位置上矩陣元素值相等。因此，可以只存儲對稱矩陣的上為軸線的對稱位置上矩陣元素值相等。因此，可以只存儲對稱矩陣的上三角或下三角元素，然后讓每一對對稱元素共享同一個存儲單元即可。三角或下三角元素，然后讓每一對對稱元素共享同一個存儲單元即可

11、。與三角矩陣類似，與三角矩陣類似，n階對稱矩陣中的階對稱矩陣中的 個元素可以被壓縮存儲到長個元素可以被壓縮存儲到長度為度為 的一維地址空間。的一維地址空間。1,1)ijjiaainjn n nA00111,1,nnaaan n(1)/ 2nnNEXT Neusoft采用長度為采用長度為 的一維數組的一維數組B，行優(yōu)先壓縮存儲對稱矩陣中的元素，得出，行優(yōu)先壓縮存儲對稱矩陣中的元素，得出矩陣中任意一個元素矩陣中任意一個元素aij與一維數組與一維數組B的下標的下標k( )之間的關系如下之間的關系如下：其中，其中，i為行下標，為行下標，j為列下標。假設每個元素占用為列下標。假設每個元素占用L個字節(jié)，取

12、個字節(jié)，取 ， ，則，則n階方陣中任意元素階方陣中任意元素aij的地址為：的地址為：(1)/ 2nn(1)()2(1)()2iijijkjjiij 0(1)/2knn max( , )ii jmin( , )ji j()( 0)(1)/ 2)ijLoc aLoc BiijLNEXT Neusoft3、對角矩陣、對角矩陣對角矩陣對角矩陣是指是指n階方陣階方陣 的所有非零元素都集中在以主對角線為中心的的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線上和直接在主對角線上、下方若干條對角帶狀區(qū)域中，即除了主對角線上和直接在主對角線上、下方若干條對角線上的元素之外，其余元素皆為零。如下

13、圖所示，主對角線的兩側分別線上的元素之外，其余元素皆為零。如下圖所示，主對角線的兩側分別有有d條次對角線，稱條次對角線，稱d為對角矩陣的半帶寬，為對角矩陣的半帶寬，2d+1為對角矩陣的帶寬。例為對角矩陣的帶寬。例如對角矩陣如對角矩陣A為：為：其半帶寬其半帶寬d=1，帶寬為，帶寬為3，類似這樣的矩陣也被稱作三對角矩陣。，類似這樣的矩陣也被稱作三對角矩陣。 0001101112212223323334aaaaaAaaaaaa 4344aan nANEXT Neusoft矩陣矩陣 中除第中除第0行外的任意元素行外的任意元素aij與一維數組與一維數組B的下標的下標k之間存在如下之間存在如下關系：關系：

14、n nA2+3i-1-1i jki j（ -1）+j-(i-1)=2i+j ()()NEXT Neusoft4、稀疏矩陣、稀疏矩陣稀疏矩陣稀疏矩陣（Sparse Matrix）是指具有較多非零元素且非零元素的分布無）是指具有較多非零元素且非零元素的分布無規(guī)律的矩陣。假設在規(guī)律的矩陣。假設在 的矩陣的矩陣 中，有中，有t個元素不為零，令個元素不為零，令 ，稱稱 為矩陣的稀疏因子。如果為矩陣的稀疏因子。如果 ，一般認為是稀疏矩陣。，一般認為是稀疏矩陣。 （1）三元組順序表）三元組順序表例如有矩陣例如有矩陣A如下所示：如下所示：m nm nA/()tm n0.05A NEXT Neusoft矩陣矩陣

15、A共有共有56個元素，其中大部分是零元素，只有個元素，其中大部分是零元素，只有3個非零元素。矩陣的稀疏因個非零元素。矩陣的稀疏因子，故子，故A為稀疏矩陣。可以用為稀疏矩陣。可以用三元組三元組按行為主序將按行為主序將A表示為一個線性表：表示為一個線性表：（0，1，6），（），（3，4，8），（），（6，7，5）。然后我們可以采用順序存儲結構的一維。然后我們可以采用順序存儲結構的一維數組來存放這個線性表，設為數組數組來存放這個線性表，設為數組array。數組。數組array與其對應的三元組表如表與其對應的三元組表如表5.1所示。所示。表表5.1 稀疏矩陣稀疏矩陣A的順序存儲的順序存儲數組數組Bi(

16、行標行標)j(列標列標)value（值）（值）array0016array1348array2675NEXT Neusoft/* 三元組結點類三元組結點類*/public class SMnode private int row;/行標行標private int column;/列標列標private int value;/矩陣元素的值矩陣元素的值/構造方法構造方法1public SMnode() this(0,0,0);/構造方法構造方法2public SMnode(int row, int column, int value) this.row = row;this.column = co

17、lumn;this.value = value;public int getColumn() return column;NEXT Neusoftpublic void setColumn(int column) this.column = column;public int getRow() return row;public void setRow(int row) this.row = row;public int getValue() return value;public void setValue(int value) this.value = value; NEXT Neusof

18、t接下來基于三元組順序表來實現稀疏矩陣。對于稀疏矩陣來說，矩陣的接下來基于三元組順序表來實現稀疏矩陣。對于稀疏矩陣來說，矩陣的行數、列數和存放非零元素的三元組是矩陣操作的基本數據。因此可以行數、列數和存放非零元素的三元組是矩陣操作的基本數據。因此可以把上述成分設計成稀疏矩陣類中的私有成員變量，其中三元組存放在一把上述成分設計成稀疏矩陣類中的私有成員變量，其中三元組存放在一個一維數組中，三元組的個數可以通過數組的個一維數組中，三元組的個數可以通過數組的length屬性獲得。屬性獲得。 public class SparseMatrix private SMnode tripleData;/三元組

19、順序表三元組順序表private int rows;/稀疏矩陣總行數稀疏矩陣總行數private int columns;/稀疏矩陣總列數稀疏矩陣總列數/構造方法構造方法1，指定三元組表長度，指定三元組表長度public SparseMatrix(int n) rows=0;columns=0;tripleData=new SMnoden;/為數組分配存儲空間為數組分配存儲空間for(int i=0;in;i+)tripleDatai=new SMnode();NEXT Neusoftpublic SparseMatrix(int sm ) /構造方法構造方法2，指定稀疏矩陣，指定稀疏矩陣ro

20、ws=sm.length;/矩陣行數矩陣行數columns=sm0.length;/矩陣列數矩陣列數int i,j,count=0; /count用于保存矩陣中非零元素個數用于保存矩陣中非零元素個數for(i=0;ism.length;i+)for(j=0;jsmi.length;j+)if(smij!=0)count+;/累加累加int k=0;tripleData=new SMnodecount;/為數組分配存儲空間為數組分配存儲空間for(i=0;ism.length;i+)for(j=0;jsmi.length;j+)if(smij!=0)tripleDatak=new SMnode(

21、i,j,smij);k+;NEXT Neusoft/輸出稀疏矩陣的三元組表示輸出稀疏矩陣的三元組表示public void showSparseMatrix()System.out.println(稀疏矩陣：稀疏矩陣：+rows+行行 +columns+列列+tripleData.length+個非零元素個非零元素n);System.out.println(矩陣的三元組順序表如下：矩陣的三元組順序表如下：n);System.out.println(行標行標t列標列標t元素值元素值n);for(int i=0;itripleData.length;i+)System.out.println(tr

22、ipleDatai.getRow()+t+tripleDatai.getColumn()+t+tripleDatai.getValue()+n); NEXT Neusoft【例例5.2】編寫程序，基于三元組順序表來存儲稀疏矩陣，編寫程序，基于三元組順序表來存儲稀疏矩陣，然后將該稀疏矩陣轉置然后將該稀疏矩陣轉置?！菊f明說明:】矩陣轉置指的是將矩陣中每個元素的行列序號進行調換。矩陣轉置指的是將矩陣中每個元素的行列序號進行調換。NEXT Neusoft（2）十字鏈表）十字鏈表對于任意的稀疏矩陣，每個非零元素用一個結點來表示，結點的結構如對于任意的稀疏矩陣，每個非零元素用一個結點來表示，結點的結構如下

23、圖所示。可以看到，每個結點由五個域組成，其中三個數據域，下圖所示?？梢钥吹?，每個結點由五個域組成，其中三個數據域，row存放元素所在的行號，存放元素所在的行號，column存放元素所在的列號，存放元素所在的列號，value存放元素的存放元素的值。其他兩個指針域值。其他兩個指針域down和和right分別存放列后繼引用和行后繼引用，分別存放列后繼引用和行后繼引用，分別用來鏈接在同列和同行中的下一個非零元素結點。分別用來鏈接在同列和同行中的下一個非零元素結點。 NEXT Neusoft例如有矩陣例如有矩陣B： 稀疏矩陣的十字鏈表表示稀疏矩陣的十字鏈表表示 4 5BNEXT Neusoft四四、廣義

24、表廣義表 1、廣義表的定義、廣義表的定義廣義表廣義表是線性表的推廣，線性表限定其中元素必須是原子類型，不能再分是線性表的推廣，線性表限定其中元素必須是原子類型，不能再分解，而廣義表中數據元素還可再分解，即是又一個廣義表。一般記作：解，而廣義表中數據元素還可再分解，即是又一個廣義表。一般記作：LS=（a1，a2，ai-1，ai，ai+1，an）其中，其中，LS是廣義表的名稱，是廣義表的名稱，n是廣義表的是廣義表的長度長度，某一個數據元素，某一個數據元素ai可以是可以是單個元素（稱為單個元素（稱為原子原子），也可以是廣義表（稱為），也可以是廣義表（稱為子表子表）。當廣義表）。當廣義表LS非空非空時

25、，稱第一個元素時，稱第一個元素a1為廣義表的為廣義表的表頭表頭（Head），稱其余元素組成的廣義），稱其余元素組成的廣義表為表為表尾表尾（Tail）。廣義表中所含括號的層數稱為廣義表的）。廣義表中所含括號的層數稱為廣義表的深度深度。原子的。原子的深度為深度為0，空表的深度為，空表的深度為1。 NEXT Neusoft下面列舉一些廣義表的例子：下面列舉一些廣義表的例子：A=（）；（）；/廣義表廣義表A是空表，長度為是空表，長度為0，深度為，深度為1。B=（a，b）；）；/廣義表廣義表B長度為長度為2，深度為，深度為1。C=（c，B）=（c，（，（a，b）；）；/廣義表廣義表C長度為長度為2，兩個

26、元素分別是，兩個元素分別是原子元素原子元素c和子表和子表B，深度為，深度為2。D=（d，D）=（d，（，（d，（，（d，（，（d，（，（）；）；/廣義表廣義表D長度長度為為2，深度無窮，深度無窮E=（A）=（）；（）；/廣義表廣義表E非空，長度為非空，長度為1，元素是一個空表，深度，元素是一個空表，深度為為2。NEXT Neusoft2、廣義表的圖形表示、廣義表的圖形表示 廣義表的圖形表示中，采用圓圈表示廣義表的圖形表示中，采用圓圈表示子表子表，方塊表示，方塊表示原子原子，并用線段把，并用線段把表和它們的元素連接起來。表和它們的元素連接起來。圖圖5.7 A=（）；（）； 圖圖5.8 B=（a，

27、b）；）； NEXT Neusoft圖圖5.9 C=（c，B）=（c，（，（a，b）；）；圖圖5.10 D=（d，D）=（d，（，（d，（，（d，（，（d，（，（）；）； NEXT Neusoft3、廣義表的性質、廣義表的性質（1）廣義表是一個多層次的結構。）廣義表是一個多層次的結構。根據廣義表的定義，廣義表的元素可以是子表，而子表的元素仍然可以根據廣義表的定義，廣義表的元素可以是子表，而子表的元素仍然可以是子表。廣義表中所含括號的層數稱為廣義表的深度。是子表。廣義表中所含括號的層數稱為廣義表的深度。（2）一個廣義表可以為其他廣義表所共享）一個廣義表可以為其他廣義表所共享一個廣義表可以作為多個

28、廣義表的子表，通過該廣義表的名稱來引用。一個廣義表可以作為多個廣義表的子表，通過該廣義表的名稱來引用。（3）可遞歸性）可遞歸性如果一個廣義表的子表之一是它自身，那么該廣義表成為了一個遞歸表如果一個廣義表的子表之一是它自身，那么該廣義表成為了一個遞歸表。NEXT Neusoft4、廣義表的運算、廣義表的運算（1）創(chuàng)建廣義表：）創(chuàng)建廣義表：initGList()初始條件：廣義表不存在。初始條件：廣義表不存在。操作結果：創(chuàng)建一個空的廣義表。操作結果：創(chuàng)建一個空的廣義表。（2）插入數據元素：）插入數據元素：insert(x)初始條件：廣義表已存在。初始條件：廣義表已存在。操作結果：將新的數據元素操作結

29、果：將新的數據元素x插入到廣義表的第一個位置。插入到廣義表的第一個位置。（3）刪除數據元素：）刪除數據元素：delete()初始條件：廣義表已存在。初始條件：廣義表已存在。操作結果：刪除廣義表中的第一個數據元素，同時將廣義表的長度減操作結果：刪除廣義表中的第一個數據元素，同時將廣義表的長度減1。NEXT Neusoft（4）求長度：）求長度：length()初始條件：廣義表已存在。初始條件：廣義表已存在。操作結果：返回廣義表的長度，即廣義表中數據元素的個數。操作結果：返回廣義表的長度，即廣義表中數據元素的個數。（5）求深度：）求深度：getDepth()初始條件：廣義表已存在。初始條件：廣義表

30、已存在。操作結果：返回廣義表的深度。操作結果：返回廣義表的深度。（6）判斷廣義表是否為空：）判斷廣義表是否為空：isEmpty()初始條件：廣義表已存在。初始條件：廣義表已存在。操作結果：若廣義表為空表，返回操作結果：若廣義表為空表，返回true，否則返回，否則返回false。NEXT Neusoft（7）取表頭：）取表頭：getHead( )初始條件：廣義表已存在。初始條件：廣義表已存在。操作結果：判斷廣義表是否為空，如操作結果：判斷廣義表是否為空，如false則返回該廣義表的第一個數據則返回該廣義表的第一個數據元素。如元素。如true則返回則返回null。（8）取表尾：）取表尾：getTail()初始條件：廣義表已存在。初始條件：廣義表已存在。操作結果：判斷廣義表是否為空，如操作結果：判斷廣義表是否為空，如false則返回該廣義表除第一個數據則返回該廣義表除第一個數據元素外的所有其他元素。如元素外的所有其他元素。如true則返回則返回