[教育]第五章 数组和广义表.ppt

若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp 复制求广义表的算法描述如下: Status CopyGList(Glist T, Glist L) { if (!L) T = NULL; // 复制空表 else { if ( !(T = (Glist)malloc(sizeof(GLNode))) ) exit(OVERFLOW); // 建表结点 T-tag = L-tag; if (L-tag == ATOM) T-atom = L-atom; // 复制单原子结点 else { } } // else return OK; } // CopyGList 分别复制表头和表尾 CopyGList(T-ptr.hp, L-ptr.hp); // 复制求得表头T-ptr.hp的一个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); // 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp 语句 CopyGList(T-ptr.hp, L-ptr.hp); 等价于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp; 二、后置递归的设计思想为: 递归的终结状态是，当前的问题可以直接求解，对原问题而言，则是已走到了求解的最后一步。 链表是可以如此求解的一个典型例子。 例如：编写“删除单链表中所有值为x 的数据元素”的算法。 1) 单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素； 分析: 2) 从另一角度看，链表又是一个递归结构，若 L 是线性链表 (a1, a2, ?, an) 的头指针，则 L-next是线性链表 (a2, ?, an)的头指针。 a1 a2 a3 an … ? L 例如: a1 a2 a3 an ? L a1 a2 a3 an ? L 已知下列链表 1) “a1=x”，则 L 仍为删除 x 后的链表头指针 2) “a1≠x”，则余下问题是考虑以 L-next 为头指针的链表 … … a1 L-next L-next=p-next p=L-next void delete(LinkList L, ElemType x) { // 删除以L为头指针的带头结点的单链表中 // 所有值为x的数据元素 if (L-next) { if (L-next-data==x) { p=L-next; L-next=p-next; free(p); delete(L, x); } else delete(L-next, x); } } // delete 算法：删除广义表中所有元素为x的原子结点 分析: 比较广义表和线性表的结构特点： 相似处：都是链表结构。 不同处：1)广义表的数据元素可能还是个 广义表； 2)删除时，不仅要删除原子结点， 还需要删除相应的表结点。 void Delete_GL(GlistL, AtomType x) { //删除广义表L中所有值为x的原子结点 if (L) { head = L-ptr.hp; // 考察第一个子表 if ((head-tag == Atom) (head-atom == x)) { } // 删除原子项 x的情况 else { }// 第一项没有被删除的情况 } } // Delete_GL … … … … p=L; L = L-ptr.tp; // 修改指针 free(head); // 释放原子结