第四章数组、串与广义表.ppt

template class T GenListNodeT *GenListT:: Next(GenListNodeT *elem) { //返回表元素elem的直接后继元素 if (elem-tlink == NULL) return NULL; else return elem-tlink; }; * 广义表的递归算法 一个递归算法有两种：一个是递归函数的外部调用；另一个是递归函数的内部调用。 通常，把外部调用设置为公有函数，把内部调用设置为私有函数。 * template class T //公有函数 void GenListT::Copy(const GenListT R) first = Copy(R.first); //调用私有函数 }; * 广义表的复制算法 template class T //私有函数 GenListNodeT* GenListT::Copy(GenListNode T *ls) {//复制一个 ls 指示的无共享子表的非递归表 GenListNodeT *q = NULL; if (ls != NULL) { q = new GenListNodeT; //处理当前的结点q q-utype = ls-utype; //复制结点类型 switch (ls-utype) { //根据utype传送信息 case 0: q-info.ref = ls-info.ref; break; case 1: q-info.value = ls-info.value; break; case 2: q-info.hlink = Copy(ls-info.hlink); break; } q-tlink = Copy(ls-tlink); //处理同层下一结点 } return q; }; * 0 1 1 a 1 b ∧ 0 1 2 1 e ∧ 2 0 1 1 c 1 d ∧ 2 0 0 ∧ ls * 1 1 1 1 2 3 4 求广义表深度的算法 例如，对于广义表 E (B (a, b), D (B (a, b), C (u, (x, y, z)), A ( ) ) ) * template class T int GenListT::Depth() { //公有函数 //计算一个非递归表的深度 return Depth(first); }; template class T //私有函数 int GenListT::Depth(GenListNodeT *ls) { if (ls-tlink == NULL) return 1; // ls-tlink ==NULL, 空表，深度为1 GenListNodeT *temp = ls-tlink; int m = 0, n; * while (temp != NULL) { //在广义表顶层横扫 if (temp-utype == 2) { //扫描到表结点 n = Depth(temp-info.hlink); //递归计算以子表深度 if (m n) m = n; //取最大深度 } temp = temp-tlink; } return m+1; //返回深度 }; * 0 1 1 a 2 2 1 b ? 0 1 1 c ? 0 1 0 1 1 d ls 2 1 c ? ? 广义表的删除算法 扫描子链表 若结点数据为c, 删除。可能做循环连续删。 若结点数据不为c，不执行删除。 若结点为子表，递归在子表执行删除。 * template class T void delvalue(GenListNodeT *ls, T x) { if (ls-tlink != NULL) { //非空表 GenListNodeT * p = l