二、复制广义表 类似于复制二叉树,复制广义表是求得由指针 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 |
想必读者对这个算法也不会觉得眼生,对比"复制二叉树"的算法,容易看出两者极其相似。 |