數(shù)組和廣義表

1、目錄5.1多維數(shù)組多維數(shù)組 5.1.1多維數(shù)組的概念多維數(shù)組的概念 1一維數(shù)組一維數(shù)組一維數(shù)組可以看成是一個線性表或一個向一維數(shù)組可以看成是一個線性表或一個向量（第二章已經(jīng)介紹），它在計算機內是量（第二章已經(jīng)介紹），它在計算機內是存放在一塊連續(xù)的存儲單元中，適合于隨存放在一塊連續(xù)的存儲單元中，適合于隨機查找。這在第二章的線性表的順序存儲機查找。這在第二章的線性表的順序存儲結構中已經(jīng)介紹。結構中已經(jīng)介紹。2二維數(shù)組二維數(shù)組二維數(shù)組可以看成是向量的推廣。二維數(shù)組可以看成是向量的推廣。 a00 a01 a0n-1 a10 a11 a1n-1 . am-1 0 am-1 1 am-1 n-1 A= 例

2、如，設例如，設A是一個有是一個有m行行n列的二維數(shù)組，列的二維數(shù)組，則則A可以表示為：可以表示為：在此，可以將二維數(shù)組在此，可以將二維數(shù)組A看成是由看成是由m個行向量個行向量X0，X1， ，Xm-1T組成，其中，組成，其中，Xi=( ai0, ai1, .,ain-1)， 0im-1；也可以將二維數(shù)組也可以將二維數(shù)組A看成是由看成是由n個列向量個列向量Y0, Y1, ,Yn-1組成，其中組成，其中 Yi=(a0i, a1i, .,am-1i)， 0in-1。 由此可知由此可知二維數(shù)組二維數(shù)組中的每一個元素最多可有中的每一個元素最多可有二個直接前驅和兩個直接后繼（邊界除外），二個直接前驅和兩個直

3、接后繼（邊界除外），故是一種典型的非線性結構。故是一種典型的非線性結構。3多維數(shù)組多維數(shù)組同理，三維數(shù)組最多可有三個直接前驅和三個直同理，三維數(shù)組最多可有三個直接前驅和三個直接后繼，三維以上數(shù)組可以作類似分析。因此，接后繼，三維以上數(shù)組可以作類似分析。因此，可以把三維以上的數(shù)組稱為多維數(shù)組，多維數(shù)組可以把三維以上的數(shù)組稱為多維數(shù)組，多維數(shù)組可有多個直接前驅和多個直接后繼，故多維數(shù)組可有多個直接前驅和多個直接后繼，故多維數(shù)組是一種非線性結構。是一種非線性結構。5.1.2 多維數(shù)組在計算機內的存放多維數(shù)組在計算機內的存放怎樣將多維數(shù)組中元素存入到計算機內存中呢？怎樣將多維數(shù)組中元素存入到計算機內存

4、中呢？由于計算機內存結構是一維的（線性的），因由于計算機內存結構是一維的（線性的），因此，用一維內存存放多維數(shù)組就必須按某種次此，用一維內存存放多維數(shù)組就必須按某種次序將數(shù)組元素排成一個線性序列，然后將這個序將數(shù)組元素排成一個線性序列，然后將這個線性序列順序存放在存儲器中線性序列順序存放在存儲器中 5.2多維數(shù)組的存儲結構多維數(shù)組的存儲結構由于數(shù)組由于數(shù)組一般不作插入或刪除操作一般不作插入或刪除操作，也就是說，也就是說，一旦建立了數(shù)組，則結構中的數(shù)組元素個數(shù)和元一旦建立了數(shù)組，則結構中的數(shù)組元素個數(shù)和元素之間的關系就不再發(fā)生變動，即它們的邏輯結素之間的關系就不再發(fā)生變動，即它們的邏輯結構就固定

5、下來了，不再發(fā)生變化。因此，采用構就固定下來了，不再發(fā)生變化。因此，采用順順序存儲序存儲結構表示數(shù)組是順理成章的事了。本章中，結構表示數(shù)組是順理成章的事了。本章中，僅重點討論二維數(shù)組的存儲，三維及三維以上的僅重點討論二維數(shù)組的存儲，三維及三維以上的數(shù)組可以作類似分析。數(shù)組可以作類似分析。多維數(shù)組的順序存儲有兩種形式：多維數(shù)組的順序存儲有兩種形式：5.2.1 行優(yōu)先順序行優(yōu)先順序1存放規(guī)則存放規(guī)則 行優(yōu)先順序也稱為低下標優(yōu)先。具體實現(xiàn)時，行優(yōu)先順序也稱為低下標優(yōu)先。具體實現(xiàn)時，按行號從小到大的順序，先將第一行中元素全按行號從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，

6、部存放好，再存放第二行元素，第三行元素，依次類推依次類推 在在BASIC語言、語言、 PASCAL語言、語言、 C/C+語言等語言等高級語言程序設計中，都是按行優(yōu)先順序存放高級語言程序設計中，都是按行優(yōu)先順序存放的。例如，對剛才的的。例如，對剛才的Amn二維數(shù)組，可用如下二維數(shù)組，可用如下形式存放到內存：形式存放到內存：a00， a01, a0n-1，a10，a11，.， a1 n-1，am-1 0 ， am-1 1，am-1 n-1。即二維數(shù)組按行優(yōu)先存放到內存后，變成了一即二維數(shù)組按行優(yōu)先存放到內存后，變成了一個線性序列（線性表）。個線性序列（線性表）。因此，可以得出多維數(shù)組按行優(yōu)先存放到

7、內存因此，可以得出多維數(shù)組按行優(yōu)先存放到內存的規(guī)律：最左邊下標變化最慢，最右邊下標變的規(guī)律：最左邊下標變化最慢，最右邊下標變化最快，右邊下標變化一遍，與之相鄰的左邊化最快，右邊下標變化一遍，與之相鄰的左邊下標才變化一次。因此，在算法中，最左邊下下標才變化一次。因此，在算法中，最左邊下標可以看成是外循環(huán)，最右邊下標可以看成是標可以看成是外循環(huán)，最右邊下標可以看成是最內循環(huán)。最內循環(huán)。 2地址計算地址計算 由于多維數(shù)組在內存中排列成一個線性序列，由于多維數(shù)組在內存中排列成一個線性序列，因此，若知道第一個元素的內存地址，如何求因此，若知道第一個元素的內存地址，如何求得其它元素的內存地址？得其它元素的

8、內存地址？ 我們可以將它們的地址排列看成是一個等差數(shù)列，假我們可以將它們的地址排列看成是一個等差數(shù)列，假設每個元素占設每個元素占L個字節(jié)，元素個字節(jié)，元素aij 的存儲地址應為第一的存儲地址應為第一個元素的地址加上排在個元素的地址加上排在aij 前面的元素所占用的單元數(shù)，前面的元素所占用的單元數(shù)，而而aij 的前面有的前面有i行行(0i-1)共共in個元素，而本行前面又個元素，而本行前面又有有j個個(0j-1)元素，故元素，故aij的前面一共有的前面一共有in+j個元素，設個元素，設a00的內存地址為的內存地址為LOC(a00)，則，則aij的內存地址按等差數(shù)的內存地址按等差數(shù)列計為列計為:L

9、OC(aij)=LOC(a00)+（in+j）L。同理，三維數(shù)組同理，三維數(shù)組Amnp按行優(yōu)先存放的地址計算公式按行優(yōu)先存放的地址計算公式為：為：LOC(aijk)=LOC(a000)+(inp+jp+k)L。5.2.2 列優(yōu)先順序列優(yōu)先順序1存放規(guī)則存放規(guī)則列優(yōu)先順序也稱為高下標優(yōu)先。具體實現(xiàn)時，列優(yōu)先順序也稱為高下標優(yōu)先。具體實現(xiàn)時，按列號從小到大的順序，先將第一列中元素全按列號從小到大的順序，先將第一列中元素全部存放好，再存放第二列元素，第三列元素，部存放好，再存放第二列元素，第三列元素，依次類推依次類推 在在FORTRAN語言程序設計中，數(shù)組是按列優(yōu)先語言程序設計中，數(shù)組是按列優(yōu)先順序

10、存放的。例如，對前面提到的順序存放的。例如，對前面提到的Amn二維數(shù)組，二維數(shù)組，可以按如下的形式存放到內存：可以按如下的形式存放到內存：a00， a10， am-10， a01，a11， ， am-1 1， a0 m-1，a1m-1，.， am-1 n-1。 即二維數(shù)組按列優(yōu)先存放到內存后，也變成即二維數(shù)組按列優(yōu)先存放到內存后，也變成了一個線性序列（線性表）。了一個線性序列（線性表）。因此，可以得出多維數(shù)組按列優(yōu)先存放到內存的因此，可以得出多維數(shù)組按列優(yōu)先存放到內存的規(guī)律：最右邊下標變化最慢，最左邊下標變化最規(guī)律：最右邊下標變化最慢，最左邊下標變化最快，左邊下標變化一遍，與之相鄰的右邊下標才

11、快，左邊下標變化一遍，與之相鄰的右邊下標才變化一次。因此，在算法中，最右邊下標可以看變化一次。因此，在算法中，最右邊下標可以看成是外循環(huán)，最左邊下標可以看成是最內循環(huán)。成是外循環(huán)，最左邊下標可以看成是最內循環(huán)。2地址計算地址計算 同樣與行優(yōu)先存放類似，若知道第一個元素的內同樣與行優(yōu)先存放類似，若知道第一個元素的內存地址，則同樣可以求得按列優(yōu)存放的某一元素存地址，則同樣可以求得按列優(yōu)存放的某一元素aij的地址。的地址。對二維數(shù)組有：對二維數(shù)組有：LOC(aij)=LOC(a00)+(jm+i)L對三維數(shù)組有：對三維數(shù)組有： LOC(aijk)=LOC(a000)+(kmn+jm+i)L題目題目1

12、: 1: 假設有二維數(shù)組假設有二維數(shù)組A A6x86x8，每個元素用相鄰的，每個元素用相鄰的6 6 個字節(jié)存儲，存儲器按字節(jié)編址。已知個字節(jié)存儲，存儲器按字節(jié)編址。已知A A 的起始存儲地址（基地址）為的起始存儲地址（基地址）為10001000，計算：，計算：數(shù)組數(shù)組A A的存儲量；的存儲量；數(shù)組數(shù)組A A的最后一個元素的最后一個元素a a5757的第一個字節(jié)的地址；的第一個字節(jié)的地址；按行存儲時，元素按行存儲時，元素a a1414的第一個字節(jié)的地址；的第一個字節(jié)的地址；按列存儲時，元素按列存儲時，元素a a4747的第一個字節(jié)的地址；的第一個字節(jié)的地址；二維數(shù)組二維數(shù)組M M 的成員是的成員

13、是6 6個字符（每個字符占一個存儲個字符（每個字符占一個存儲單元）單元） 組成的串，行下標的范圍從組成的串，行下標的范圍從0 0到到8 8，列下標的，列下標的范圍從范圍從1 1到到1010，則，則M M至少需要至少需要_ _ _個字節(jié)，個字節(jié)，M M 的第的第8 8列列和第和第5 5行共占行共占_個字節(jié)，若個字節(jié)，若M M 按行優(yōu)先方式存儲，按行優(yōu)先方式存儲，M M 8585的起始地址與的起始地址與M M 按列優(yōu)先方式存儲時的按列優(yōu)先方式存儲時的_元元素的起使地址一致。素的起使地址一致。 A A、 90 ; 114; M5890 ; 114; M58 B B、 180; 54; M89180;

14、 54; M89 C C、 240; 60; M09240; 60; M09 D D、 540; 108; M310540; 108; M310數(shù)組數(shù)組A A中，每個元素中，每個元素A A 的長度為的長度為3 3個字節(jié)，行下標個字節(jié)，行下標i i從從1 1到到8 8，列下標，列下標j j從從1 1到到1010 ，從首地址，從首地址SASA開始連開始連續(xù)存放在存儲器內，該數(shù)組按行存放時，元素續(xù)存放在存儲器內，該數(shù)組按行存放時，元素A85A85的起始地址為的起始地址為_。 A A、 SA+141SA+141 B B、 SA+180SA+180 C C、 SA+222SA+222 D D、 SA+2

15、25SA+225二維二維A1020A1020采用列序為主方式存儲，每個元素占一采用列序為主方式存儲，每個元素占一個存儲單元，并且個存儲單元，并且A00A00的存儲地址是的存儲地址是200200，則，則A612A612的地址是的地址是_。二維數(shù)組二維數(shù)組A10.205.10A10.205.10采用行序為主方式存儲，采用行序為主方式存儲，每個元素占每個元素占4 4個存儲單元，并且個存儲單元，并且A105A105的存儲地址是的存儲地址是10001000，則，則A189A189的地址是的地址是_。 1. 設二維數(shù)組設二維數(shù)組a610，每個數(shù)組元素占用，每個數(shù)組元素占用4個存儲單元，若按行個存儲單元，若

16、按行 優(yōu)先順序存放數(shù)組元素，優(yōu)先順序存放數(shù)組元素，a00的存儲的地址為的存儲的地址為860，則，則a35 的存儲地址是（的存儲地址是（ ） A. 1000 B. 860 C. 1140 D. 1200AC2. 一個矩陣從一個矩陣從a00開始存放，每個元素占用開始存放，每個元素占用4個存儲單元，若個存儲單元，若 a78的存儲地址為的存儲地址為2732，a1316的存儲地址為的存儲地址為3364，則此，則此 矩陣的存儲方式是（矩陣的存儲方式是（ ） A. 只能按行優(yōu)先存儲只能按行優(yōu)先存儲 B. 只能按列優(yōu)先存儲只能按列優(yōu)先存儲 C. 按行優(yōu)先存儲或按列優(yōu)先存儲均可按行優(yōu)先存儲或按列優(yōu)先存儲均可 D

17、. 以上都不對以上都不對D3. 在一個二維數(shù)組在一個二維數(shù)組A中，假設每個數(shù)組元素長度為中，假設每個數(shù)組元素長度為3個存儲單元，個存儲單元， 行下標行下標i為為08，列下標，列下標j為為09，從首地址，從首地址SA開始連續(xù)存放，此開始連續(xù)存放，此 時時A85起始地址為（起始地址為（ ） A. SA+141 B. SA+144 C. SA+222 D. SA+2555.3 特殊矩陣及其壓縮存儲特殊矩陣及其壓縮存儲 5.3.1 特殊矩陣特殊矩陣 若一個若一個n階方陣階方陣A中元素滿足下列條件：中元素滿足下列條件： aij=aji 其中其中 0 i, jn-1 ，則稱，則稱A為對稱為對稱矩陣。矩陣。

18、1對稱矩陣對稱矩陣 例如，圖例如，圖5-1是一個是一個3*3的對稱矩陣。的對稱矩陣。 A= 643452321 圖 5-1 一個對稱矩陣 2三角矩陣三角矩陣 （1）上三角矩陣）上三角矩陣即矩陣上三角部分元素是隨機的，而下三即矩陣上三角部分元素是隨機的，而下三角部分元素全部相同（為某常數(shù)角部分元素全部相同（為某常數(shù)C）或全為）或全為0，具體形式見圖，具體形式見圖5-2(a)。 圖圖5-2(a) 上三角矩陣上三角矩陣 11,11,1110,0100.- - - - - - n n n n acccaacaaa （2）下三角矩陣）下三角矩陣即矩陣的下三角部分元素是隨機的，而上即矩陣的下三角部分元素是

19、隨機的，而上三角部分元素全部相同（為某常數(shù)三角部分元素全部相同（為某常數(shù)C）或）或全為全為0，具體形式見圖，具體形式見圖5-2(b)。 111,11,0111000.- - - - -,nnnnaaacaacca 圖圖5-2(b) 下三角矩陣下三角矩陣 3對角矩陣對角矩陣 若矩陣中所有非零元素都集中在以主對角若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的有三對角矩陣、則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。五對角矩陣、七對角矩陣等。例如，圖例如，圖5-3為為7 7的三對角矩陣（即有三的

20、三對角矩陣（即有三條對角線上元素非條對角線上元素非0）。）。 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa 圖圖 5-3 一個一個 7X77X7的三對角矩陣的三對角矩陣 5.3.2 壓縮存儲壓縮存儲1對稱矩陣對稱矩陣 若矩陣若矩陣An n是對稱的，對稱的兩個元素可以共用一個是對稱的，對稱的兩個元素可以共用一個存儲單元，這樣，原來存儲單元，這樣，原來n 階方陣需階方陣需 n2個存儲單元，若個存儲單元，若采用壓縮存儲，僅需采用壓縮存儲，僅需 n(n+1)/2個存貯單元，

21、將近節(jié)約個存貯單元，將近節(jié)約一半存貯單元，這就是實現(xiàn)壓縮的好處。但是，將一半存貯單元，這就是實現(xiàn)壓縮的好處。但是，將n階階對稱方陣存放到一個向量空間對稱方陣存放到一個向量空間s0到到s -1中，我們中，我們怎樣找到怎樣找到sk與與aij的一一對稱應關系呢？使我們在的一一對稱應關系呢？使我們在sk中直接找到中直接找到aij。2) 1( + +nn我們僅以行優(yōu)先存放分兩種方式討論：我們僅以行優(yōu)先存放分兩種方式討論：例如，圖例如，圖5-1是一個是一個3*3的對稱矩陣。的對稱矩陣。 A= 643452321 圖 5-1 一個對稱矩陣 （1）只存放下三角部分）只存放下三角部分由于對稱矩陣關于主對角線對稱

22、，故我們只需存放主對由于對稱矩陣關于主對角線對稱，故我們只需存放主對角線及主對角線以下的元素。這時，角線及主對角線以下的元素。這時，a00存入存入s0，a10 存入存入s1，a11存入存入 s2，具體參見下圖。，具體參見下圖。aij這時這時sk與與aij的對應關系為的對應關系為: i(i+1)/2+j 當當 ij k= j(j+1)/2+i 當當 ij aijaji下面的對應關系容易推出：當下面的對應關系容易推出：當ij 時，時，aij在下三角部分在下三角部分中，中，aij前面有前面有i行，共有行，共有1+2+3+i個元素，而個元素，而aij是第是第i+1行的第行的第j個元素，即有個元素，即有

23、k=1+2+3+-+i+j=i(i+1)/2+j；當當ij時，交換時，交換i與與j即可。即可。ajiaij(1)2iinjiki- -+-(1)2iin i- - 11122211121110020100.- - - - - -nnnnnaaaaaaaaaa a00 a01 a02 a03 a04 a05 a06 a07 an-2n-2 an-2n-1 an-1n-1 0 1 2 3 4 5 6 7 2) 1( +nn -3 2) 1( +nn -2 2) 1( +nn -1 對稱矩陣及用上三角壓縮存儲 i*n- +j-i 當當ij k= j*n- +i-j 當當ij2) 1( - -ii2)

24、1( - -jj故sk與aij的對應關系為：設有一個設有一個n n n n的對稱矩陣的對稱矩陣A A，將其上三角部分，將其上三角部分按行存放在一個一維數(shù)組按行存放在一個一維數(shù)組B B中，中，A00A00存放存放于于B0B0中，那么第中，那么第i+1i+1行的對角元素行的對角元素AiiAii存放于存放于B B中（中（ ）處。）處。 A. (i+3)A. (i+3)* *i/2 i/2 B. (i+1) B. (i+1)* *i/2i/2 C. (2n-i+1) C. (2n-i+1)* *i/2i/2 D. (2n-i-1) D. (2n-i-1)* *i/2i/2C C2三角矩陣三角矩陣 （1

25、）下三角矩陣）下三角矩陣下三角矩陣的壓縮存放與對稱矩陣用下三角形式存放類下三角矩陣的壓縮存放與對稱矩陣用下三角形式存放類似，但必須多一個存儲單元存放上三角部分元素，使用似，但必須多一個存儲單元存放上三角部分元素，使用的存儲單元數(shù)目為的存儲單元數(shù)目為n(n+1)/2+1。故可以將。故可以將n n的下三角矩的下三角矩陣壓縮存放到只有陣壓縮存放到只有n(n+1)/2+1個存儲單元的向量中，假個存儲單元的向量中，假設仍按行優(yōu)先存放，這時設仍按行優(yōu)先存放，這時sk與與aij的對應關系為：的對應關系為： i(i+1)/2+j ij k= n(n+1)/2 ij) 5.4 稀疏矩陣稀疏矩陣按照壓縮存儲的概念

26、，要存放稀疏矩陣的元素，由于沒按照壓縮存儲的概念，要存放稀疏矩陣的元素，由于沒有某種規(guī)律，除存放非零元的值外，還必須存貯適當?shù)挠心撤N規(guī)律，除存放非零元的值外，還必須存貯適當?shù)妮o助信息，才能迅速確定一個非零元是矩陣中的哪一個輔助信息，才能迅速確定一個非零元是矩陣中的哪一個位置上的元素。下面將介紹稀疏矩陣的幾種存儲方法及位置上的元素。下面將介紹稀疏矩陣的幾種存儲方法及一些算法的實現(xiàn)。一些算法的實現(xiàn)。 5.4.1 稀疏矩陣的存儲稀疏矩陣的存儲 1三元組表三元組表在壓縮存放稀疏矩陣的在壓縮存放稀疏矩陣的非零元非零元同時，若還存放此同時，若還存放此非零元所在的非零元所在的行號行號和和列號列號，則稱為，則

27、稱為三元組表法三元組表法，即稱稀疏矩陣可用三元組表進行壓縮存儲，但它即稱稀疏矩陣可用三元組表進行壓縮存儲，但它是一種順序存貯（按行優(yōu)先順序存放）。一個非是一種順序存貯（按行優(yōu)先順序存放）。一個非零元有零元有行號、列號、值行號、列號、值，為一個，為一個三元組三元組，整個稀整個稀疏矩陣中非零元的三元組合起來稱為三元組表疏矩陣中非零元的三元組合起來稱為三元組表。 00070015000001800000240001400003000000000009120- 稀疏矩陣M 2帶行指針的鏈表帶行指針的鏈表 把具有相同行號的非零元用一個單鏈表連接起把具有相同行號的非零元用一個單鏈表連接起來，稀疏矩陣中的若

28、干行組成若干個單鏈表，來，稀疏矩陣中的若干行組成若干個單鏈表，合起來稱為帶行指針的鏈表。例如，稀疏矩陣合起來稱為帶行指針的鏈表。例如，稀疏矩陣M的帶行指針的鏈表描述形式見下圖。的帶行指針的鏈表描述形式見下圖。 5.5 廣義表廣義表 5.5.1基本概念基本概念廣義表是第二章提到的線性表的推廣。線性表廣義表是第二章提到的線性表的推廣。線性表中的元素僅限于原子項，即不可以再分，而廣中的元素僅限于原子項，即不可以再分，而廣義表中的元素既可以是義表中的元素既可以是原子項原子項，也可以是，也可以是子表子表(另一個線性表另一個線性表)。 1廣義表的定義廣義表的定義廣義表是廣義表是n0個元素個元素a1，a2，

29、an的有限序列，的有限序列，其中每一個其中每一個ai或者是或者是原子原子，或者是一個，或者是一個子表子表。廣義表通常記為廣義表通常記為LS=(a1,a2,an)，其中，其中LS為廣為廣義表的名字，義表的名字，n為廣義表的長度，為廣義表的長度， 每一個每一個ai為廣為廣義表的元素。但在習慣中，一般用大寫字母表義表的元素。但在習慣中，一般用大寫字母表示廣義表，小寫字母表示原子。示廣義表，小寫字母表示原子。2廣義表舉例廣義表舉例 (1) A=( ), A為空表，長度為為空表，長度為0。B=(a,（b,c） ), B是長度為是長度為2的廣義表，第一項的廣義表，第一項 為原子，第二項為子表。為原子，第二

30、項為子表。C=(x,y,z) C是長度為是長度為3的廣義表，每一項都是的廣義表，每一項都是 原子。原子。(4) D=(B,C) ， D是長度為是長度為2的廣義表，每一項都是上的廣義表，每一項都是上 面提到的子表。面提到的子表。(5) E=(a,E) 是長度為是長度為2的廣義表，第一項為原子，第的廣義表，第一項為原子，第 二項為它本身。二項為它本身。 3廣義表的表示方法廣義表的表示方法 (1) 用用LS=(a1，a2，an)形式，其中每一個形式，其中每一個ai為原子為原子 或廣義表或廣義表例如：例如： A=(b,c) B=(a,A) E=(a,E) 都是廣義表。都是廣義表。（2）將廣義表中所有子

31、表寫到）將廣義表中所有子表寫到原子形式原子形式，并利用圓括號，并利用圓括號 嵌套嵌套 例如，上面提到的廣義表例如，上面提到的廣義表A、B、C可以描述為：可以描述為： A (b,c) B (a,(b,c) E (a, (a,（a,）)(3) 將廣義表用樹和圖來描述將廣義表用樹和圖來描述 上面提到的廣義表上面提到的廣義表A、B、C的描述見下圖。的描述見下圖。 B A C b a c A b c B a A b c (a) A=(b,c) (b) B=(a,A) (c) C=(A,B) 廣義表用廣義表用樹樹或或圖圖來表示來表示 4廣義表的廣義表的深度深度 一個廣義表的深度是指該廣義表展開后所含括號的

32、一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。層數(shù)。例如，例如，A=(b,c)的深度為的深度為1，B=(A,d)的深度為的深度為2，C=(f,B,h)的深度為的深度為3。設有廣義表設有廣義表D(a,b,D)D(a,b,D)，其長度為，其長度為-，深度為，深度為-.-.廣義表廣義表(a,(a,b),d,e,(i,j),k)的長度是的長度是_，深度是，深度是_5廣義表的廣義表的表頭、表尾表頭、表尾若廣義表若廣義表LSLS（n=1)n=1)非空，則非空，則a1a1是是LSLS的表頭，其余的表頭，其余元素組成的表元素組成的表(a(a1 1,a,a2 2, ,a an n) )稱為稱為LSLS的表尾

33、。的表尾。任何一個非空廣義表其任何一個非空廣義表其表頭可能是原子表表頭可能是原子表，也可能，也可能是是廣義表廣義表，而其，而其表尾必定是廣義表表尾必定是廣義表。廣義表廣義表(a),a)的表頭是的表頭是_，表尾是，表尾是_廣義表廣義表(a,b),c,d)的表頭是的表頭是_，表尾是，表尾是_ 廣義表廣義表(a,b,c,d)的表頭是的表頭是_，表尾是，表尾是_問：一個廣義表由其表頭和表尾唯一確定？問：一個廣義表由其表頭和表尾唯一確定？設設HAEDpHAEDp為求廣義表為求廣義表p p的表頭函數(shù)，的表頭函數(shù)，TAILpTAILp為求廣義表為求廣義表p p的表尾函數(shù)，其中的表尾函數(shù)，其中是函數(shù)的符是函數(shù)的符號，給出下列廣義表的運算結果：號，給出下列廣義表的運算結果：HEADHEAD（a a，b b，c c） 的結果是的結果是_。TAILTAIL（a,b,ca,b,c） 的結果是的結果是_。HEAD(a),(b)HEAD(a),(b)的結果是的結果是_。TAIL(a),(b)TAIL(a),(b)的結果是的結果是_。HEADTAIL(a,b,c)HEADTAIL(a,b,c)的結果是的結果是_。TAILHEAD(a,b),(c,d)TAILHEAD(a,b),(c,d)的結果是的結果是_。HEADHEAD(a,b),(c,d)HEADHEAD(a,b),(c,d)的結