广义表

一、广义表的定义

广义表也称为列表,是 n(n≥0)个元素 a1,a2,…,an的有限序列,即

LS=(a1,a2,…,an)

其中,LS 是广义表的名称,n 是它的长度。ai可以是单个元素,也可以是广义表。若 ai 是单个元素,则称它是广义表 LS 的原子;若 ai 是广义表,则称它为 LS 的子表。当 LS 非空时,称第一个元素 a1 为 LS 的表头(Head),其余元素组成的表(a2,a3,…,an)为表尾(Tail)。

由于在广义表的定义中又用到了广义表的概念,因而广义表是一个递归定义。一般约定大写字母表示广义表(或子表),小写字母表示单个元素(或原子)。

下面列举一些广义表的例子:

  • A=():A 是一个空表,其长度为 0。

  • B=(b, c):B 是一个长度为 2 的列表。

  • C=(a, (d, e, f)):C 是一个长度为 2 的列表,其中第一个元素是原子 a,第二个元素是子表 (d, e, f)。

  • D=(A, B, C):D 是一个长度为 3 的列表,其中 3 个元素都是子表。

  • E=(a, E):E 是一个长度为 2 的列表,它是一个递归表。

广义表可以用图形象地表示,如上述例子可以用下图表示。图中用圆圈表示广义表,用方块表示原子。

广义表图形表示:
广义表图形表示

由广义表的定义可以推导出以下 4 个结论:

  1. 由于广义表中的元素可以是原子也可以是子表,因此广义表是一个多层次结构。

  2. 广义表是可以共享的。例如在上述例子中,广义表 B 是 D 的子表。

  3. 广义表可以是其本身的一个子表,因此广义表允许递归。例如在上述例子中,广义表 E 是一个递归表。

  4. 广义表的元素之间除了存在次序关系之外,还存在层次关系。把广义表展开后所包含的括号层数称为广义表的深度。例如,广义表 C 的深度为 2,E 的深度为 ∞。

二、广义表的存储

由于广义表(a1,a2,…,an)中的元素不是同一类型,可以是原子元素,也可以是子表,因此很难用顺序结构存储。通常采用模拟线性链式存储方法来存储广义表。广义表中的每个元素由一个结点表示。该结点既可表示原子元素,又可表示子表。为区分两者,可用一个标志位 tag 来区分。结点的结构可设计为如下形式:

广义表存储结点:

广义表存储结点

当 tag=0 时,原子结点由标志域、值域构成;当 tag=1 时,表结点由标志域、指向表头的指针域和指向表尾的指针域三部分构成。其形式定义如下:

typedef Struct GenNode {
  int tag;

  Union {
    DataType data;

    Struct {
      Struct GenNode *hp,*tp;
    }

    ptr;
  }
}

class Glist {

  Public:
    GenNode *first;

    int depth(GenNode *ls); //求广义表的深度

    int equal(GenNode *s, GenNode *t);

    Glist(){first=Null}; //构造函数

    ~Glist(); //析构函数

    GenNode *GetHead(); //取广义表表头

    GenNode *GetTail(); //取广义表表尾

    GenNode *GetFirst(); //取广义表的第一个元素

    GenNode *GetNext(GenNode *elem); //取广义表的元素 elem 后继
}

上述所列举的几个广义表,其存储结构如下图所示:

广义表存储结构示例:

广义表存储结构示例

三、广义表基本操作的实现

由于广义表是对线性表的推广,因此广义表上的操作也有查找、取元素、插入和删除等基本操作。在此介绍广义表的几个特殊的基本操作,主要有取表头、取表尾和求广义表的深度等操作。

(一) 取广义表表头 GetHead() 和取广义表表尾 GetTail()

任何一个非空广义表的表头是表中第一个元素,它可能是原子,也可能是广义表,而其表尾必定是广义表。例如广义表B、C、D的表头和表尾分别为:

广义表 表头 表尾
B GetHead() = b GetTail() = ( c )
C GetHead() = a GetTail() = ((d, e, f))
D GetHead() = A GetTail() = (B, C)

取表头的算法如下:

GenNode *Glist::GetHead() {
  // 若广义表非空,则返回指向第一个元素的指针,否则返回空
  if(first == NULL || first->tag == 0) {
    cout << "空表或是单个原子" <<endl;
    return null;
  }

  return first->ptr.hp;
}

取表尾算法如下:

GenNode *Glist::GetTail() {
  //空表或是单个原子,函数无意义,否则返回表尾指针
  if(first==NULL||first->tag==0) {
    cout << "空表或是单个原子" << endl;
    return null;
  }

  return first->ptr.tp;
}

值得注意的是,广义表 () 和(())是不同的。前者长度 n 为 0,表示一个空表;后者长度 n 为 1,表示一个有一个空表的广义表,它可以分解得到表头和表尾,均是空表()。

(二) 求广义表的深度

广义表的深度是指广义表中所含括号的重数。

设非空广义表为:

LS = (a1,a2,…,an)

其中,ai(i=1,2,…,n)或为原子,或为 LS 的子表。求广义表 LS 的深度可用递归算法来处理,具体过程为:把原问题转换为求 n 个子问题 ai 的深度,LS 的深度为各 ai(i=1,2,…,n)的深度中最大值加 1。对于每个子问题 ai(i=1,2,…,n),若 ai 是原子,则由定义知其深度为 0;若 ai 是空表,其深度为 1;若 ai 是非空广义表,则采用和上述同样的方法处理。

由此可见,求广义表深度的算法如下:

// 递归计算广义表的深度
int Glist::depth(GenNode *ls) {
  if (ls == NULL) return 1;  // ls 是空表

  GenNode *tmp = ls;

  if (tmp->tag == 0) return 0;

  int max = 0;
  
  //ls 是非空的广义表
  while(tmp != NULL) {
    dep = depth(tmp->ptr.hp); // ai的深度
    if (dep > max) max = dep;
    tmp = tmp->ptr.tp;
  }

  return(max+1);  //返回表的深度
}

上述算法的执行过程实质上是遍历广义表的过程,在遍历中首先求得各子表的深度,然后综合得到广义表的深度。

用户头像
登录后发表评论