数据结构课件第14讲广义表

数据结构第14讲第14讲广义表内容提要广义表的概念广义表的存储结构广义表的基本操作广义表的概念广义表广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。记作：LS=(d0,d1,d2,......dn-1)。其中di既可以是单个元素，也可以是广义表。在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素,称为单元素(原子)，也可以是广义表，称为广义表的子表。广义表的概念广义表的例子若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。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)。广义表的存储结构由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采用链表存储方式。需要两种结点：一种是表结点，用以表示广义表；一种是单元素结点，用以表示单元素（原子）。广义表的存储结构头尾表示法typedefenum{ATOM,LIST}Elemtag;/*ATOM=0：单元素；LIST=1：子表*/typedefstructGLNode{Elemtagtag;/*标志域，用于区分元素结点和表结点*/union{/*元素结点和表结点的联合部分*/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;//标志域：用于区分原子结点和表结点

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广义表的基本操作广义表是递归结构，所以广义表的许多操作可以用递归算法实现。求广义表的深度

intdepth(NODE*head)

广义表的深度=1+MAX(depth(αi))depth(αi)的递归定义：基本项：

L为空表，depth(αi)=1L为原子结点指针，depth(αi)=0递归项：

αi为非空表，depth(L