[广义表](4)广义表

顾名思义,广义表就是线性表的推广,也有人称其为列表(Lists,用复数形式以示与统称的表list区别),广泛的用于人工智能等领域的表处理语音LISP语言,把广义表作为基本的数据结构,就连程序也表示为一系列的广义表

抽象数据类型广义表的定义如下:

ADT GList{

    数据对象:D = {e[i] | i = 1,2,...,n; n >= 0; e属于AtoSet或e[i]属于GList
                   AtomSet为某个数据对象}
    数据关系:R1 = {<e[i - 1],e[i]> | e[i - 1],e[i]属于D,2 <= i <= n};
    基本操作:
        InitGList(&L);
            操作结果:创建空的广义表L
        
        CreateGList(&L, S);
            初始条件:S是广义表的书写形式串
            操作结果:由S创建广义表L
        
        DestroyGList(&L, S);
            初始条件:广义表L存在
            操作结果:销毁广义表L

        CopyGList(&T, L);
            初始条件:广义表L存在
            操作结果:由广义表L复制得到广义表T

        GListLength(L);
            初始条件:广义表L存在
            操作结果:求广义表L的深度

        GListEmpty(L);
            初始条件:广义表L存在
            操作结果:判定广义表L是否为空

        GetTail(L);
            初始条件:广义表L存在
            操作结果:取广义表L的尾

        InsertFirst_GL(&L, e);
            初始条件:广义表L存在
            操作结果:插入元素e作为广义表L的第一元素

        DeleteFirst_GL(&L,& e);
            初始条件:广义表L存在
            操作结果:删除广义表L的第一元素,并用e返回其值

        Traverse_GL(L, Visit());
            初始条件:广义表L存在
            操作结果:遍历广义表L,用函数Visit处理每个元素
}ADT GList

广义表一般记作:

LS=(a1,a2,...,an)

其中LS是广义表(a1,a2,...,an)的名称,n是它的长度,在线性表的定义中,ai(1<=i<=n)只限于是单个元素,而在广义表的定义中,ai可以单个元素,也可以是广义表。

分别称为广义表LS的原子和子表,习惯上,用大写字母表示广义表的名称,用小写字母表示原子,当广义表LS非空时,称第一个元素ai为LS的表头(Head),称其余元素组成的表(a2,a3,...,an)是LS的表尾(Tail)

显然,广义表的定义是一个递归的定义,因为在描述广义表时又用到了广义表的概念,下面列举一些广义表的列子:

  • A=()——A是一个空表,它的长度为零
  • B=(e)——列表B只有一个原子e,B的长度为1
  • C=(a,(b,c,d))——列表C的长度为2,两个元素分别为原子,a和子表(b,c,d)
  • D=(A,B,C)——列表D的长度为3,3个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))
  • E=(a,E)——这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,(a,...))))

从上述定义和例子可以推出列表的3个重要结论:

  1. 列表的元素可以是子表,而子表的元素还可以是子表......由此,列表是一个多层次的结构,可以用图形象的表示,例如下图中图示的列表D图中以圆圈表示列表,以方块表示原子
  2. 列表可为其他列表所共享,例如在上述例子中,列表A、B、和C为D的子表,则在D中可以不必列出子表的值,而是通过子表的名称来引用
  3. 列表可以是一个递归的表,即列表也可以是其本身的一个子表,例如列表E就是一个递归的表

img

根据前述对表头、表尾的定义可知:任何一个非空列表其表头可能是原子,也可能是列表,而其表尾必定为列表,例如:

GetHead(B)=e,GetTail(),GetHead(D)=A,GetTail(D)=(B,C)

由于(B,C)非空列表,则可继续分解得到:

GetHead((B,C))=B,GetTail((B,C))=(C)

值得提醒的是列表()和(())不同,谴责为控标,长度n=0;后者长度n=1,可分解得到其表头、表尾均为空表()

广义表的存储结构

由于广义表(a1,a2,...,an)中的数据元素可以具有不同的结构(或是原子,或是列表),因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个结点表示

如何设定结点的结构?由于列表中的数据元素可能为原子或列表,由此需要两种结构的几点:

  • 一种是表结点,用以表示列表;
  • 一种是原子结点,用以表示原子

从之前得知,若列表不空,则可分解成表头和表尾;反之,一对确定的表头 和表尾可唯一确定列表,由此:

  • 一个表结点可由三个域组成:标志域、指示表头的指针域和指示表尾的指针域
  • 而原子结点只需要两个域:标志域和值域
  • 如下图所示

img头尾链存储结构

其形式定义说明如下:

typedef enum {
    ATOM, LIST
}ElemTag;//ATOM==0;原子,LIST==1;子表

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

上方A,B,C,D,E四表的存储结构图如下:

img

img

在上方这种存储结构中有几种情况:

  • 除空表的表头指针为空外,对任何非空列表,其表头指针均指向一个表结点,且该结点中的hp域只是列表表头(或为原子结点,或为表结点),tp域指向列表表尾(除非表尾为空,则指针为空,否则必为表结点)
  • 容易分清列表中原子和子表所在层次,如在列表D中,原子a和e在同一层次上,而b、c、d、在同一层次,且比a和e低一层,B、C是同一层子表
  • 最高层的表结点个数即为列表长度

以上三个特点在某种程度上给列表的操作带来方便,我们将上述存储结构称之为头尾链存储结构

同时可以采用另一种结点结构的链表表示列表,如下所示:

typedef enum {
    ATOM, LIST
}ElemTag;//ATOM==0;原子,LIST==1;子表

typedef struct GLNode {
    ElemTag tag;//公共部分,用于区分原子结点和表结点
    union {//原子结点和表结点的联合部分
        AtomType atom;//atom是原子结点的值域,AtomType由用户定义
        struct GLNode* hp;//表结点的表头指针
    };
      struct GLNode* tp;
}*GList;//广义表类型GList是一种扩展的线性链表

相比于上一种存储结构,我个人更喜欢这种存储结构,逻辑清晰点,并且可以用线性表的思想来看待

img在这种存储结构中,将原子和表结统一来看待

img扩展线性存储结构

对于列表的这两种存储结构,只需要根据自己的习惯掌握其中一种即可,在此,对于lists不过就是data域除了原子外还可为另一条list

我们将这种存储结构称之为:扩展线性存储结构

m元多项式的表示

在学习线性表的时候,我们用一元多项式进行过一个理解,同样,在广义表中,m元多项式也是广义表的典型案例

一个一元多项式可以用一个长度为m,且每个数据元素有两个数据项(系数和指数项)的线性表来表示

一个m元多项式的每一项,最多有m个变元,如果用线性表来表示,则每个数据元素需要m+1个数据项,以存储一个系数值和m个指数值,这将产生两个问题:

  • 一是无论多项式中各项的变元数是多是少,若都按m个变元分配存储空间,将会造成浪费

    • 反之,若按各项实际的变元数分配存储空间,则会照成结点的大小不均匀,给操作带来不便
  • 二是m值不同的多项式中每一项的变化数目的不均匀性和变元信息的重要性,故不适于线性表表示

img例如三元多项式

其中各项的变元项目不尽相同,而y^3和z²等因子又多次出现,如若改写为:

img

情况就不同了,现在,我们再来看这个多项式P,它的变元z的多项式,即Az²+Bz+15z^0,只是其中A和B本身又是一个(x,y)的二元多项式,15是z的零次项系数

进一步考察A(x,y),又可把他看成是y的多项式,Cy²+Dy²,而其中C和D为X的一元多项式,循此以往,每个多项式都可看作由一个变量加上若干个系数指数偶对组成

任何一个m元多项式都可以如此做:

  • 先分解出一个主变元,再分解出第二个主变元等等
  • 由此,一个m元多项式首先是它的主变元多项式,而其系数又是第二变元的多项式
  • 由此可用广义表来表示m元多项式,例如上述的三元多项式可用下列式子表示,广义表的深度即为变元个数:

P=z((A,2),(B,1),(15,0))

其中:

  • A=y((C,3),(D,2))
  • C=x((1,10),(2,6))
  • D=x((3,5))
  • B=y((E,4),(F,1))
  • E=x((1,4),(6,3))
  • F=x((2,0))

可类似于广义表的扩展线性存储结构来定义表示m元多项式的广义表存储结构,链表的结点结构可视为:

img

其中exp为指数域,coef为系数域,hp指向其系数子表,tp指向同一层的下一结点,其形式定义说明如下:

#include<stdio.h>
#include<stdlib.h>
typedef struct MPNode
{
    int tag;//区分原子结点和表结点
    int exp; //指数域
    union
    {
        float coef;//系数域
        struct MPNode* hp;//表结点的表头指针
    };
    struct MPNode* tp;//相当于线性表的next
}*MPList;

本文链接:

https://nullcode.fun/35.html
1 + 2 =
快来做第一个评论的人吧~