数据结构第5章广义表新.pptx

5.4 广义表 广义表的基本概念广义表的链接存储结构广义表相关操作ADT Glist { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系： LR＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n}} ADT Glist? 结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基本操作? 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);? 插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e);? 遍历 Traverse_GL(L, Visit());一、基本概念广义表是第二章提到的线性表的推广。线性表中的元素仅限于原子项(单个数据元素)，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表(另一个线性表)。 (如果ai是单个数据元素,则称ai为广义表的原子 )1．广义表的定义广义表是n≥0个元素a1，…，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为GL=(a1,…,an)，其中GL为广义表的名字，n为广义表的长度， 每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。称第一个元素a1为广义表GL的表头,其余部分(a2,...an)为GL的表尾,分别记作head(GL)= a1和tail(GL)= (a2,...an)例如:LS=( a, (x,y), ((x)) )ls? a (x, y) ((x)) 说明:1.广义表是线性表的一种推广。2.广义表是递归定义的线性结构LS = ( ?1, ?2, ???, ?n )其中：?i 或为原子 或为广义表3.一个广义表可以为其它广义表所共享 4.广义表是一个多层次的线性结构例如：DD=(E, F)EF其中: E=(a, (b, c)) F=(d, (e))a( )d( )ebc广义表 LS = ( ?1, ?2, …, ?n )的结构特点:1) 广义表中的数据元素有相对次序；2) 广义表的长度定义为最外层包含元素个数；3) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 　“空表”的深度为 1 广义表举例 (1) A=( ), A为空表，长度为0。(2) B=(a,（b,c) ), B是长度为2的广义表，第一项为原子，第二项为子表。(3) C=(x,y,z) C是长度为3的广义表，每一项都是原子。(4)D=(B,C) ， D是长度为2的广义表，每一项都是上面提到的子表。(5)E=(a,E) 是长度为2的广义表，第一项为原子，第二项为它本身。?3．取表头运算head 若广义表LS=(a1，a2，…，an)， 则head(LS)=a1 。取表头运算得到的结果可以是原子，也可以是一个子表。例如，head((a1,a2,a3,a4))=a1，head(((a1,a2),(a3,a4),a5))=(a1,a2)。4．取表尾运算tail若广义表LS=(a1，a2，…，an)，则tail(LS)=(a2，a3，…，an)。取表尾运算得到的结果是除表头以外的所有元素，取表尾运算得到的结果一定是一个子表。值得注意的是广义表( )和(())是不同的，前者为空表，长度为0，后者的长度为1，可得到表头、表尾均为空表，例：求下列广义表操作的结果（严题集5.10②）(k, p, h)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))】】＝ ;(a,b)((c,d))（b）( )5. GetTail【（e）】＝ ;6. GetHead 【 ( ( ) )】＝ .7. GetTail【 ( ( ) ) 】＝ .(a,b)( )( )5.5 广义表的存储结构由于广义表的元素类型不一定相同，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。有2种结点形式表结点:原子结点：tag=1 hp tptag=0 data构造存储结构的两种分析方法:1) 头、尾链表分析法：空表