數(shù)據(jù)結構課件第14講廣義表

數(shù)據(jù)結構第14講第14講廣義表內容提要廣義表的概念廣義表的存儲結構廣義表的基本操作廣義表的概念廣義表廣義表也稱為列表，是線性表的一種擴展，也是數(shù)據(jù)元素的有限序列。記作：LS=(d0,d1,d2,......dn-1)。其中di既可以是單個元素，也可以是廣義表。在線性表中數(shù)據(jù)元素是單個元素，而在廣義表中，元素可以是單個元素,稱為單元素(原子)，也可以是廣義表，稱為廣義表的子表。廣義表的概念廣義表的例子若廣義表不空，則可分成表頭和表尾，反之，一對表頭和表尾可唯一確定廣義表。A=()空表，表長為0；

B=(a,(b,c,d))B的表長為2，兩個元素分別為a和子表（b,c,d)；C=(e)C中只有一個元素e，表長為1；

D=(A,B,C,f)D的表長為4，它的前三個元素A，B，C廣義表,第四個f是單元素；E=(a,E)遞歸表.對非空廣義表：稱第一個元素為L的表頭，其余元素組成的表稱為LS的表尾；B=(a,(b,c,d))表頭：a表尾((b,c,d))

即HEAD（B）=a,TAIL(B)=((b,c,d)),C=(e)表頭：e表尾()D=(A,B,C,f)表頭：A表尾(B,C,f)運算可以嵌套，如：HEAD（TAIL（B））=b,TAIL(TAIL(B))=(c,d)。廣義表的存儲結構由于廣義表中數(shù)據(jù)元素可以具有不同結構，故難以用順序結構表示廣義表。通常采用鏈表存儲方式。需要兩種結點：一種是表結點，用以表示廣義表；一種是單元素結點，用以表示單元素（原子）。廣義表的存儲結構頭尾表示法typedefenum{ATOM,LIST}Elemtag;/*ATOM=0：單元素；LIST=1：子表*/typedefstructGLNode{Elemtagtag;/*標志域，用于區(qū)分元素結點和表結點*/union{/*元素結點和表結點的聯(lián)合部分*/datatypedata;/*data是元素結點的值域*/struct{structGLNode*hp,*tp}ptr;/*ptr是表結點的指針域，ptr.hp和ptr.tp分別*//*指向表頭和表尾*/};}*GList;/*廣義表類型*/Tag=1hptpTag=0atom表結點原子結點A=NILB1^0eD1^11^C11^111^0a0b0c0dE11^0a廣義表的存儲結構孩子兄弟表示法TypedefstructGLNode{inttag;//標志域：用于區(qū)分原子結點和表結點

union{intatom;//原子結點的值域

structGLNode*hp;//表結點的表頭指針域，

};structGLNode*tp;//指向下一個元素的指針

}*GList;廣義表的存儲結構示例A=（）,B=(a,(b,c,d))C=(e),D=(A,B,C,f)E=(a,E)∧1A∧∧1C∧0e0∧B110c∧0aD11∧∧0bd∧10∧1fE11∧0a∧0∧B110c∧0aD11∧∧0bd∧10∧1f廣義表的基本操作廣義表是遞歸結構，所以廣義表的許多操作可以用遞歸算法實現(xiàn)。求廣義表的深度

intdepth(NODE*head)

廣義表的深度=1+MAX(depth(αi))depth(αi)的遞歸定義：基本項：

L為空表，depth(αi)=1L為原子結點指針，depth(αi)=0遞歸項：

αi為非空表，depth(L