數(shù)據(jù)結(jié)構(gòu)課件：第5章 數(shù)組與廣義表

1、第5章 數(shù)組與廣義表第 2 頁5.1 數(shù)組的概念數(shù)量固定，數(shù)據(jù)類型相同的（變量）元素組合在一起。使用一個名稱代表它。這個名稱就是數(shù)組名。如果要訪問其中某個元素(變量)，可以使用元素的索引值(下標)來訪問它。在C語言中，數(shù)組元素的索引值從0開始。 int A3010; int Ac1.d1, c2.d2 一般情況：子界類型第 3 頁5.1 數(shù)組的概念數(shù)組的邏輯結(jié)構(gòu)1. 線性結(jié)構(gòu)擴展AMN=a0 0 a0 1 a0 N-1a1 0 a1 1 a1 N-1aM-1 0 aM-1 1 aM-1 N-1 A=(A0，A1，AN-1) 其中： Ai=(a0i, a1i, , Am-1i) (0iN-1)二

2、維數(shù)組是數(shù)據(jù)元素為線性表的線性表第 4 頁5.1 數(shù)組的概念數(shù)組的邏輯結(jié)構(gòu)2. 二維數(shù)組中的每個元素都受兩個線性關(guān)系的約束行關(guān)系、列關(guān)系AMN=a0 0 a0 1 a0 N-1a1 0 a1 1 a1 N-1aM-1 0 aM-1 1 aM-1 N-1在行關(guān)系中 aij 直接前趨是 aij-1 aij 直接后繼是 aij+1在列關(guān)系中 aij 直接前趨是 ai-1j aij 直接后繼是 ai+1jN維數(shù)組中的每個元素都受N個線性關(guān)系的約束第 5 頁5.1 數(shù)組的概念數(shù)組的基本操作初始化操作 InitArray(&A,n,bound1,boundn)銷毀操作 DestroyArray(&A)讀元

3、素操作 Value(A,&e,index1,indexn)寫元素操作 Assign(&A,e,index1,indexn) 在高級語言中的典型體現(xiàn)： int AMN; Aij = x; 寫 y = Aij; 讀AMN=a0 0 a0 1 a0 N-1a1 0 a1 1 a1 N-1aM-1 0 aM-1 1 aM-1 N-1第 6 頁5.1 數(shù)組的概念數(shù)組的基本操作1. 讀：給定一組下標，讀出對應的數(shù)組元素；2. 寫：給定一組下標，存儲或修改與其相對應的數(shù)組元素。讀/寫操作本質(zhì)上只對應一種操作尋址。確定指定元素在內(nèi)存中的物理地址。數(shù)組的存儲兩種形式：既可以是順序存儲，也可以采用鏈式結(jié)構(gòu)。第 7

4、 頁5.2 數(shù)組的存儲和實現(xiàn)數(shù)組的存儲結(jié)構(gòu)與尋址一維數(shù)組設具有M個元素的一維數(shù)組的下標范圍為閉區(qū)間 0, M-1，每個數(shù)組元素占用 L 個存儲單元。L a0 ai-1 ai aM-1 a1 Loc(a0)Loc(ai)ai 的存儲地址：Loc( ai )Loc(a0)iL 第 8 頁5.2 數(shù)組的存儲和實現(xiàn)數(shù)組的存儲結(jié)構(gòu)與尋址二維數(shù)組常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。按列優(yōu)先：先列后行，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。 二維數(shù)組內(nèi) 存二維結(jié)構(gòu)一維結(jié)構(gòu)第 9 頁5.2 數(shù)組的存儲和實現(xiàn)二維數(shù)組按行優(yōu)先（MN）0N

5、-1 0M-1aij前面的元素個數(shù) = 陰影部分的面積= 整行數(shù)每行元素個數(shù) + 本行中aij前面的元素個數(shù)= i Nj本行中 aij 前面的元素個數(shù)每行元素個數(shù)整行數(shù)aijLoc(aij) = Loc(a00)( Nij )L第 10 頁5.2 數(shù)組的存儲和實現(xiàn)二維數(shù)組按行優(yōu)先的更一般情況l2h2 l1h1aij前面的元素個數(shù) = 陰影部分的面積= 整行數(shù)每行元素個數(shù) + 本行中aij前面的元素個數(shù)= (i -l1)(h2 -l21)(j -l2)aijLoc(aij)Loc(al1 l2) + (i-l1)(h2-l2+1) + (j-l2)L本行中 aij 前面的元素個數(shù)每行元素個數(shù)整行

6、數(shù)第 11 頁5.2 數(shù)組的存儲和實現(xiàn)三維數(shù)組三維數(shù)組：Am1, m2, m3：Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )L 第 12 頁5.2 數(shù)組的存儲和實現(xiàn)N維數(shù)組一般的N維數(shù)組：Ab1, b2, , bn： Loc( j1, j2, , jn ) = Loc(0, 0, , 0) + ci ji其中：cn=L，ci-1 =bici，1in。ni=1數(shù)組基址Ci為常數(shù)第 13 頁5.2 數(shù)組的存儲和實現(xiàn)二維數(shù)組靜態(tài)數(shù)組表示法typedef ElemType Arraym*n; Array A; Amn=a0 0 a0 1 a0 n-1a1 0

7、a1 1 a1 n-1 am-1 0 am-1 1 am-1 n-1a00.a0n-1a10.a1n-1.am-1 0.am-1 n-1第 14 頁5.2 數(shù)組的存儲和實現(xiàn)數(shù)組的動態(tài)表示法typedef struct ElemType *base; / 動態(tài)空間基址 int dim; / 數(shù)組維數(shù) int *bound； / 維界基址 int *constants; / 數(shù)組映像函數(shù)常量基址 Array;A.baseA.dimA.boundsA.constantsb1 b2 b3c1 c2 c3a000 a0013Ab1b2b3第 15 頁5.3 矩陣的壓縮存儲 為了節(jié)省存儲空間，時常會對某些

8、矩陣進行壓縮存儲。所謂壓縮存儲：1）對多個值相同的元只分配一個存儲空間；2）對零元不分配存儲空間。5.3.1 特殊矩陣的壓縮存儲5.3.2 稀疏矩陣的壓縮存儲第 16 頁5.3.1 特殊矩陣 值相同元素或者非零元素的分布有一定規(guī)律的矩陣，稱為特殊矩陣。 對稱矩陣、 上（下）三角矩陣。a11 a12 a1na21 a22 a2n am1 am2 amna11 a12 a1n0 a22 a2n 0 0 amn第 17 頁5.3.1 特殊矩陣對稱矩陣/上（下）三角矩陣用一維數(shù)組，按行優(yōu)先存儲下三角元素。a11 a12 a13 a14 a1na21 a22 a23 a24 a2na31 a32 a33

9、 a34 a3nan1 an2 an3 an4 anna11 a21 a22 a31 a32 a33 an1 an2 ann 0 1 2 3 4 5 n(n+1)/2-1k =i(i-1)/2+j-1 當 i jj(j-1)/2+i-1 當 i j性質(zhì)：aij = aji 1i, jn對于下標i, j，線性地址第 18 頁5.3.2 稀疏矩陣 含有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。 討論含有較多零元素的稀疏矩陣的壓縮存儲。M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0

10、0 0 18 0 0 0 0 015 0 0 -7 0 0 0M有42（67）個元素，有8個非零元素如何進行稀疏矩陣的壓縮存儲？第 19 頁5.3.2 稀疏矩陣三元組順序表M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0采用三元組存儲：(行, 列, 值)( (1,2,12),(1,3,9), (3,1,-3),(3,6,14), (4,3,24),(5,2,18), (6,1,15),(6,4,-7) )加上矩陣的行數(shù)和列數(shù)：6,7 第 20 頁5.3.2 稀

11、疏矩陣三元組順序表 #define MAXSIZE 12500 typedef struct int i,j; / 非零元的行下標和列下標 ElemType e; / 非零元值 Triple; typedef struct Triple data MAXSIZE+1 ; / 用于存儲三元組表, data0未用 int mu,nu,tu; / 行數(shù)、列數(shù)和非零元個數(shù) TSMatrix;第 21 頁5.3.2 稀疏矩陣三元組表的順序存儲M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0

12、0 -7 0 0 0i j e12345678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14678 按行（行內(nèi)按列）順序存儲非零元素。第 22 頁5.3.2 稀疏矩陣三元組表的順序存儲轉(zhuǎn)置算法M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0 T = 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0

13、0 0 14 0 0 0 0 0 0 0 0 0 基本算法：交換對應行、列位置上的元素。第 23 頁5.3.2 稀疏矩陣一般矩陣的轉(zhuǎn)置算法 int amn,bmn; for ( i =0; im; +i ) for (j = 0; jn; +j ) b j i = a i j ; 算法的時間復雜度為：O(m*n)第 24 頁5.3.2 稀疏矩陣i j e12345678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 146782 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 1

14、8i j e12345678T.dataT.muT.nuT.tu768第 25 頁5.3.2 稀疏矩陣轉(zhuǎn)置運算算法TransposeSMatrix(TSMatrix M, TSMatrix &T) 基本思想 對 M.data 從頭至尾掃描： 第一次掃描時，將 M.data 中列號為 1 的三元組賦值到 T.data 中； 第二次掃描時，將 M.data 中列號為 2 的三元組賦值到T.data中； 依此類推，直至將 M.data 所有三元組賦值到T.data 中。第 26 頁1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j vi j v3 1

15、 -32 5 181 3 -36 1 151 6 151 2 122 1 125 2 181 3 93 1 94 3 243 4 246 4 -74 6 -73 6 146 3 14M.dataT.data第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素5.3.2 稀疏矩陣第七次掃描查找第7列元素三元組表的順序存儲轉(zhuǎn)置算法第 27 頁5.3.2 稀疏矩陣Status TranMatrix( TSMatrix M, TSMatrix &T ) T.mu=M.nu; T.nu

16、=M.mu; T.tu=M.tu; if ( T.tu ) / 非零元素個數(shù)!=0 q=1; / q為當前三元組在T.data 存儲位置(下標) for ( col=1; col=M.nu; +col ) for (p=1;p=M.tu;+p) /p為掃描M.data指示器 if ( M.datap.j= =col ) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +q; / if return OK; / TranMtrix算法的時間復雜度：O(nu*tu)第 28 頁5.3.2 稀疏矩陣時間復雜度分

17、析轉(zhuǎn)置算法 TranMatrix 的時間復雜度為O(nutu) 當非零元的個數(shù)tu和矩陣元素個數(shù) munu 同數(shù)量級時，轉(zhuǎn)置運算算法的時間復雜度為 O(nu munu)算法一般用于 tu munu 的情況第 29 頁5.3.2 稀疏矩陣提高算法效率numcol：存儲M第 col 列非零元個數(shù)cpotcol：存儲M第 col 列第一個非零元在T.data 中的位置1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j vM.datacpotcol的計算方法： cpot1 = 1 cpotcol = cpotcol-1 + numcol-1 2 col

18、 ncolnumcolcpotcol1 2 3 4 5 6 7 22811012785309第 30 頁5.3.2 稀疏矩陣第3列第二個非零元在b中的位置1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7colnumcolcpotcol1 2 3 4 5 6 7 228110135278M.dataT.data1 2 122 1 12第2列第一個非零元在b中的位置1 3 9第3列第一個非零元在b中的位置3 1 93 1 -31 3 -33 6 146 3 144 3 243 4 245 2 182 5 186 1 151 6 156 4 -74 6

19、-74第2列第二個非零元在b中的位置65第4列第二個非零元在b中的位置第1列第一個非零元在b中的位置2793第6列第一個非零元在b中的位置掃描M.data實現(xiàn)M到T 的轉(zhuǎn)置809第 31 頁5.3.2 稀疏矩陣Status FastTransMatrix(TSMatrix M, TSMatrix &T) /采用三元組順序表存儲稀疏矩陣，求M的轉(zhuǎn)置矩陣T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if ( T.tu ) for ( col=1; col=M.nu; +col ) numcol=0; / 求M中每一列非零元個數(shù) for ( t=1; t=M.tu; +t )

20、 + num M.datat.j ; /求第 col列中第一個非零元在T.data中的序號 cpot1 = 1; for ( col=2; col=M.nu; +col ) cpotcol = cpotcol-1 + numcol-1;第 32 頁5.3.2 稀疏矩陣 for ( p=1; pM.tu; +p ) col = M.data p .j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; + cpot col ; / for / if return OK; / Fast

21、TranMatrix時間復雜度分析算法中有四個并列的單循環(huán)，循環(huán)次數(shù)分別為 nu、tu、nu 和 tu，時間復雜度為：O(nu+tu)第 33 頁5.3.2 稀疏矩陣 行邏輯鏈接順序表 #define MAXMN 500 typedef struct Triple data MAXSIZE+1 ; int rposMAXMN+1; / 每行第一個元素的位置表 int mu, nu, tu; RLSMatrix; 1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7123456M.rpos M.muM.nuM.tu678103567第 34 頁5.3.2

22、 稀疏矩陣例：給定一組下標，求矩陣指定元素的值ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while ( M.datap.i=r & M.datap.j c ) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; else return 0; /value第 35 頁5.3.2 稀疏矩陣 稀疏矩陣的鏈式存儲十字鏈表 采用鏈式存儲結(jié)構(gòu)存儲三元組表，每個非零元素對應的三元組存儲為一個鏈表結(jié)點：rowcolitemdownrightrow： 存儲非零元素的行號col： 存儲非零元素

23、的列號item： 存儲非零元素的值right： 指針域，指向同一行中的下一個三元組down：指針域，指向同一列中的下一個三元組第 36 頁5.3.2 稀疏矩陣 稀疏矩陣的鏈式存儲十字鏈表3 0 0 50 -1 0 02 0 0 0M=1 1 33 1 22 2 -11 4 5M.cheadM.rhead第 37 頁5.3.2 稀疏矩陣 十字鏈表的類型定義typedef struct OLNode int row, col; / 非零元的行下標和列下標 ElemType e; / 非零元值 struct OLNode * right, * down OLNode,OLink;typedef st

24、ruct OLink *rhead,*chead; / 行/列表頭指針數(shù)組 int mu, nu, tu; / 行數(shù)、列數(shù)和非零元個數(shù) CrossList;第 38 頁廣義表(generalized lists)的概念廣義表是一種不同構(gòu)的線性結(jié)構(gòu)，5.4.1 廣義表的定義 LS = ( 1, 2, , n )其中：i 或為原子(atom) 或為廣義表。廣義表的基本性質(zhì) 1. 廣義表的定義是一個遞歸定義，因為在描述廣義表時又用到了廣義表； 2. 在線性表中數(shù)據(jù)元素是單個元素，而在廣義表中， 元素可以是單個元素稱為原子(atom)，也可以是廣義表，稱為廣義表的子表(sublist)； 3. 當每個

25、元素均為原子且類型相同時，就是線性表。第 39 頁廣義表的術(shù)語5.4.1 廣義表的定義LS = ( 1, 2, , n )表頭head表名表尾tailn是表長表頭：LS的第一個元素稱為表頭表尾：其余元素組成的表稱為LS的表尾表長：為最外層包含元素個數(shù) 深度：所含括弧的重數(shù)。原子的深度為 0，“空表”的深度為 1。第 40 頁5.4.1 廣義表的定義例： A = ( ) 空表 B = ( b, c, d ) C = ( a, B ) = ( a, (b,c,d) ) D = ( A, B, C ) = ( ( ), (b,c,d), (a,(b,c,d) )特點有次序有長度有深度可遞歸可共享一個

26、直接前驅(qū)和一個直接后繼表中元素個數(shù)表中括號的重數(shù)自己可以作為自己的子表可以為其他廣義表所共享第 41 頁5.4.1 廣義表的定義例： A = ( ) 空表 B = ( b, c, d ) C = ( a, B ) = ( a, (b,c,d) ) D = ( A, B, C ) = ( ( ), (b,c,d), (a,(b,c,d) )表長：0；深度：1表長：3，深度：1表長：2，深度：2表長：3，深度：3遞歸表共享表E = (a,E) = (a, (a,E) ) = ( a, (a, (a, .) ) )第 42 頁5.4.1 廣義表的定義 廣義表的圖形化表示ABDCeabcdA = (

27、a , (b, A) )D = ( A, B, C ) = ( ( ), (e), ( a, (b,c,d) ) )Aab表長：3深度：3表長：2深度：深度括號的重數(shù) 結(jié)點的層數(shù)用表示子表用表示原子第 43 頁 任何一個非空廣義表 LS = ( 1, 2, , n) 均可分解為 表頭 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n ) 兩部分。5.4.1 廣義表的定義例如：D = ( E, F ) = ( ( a, ( b, c ) )，F(xiàn) )Head( D ) = Tail( D ) = Head( E ) = Tail( E ) = Head( (b, c) )

28、 = Tail( (b, c) ) = Head( (b, c) ) = Tail( (b, c) ) = Head( ( c ) ) = Tail( ( c ) ) =E( F )a( (b, c) )(b, c)( )b( c )c( )第 44 頁 廣義表的基本操作 教材P107 1） 創(chuàng)建空的廣義表L； 2） 銷毀廣義表L； 3） 已有廣義表L，由L復制得到廣義表T； 4） 求廣義表L的長度； 5） 求廣義表L的深度； 6） 判廣義表L是否為空； 7） 取廣義表L的表頭； 8） 取廣義表L的表尾； 9） 在L中插入元素作為L的第一個元素； 10）刪除廣義表L的第一個元素，并e用返回其值

29、； 11）遍歷廣義表L，用函數(shù)visit( )處理每個元素；5.4.1 廣義表的定義第 45 頁 廣義表中的數(shù)據(jù)元素可能為原子或列表，由此需要兩種結(jié)點： 表結(jié)點：用以表示廣義表； 原子結(jié)點：用以表示原子。5.4.2 廣義表的存儲結(jié)構(gòu) 鏈表存儲： 兩種鏈式存儲形式：根據(jù)廣義表分解方法的不同，其具體實現(xiàn)也有差異。第 46 頁廣義表(1, 2 n)的兩種分解方法：5.4.2 廣義表的存儲結(jié)構(gòu) 廣義表：表頭+表尾 廣義表 L= (1, 2 n) 表頭: 1 表尾: (2 , ,n) 廣義表 L= (1, 2 n) 子表: 1 2 3 n 廣義表：子表1 +子表2 + + 子表n 第 47 頁 結(jié)點的類

30、型定義（頭尾鏈表）Typedef enum ATOM, LIST ElemTag; / ATOM=0:原子，LIST=1: 列表Typedef struct GLNode ElemTag tag; / 標志域 union AtomType atom; / 原子結(jié)點的值域 struct struct GLNode *hp,*tp; ptr; / 表結(jié)點的指針域：ptr.hp指表頭，ptr.tp指表尾 ; * Glist;5.4.2 廣義表的存儲結(jié)構(gòu)tag ptr表結(jié)點1 hp tp data0 tag atom原子結(jié)點第 48 頁 廣義表頭尾存儲方式的實現(xiàn)：5.4.2 廣義表的存儲結(jié)構(gòu)若表頭為原

31、子，則為空表 ls=NULL非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否則，依次類推。tag=1 第 49 頁 頭尾表構(gòu)造法5.4.2 廣義表的存儲結(jié)構(gòu)L = (a , ( b, c ) , ( ( d ) ) )1 L0 a 1 1 1 1 1 1 a( ( b, c ) , ( ( d ) ) ) ( b, c )b( c )c( ( ( d ) ) )( ( d ) ) ( d ) d0 b 0 c 0 d 第 50 頁 廣義表存儲方式練習（頭尾法）：5.4.2 廣義表的存儲結(jié)構(gòu)A = ( ) B = (e) C = (a, (b,c,d) ) D = (A

32、, B, C)A=NULL1B0eD1111Aa(b,c,d)(b,c,d)b(c,d)c(d)d( )C11110a0b0c0d1？第 51 頁 結(jié)點的類型定義（子表鏈表）Typedef enum ATOM, LIST ElemTag; / ATOM=0:原子，LIST=1: 列表Typedef struct GLNode ElemTag tag; / 標志域 union AtomType atom; / 原子結(jié)點的值域 struct GLNode *hp; /表節(jié)點的表頭指針 ; struct GLNode *tp; /指向下一個元素結(jié)點 * Glist;5.4.2 廣義表的存儲結(jié)構(gòu)tag

33、 表結(jié)點1 hp tp data0 tag atom原子結(jié)點tp第 52 頁 b c 子表構(gòu)造法5.4.2 廣義表的存儲結(jié)構(gòu)L = (a , ( b, c ) , ( ( d ) ) ) a ( b, c ) ( ( d ) ) 1 L1 ( d ) 1 1 d 0 a 0 b 0 c 0 d 第 53 頁 廣義表是遞歸結(jié)構(gòu)，所以廣義表的許多操作可以用遞歸算法實現(xiàn)。5.4.3 廣義表操作的實現(xiàn) 遞歸函數(shù) 一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個條件： 1. 在每一次調(diào)用自己時，必須是（在某種意義上）更接近于解; 2. 必須有一個終止條件。第 54 頁5.4.3

34、廣義表操作的實現(xiàn) 遞歸算法的基本思路分治法 對于一個輸入規(guī)模為 n 的函數(shù)或問題，用某種方法把輸入分解成 k(1tag=ATOM ) return 0; / 原子深度0 for ( max=0, pp=L; pp; pp=pp-ptr.tp ) dep = GListDepth( pp-ptr.hp ); if ( depmax ) max = dep; return max+1;第 59 頁5.4.3 廣義表操作的實現(xiàn) 復制廣義表 CopyGList(T,L)1 L1 1 1 1 1 0 d 1 0 c 0 b 0 a L = ( a , ( b ,c ) , ( ( d ) ) )表頭表尾

35、第 60 頁5.4.3 廣義表操作的實現(xiàn)void GListCopy( GList &T, GList L ) /*由廣義表L復制得到廣義表T */ if ( !L ) T=NULL; / 復制空表 else T=(GList) malloc( sizeof(GLNode) ); / 建表結(jié)點 if ( !T ) exit(OVERFLOW); T-tag = L-tag; if ( L-tag=ATOM ) T-data = L-data; / 原子 else GListCopy( T-ptr.hp, L-ptr.hp ); / 復制hp GListCopy( T-ptr.tp, L-ptr

36、.tp ); / 復制tp 第 61 頁5.4.3 廣義表操作的實現(xiàn) 建立廣義表輸入：字符串 (1, 2, , n )結(jié)果: 建立廣義表的鏈表分解：將廣義表分解成 n個子表1,2,n，分別建立 1, 2, , n 對應的子表。直接求解： 空表: NULL 原子: 建立原子結(jié)點 組合：將 n 個子表組合成一個廣義表第 62 頁5.4.3 廣義表操作的實現(xiàn) 建立廣義表子表和廣義表的關(guān)系相鄰兩個子表之間的關(guān)系( ( d ) )( b ,c )a子表1 L1 1 1 1 1 0 d 1 0 c 0 b 0 a 第 63 頁5.4.3 廣義表操作的實現(xiàn)void CreateGList( GList &L

37、, char str ) if ( strcmp( str,()“ )=0) L=NULL; /空表 else /非空表 L=(GList)malloc(sizeof(GLNode); L-tag=LIST； p=L; /p始終指向新建節(jié)點 SubString(sub,str,2,strlen(str)-2); /脫外層括號 do 由sub中所含n個子串重復建立n個子表; while(!StrEmpty(sub); p-ptr.tp=NULL; /表尾為空，結(jié)束 / else / CreateGList第 64 頁5.4.3 廣義表操作的實現(xiàn)do /由sub中所含n個子串建立n個子表 seve

38、r( sub, hsub ); /分離出子表串hsub=i if(StrLength(hsub)=1) /建原子結(jié)點 p-ptr.hp= (GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-prt.hp-atom=hsub; else /遞歸建子表 CreateGList( p-ptr.hp, hsub ); if ( !strempty(sub) ) /建下一個子表的表結(jié)點 p-ptr.tp = (GList)malloc(sizeof(GLNode); p-ptr.tp-tag = LIST; p = p-ptr.tp; while(!st

39、rempty(sub);第 65 頁5.4.3 廣義表操作的實現(xiàn) 刪除廣義表中所有元素為 x 的原子結(jié)點分析： 比較廣義表和線性表的結(jié)構(gòu)特點。相似處：都是鏈表結(jié)構(gòu)。不同處： 1)廣義表的數(shù)據(jù)元素可能還是個廣義表； 2)刪除時，不僅要刪除原子結(jié)點，還需要刪除相應的表結(jié)點。第 66 頁5.4.3 廣義表操作的實現(xiàn)void Delete_GL( Glist&L, AtomType x ) /刪除廣義表L中所有值為x的原子結(jié)點 if ( L ) head = L-ptr.hp; / 考察第一個子表 if ( ( head-tag = Atom ) & ( head-atom = x ) ) / 刪除原子項 x的情況 else / 第一項沒有被刪除的情況 / Delete_GL第 67 頁5.4.3 廣義表操作的實現(xiàn)void Delete_GL( Glist&L, AtomType x )p=L; L = L-ptr.tp;