广义表

2014/10/15 posted in  算法&数据结构

广义表是线性表的推广,也可称之为列表(lists)。广泛地用于人工智能等领域的表处理语言LISP语言,把广义表为基本的数据结构,就连程序也表示为一系列的广义表。

线性表被定义为一个有限的序列(a1,a2,a3,…,an)其中ai被限定为是单个数据元素。广义表也是n个数据元素d1,d2,d3,…,dn的有限序列,但不同的是,广义表中的di 则既可以是单个元素,还可以是一个广义表,通常记作:GL=(d1,d2,d3,…,dn)。GL是广义表的名字,通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表,则称di是广义表GL的子表。在广义表GL中,d1是广义表GL的表头,而广义表GL其余部分组成的表(d2,d3,…,dn)称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时,又使用了广义表的概念。(百度百科,发现百度百科上就是抄的《数据结构》的原话嘛)

在广义表的定义中,元素a1可以是单个元素,也可以是广义表,分别称为广西表的原子子表

当广义表非空时,称第一个元素a1为广义表的表头,称其余元素组成的表是广义表的表尾。

广义表的定义是一个递归的定义,因为在描述广义表时又用到了广义表的概念。

根据定义,广义表的三条重要结论:

1.广义表的元素可以是子表,而子表的元素还可以是子表。由此,广义表是一个多层次结构;

2.广义表可为其他广义表共享(子表);

3.广义表可以是一个递归的表,即任何广义表可以是其本身的一个子表。

根据表头、表尾的定义可知:任何一个非空广义表其表头可能是原子,也可能是广义表,而其表尾必定为广义表。

注意:列表()和(())是不一样的,前者是空表,长度n=0,后者长度n=1,可分解得到其表头、表尾均为空表。即使成员表的长度为零,但因为有成员表,因此长度为1.这也体现了为什么说广义表是一个递归的表。

广义表的存储结构

由于广义表中的数据元素可以具有不同的结构(或原子或广义表),因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据可用一个结点(还有升级空间啊,换上树的话鸟枪换炮啊)。

因为数据元素可能为原子或广义表,因此需要两种结构特点:一种是表结点,用以表示列表;一种是原子结点,用以表示原子。

反之,一对确定的表头表尾可唯一确定广义表。因此,一个表结点可由3个域组成:标志域(用枚举类型),指示表头的指针域和指示表尾的指针域;而原子结点只需两个域:标志域和值域。

模型如下:

typedef enum{ATOM,LIST}ElemTag; //ATOM == 0:原子,LISE == 1:子表
typedef struct GLNode{
    ElemTag tag;    //公共部分,用于区分原子结点和表结点
    union{          //原子结点和表结点的联合部分
        AtomType atom;  //atom是原子结点 的值域,AtomType由用户定义
        //ptr是表结点的指针域,ptr.hp和ptr.tp分别指向表头和表尾
        struct{struct GLNode *hp,*tp;}ptr;
    };
}*GList;  //广义表的类型

这种存储结构吧,是我挺喜欢的一种结构,因为第二种太丑了。

这种存储结构中:

1.除了空表的表头指针为空外,对任何非空列表,其表头指针均指向一个表结点,且该结点中的hp域指示列表表头(或为原子结点,或为表结点),tp域指向列表表尾(除非表尾为空,则指针为空,否则必为表结点);

2. 容易分清列表中原子列表中原子和子表所在层次。

3.最高层的表结点个数即为列表的长度。

还有另外一种结构,刚开始的时候我还没看出这两种结构的区别,仔细琢磨发现这两种结构的区别还是很明显的。

typedef enum{ATOM,LIST}ElemTag; //ATOM == 0:原子,LISE == 1:子表
typedef struct GLNode{
    ElemTag tag;    //公共部分,用于区分原子结点和表结点
    union{          //原子结点和表结点的联合部分
        AtomType atom;  //atom是原子结点 的值域,AtomType由用户定义
        struct GLNode *hp;  //表头指针
    };
    struct GLNode *hp;      //相当于next
}*GList;  //广义表的类型

看起来没有区别,但是画画图会发现这种存储结构相对离散。如果广义表中的子表需要较强独立访问的时候,还是可以考虑的。

m元多项式的表示

在第二章写线性表的时候就提到过如何存储多项式问题,在这里又提到了m元多项式的存储问题。在《数据结构》中,应用模型是实战的第一步,数据结构模型不是单纯的孤立存在,要有不太复杂的操作存在才有意义,才更有实用性。可以说一个模型是有存储,方法两部分组成的(好像C++的封装,不过这也就是ADT所在吧)。

在一般情况下使用的广义表多数既非是递归表,也不为其他表所共享。广义表中的一个数据元素可以是另一个广义表,这就为存储系数提供了便利。

其实m元多项式的表示和多项式的表示一样无语。其实就是先提取公因式把然后把系数保存下来。

步骤:

1.对一个字母提取公因式

2.分解出系数来依次保存(利用递归的特点)

3.向内递归(就是把系数再进行第一步操作)

typedef struct MPNode{
    ElemTag Tag;   //区分原子结点还是表结点
    int exp;    //指数域
    union{
        float coef //系数域
        struct MPNode *hp //表结点的表头指针
    };
    struct MPNode *tp //相当于next
}*MPList;

这个用的是第二种存储结构,虽然丑,但尽量保证的系数的独立性,在以后访问、计算速度可能会更棒一些。

在每一层上增设一个表头结构并利用exp指示该层的变元,可用一维数组存储多项式中所有的变元,故exp域存储的是该变元在一维数组的下标。

广义表的递归算法

鞠老师说这是这章最关键的地方,的确,非常有意思。

因为在做竞赛的时候学个一些树,对写一些简单的递归也算轻车熟路,这一节属于难点,但不是我的难点。大体总结之。

先说说递归,让我形容递归,就三个词:

1.慢:因为递归就是栈的应用,在使用栈空间时间是个问题,递归求阶乘就很好说明问题

2.不负责任:我写递归的时候一直处在不负责任状态,先写出来,管他对错呢,写完在想对错问题,= =。其实递归函数不好理解,等你想明白黄瓜菜都凉了,递归就要随心所欲,然后约束之。

3.强大:很多高级算法就是由递归写的,当递归看多了就发现,数学才是硬伤。

递归设计的实质是:当一个复杂的问题可以分解成若干子问题来处理时,其中某些子问题与原问题有相同的特征属性,则可利用和原问题相同的分析处理方法;反之,这些问题之间的转化关系。

由于递归函数的设计用的是归纳的思想,则在设计递归函数的时候注意:

1.严格定义功能和接口

2.把递归的每个操作看着简单操作

求广义表的深度

求广义表的深度和字典树很像,递归遇到子集深入。

复制广义表

因为广义表可以分为表头和表尾,那么只需要分别复制表头和表尾即可(有点分治的意思)。

if(L->tag==ATOM) T->atom = L->atom;
else{
    //分而治之
    CopyGList(T->ptr.hp,L->ptr.hp);
    CopyGList(T->ptr.tp,L->ptr.tp);
}

建立广义表的存储结构

因为前面已经提到过有两种存储结构,一种是把广义表分解为表头和表尾,另一种是把广义表看成含有n个并列子表(假设原子也视为子表)的表。其实递归存储和复制也差不到哪去。不过书中给出的代码的确不错

Status CreateGList(GList &L, SString S) {
  // 采用头尾链表存储结构,由广义表的书写形式串S创建广义表L。
  // 设emp="()"。
  char s[3]="()";
  SString emp;
  crt_SString(emp,s);
  SString sub,hsub;
  GList p,q;
  if (StrCompare(S, emp)) L = NULL;  // 创建空表
  else {
    if (!(L=(GList)malloc(sizeof(GLNode)))) return ERROR;  // 建表结点
    if (StrLength(S)==1) {  // 创建单原子广义表
       L->tag = ATOM;  L->atom =S[1]; }
    } else {
      L->tag = LIST;  p = L;
      SubString(sub, S, 2, StrLength(S)-2);  // 脱外层括号
      do {  // 重复建n个子表
        sever(sub, hsub);  // 从sub中分离出表头串 hsub
        CreateGList(p->ptr.hp, hsub);  q = p;
        if (!StrEmpty(sub)) {   // 表尾不空
          if (!(p = (GLNode *) malloc (sizeof(GLNode)))) return ERROR;
          p->tag = LIST;  q->ptr.tp = p;
        }//if
      } while (!StrEmpty(sub));
      q->ptr.tp = NULL;
    } // else
  } // else
  return OK;
} // CreateGList