第6章數(shù)組和廣義表

1、1數(shù)組和廣義表數(shù)組和廣義表u數(shù)組和廣義表數(shù)組和廣義表邏輯上是線性結(jié)構(gòu)的推廣邏輯上是線性結(jié)構(gòu)的推廣u數(shù)數(shù) 組組：元素的結(jié)構(gòu)相同元素的結(jié)構(gòu)相同u廣義表：廣義表：元素的結(jié)構(gòu)可以不同元素的結(jié)構(gòu)可以不同 2第第6章章 數(shù)組和廣義表數(shù)組和廣義表 6.1 6.1 數(shù)組數(shù)組6.2 6.2 稀疏矩陣稀疏矩陣6.3 6.3 廣義表廣義表3數(shù)組數(shù)組 n(n1)個相同類型的數(shù)據(jù)元素構(gòu)成的有限個相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。序列。邏輯表示：邏輯表示： A=(a1,a2,an)高級語言中的數(shù)組高級語言中的數(shù)組 int A10; char B45 ;6.1.1 數(shù)組的基本概念數(shù)組的基本概念4二維數(shù)組的定義二維數(shù)組的定義

2、 int a23; /聲明聲明A為整型數(shù)組類型為整型數(shù)組類型 typedef int A3; /定義類型為定義類型為A的一維數(shù)組變量的一維數(shù)組變量a A a2; 兩個變量組成的一個數(shù)組，兩個變量組成的一個數(shù)組，其中每一個變量都是數(shù)組其中每一個變量都是數(shù)組a01a00a12a11a10a02a0a1結(jié)論：結(jié)論：二維數(shù)組是一個特殊的一維數(shù)組，其每個數(shù)二維數(shù)組是一個特殊的一維數(shù)組，其每個數(shù)據(jù)元素又是一個一維數(shù)組。據(jù)元素又是一個一維數(shù)組。5 nmmmnnnmaaaaaaaaaA,2,1 ,22,21 ,2, 12, 11 , 1 將將Am*n簡記為簡記為A A=(a1,a2,ai,am)其中，其中，a

3、i=(ai,1,ai,2,ai,n) 二維數(shù)組二維數(shù)組 二維數(shù)組是一個特殊的線性表，其每個數(shù)據(jù)元素又二維數(shù)組是一個特殊的線性表，其每個數(shù)據(jù)元素又是一個線性表。是一個線性表。 任何多維數(shù)組都可以看作一個線性表，線性表中的任何多維數(shù)組都可以看作一個線性表，線性表中的每個數(shù)據(jù)元素又是一個線性表。每個數(shù)據(jù)元素又是一個線性表。 數(shù)組是線性表的推廣。數(shù)組是線性表的推廣。6數(shù)組作為數(shù)據(jù)類型的性質(zhì)數(shù)組作為數(shù)據(jù)類型的性質(zhì)1、數(shù)組中的、數(shù)組中的數(shù)據(jù)元素數(shù)目固定數(shù)據(jù)元素數(shù)目固定。一旦定義了。一旦定義了一個數(shù)組，其數(shù)據(jù)元素數(shù)目一個數(shù)組，其數(shù)據(jù)元素數(shù)目不再有增減變化不再有增減變化。2、數(shù)組中的數(shù)據(jù)元素具有、數(shù)組中的數(shù)據(jù)

4、元素具有相同的數(shù)據(jù)類型相同的數(shù)據(jù)類型。3、數(shù)組中的每個數(shù)據(jù)元素都和、數(shù)組中的每個數(shù)據(jù)元素都和一組唯一的下一組唯一的下標值標值對應(yīng)。對應(yīng)。4、數(shù)組是一種、數(shù)組是一種隨機存儲結(jié)構(gòu)隨機存儲結(jié)構(gòu)，可隨機存取數(shù)，可隨機存取數(shù)組中的任意數(shù)據(jù)元素。組中的任意數(shù)據(jù)元素。7數(shù)組的抽象數(shù)據(jù)類型數(shù)組的抽象數(shù)據(jù)類型ADT Array數(shù)據(jù)對象：數(shù)據(jù)對象： Daj1j2jn|ji是數(shù)組元素的第是數(shù)組元素的第i維下標，維下標，1jibi，bi是數(shù)組第是數(shù)組第i維的長維的長度，度，aj1j2jn ElemSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R=r1,r2,rn ri=| 0jkbk-1, 1kn 且且 ki, 0jibi-2, a

5、j1jijn,aj1ji+1jn D, i=2,n基本操作：基本操作： Value(A,index1,indexn) 操作結(jié)果：若各下標不超界，返回數(shù)組操作結(jié)果：若各下標不超界，返回數(shù)組A的對應(yīng)下標的元素值的對應(yīng)下標的元素值 Assign(A,e,index1,indexn) 操作結(jié)果：若各下標不超界，將變量操作結(jié)果：若各下標不超界，將變量e的值賦給由的值賦給由n個下標確定的個下標確定的A的元素的元素 ADisp(A,b1,b2,bn) 操作結(jié)果：輸出操作結(jié)果：輸出n維數(shù)組維數(shù)組A的所有元素值的所有元素值A(chǔ)DT Array 特點：數(shù)組一般不做插入和刪除操作特點：數(shù)組一般不做插入和刪除操作86.

6、1.2 數(shù)組的存儲結(jié)構(gòu)數(shù)組的存儲結(jié)構(gòu)u類型特點類型特點: 只有只有引用型引用型操作操作 沒有沒有加工型加工型操作操作適合順序存儲適合順序存儲9一維數(shù)組中，一旦一維數(shù)組中，一旦a1的存儲地址的存儲地址LOC(a1)確定，并確定，并假設(shè)每個數(shù)據(jù)元素占用假設(shè)每個數(shù)據(jù)元素占用k個存儲單元，則任一數(shù)據(jù)元個存儲單元，則任一數(shù)據(jù)元素素ai的存儲地址的存儲地址LOC(ai)就可由以下公式求出：就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in)可見，一維數(shù)組中任一數(shù)據(jù)元素的存儲地址可直可見，一維數(shù)組中任一數(shù)據(jù)元素的存儲地址可直接計算得到接計算得到一維數(shù)組中任一數(shù)據(jù)元素可直接存取，是

7、一種一維數(shù)組中任一數(shù)據(jù)元素可直接存取，是一種隨隨機存儲的機存儲的結(jié)構(gòu)。結(jié)構(gòu)。一維數(shù)組的存儲一維數(shù)組的存儲10 矛盾：矛盾：計算機的存儲結(jié)構(gòu)是線性的、一維的計算機的存儲結(jié)構(gòu)是線性的、一維的 問題：問題：如何用線性的存儲結(jié)構(gòu)存放二維數(shù)組的元素？如何用線性的存儲結(jié)構(gòu)存放二維數(shù)組的元素？ 解決方法：解決方法： 1）以）以行序為主序行序為主序存儲：存儲： 先存儲第先存儲第1行，然后緊接著存儲第行，然后緊接著存儲第2行，最后存行，最后存儲第儲第m行行 2）以）以列序為主序列序為主序存儲：存儲： 先存儲第先存儲第1列，然后緊接著存儲第列，然后緊接著存儲第2列，最后存列，最后存儲第儲第n列列二維數(shù)組的存儲二維

8、數(shù)組的存儲11數(shù)組數(shù)組a23的順序存儲的順序存儲a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2行序為主序行序為主序a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2列序為主序列序為主序12 當二維數(shù)組當二維數(shù)組Am*n第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素a1,1的存儲地址的存儲地址LOC(a1,1)和每個數(shù)據(jù)元素所占用的存儲單元和每個數(shù)據(jù)元素所占用的存儲單元k確定后，確定后，該二維數(shù)組中任一數(shù)據(jù)元素該二維數(shù)組中任一數(shù)據(jù)元素ai,j的存儲地址可由下式的存儲地址可由下式確定：確定： LOC(ai,j)=LOC(

9、a1,1)+(i-1)*n+(j-1)*k 同理可推出在以列序為主序的計算機系統(tǒng)中有：同理可推出在以列序為主序的計算機系統(tǒng)中有： LOC(ai,j)=LOC(a1,1)+(j-1)*m+(i-1)*k 以行序為主序以行序為主序13數(shù)組的順序存儲數(shù)組的順序存儲 設(shè)二維數(shù)組設(shè)二維數(shù)組A是：是： Ac1.d1,c2.d2(c1id1,c2jd2) 其中其中c1、c2和和d1、d2分別為二維數(shù)組分別為二維數(shù)組A的邊界的的邊界的下界和上界，每個數(shù)組元素占用下界和上界，每個數(shù)組元素占用k個存儲單元個存儲單元 LOC(i,j)=LOC(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*k 14

10、例例6.1 對二維數(shù)組對二維數(shù)組float a54計算：計算： (1) 數(shù)組數(shù)組a中的數(shù)組元素數(shù)目；中的數(shù)組元素數(shù)目； (2) 若數(shù)組若數(shù)組a的起始地址為的起始地址為2000，且每個數(shù)組元素長，且每個數(shù)組元素長度為度為32位位(即即4個字節(jié)個字節(jié))，數(shù)組元素，數(shù)組元素a32的內(nèi)存地址。的內(nèi)存地址。 解：該數(shù)組的元素數(shù)目共有解：該數(shù)組的元素數(shù)目共有5*4=20個。個。 由于由于C語言采用行序為主序的存儲方式，則有：語言采用行序為主序的存儲方式，則有： LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=205616 特殊矩陣：特殊矩陣：非零元素或零元素的分

11、布有一定非零元素或零元素的分布有一定規(guī)律規(guī)律 特別是在高階矩陣的情況下，可以利用特殊特別是在高階矩陣的情況下，可以利用特殊矩陣的規(guī)律，對它們進行壓縮存儲，以便矩陣的規(guī)律，對它們進行壓縮存儲，以便節(jié)省節(jié)省存儲空間存儲空間 做法：做法：使多個相同的非零元素使多個相同的非零元素共享共享同一個存同一個存儲空間，對零元素儲空間，對零元素不分配不分配存儲空間存儲空間6.1.3 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲17 對稱矩陣對稱矩陣 n階方陣階方陣Ann 元素滿足元素滿足ai,j=aj,i(0i，jn-1) 對稱矩陣中的元素關(guān)于主對角線對稱，在存儲時可對稱矩陣中的元素關(guān)于主對角線對稱，在存儲時可只存儲對

12、稱矩陣中上三角或下三角中的元素，使得只存儲對稱矩陣中上三角或下三角中的元素，使得對對稱的元素共享一個存儲空間。稱的元素共享一個存儲空間。 n2個元素個元素壓縮存儲壓縮存儲到到n(n+1)/2個元素的空間中。個元素的空間中。1、對稱矩陣的壓縮存儲、對稱矩陣的壓縮存儲1, 11 , 10, 11, 11 , 10, 11,01 ,00,0nnnnnnaaaaaaaaaai,i（0in-1-1）對角線對角線ai,j（ij）上三角上三角ai,j（ij）下三角下三角18 n2個元素個元素 n(n+1)/2個元素個元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bk21)i(i k=+

13、 j ij+ i ij21)j(j k= 0 1 2 3 2) 1( nn12) 1(nn以行序為主序存儲其下三角的元素以行序為主序存儲其下三角的元素a00a10a11a20an-1,0an-1,n-119上三角矩陣：上三角矩陣： 2)12(* ini2)1( nnk=+ j i ij時時ij時時下三角矩陣：下三角矩陣： jii2)1(* 2)1( nnk= ij時時ij時時1, 11, 11 , 11,01 ,00,0nnnnaaaaaac1, 11 ,0,1 , 10, 10,0nnnnaaaaaac20 2、 對角矩陣的壓縮存儲對角矩陣的壓縮存儲（略）（略） n階對角矩陣：階對角矩陣：n

14、階方陣階方陣A，滿足其，滿足其所有非零元素都所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中集中在以主對角線為中心的帶狀區(qū)域中。 若其主對角線上下方各有若其主對角線上下方各有b條次對角線條次對角線，稱，稱b為為矩陣矩陣半帶寬半帶寬，(2b+1)為為矩陣的帶寬矩陣的帶寬。 對于半帶寬為對于半帶寬為b（0b(n-1)/2）的對角矩陣，其）的對角矩陣，其|i-j|b的元素的元素ai,j不為零，其余元素為零。不為零，其余元素為零。 . b條條 b條條 0 0 . 當當b1時稱為時稱為三對角矩陣三對角矩陣。其壓縮地址計算公式如下：其壓縮地址計算公式如下： k=2i+j 216.2 稀疏矩陣稀疏矩陣 非零

15、元素較少，分布無規(guī)律非零元素較少，分布無規(guī)律 稀疏因子：稀疏因子：= s/(m*n) = 0.05 由于分布無規(guī)律，存放非零元素由于分布無規(guī)律，存放非零元素必須同時存必須同時存放其在矩陣中的位置放其在矩陣中的位置，即下標和值一起存放，即下標和值一起存放 一個三元組唯一確定了稀疏矩陣中的一個非一個三元組唯一確定了稀疏矩陣中的一個非零元素零元素226.2.1 稀疏矩陣的三元組表示稀疏矩陣的三元組表示 假設(shè)有一個假設(shè)有一個67階稀疏矩陣階稀疏矩陣A，A中元素如下中元素如下圖所示。圖所示。 47000000060000000500000000030000020000010076A 則對應(yīng)的三元組線性表

16、為：則對應(yīng)的三元組線性表為： (0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4)23稀疏矩陣的存儲結(jié)構(gòu)稀疏矩陣的存儲結(jié)構(gòu) 三元組線性表：三元組線性表： (0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4) 順序存儲結(jié)構(gòu)三元組順序表順序存儲結(jié)構(gòu)三元組順序表 鏈式存儲結(jié)構(gòu)十字鏈表鏈式存儲結(jié)構(gòu)十字鏈表 24三元組順序表舉例三元組順序表舉例 0009012700030008000000000200060A0700200000008009000003006120000Brcd01605-

17、223-831335740-12429rcd04-1210613324932-850-253725三元組順序表三元組順序表#define MaxSize typedef struct 三元組三元組int r,c; 非零元的行號、列號非零元的行號、列號 ElemType d; 非零元的值非零元的值 TupNode;typedef struct int rows,cols; 矩陣的行數(shù)、列數(shù)矩陣的行數(shù)、列數(shù) int nums; /非零元個數(shù)非零元個數(shù)TupNode dataMaxSize; 三元組表三元組表TSMatrix; 下面的討論假設(shè)按行有序存儲。下面的討論假設(shè)按行有序存儲。26 (1) 從

18、一個二維稀疏矩陣創(chuàng)建其三元組表示從一個二維稀疏矩陣創(chuàng)建其三元組表示 以行序方式掃描二維矩陣以行序方式掃描二維矩陣A，將其非零的元素插入，將其非零的元素插入到三元組到三元組t的后面。的后面。 void CreatMat(TSMatrix &t,ElemType AMN) int i,j; t.rows=M; t.cols=N; t.nums=0; for (i=0;iM;i+) for (j=0;j=t.rows | j=t.cols) return false; while (kt.datak.r) k+;/*查找行查找行*/ while (kt.datak.c) k+;/*查找列查找

19、列*/ if (t.datak.r=i & t.datak.c=j) t.datak.d=x; /*存在這樣的元素存在這樣的元素 else /*不存在這樣的元素時插入一個元素不存在這樣的元素時插入一個元素*/ for (k1=t.nums-1;k1=k;k1-) /*元素后移元素后移*/ t.datak1+1.r=t.datak1.r; t.datak1+1.c=t.datak1.c; t.datak1+1.d=t.datak1.d; t.datak.r=i; t.datak.c=j; t.datak.d=x; t.nums+; return true; 29 (3) 將指定位置的元素

20、值賦給變量將指定位置的元素值賦給變量 x=Aij; 先在三元組中找到指定的位置，將其元素值賦給先在三元組中找到指定的位置，將其元素值賦給x。 bool Assign(TSMatrix t,ElemType &x,int i,int j) int k=0; if (i=t.rows | j=t.cols) return false; while (kt.datak.r) k+; while (kt.datak.c) k+; if (t.datak.r=i & t.datak.c=j) x=t.datak.d; else x=0; return true; 30 (4) 輸出三元組

21、輸出三元組 從頭到尾掃描三元組從頭到尾掃描三元組t，依次輸出元素值。，依次輸出元素值。 void DispMat(TSMatrix t) int i; if (t.nums=0) return;printf(“t%dt%dt%dn,t.rows,t.cols,t.nums); printf( -n); for (i=0;it.nums;i+) printf(t%dt%dt%dn,t.datai.r,t.datai.c, t.datai.d); 31 (5) 矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置 對于一個對于一個mn的矩陣的矩陣Amn,其轉(zhuǎn)置矩陣是一個其轉(zhuǎn)置矩陣是一個nm的矩陣。的矩陣。設(shè)為設(shè)為Bnm,滿足滿足ai

22、,j=bj,i,其中其中0im-1,0jn-1。 0009012700030008000000000200060A0700200000008009000003006120000Brcd01605-223-831335740-12429rcd04-1210613324932-850-253732void TranTat(TSMatrix t,TSMatrix &tb) int p,q=0,v; /*q為為tb.data的下標的下標*/ tb.rows=t.cols; tb.cols=t.rows; tb.nums=t.nums; if (t.nums!=0) for (v=0;vt.co

23、ls;v+) for (p=0;p(N)?(M):(N) /*矩陣行列較大者矩陣行列較大者*/typedef struct mtxn int row; /*行號行號*/ int col;/*列號列號*/ struct mtxn *right,*down;/*向右和向下的指針向右和向下的指針*/ union int value; struct mtxn *link; tag; MatNode;/*十字鏈表類型定義十字鏈表類型定義*/38 6.3.1 廣義表的定義廣義表的定義廣義表廣義表簡稱表簡稱表，它是線性表的推廣。，它是線性表的推廣。一個廣義表是一個廣義表是n(n0)個元素的一個序列，若個元素

24、的一個序列，若n=0時時則稱為空表。則稱為空表。設(shè)設(shè)ai為廣義表的第為廣義表的第i個元素，則廣義表個元素，則廣義表GL的一般表的一般表示與線性表相同：示與線性表相同： GL=(a1,a2,ai,an)其中其中n表示廣義表的長度，即廣義表中表示廣義表的長度，即廣義表中所含元素的所含元素的個數(shù)個數(shù)，n0。如果如果ai是單個數(shù)據(jù)元素，則是單個數(shù)據(jù)元素，則ai是廣義表是廣義表GL的的原子；原子；如果如果ai是一個廣義表，則是一個廣義表，則ai是廣義表是廣義表GL的的子表。子表。 6.3 廣義表廣義表 39 (1)廣義表中的數(shù)據(jù)元素有相對次序；廣義表中的數(shù)據(jù)元素有相對次序； (2)廣義表的長度定義為廣義

25、表的長度定義為最外層最外層包含元素個數(shù)；包含元素個數(shù)； (3)廣義表的深度定義為所含括弧的重數(shù)。其中，原子的深廣義表的深度定義為所含括弧的重數(shù)。其中，原子的深度為度為0，空表的深度為，空表的深度為1； (4)廣義表可以廣義表可以共享共享；一個廣義表可以為其他廣義表共享；一個廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表；這種共享廣義表稱為再入表； (5)廣義表可以是一個廣義表可以是一個遞歸遞歸的表。一個廣義表可以是自已的的表。一個廣義表可以是自已的子表。這種廣義表稱為遞歸表。子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值，長遞歸表的深度是無窮值，長度是有限值度是有限值； (6)任何一個

26、非空廣義表任何一個非空廣義表GL均可分解為均可分解為表頭表頭head(GL) = a1和和表尾表尾tail(GL) = ( a2,an) 兩部分。兩部分。 廣義表的特性廣義表的特性40我們規(guī)定用小寫字母表示原子，用大寫字母表我們規(guī)定用小寫字母表示原子，用大寫字母表示廣義表的表名。示廣義表的表名。例如：例如： A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c)分別求出上述各表的分別求出上述各表的表頭、表尾、表頭、表尾、深度和長度。深度和長度。 長度：長度：最外層最外層包含元素個數(shù)包含元素個數(shù) 深度：所含括

27、弧的深度：所含括弧的重數(shù)重數(shù)416.3.2 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：不能；不能；分析原因：分析原因： 1）廣義表中的數(shù)據(jù)元素可以具有廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)不同的結(jié)構(gòu)； 2）廣義表可以遞歸，廣義表可以遞歸，很難分配很難分配固定大小的存儲空間固定大小的存儲空間鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)關(guān)鍵是結(jié)點的定義關(guān)鍵是結(jié)點的定義 一類是單個元素結(jié)點，即一類是單個元素結(jié)點，即原子結(jié)點原子結(jié)點 一類是一類是子表結(jié)點子表結(jié)點42 每一個廣義表的鏈式存儲結(jié)構(gòu)都有頭結(jié)點，每一個廣義表的鏈式存儲結(jié)構(gòu)都有頭結(jié)點，且該頭結(jié)點一定是一個表結(jié)點；且該頭結(jié)點一定是一個表結(jié)點； 一個空

28、列表也存在頭結(jié)點，結(jié)點的兩個指針一個空列表也存在頭結(jié)點，結(jié)點的兩個指針域為域為NULL；廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)-子表分析法子表分析法u結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)子表結(jié)點子表結(jié)點tag=1sublistlink原子結(jié)點原子結(jié)點tag=0datalink指向該子表的第指向該子表的第一個結(jié)點一個結(jié)點指向該子表的下指向該子表的下一個結(jié)點一個結(jié)點43廣義表的兩種基本情況廣義表的兩種基本情況 為原子的情況為原子的情況 ： g3 0 a g1 1 g2 1 * * * * * * 第 1 個元素 第 2 個元素 第 n 個元素 空表空表 非空表非空表44例例 1 C=(a,(b,c,d) C a b c d

29、 C a b c d C 1 0 a 1 0 b 0 c 0 d 45例例 2A=( ) B=(e,f) C=(a,(b,c) D=(B,A,C) E=(a,E)1011000111ebca1111ABCDE0a0fw 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)子表結(jié)點子表結(jié)點tag=1hptptag=0atom原子結(jié)點原子結(jié)點廣義表的鏈式存儲結(jié)構(gòu)廣義表的鏈式存儲結(jié)構(gòu) 2 表頭、表尾分析法表頭、表尾分析法 任何一個非空的廣義表都可以分解成表頭和表尾兩任何一個非空的廣義表都可以分解成表頭和表尾兩部分，反之，一對確定的表頭和表尾可唯一確定一部分，反之，一對確定的表頭和表尾可唯一確定一個廣義表個廣義表 表尾是一個列表，表頭可

30、以是原子，也可以是列表表尾是一個列表，表頭可以是原子，也可以是列表廣義表的鏈式存儲結(jié)構(gòu)廣義表的鏈式存儲結(jié)構(gòu) 2B1011111111100001efabc0aCDEAA=( ) B=(e,f) C=(a,(b,c) D=(B,A,C) E=(a,E)練練 習習 畫出下列廣義表的兩種存儲結(jié)構(gòu)圖畫出下列廣義表的兩種存儲結(jié)構(gòu)圖( ),a,(b,(c,d),(e,f)49(1) 求廣義表的長度求廣義表的長度 在廣義表中在廣義表中,同一層次的每個結(jié)點是通過同一層次的每個結(jié)點是通過link域鏈接起來的域鏈接起來的,所以可把它看做是由所以可把它看做是由link域鏈接起來的單鏈表。這樣，求廣義域鏈接起來的單鏈

31、表。這樣，求廣義表的長度就是求單鏈表的長度。表的長度就是求單鏈表的長度。求廣義表長度的非遞歸算法如下：求廣義表長度的非遞歸算法如下： int GLLength(GLNode *g) /g為一個廣義表頭結(jié)點的指針為一個廣義表頭結(jié)點的指針 int n=0; g=g-val.sublist; /g指向廣義表的第一個元素指向廣義表的第一個元素 while (g!=NULL) n+; g=g-link; return n; 6.3.3 廣義表的運算（略）廣義表的運算（略）50對于帶頭結(jié)點的廣義表對于帶頭結(jié)點的廣義表g,廣義表深度的遞歸定義廣義表深度的遞歸定義是它等于所有子表中表的最大深度加是它等于所有子表中表的最大深度加1。若。若g為原子為原子,其深度為其深度為0。求廣義表深度的遞歸模型求廣義表深度的遞歸模型f()如下：如下：f(g)= 0 若若g為原子為原子 1 若若g為空表為空表MAXf(subg)+1 其他情況其他情況,subg為為g的子表的子表 (2) 求廣義表的深度求廣義表的深度51int GLDepth(GLNode *g) /求帶頭結(jié)點的廣義表求帶頭結(jié)點的廣義表g的深度的深度 int max=0,dep; if (g-tag=0) return 0; /為原子時返回為原子時返回0 g=g-val.sub