广义表操作的递归.ppt

5.6 广义表操作的递归函数 什么是递归函数？ 递归函数：直接或者简介调用自身的函数 递归调用有两种方式: 直接调用其本身 通过其他函数间接地调用。 递归程序特点 通常以递归形式定义算法与非递归算法比较，算法结构会更紧凑、清晰; 但是，递归函数在递归调用过程中，会占用更多的内存空间和需更多的运行时间; 它必须满足以下两个条件： 1) 在每一次调用自己时，必须是（在某种意义上）更接近于解; 2) 必须有一个终止条件。 防止振荡式的相互递归调用，否则会产生无限递归调用现象; 一个问题是否可以转换为递归来处理必须满足以下条件： （1）必须包含一种或多种非递归的基本形式； （2）一般形式必须能最终转换到基本形式； （3）由基本形式来结束递归。 递归求解的问题 在以下三种情况下，常常用到递归方法 1）定义是递归的 2）数据结构是递归的 3）问题的解法是递归的 1）定义是递归的 例2：斐波那契数列 1，1，2，3，5，8，13，21…… F(1)=F(2)=1, F(n)=F(n-1)+F(n-2) (n≥3) 例2：斐波那契数列 方法2：求出通项公式 (1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n} 这样一个完全是自然数的数列，通项公式居然是用无理数来表达的 3）问题的解法是递归的 例2、求两个数的最大公约数的数学模型 5.4.3 广义表操作的实现 广义表从结构上可以分解成 广义表 = 表头 + 表尾 广义表 = 子表1 + 子表2 + ··· + 子表n 5.4.3.1 求广义表的深度 GListDepth( L ) 5.4.3.2 复制广义表 CopyGList(T,L) 5.4.3.3 建立广义表CreateGList(L, str[ ] ) 5.4.3.4 删除广义表中所有元素为 x 的原子结点 …… 5.4.3.3 建立广义表 5.4.3.4 删除广义表中所有元素为 x 的原子结点 删除单链表中所有值为x 的数据元素 基本思想： 1) 单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素； 2) 从另一角度看，链表又是一个递归结构 若 L 是线性链表 (a1, a2, ?, an) 的头指针 则 L-next是线性链表 (a2, ?, an)的头指针。 删除单链表中所有值为x 的数据元素 删除广义表中所有元素为x的原子结点 删除原子项 x的情况 第一项是原子项单不等于x 广义表操作的实现—删除广义表 void DestroyGList(GList L) { if (!L) return; if (L-tag == LIST) { DestroyGList(L-ptr.hp); DestroyGList(L-ptr.tp); } free(L); L = NULL; }//DestroyGList 广义表操作的实现—计算广义表长度 int GListLength(GList L) { if (L) return (1 + GListLength(L-ptr.tp)); else return 0; }//GListLength 广义表操作的实现—计算广义表深度 广义表操作的实现—插入节点 Status InsertFirst_GL(GList L, GList e) { //在广义表第一个节点前插入一个子表节点 p =(GList)malloc(sizeof(GLNode)); if (!p) exit(OVERFLOW); p-tag = LIST; p-ptr.hp = e; p-ptr.tp = L; L = p; return OK; }//InsertFirst_GL 广义表操作的实现—删除节点 本章学习要点 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 掌握对特殊矩阵进行压缩存储时的下标变换公式。 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的方法：即可将一个非空广义表分解为表头和表尾两部分。 掌握广义表的递归算法设计。 //该项为原子项，不等于x Delete_GL(L-ptr.tp, x); // 递归处理剩余表项 1 L 0 a 1 head L-ptr.tp Else if ((head-tag == Atom) (head-atom != x)) Else if (head-tag == LIST) //该项为广义表 Delete_G