广义表 广义表的定义 广义表是线性表的推广。 广义表一般记作LS=(d0,d1,...dn-1)当广义表LS非空时,称第一个元素d0为表头(Head),称其余元素组成的表(d1,d2,...dn-1)是LS的表尾(Tail)。显然，广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。下面列举一些广义表的例子。　　1) A=( ); A是一个空表，它的长度为0。　　2) B=( e );　 广义表B只有一个单元e，B的长度为１。　　3) C=( a,( b,c,d ) ); 广义表C的长度为２，两个元素分别为单元素a和子表( b,c,d )。　　4) D=( A,B,C ); 广义表D的长度为３，三个元素都是列表。显然，将子表的值代入后，则有D=( ( ),( e ), ( a,( b,c,d ) ) )。　　5) E=( a,E ); 这是一个递归的表，它的长度为２。E相当于一个无限的广义表E=( a,( a,( a......) ) )。从上述定义和例子可推出广义表的三个重要结论：　　1)　 广义表的元素可以是子表，而子表的元素还可以是子表，...。 　　2)　 广义表可为其他广义表所共享。 　　3)　 广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。  广义表的深度一个广义表的深度是指该广义表展开后所含括号的层数。例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3。广义表的存储结构 由于广义表的元素类型不一定相同，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。采用链式存储结构,每个数据元素可用一个结点表示:· (1)表结点,用以表示子表· (2)元素结点,用以表示单元素 第一种表示        用C语言描述结点的类型如下：typedef struct node{int tag;union{
    struct node *hp,*tp;char data;}dd;}NODE;  广义表的递归算法 一、求广义表的深度深度公式:（1）maxdh(p)=0 当p->tag=1（2）maxdh(p)=1 当空表(p->tag=1&&p->dd.sublist=NULL)（3）maxdh(p)=max(maxdh(p1),...,maxdh(pn))+1 其余情况其中p=(p1,p2,...,pn)int depth(NODE *p) /*求表的深度函数 */{int h,maxdh;NODE *q;if(p->tag==0) return(0);else if(p->tag==1&&p->dd.sublist==NULL) return 1;else{maxdh=0;while(p!=NULL){ if(p->tag==0) h=0;else{q=p->dd.sublist;h=depth(q);}if(h>maxdh)maxdh=h;p=p->link;}return(maxdh+1);}}二、求原子结点个数 原子结点个数公式：（1）f(p)=0 当p=NULL（2）f(p)=1+f(p->link) 当p->tag=0（3）f(p)=f(p->dd.sublist)+f(p->link) 当p->tag=1int count(NODE *p) /*求原子结点的个数函数 */{int m,n;if(p==NULL) return(0);else{if(p->tag==0) n=1;else n=count(p->dd.sublist);if(p->link!=NULL)m=count(p->link);else m=0;return(n+m);}}三、求原子结点数据域之和原子结点数据域之和公式:（1）f(p)=0 当p=NULL（2）f(p)=p->data+f(p->link) 当p->tag=0（3）f(p)=f(p->dd.sublist)+f(p->link) 当p->tag=1int sum(NODE *p) /*求原子结点数据域之和函数 */{int m,n;if(p==NULL) return(0);else{if(p->tag==0) n=p->dd.data-’0’;else n=sum(p->dd.sublist);if(p->link!=NULL)m=sum(p->link);else m=0;return(n+m);}}