數(shù)據(jù)結(jié)構(gòu)(Java)-第5章

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

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

3、條件：數(shù)組已存在。初始條件：數(shù)組已存在。操作結(jié)果：返回?cái)?shù)組中數(shù)據(jù)元素的個(gè)數(shù)。操作結(jié)果：返回?cái)?shù)組中數(shù)據(jù)元素的個(gè)數(shù)。（2）取值：）取值：getValue（index）初始條件：數(shù)組已存在。初始條件：數(shù)組已存在。操作結(jié)果：返回?cái)?shù)組下標(biāo)為操作結(jié)果：返回?cái)?shù)組下標(biāo)為index的數(shù)組元素的值。的數(shù)組元素的值。（3）賦值：）賦值：setValue（index，newValue）初始條件：數(shù)組已存在。初始條件：數(shù)組已存在。操作結(jié)果：將數(shù)組下標(biāo)為操作結(jié)果：將數(shù)組下標(biāo)為index的數(shù)組元素的值設(shè)置為的數(shù)組元素的值設(shè)置為newValue。NEXT Neusoft 二、二、數(shù)組順序存儲(chǔ)結(jié)構(gòu)數(shù)組順序存儲(chǔ)結(jié)構(gòu) 1、一維數(shù)組

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

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

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

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

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

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

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

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

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

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

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

15、A共有共有56個(gè)元素，其中大部分是零元素，只有個(gè)元素，其中大部分是零元素，只有3個(gè)非零元素。矩陣的稀疏因個(gè)非零元素。矩陣的稀疏因子，故子，故A為稀疏矩陣?？梢杂脼橄∈杈仃?。可以用三元組三元組按行為主序?qū)葱袨橹餍驅(qū)表示為一個(gè)線性表：表示為一個(gè)線性表：（0，1，6），（），（3，4，8），（），（6，7，5）。然后我們可以采用順序存儲(chǔ)結(jié)構(gòu)的一維。然后我們可以采用順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組來存放這個(gè)線性表，設(shè)為數(shù)組數(shù)組來存放這個(gè)線性表，設(shè)為數(shù)組array。數(shù)組。數(shù)組array與其對(duì)應(yīng)的三元組表如表與其對(duì)應(yīng)的三元組表如表5.1所示。所示。表表5.1 稀疏矩陣稀疏矩陣A的順序存儲(chǔ)的順序存儲(chǔ)數(shù)組數(shù)組Bi(

16、行標(biāo)行標(biāo))j(列標(biāo)列標(biāo))value（值）（值）array0016array1348array2675NEXT Neusoft/* 三元組結(jié)點(diǎn)類三元組結(jié)點(diǎn)類*/public class SMnode private int row;/行標(biāo)行標(biāo)private int column;/列標(biāo)列標(biāo)private int value;/矩陣元素的值矩陣元素的值/構(gòu)造方法構(gòu)造方法1public SMnode() this(0,0,0);/構(gòu)造方法構(gòu)造方法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接下來基于三元組順序表來實(shí)現(xiàn)稀疏矩陣。對(duì)于稀疏矩陣來說，矩陣的接下來基于三元組順序表來實(shí)現(xiàn)稀疏矩陣。對(duì)于稀疏矩陣來說，矩陣的行數(shù)、列數(shù)和存放非零元素的三元組是矩陣操作的基本數(shù)據(jù)。因此可以行數(shù)、列數(shù)和存放非零元素的三元組是矩陣操作的基本數(shù)據(jù)。因此可以把上述成分設(shè)計(jì)成稀疏矩陣類中的私有成員變量，其中三元組存放在一把上述成分設(shè)計(jì)成稀疏矩陣類中的私有成員變量，其中三元組存放在一個(gè)一維數(shù)組中，三元組的個(gè)數(shù)可以通過數(shù)組的個(gè)一維數(shù)組中，三元組的個(gè)數(shù)可以通過數(shù)組的length屬性獲得。屬性獲得。 public class SparseMatrix private SMnode tripleData;/三元組

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

20、ws=sm.length;/矩陣行數(shù)矩陣行數(shù)columns=sm0.length;/矩陣列數(shù)矩陣列數(shù)int i,j,count=0; /count用于保存矩陣中非零元素個(gè)數(shù)用于保存矩陣中非零元素個(gè)數(shù)for(i=0;ism.length;i+)for(j=0;jsmi.length;j+)if(smij!=0)count+;/累加累加int k=0;tripleData=new SMnodecount;/為數(shù)組分配存儲(chǔ)空間為數(shù)組分配存儲(chǔ)空間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+個(gè)非零元素個(gè)非零元素n);System.out.println(矩陣的三元組順序表如下：矩陣的三元組順序表如下：n);System.out.println(行標(biāo)行標(biāo)t列標(biāo)列標(biāo)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】編寫程序，基于三元組順序表來存儲(chǔ)稀疏矩陣，編寫程序，基于三元組順序表來存儲(chǔ)稀疏矩陣，然后將該稀疏矩陣轉(zhuǎn)置然后將該稀疏矩陣轉(zhuǎn)置?！菊f明說明:】矩陣轉(zhuǎn)置指的是將矩陣中每個(gè)元素的行列序號(hào)進(jìn)行調(diào)換。矩陣轉(zhuǎn)置指的是將矩陣中每個(gè)元素的行列序號(hào)進(jìn)行調(diào)換。NEXT Neusoft（2）十字鏈表）十字鏈表對(duì)于任意的稀疏矩陣，每個(gè)非零元素用一個(gè)結(jié)點(diǎn)來表示，結(jié)點(diǎn)的結(jié)構(gòu)如對(duì)于任意的稀疏矩陣，每個(gè)非零元素用一個(gè)結(jié)點(diǎn)來表示，結(jié)點(diǎn)的結(jié)構(gòu)如下

23、圖所示?？梢钥吹?，每個(gè)結(jié)點(diǎn)由五個(gè)域組成，其中三個(gè)數(shù)據(jù)域，下圖所示?？梢钥吹?，每個(gè)結(jié)點(diǎn)由五個(gè)域組成，其中三個(gè)數(shù)據(jù)域，row存放元素所在的行號(hào)，存放元素所在的行號(hào)，column存放元素所在的列號(hào)，存放元素所在的列號(hào)，value存放元素的存放元素的值。其他兩個(gè)指針域值。其他兩個(gè)指針域down和和right分別存放列后繼引用和行后繼引用，分別存放列后繼引用和行后繼引用，分別用來鏈接在同列和同行中的下一個(gè)非零元素結(jié)點(diǎn)。分別用來鏈接在同列和同行中的下一個(gè)非零元素結(jié)點(diǎn)。 NEXT Neusoft例如有矩陣?yán)缬芯仃嘊： 稀疏矩陣的十字鏈表表示稀疏矩陣的十字鏈表表示 4 5BNEXT Neusoft四四、廣義

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

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

26、元素分別是，兩個(gè)元素分別是原子元素原子元素c和子表和子表B，深度為，深度為2。D=（d，D）=（d，（，（d，（，（d，（，（d，（，（）；）；/廣義表廣義表D長(zhǎng)度長(zhǎng)度為為2，深度無窮，深度無窮E=（A）=（）；（）；/廣義表廣義表E非空，長(zhǎng)度為非空，長(zhǎng)度為1，元素是一個(gè)空表，深度，元素是一個(gè)空表，深度為為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、廣義表的性質(zhì)、廣義表的性質(zhì)（1）廣義表是一個(gè)多層次的結(jié)構(gòu)。）廣義表是一個(gè)多層次的結(jié)構(gòu)。根據(jù)廣義表的定義，廣義表的元素可以是子表，而子表的元素仍然可以根據(jù)廣義表的定義，廣義表的元素可以是子表，而子表的元素仍然可以是子表。廣義表中所含括號(hào)的層數(shù)稱為廣義表的深度。是子表。廣義表中所含括號(hào)的層數(shù)稱為廣義表的深度。（2）一個(gè)廣義表可以為其他廣義表所共享）一個(gè)廣義表可以為其他廣義表所共享一個(gè)廣義表可以作為多個(gè)

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

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

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