二、复制广义表

  类似于复制二叉树,复制广义表是求得由指针 Ls 所指广义表的一个复制品,即由指针 newLs 所指广义表。换句话说,求得 Ls 所指结点的复制品― newLs 所指结点,其中指针 newLs->ptr.hp 所指为 Ls->ptr.hp 所指表头的复制品,newLs->ptr.tp 所指为 Ls->ptr.tp 所指表尾的复制品。

  由于广义表的表头和表尾也是广义表,由此可递归求解,递归的终结状态亦为"空表" 或 "原子"。
 
     
  算法8.2
  GList CopyGList(GList Ls) {
  // L为广义表的头指针,求得和L结构完全相同的复制品,
  // 返回指向复制所得广义表的头指针

  if (!Ls) return NULL;            // 复制空表
  else {
   newLs = new GLNode;             // 建表结点
   newLs->tag = Ls->tag;
   if (Ls->tag == ATOM) newLs->atom = Ls->atom;  // 复制单原子
   else {
    newLs->ptr.hp = CopyGList( Ls->ptr.hp);
           // 复制求得表头Ls->ptr.hp的一个副本newLs->ptr.hp
    newLs->ptr.tp = CopyGList( Ls->ptr.tp);
           // 复制求得表尾Ls->ptr.tp的一个副本newLs->ptr.tp
   } // else
  } // else
  return newLs;
 } // CopyGList
    想必读者对这个算法也不会觉得眼生,对比"复制二叉树"的算法,容易看出两者极其相似。