武汉理工大学-信息工程学院-数据结构-ppt-课件ch05-2-数组与广义表2-广义表

第5章数组与广义表数据结构讲义-广义表信息工程学院魏洪涛Email:[e-mail]线性表中的元素仅限于原子项(单个数据元素)，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表(另一个线性表)。1．广义表的定义广义表是n≥0个元素a0，a1，…，an-1的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为GL=(a0,a1,…,an-1)。称第一个元素a0为广义表GL的表头,其余部分(a1,...an-1)为GL的表尾,分别记作head(GL)=a0和tail(GL)=(a1,...an-1)。一、基本概念2．广义表举例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的广义表，第一项为原子，第二项为它本身。广义表是一个多层次的线性结构例如：D=(E,F)其中:E=(a,(b,c))F=(d,(e))DEFa()d()bce3．取表头运算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，可得到表头、表尾均为空表，即head((()))=()，tail((()))=()。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))】】＝;例：求下列广义表操作的结果（严题集5.10②）(k,p,h)（b）(a,b)5.GetTail【（e）】＝;6.GetHead【(())】＝.7.GetTail【(())】＝.()(a,b)()()((c,d))由于广义表的元素类型不一定相同，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。1、结点结构形式是：tagdata/sublistlinktag为标志字段，若tag=0表示该结点为原子结点，第二个域data存放相应原子元素的信息。若tag=1为子表结点,第二个域为sublist存放相应子表第一个元素对应的结点的地址。link存放本元素同一层的下一个元素所在链结点的地址。二、广义表的链接存储结构用C语言描述结点的类型如下：typedefstructnode{inttag;union{structnode*sublist;chardata;}dd;structnode*link;}NODE;0a0b0c^BA=NULL0a1^C11^1^0a^1^1^DE一般的广义表链接存储结构（书中第二种结构P110）A=()B=((b,c))C=(a,(b,c))D=(C,((a)))E=(a,E)1、广义表的建立creat_GL(s)假设广义表以单链表的形式存储，广义表的元素类型elemtype为字符型char，广义表GL由键盘输入，假定全部为字母，输入格式为：元素之间用逗号分隔，表元素的起止符号分别为左、右圆括号。函数creat_GL(s)根据广义表表达式字符串，建立相应带附加表头结点的链接存储广义表，并返回表头指针。三、基本运算2.输出广义表prn_GL(p)对于广义表的表头结点p，若为表结点，输出空表或递归输出子表的内容，否则，输出元素值；若当前的结点还有后续结点，则递归输出后续表的内容。3.广义表的复制对于广义表的头结点p，若为空，返回空指针；若为表结点，递归复制子表；否则，复制原子结点；然后递归复制后续表。4.求广义表的深度maxdh(p)=0p-tag=1maxdh(p)=1空表(p-tag=1&&p-dd.sublist=NULL)maxdh(p)=max(maxdh(p1),...,maxdh(pn))+1其余情况p=(p1,p2,...,pn)一个广义表的深度是指该广义表展开后所含括号的层数。例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3。5.求原子结点个数(f(p)=0p=NULLf(p)=1+f(p-link)p-tag=0f(p)=f(p-dd.sublist)+f(p-link)p-tag=1示例代码ch5_GList.c作业根据广义表的递归复制算法，写出复制广义表A=((),(e),(a,(b,c,d)))的具体过程，即函数的具体执行过程。NODE*copy_GL(NODE*p){NODE*q;if(p==NULL)return(NULL);q=(NODE*)malloc(sizeof(NODE));q-tag=p-tag;if(p-tag)q-dd.sublist=copy_GL(p-dd.sublist);elseq-dd.data=p-dd.data;q-link=copy_GL(p-link);return(q);}