第七章广义表

第七章广义表

广义表的表头是第一个元素，表尾是剩下的元素组成的广义表

广义表的长度是包含的元素（子表和原子）个数，深度是括号的层数

广义表的存储结构：

typedef struct LNode{

    int tag;//0表示原子节点，1表示子表节点

    struct LNode *next;

    union{

       char data;

       struct LNode *sublist;

    }val;

}LNode;

广义表的两种存储结构：第一种将表头和表尾分别存储；第二种存储同层的兄弟节点（分为带头结点和不带头结点两种）

广义表的操作主要包括：求表头，求表尾，求长度，求深度，复制，求原子的个数等等

一般用递归处理子表的情况

求长度

int length(LNode *h){

    int len=0;

//  LNode *p = h;//不带头结点的第二种存储

    LNode *p = h->val.sublist;//带头结点的第二种存储

    while(h!=NULL){

       len++;

       h = h->next;

    }

}

求深度，结果为最深的子表的深度+1；

 

int depth(LNode *h){

    int dep = 0 ;

    int max = 0;

    LNode *p = h;

    while(p!=NULL){

       if(p->tag==1){

           dep = depth(p->val.sublist);

           if(dep>max)

              max = dep;

       }

       p = p->next;

    }

    return max+1;

}

求表头

LNode *head(LNode *h){

    return h->val.sublist;

}

求表尾

LNode *tail(LNode *h){

    return h->next;

}