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

1、武漢科技大學(xué)Wuhan University of Science and Technology張 凱計(jì)算機(jī)學(xué)院 軟件工程系2021年3月12日;廣義表的定義第第5 5章章 數(shù)組和廣義表數(shù)組和廣義表數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的緊縮存儲(chǔ)廣義表的存儲(chǔ)構(gòu)造;v定義定義5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義廣義表是線性表的推行，也稱(chēng)為列表(lists)記為： LS = ( a1 , a2 , , an ) 廣義表名 第一個(gè)元素是表頭，而其他元素組成的表稱(chēng)為表尾 ai 為原子或廣義表，習(xí)慣上用小寫(xiě)字母表示原子類(lèi)型，用大寫(xiě)字母表示列表n是表長(zhǎng)在廣義表中商定：表頭(Head表尾 (Tail);v討

2、論：廣義表與線性表的區(qū)別和聯(lián)絡(luò)？討論：廣義表與線性表的區(qū)別和聯(lián)絡(luò)？5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義LS = ( a1, a2, . , ai , . , an )ai 為原子或廣義表1.在線性表的定義中，ai 只限于是單個(gè)元素。而在廣義表的定義中，ai 可以是單個(gè)元素，也可是廣義表，分別稱(chēng)為廣義表 LS 的原子類(lèi)型和子表。2.當(dāng)每個(gè)元素都為原子且類(lèi)型一樣時(shí)，就是線性表3.廣義表是遞歸定義的線性構(gòu)造;v廣義表的特點(diǎn)廣義表的特點(diǎn)v有次序性有次序性v有長(zhǎng)度有長(zhǎng)度v有深度有深度v可遞歸可遞歸v可共享可共享5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義;v廣義表的特點(diǎn)廣義表的特點(diǎn)v有次序性有次序性5.

3、4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義廣義表中的數(shù)據(jù)元素有固定的相對(duì)次序一個(gè)直接前驅(qū)和一個(gè)直接后繼;v廣義表的特點(diǎn)廣義表的特點(diǎn)v有長(zhǎng)度有長(zhǎng)度5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義廣義表的長(zhǎng)度定義為最外層括弧中包含的數(shù)據(jù)元素個(gè)數(shù)如: H = (d, (e,( ) 長(zhǎng)度為2表元素個(gè)數(shù)一定，不能無(wú)限，可以是空表;v廣義表的特點(diǎn)廣義表的特點(diǎn)v有深度有深度5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義廣義表的深度定義為廣義表中括弧的最大重?cái)?shù)留意：(1)空表的深度為1； (2)原子不是廣義表，所以沒(méi)有深度可言， 但可以以為它的深度為0。如: H = (d, (e,( )深度為3;v廣義表的特點(diǎn)廣義表的特點(diǎn)v可遞

4、歸可遞歸5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義廣義表可以是一個(gè)遞歸的表如: E = (a, E) = (a, (a, (a, . ,) 遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值深度為無(wú)窮大,長(zhǎng)度為2;v廣義表的特點(diǎn)廣義表的特點(diǎn)v可共享可共享5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義A = ( a , B ) =( a , ( b , c , d ) ) 廣義表的元素可以為其他廣義表所共享;v例例1：求以下廣義表的長(zhǎng)度：求以下廣義表的長(zhǎng)度5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E為遞歸表1A =( )2B = ( e ) 3C =( a ,(

5、 b , c , d ) ) 4D=( A , B ,C )5E=(a, E)n=0，由于A是空表n=1，表中元素e是原子n=2，a 為原子，(b, c, d)為子表n=3，3個(gè)元素都是子表n=2，a 為原子，E為子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表;v試用圖形表示以下廣義表試用圖形表示以下廣義表5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義 設(shè) 代表原子， 代表子表 e D=(A, B, C)=( ( ), (e), ( a, (b, c, d ) ) )的長(zhǎng)度為3，深度為3DABCeabcd;v試用圖形表示以下廣義表試用圖形表示以下廣義表.5.4 廣義表的類(lèi)型定義

6、廣義表的類(lèi)型定義 A=( a , (b, A) )A的長(zhǎng)度為2，深度為ab;v廣義表的的類(lèi)型定義廣義表的的類(lèi)型定義5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義ADT Glist 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：Dei | i=1,2,.,n; n0; ei AtomSet或或ei Glist AtomSet為某個(gè)數(shù)據(jù)對(duì)為某個(gè)數(shù)據(jù)對(duì)象象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：LR| ei-1 ,ei D, 2in 根本操作：根本操作： InitGList(&L); /創(chuàng)建空的廣義表創(chuàng)建空的廣義表L。 DestroyGList(&L) /銷(xiāo)毀廣義表銷(xiāo)毀廣義表L。 CreateGList(&L, S) /由串

7、由串S創(chuàng)建廣義表創(chuàng)建廣義表L。 CopyGList(&T, L) / 由廣義表由廣義表L復(fù)制得到廣義表復(fù)制得到廣義表T。 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L) InsertFirst_GL(&L, e); /插入元素插入元素e作為廣義表作為廣義表L的第一元素。的第一元素。 DeleteFirst_GL(&L, &e) /刪除廣義表刪除廣義表L的第一元素，并用的第一元素，并用e前往其值。前往其值。ADT Glist;v廣義表的的類(lèi)型定義廣義表的的類(lèi)型定義5.4 廣義

8、表的類(lèi)型定義廣義表的類(lèi)型定義引見(jiàn)兩種特殊的根本操作：GetHead(L) 取表頭 (能夠是原子或列表);GetTail(L) 取表尾 (一定是列表) 。;v例：求以下廣義表操作的結(jié)果例：求以下廣義表操作的結(jié)果5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義1. GetTail (b, k, p, h) ; 2. GetHead ( (a, b), (c, d) ) ; 3. GetTail ( (a, b), (c, d) ) ; 4. GetTail GetHead(a, b),(c, d) ;(k, p, h)( b )(a, b)5. GetTail (e) ; 6. GetHead ( ( )

9、 ) .7. GetTail ( ( ) ) .( )(a, b)( )( )(c, d);v留意：留意：( )和和( ( ) )的區(qū)別的區(qū)別5.4 廣義表的類(lèi)型定義廣義表的類(lèi)型定義前者為空表，長(zhǎng)度=0，深度=1；后者長(zhǎng)度=1，深度=2，表頭、表尾均為( );v廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造 由于廣義表( a1, a2, ., an )是一種遞歸的數(shù)據(jù)構(gòu)造，且其中的數(shù)據(jù)元素可以具有不同的構(gòu)造或是原子，或是列表，因此難以用順序存儲(chǔ)構(gòu)造表示，通常采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，每個(gè)數(shù)據(jù)元素可用一個(gè)結(jié)點(diǎn)表示。;v如何設(shè)定結(jié)點(diǎn)的構(gòu)造？如何設(shè)定結(jié)點(diǎn)的構(gòu)造？5.5 廣義表的存儲(chǔ)

10、構(gòu)造廣義表的存儲(chǔ)構(gòu)造方式一：表頭表尾鏈 在一個(gè)廣義表中，其數(shù)據(jù)元素有原子和列表之分，所以在對(duì)應(yīng)的存儲(chǔ)構(gòu)造中，其存儲(chǔ)結(jié)點(diǎn)也有相應(yīng)劃分。 對(duì)于原子結(jié)點(diǎn)，應(yīng)包含值域； 對(duì)于表結(jié)點(diǎn)，應(yīng)包含指示表頭的表頭指針域(指向表中的第一個(gè)元素)和指示表尾的表尾指針域(指向除去原表頭元素后的廣義表)。;v如何設(shè)定結(jié)點(diǎn)的構(gòu)造？如何設(shè)定結(jié)點(diǎn)的構(gòu)造？5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造 為了把原子結(jié)點(diǎn)和表結(jié)點(diǎn)區(qū)分開(kāi)，還必需在每個(gè)結(jié)點(diǎn)中增設(shè)一個(gè)標(biāo)志域，讓標(biāo)志域取兩種不同的值，從而區(qū)分不同的結(jié)點(diǎn)。tag=0atomtag=1headptailp原子結(jié)點(diǎn)表結(jié)點(diǎn);v結(jié)點(diǎn)構(gòu)造結(jié)點(diǎn)構(gòu)造5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造Ty

11、pedef enum ATOM, LIST Elemtag; /ATOM = = 0 ：原子：原子 LIST = = 1 ：子表：子表Typedef struct GLNode Elemtag tag; /標(biāo)志域標(biāo)志域 ；公共部分；公共部分,區(qū)分原子和表結(jié)點(diǎn)區(qū)分原子和表結(jié)點(diǎn) union /原子結(jié)點(diǎn)和表結(jié)點(diǎn)的結(jié)合部分原子結(jié)點(diǎn)和表結(jié)點(diǎn)的結(jié)合部分 AtomType atom; /atom是原子結(jié)點(diǎn)的值域，是原子結(jié)點(diǎn)的值域，AtomType由用戶定由用戶定義義 struct struct GLNode *hp,*tp; ptr; /ptr是表結(jié)點(diǎn)的指針域，是表結(jié)點(diǎn)的指針域，ptr.hp、ptr.tp分

12、別指分別指 /向表頭和表尾向表頭和表尾 ;*Glist ; ;例：A = ( ) B = ( e ) C = ( a , ( b , c , d ) ) D = ( A , B , C ) E = ( a , E )BACDE1e0a01b0c0d0a01111111111;5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造C = ( a , ( b , c , d ) ) a01b0c0d01111C;v如何設(shè)定結(jié)點(diǎn)的構(gòu)造如何設(shè)定結(jié)點(diǎn)的構(gòu)造v最上層的表結(jié)點(diǎn)數(shù)即為廣義表的長(zhǎng)度最上層的表結(jié)點(diǎn)數(shù)即為廣義表的長(zhǎng)度v層次清楚層次清楚v結(jié)點(diǎn)眾多，與廣義表括號(hào)不匹配，不容結(jié)點(diǎn)眾多，與廣義表括號(hào)不匹配，不容易復(fù)原廣義

13、表易復(fù)原廣義表5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造;v如何設(shè)定結(jié)點(diǎn)的構(gòu)造如何設(shè)定結(jié)點(diǎn)的構(gòu)造5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造方式二：同層結(jié)點(diǎn)鏈 對(duì)于原子結(jié)點(diǎn)，應(yīng)包含值域和指向其后繼結(jié)點(diǎn)的指針域 對(duì)于表結(jié)點(diǎn)，應(yīng)包含指向表中第一個(gè)結(jié)點(diǎn)的表頭指針域和指向其后繼結(jié)點(diǎn)的指針域 ;v如何設(shè)定結(jié)點(diǎn)的構(gòu)造如何設(shè)定結(jié)點(diǎn)的構(gòu)造5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造 為了把原子結(jié)點(diǎn)和表結(jié)點(diǎn)區(qū)分開(kāi)，還必需在每個(gè)結(jié)點(diǎn)中增設(shè)一個(gè)標(biāo)志域，讓標(biāo)志域取兩種不同的值，從而區(qū)分不同的結(jié)點(diǎn)tag=1headpLp原子結(jié)點(diǎn)表結(jié)點(diǎn)tag=0atomtp;v結(jié)點(diǎn)構(gòu)造結(jié)點(diǎn)構(gòu)造5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造Typedef

14、 enum ATOM,LIST Elemtag; /ATOM = = 0 ; 原子原子 LIST = = 1 ; 子表子表Typedef struct GLNode Elemtag tag; /標(biāo)志域標(biāo)志域 ；公共部分；公共部分,區(qū)分原子和表結(jié)點(diǎn)區(qū)分原子和表結(jié)點(diǎn) union /原子結(jié)點(diǎn)和表結(jié)點(diǎn)的結(jié)合部分原子結(jié)點(diǎn)和表結(jié)點(diǎn)的結(jié)合部分 AtomType atom; /atom是原子結(jié)點(diǎn)的值域，是原子結(jié)點(diǎn)的值域，AtomType由用戶定義由用戶定義 struct GLNode *hp /表結(jié)點(diǎn)的表頭指針表結(jié)點(diǎn)的表頭指針 ； struct GLNode *tp /相當(dāng)于線性鏈表的相當(dāng)于線性鏈表的next，指向下一個(gè)元素結(jié)點(diǎn)，指向下一個(gè)元素結(jié)點(diǎn);*Glist;BDE1a0b0111c0d0Ae0C11111a01表頭指針域:指向表中第一個(gè)結(jié)點(diǎn)例：A = ( ) B = ( e ) C = ( a , ( b , c , d ) ) D = ( A , B , C ) E = ( a , E );5.5 廣義表的存儲(chǔ)構(gòu)造廣義表的存儲(chǔ)構(gòu)造C = ( a , ( b , c , d ) ) a0b01c0d0C1;v如何設(shè)定結(jié)點(diǎn)的構(gòu)造如何設(shè)定結(jié)點(diǎn)的構(gòu)造v結(jié)點(diǎn)數(shù)目與廣義表括號(hào)對(duì)一致結(jié)點(diǎn)數(shù)目與廣義表括號(hào)對(duì)一致v遞歸算法不方便遞歸算法不方便5.5 廣義表的存儲(chǔ)構(gòu)造廣義