复习十二：广义表

一、广义表的定义及其重要特性

•   广义表简称表，它是线性表的推广。一个广义表是n(n>=0)个元素的一个序列，若n=0时，则称为空表；
•  广义表中有两种数据元素，即有两种结构的结点：表结点和原子结点；
• 广义表中的数据元素有相对次序；
• 广义表的广度定义为最外层包含元素个数；
• 广义表的深度定义为所包含括弧的重数。其中原子的深度为0，空表的深度为1；
• 广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；
• 广义表可以是一个递归的表。一个广义表可以是自己的子表。这种广义表称之为递归表。递归表的深度是无穷值，长度是有限值；
• 任何一个非空广义表GL均可分解为表头head(GL)=a1【取表头】和表尾tail(GL)=(a2,....,an)【取除表头以外的所有元素】两部分

• typedef struct MPNode{
      ElemTag    tag;    //区分原子结点和表结点
      int        exp;    //指数域
      union{
          float    coef;    //系数域
          struct    MPNode *hp;    //表结点的表指针
      };
      struct     MPNode    *tp;    //相当于线性表的next，指向下一个元素结点
   
  }*MPList;    //m元多项式广义表类型
  

       二、递归法求广义表深度

int GListDepth(GList L){
    //采用头尾链表存储结构，求广义表L的深度
    if(!L)    return 1;        //空表深度为1
    if(L->tag == ATOM)    return 0;    //原子深度为0
    for(max=0,pp=L;pp;pp=pp->ptr.tp){
        dep =GListDepth(pp->ptr.hp);    //求以pp->ptr.hp为头指针的子表深度
        if(dep>max)    max=dep;    //记录最大深度
    }
    return max+1;    //非空表的深度是各个元素的深度的最大值加1
}

三、递归法复制广义表

Status CopyGList(GList &T,GList L){
    //采用头尾链表存储结构，由广义表L复制得到广义表T
    if(!L)    T=NULL;    //复制空表
    else{
        if(!(T =(GList)malloc(sizeof(GLNode))))    exit(OVERFLOW);    //建表结点
        T->tag = L->tag;
        if(L->tag == ATOM)    T->atom = L->atom;    //复制单原子
        else{
            CopyGList(T->ptr.hp,L->ptr.hp);    //复制广义表L->ptr.hp的一个副本T->ptr.hp
            CopyGList(T->ptr.tp,L->ptr.tp);    //复制广义表L->ptr.tp的一个副本T->ptr.tp
        }
    }
    return OK;
    }

注：

表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表；

tail取出来的始终是一个表，即使只有一个简单的一个元素，tail取出来的也是一个表；

head取出来的可以是一个元素也可以是一个表