理工軟件工程考研-數(shù)據(jù)結(jié)構(gòu)

第5章數(shù)組與廣義表第2

頁廣義表（generalizedlist）概念 廣義表是一種不同構(gòu)的線性結(jié)構(gòu)，5.4.1廣義表的定義

LS=(1,2,,n)其中：i

或?yàn)樵?atom)

或?yàn)閺V義表。廣義表基本性質(zhì)1.廣義表是遞歸定義，用廣義表定義廣義表；2.線性表中數(shù)據(jù)元素是單個(gè)元素，而廣義表中的元素既可以是單個(gè)元素（稱為原子atom），也可以是廣義表（稱為廣義表的子表sublist）；3.當(dāng)每個(gè)元素均為原子且類型相同時(shí)，就是線性表。第3

頁廣義表的術(shù)語5.4.1廣義表的定義LS=(1,2,,n)表頭head表名表尾tailn是表長(zhǎng)

表頭：LS的第一個(gè)元素稱為表頭

表尾：其余元素組成的表稱為L(zhǎng)S的表尾 表長(zhǎng)：為最外層包含元素個(gè)數(shù)

深度：所含括弧的重?cái)?shù)。原子的深度為0，空表的深度為

1。第4

頁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)))特點(diǎn)有次序有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享第5

頁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)))表長(zhǎng)：0，深度：1表長(zhǎng)：3，深度：1表長(zhǎng)：2，深度：2表長(zhǎng)：3，深度：3遞歸表共享表E=(a,E)=(a,(a,E))=(a,(a,(a,….)))表長(zhǎng)：2，深度：無限第6

頁5.4.1廣義表的定義廣義表的圖形化表示ABDCeabcdA=(a,(b,A))D=(A,B,C)=((),(e),(a,(b,c,d)

))Aab表長(zhǎng)：3深度：3表長(zhǎng)：2深度：∞深度＝括號(hào)的重?cái)?shù)＝○結(jié)點(diǎn)的層數(shù)用○表示子表，用□表示原子第7

頁 任何一個(gè)非空廣義表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)))=

Tail(((b,c)))=Head(

(b,c)

)=

Tail((b,c))=Head((c))=

Tail((c))=E(F)a((b,c))(b,c)()b(

c

)c()第8

頁練習(xí)：

A=() 表頭：表尾：B=(b,c,d) 表頭：

表尾：

C=(a,(b,c,d)) 表頭：

表尾：D=(A,B,C) 表頭：

表尾：線性表的深度：5.4.1

廣義表的定義無()b(c,d)a((b,c,d))A

(B,C)1第9

頁練習(xí)：5.4.1

廣義表的定義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)))

)

＝

;(b)(a,b)5.GetTail(

(e))＝

.6.GetHead((()))＝

.7.GetTail((()))

＝

.()(a,b)()()((c,d))(k,p,h)第10

頁廣義表的基本操作教材P1071）創(chuàng)建空的廣義表L；

2）銷毀廣義表L；

3）已有廣義表L，由L復(fù)制得到廣義表T；

4）求廣義表L的長(zhǎng)度；

5）求廣義表L的深度；

6）判廣義表L是否為空；

7）取廣義表L的表頭；

8）取廣義表L的表尾；

9）在L中插入元素作為L(zhǎng)的第一個(gè)元素；

10）刪除廣義表L的第一個(gè)元素，并e用返回其值；

11）遍歷廣義表L，用函數(shù)visit()處理每個(gè)元素；5.4.1

廣義表的定義第11

頁 廣義表中的數(shù)據(jù)元素可能為原子或子表，由此需要兩種結(jié)點(diǎn)：

表結(jié)點(diǎn)：用以表示廣義表；

原子結(jié)點(diǎn)：用以表示原子。5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)tagptr表結(jié)點(diǎn)1

hptpdata0tagatom原子結(jié)點(diǎn)鏈表存儲(chǔ)方式：頭尾鏈表存儲(chǔ)第12

頁結(jié)點(diǎn)的類型定義Typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子，LIST==1:子表TypedefstructGLNode{ElemTagtag;

//公共部分：標(biāo)志域

union{AtomType

atom;//原子結(jié)點(diǎn)的值域struct{structGLNode*hp,*tp;}

ptr;

//表結(jié)點(diǎn)指針域：ptr.hp指表頭，ptr.tp指表尾

};}*Glist;5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)tagptr表結(jié)點(diǎn)1

hptpdata0tagatom原子結(jié)點(diǎn)第13

頁頭尾鏈表存儲(chǔ)5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)若表頭為原子，則為空表

ls=NULL非空表lstag=1指向表頭的指針指向表尾的指針tag=0data否則，依次類推。第14

頁廣義表(α1,α2…αn)的兩種分解方法5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)廣義表：表頭+表尾廣義表L=(α1,α2…αn)

表頭:α1

表尾:(α2,

…,αn)廣義表L=(α1,α2…αn)

子表:α1α2α3…αn

廣義表：子表1+子表2+···+子表n

第15

頁頭尾表構(gòu)造法5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)L=(a,(b,c),((d)))1L0a

111111a((b,c),((d)))

(b,c)b(c)c(((d)))((d))

(d)d0b

0c

0d第16

頁

bc子表構(gòu)造法5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)L=(a,(b,c),((d)))

a(b,c)((d))1L1111

(d)11

d0a0b0c0d第17

頁廣義表存儲(chǔ)方式5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)A=()

B=(e)C=(a,(b,c,d))D=(A,B,C)A=NULL∧1B0eD11∧1∧a((b,c,d))(b,c,d)b(c,d)c(d)d()C1∧111∧0a0b0c0d()1E=(a,E)E11∧0a第18

頁 又稱為孩子兄弟鏈表。表頭為孩子，與本元素同層的下一個(gè)元素為兄弟。5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)鏈表存儲(chǔ)方式：擴(kuò)展線性鏈表存儲(chǔ)tag表結(jié)點(diǎn)1

hptp

datatp0tagatom原子結(jié)點(diǎn)tag=1指向孩子結(jié)點(diǎn)指向兄弟結(jié)點(diǎn)第19

頁結(jié)點(diǎn)的類型定義Typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子，LIST==1:子表TypedefstructGLNode{ElemTagtag;

//公共部分：標(biāo)志域

union{AtomType

atom;//原子結(jié)點(diǎn)的值域structGLNode*hp;//表結(jié)點(diǎn)的表頭指針

};structGLNode*tp;//指向下一個(gè)元素結(jié)點(diǎn)}*Glist;5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)tag表結(jié)點(diǎn)1

hptp

datatp0tagatom原子結(jié)點(diǎn)第20

頁

bc擴(kuò)展線性鏈表存儲(chǔ)5.4.2

廣義表的存儲(chǔ)結(jié)構(gòu)A=()L=(a,(b,c),((d)))

a(b,c)((d))1L1

(d)11

d0a0b0c0d∧1A∧第21

頁廣義表是遞歸結(jié)構(gòu)，所以廣義表的許多操作可以用遞歸算法實(shí)現(xiàn)。5.4.3

廣義表操作的實(shí)現(xiàn)遞歸函數(shù)一個(gè)含有直接或間接調(diào)用函數(shù)自身的函數(shù)稱為遞歸函數(shù)，它必須滿足以下兩個(gè)條件：1.在每一次調(diào)用自己時(shí)，必須是（在某種意義上）更接近于解;2.必須有一個(gè)終止條件。第22

頁5.4.3

廣義表操作的實(shí)現(xiàn)遞歸算法的基本思路——分治法

對(duì)于一個(gè)輸入規(guī)模為n

的函數(shù)或問題，用某種方法把輸入分解成k(1<k≤n)個(gè)子集，從而產(chǎn)生k個(gè)子問題，分別求解這k

個(gè)問題，得出k個(gè)問題的子解，再用某種方法把它們組合成原來問題的解。若子問題規(guī)模還相當(dāng)大，則可以反復(fù)使用分治法，直至所分解得到的子問題足夠小，以至可以直接求解為止。第23

頁5.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)

廣義表L的深度=廣義表L中括號(hào)重?cái)?shù)GListDepth(L)=1+MAX(GListDepth(L的元素))

GListDepth(L)例L=(a,(b,c),((d)))

GListDepth((b,c))GListDepth(a)

GListDepth(((d)))=0原子=1線性表=2=3第24

頁5.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)GListDepth(L)的遞歸描述直接求解空表：深度=1

原子：深度=0

分解：將廣義表分解成n個(gè)子表，分別求得每個(gè)子表的深度。組合：廣義表的深度=max{子表的深度}+1第25

頁5.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)((d))

L=(a,(b,c),((d)))的深度(b,c)a1

L111110d

10c

0b

0a

第26

頁5.4.3

廣義表操作的實(shí)現(xiàn)

求廣義表的深度GListDepth(L)

intGListDepth(GListL){//采用頭尾鏈表存儲(chǔ)結(jié)構(gòu)，求廣義表L的深度

if(L==NULL)return1;//空表深度1

if(L->tag==ATOM)return0;//原子深度0

for(max=0,pp=L;pp!=NULL;pp=pp->ptr.tp)

{dep=GListDepth(pp->ptr.hp);if(dep>max)max=dep;

}returnmax+1;}第27

頁5.4.3

廣義表操作的實(shí)現(xiàn)復(fù)制廣義表CopyGList(T,L)1

L111110d

10c

0b

0a

L=(a,(b,c),((d)))表頭表尾第28

頁5.4.3

廣義表操作的實(shí)現(xiàn)voidGListCopy(GList&T,GListL){/*由廣義表L復(fù)制得到廣義表T*/

if(!L)T=NULL;

//復(fù)制空表

else

{T=(GList)malloc(sizeof(GLNode));//建表結(jié)點(diǎn)if(!T)exit(OVERFLOW);T->tag=L->tag;

if(L->tag==ATOM)T->data=L->data;//原子

else{GListCopy(T->ptr.hp,L->ptr.hp);//復(fù)制hpGListCopy(T->ptr.tp,L->ptr.tp);//復(fù)制tp

}

}}第29

頁5.4.3

廣義表操作的實(shí)現(xiàn)建立廣義表輸入：字符串(1,2,,n)結(jié)果:建立廣義表的頭尾鏈表分解：將廣義表分解成n個(gè)子表1,2,,n，分別建立1,2,,n

對(duì)應(yīng)的子表。直接求解：空表:NULL

原子:建立原子結(jié)點(diǎn)

組合：將n個(gè)子表組合成一個(gè)廣義表第30

頁5.4.3

廣義表操作的實(shí)現(xiàn)建立廣義表p115子表和廣義表的關(guān)系相鄰兩個(gè)子表之間的關(guān)系((d))(b,c)a子表1

L111110d

10c

0b

0a

第31

頁5.4.3

廣義表操作的實(shí)現(xiàn)voidCreateGList(GList&L,charstr[]){if(strcmp(str,"()")==0)L=NULL;//空表

else

{

if(strlen(str)==1){//建原子結(jié)點(diǎn)

L=(GList)malloc(sizeof(GLNode));L->tag=ATOM;L->atom=str[0];

}else{

//非空表，建表結(jié)點(diǎn)

L=(GList)malloc(sizeof(GLNode));L->tag=LIST; p=L;SubString(sub,str,2,strlen(str)-2);//脫外括號(hào)

由sub中所含n個(gè)子串建立n個(gè)子表;

}

}

//else}//CreateGList第32

頁5.4.3

廣義表操作的實(shí)現(xiàn)do{//由sub中所含n個(gè)子串建立n個(gè)子表

sever(sub,hsub);//分離出子表串hsub=i

CreateGList(p->ptr.hp,hsub);

//建hsub對(duì)應(yīng)的子表

if(!strempty(sub))

{

//建下一個(gè)子表的表結(jié)點(diǎn)

p->ptr.tp=(GList)malloc(sizeof(GLNode));p->tag=LIST;p=p->ptr.tp;

}//if}while(!strempty(sub));p->ptr.tp=NULL;//最后一個(gè)子表的表結(jié)點(diǎn)第33

頁5.4.3

廣義表操作的實(shí)現(xiàn)刪除廣義表中所有元素為x的原子結(jié)點(diǎn)分析：

比較廣義表和線性表的結(jié)構(gòu)特點(diǎn)。相似處：都是鏈表結(jié)構(gòu)。不同處：1)廣義表的數(shù)據(jù)元素可能還是個(gè)廣義表；

2)刪除時(shí)，不僅要?jiǎng)h除原子結(jié)點(diǎn)，還需要?jiǎng)h除相應(yīng)的表結(jié)點(diǎn)。第34

頁5.4.3

廣義表操作的實(shí)現(xiàn)voidDelete_GL(Glist&L,AtomTypex){//刪除廣義表L中所有值為x的原子結(jié)點(diǎn)

if(L){head=L->ptr.hp;//考察第一個(gè)子表

if((head->tag==Atom)&&(head->atom==x)){...}//刪除原子項(xiàng)x的情況

else{...}//第一項(xiàng)沒有被刪除的情況

}}//Delete_GL程序架構(gòu)第35

頁5.4.3

廣義表操作的實(shí)現(xiàn)voidDelete_GL(Glist&L,AtomTypex)p=L;L=L->ptr.tp;//修改指針free(head);//釋放原子結(jié)點(diǎn)free(p);//釋放表結(jié)點(diǎn)Delete_GL(L,x);

//遞歸處理剩余表項(xiàng)

1L0x

1pL

head第36

頁5.4.3

廣義表操作的實(shí)現(xiàn)voidDelete_GL(Glist&L,AtomTypex)if(head->tag==LIST)//該項(xiàng)為廣義表

Delete_GL(head,x);Delete_GL(L->ptr.tp,x);

//遞歸處理剩余表項(xiàng)

1L0a

1

1headL->ptr.tp第37

頁5.4.3

廣義表操作的實(shí)現(xiàn)voidInitGList(GList&L){ L=NULL;}voidDestroyGList(GList&L){ if(!L)return; if(L->tag==LIST){ DestroyGList(L->ptr.hp); DestroyGList(L->ptr.tp); } free(L); L=NULL;}第38

頁5.4.3

廣義表操作的實(shí)現(xiàn)intGListLength(GListL){if(L) return(1+GListLength(L->ptr.tp));else return0;}intGListDepth(GListL){ if(!L)return1; if(L->tag==ATOM) return0; dh=GListDepth(L->ptr.hp)+1; dt=GListDepth(L->ptr.tp); return((dh>dt)?dh:dt);}第39

頁5.4.3

廣義表操作的實(shí)現(xiàn)StatusInsertFirst_GL(GList&L,GListe){ p=(GList)malloc(sizeof(GLNode)); if(!p)exit(OVERFLOW); p->tag=LIST; p->ptr.hp=e; p->ptr.tp=L; L=p; returnOK;}第40

頁5.4.3

廣義表操作的實(shí)現(xiàn)StatusDeleteFirst_GL(GList&L,GList&e){ if(!L)returnERROR; p=