第五讲数组和广义表.ppt

第五章 数组和广义表 数组和广义表可看成是一种特殊的线性表，其特殊在于:表中的数据元素本身也是一种线性表,5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 a1n a21 a22 a2n am1 am2 amn,Amn=,可以看成是m由个行向量组成的向量，也可以看成是n个列向量组成的向量。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。,5.2 数组的顺序表示和实现 由于计算机的内存储结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。,5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数,5.1 数组的类型定义,ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,n 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,基本操作：,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Value(A, &e, index1, ., indexn),Assign(&A, e, index1, ., indexn),InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。,DestroyArray(&A) 操作结果：销毁数组A。,Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。,Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。,5.2 数组的顺序表示和实现,类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。,有两种顺序映象的方式: 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2×ij)×,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L,L,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系,称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数。,其中 cn = L，ci-1 = bi ×ci , 1 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,5.3 稀疏矩阵的压缩存储,何谓稀疏矩阵？,以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零。,1) 尽可能少存或不存零值元素；,解决问题的原则:,2) 尽可能减少没有实际意义的运算；,3) 操作方便。 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元。,1) 特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵,2) 随机稀疏矩阵 非零元在矩阵中随机出现,有两类稀疏矩阵：,5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先,顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak,之间找一个对应关系。 若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J 0 kn(n+1)/2,因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sak中找到矩阵元素aij，反之，对所有 的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图： k=0 1 2 3 n(n-1)/2 n(n+1)/2-1 例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4,2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数，如图所示。在大多数情况下， 三角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)/2中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pj,k=,下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . 图5.3 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1,k=,非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。,K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：,LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10。 k=2*i+j=2*3+4=10 a21对应着sa5 k=2*2+1=5 由此，我们称sa03*n-2是阶三对角带状矩阵A的压缩存储表示。,上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 5.3.2 稀疏矩阵 。,随机稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑联接的顺序表,三、 十字链表,#define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,一、三元组顺序表,typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,如何求转置矩阵？,用常规的二维数组表示时的算法,其时间复杂度为: O(mu×nu),for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,用“三元组”表示时如何实现？,1 2 14,1 5 -5,2 2 -7,3 1 36,3 4 28,2 1 14,5 1 -5,2 2 -7,1 3 36,4 3 28,首先应该确定每一行的第一个非零元在三元组中的位置。,cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;,Status FastTransposeSMatrix(TSMatrix M, TSMatrix / FastTransposeSMatrix,转置矩阵元素,Col = M.datap.j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol,分析算法FastTransposeSMatrix的时间复杂度：,时间复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) ,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,二、行逻辑联接的顺序表,#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型,修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。,例如：给定一组下标，求矩阵的元素值,ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r / value,矩阵乘法的精典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; ,其时间复杂度为: O(m1×n2×n1),Q初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if,两个稀疏矩阵相乘（QMN） 的过程可大致描述如下：,Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix / MultSMatrix,ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; p MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if,处理 的每一行,M,分析上述算法的时间复杂度,累加器ctemp初始化的时间复杂度为(M.muN.nu)， 求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)， 进行压缩存储的时间复杂度为(M.muN.nu)， 总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。,若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵， 则M中非零元的个数 M.tu = Mmn， N中非零元的个数 N.tu = Nnp， 相乘算法的时间复杂度就是 (mp(1+nMN) ， 当M0.05 和N0.05及 n 1000时， 相乘算法的时间复杂度就相当于 (mp)。,三、 十字链表,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,5.4 广义表的类型定义,ADT Glist 数据对象：Dei | i=1,2,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： LR| ei-1 ,eiD, 2in ADT Glist,基本操作:,广义表是递归定义的线性结构，,LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ),广义表是一个多层次的线性结构,例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,广义表 LS = ( 1, 2, , n )的结构特点:,1) 广义表中的数据元素有相对次序；,2) 广义表的长度定义为最外层包含元素个数；,3) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “空表”的深度为 1,4) 广义表可以共享；,5) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。,6) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分。,例如: D = ( E, F ) = (a, (b, c)，F ),Head( D ) = E Tail( D ) = ( F ),Head( E ) = a Tail( E ) = ( ( b, c) ),Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( ),Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ),Head( ( c ) ) = c Tail( ( c ) ) = ( ), 结构的创建和销毁 InitGList(,基本操作, 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);, 插入和删除操作 InsertFirst_GL(, 遍历 Traverse_GL(L, Visit();,5.5 广义表的表示方法,通常采用头、尾指针的链表结构,表结点: 原子结点：,tag=1 hp tp,tag=0 data,1) 表头、表尾分析法：,构造存储结构的两种分析方法:,若表头为原子，则为,空表 ls=NIL,非空表 ls,tag=1,指向表头的指针,指向表尾的指针,tag=0 data,否则，依次类推。,L = ( a, ( x, y ), ( ( x ) ) ),a,( x, y ),( ),1,L,L = ( ),0 a,1,1,1,1,1,0 x,( ),x,2) 子表分析法：,若子表为原子，则为,空表 ls=NIL,非空表,1,指向子表1 的指针,tag=0 data,否则，依次类推。,1,指向子表2 的指针,1,指向子表n 的指针,ls,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),ls,5.6 广义表操作的递归函数,递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：,1)在每一次调用自己时，必须是(在某 种意义上)更接近于解;,2)必须有一个终止处理或计算的准则。,例如: 梵塔的递归函数,void hanoi (int n, char x, char y, char z) if (n=1) move(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); ,二叉树的遍历,void PreOrderTraverse( BiTree T,void (Visit)(BiTree P) if (T) Visit(T-data); (PreOrderTraverse(T-lchild, Visit); (PreOrderTraverse(T-rchild, Visit); / PreOrderTraverse,一、分治法 (Divide and Conquer) (又称分割求解法),如何设计递归函数？,二、后置递归法(Postponing the work),三、回溯法(Backtracking),对于一个输入规模为 n 的函数或问题， 用某种方法把输入分割成 k(1kn)个子集， 从而产生 l 个子问题，分别求解这 l 个问题， 得出 l 个问题的子解，再用某种方法把它们 组合成原来问题的解。若子问题还相当大， 则可以反复使用分治法，直至最后所分得 的子问题足够小，以至可以直接求解为止。,分治法的设计思想为:,在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。,例如:,梵塔问题: Hanoi(n, x, y, z),可递归求解 Hanoi(n-1, x, z, y),将 n 个盘分成两个子集(1至n-1 和 n )，从而产生下列三个子问题：,1) 将1至n-1号盘从 x 轴移动至 y 轴；,3) 将1至n-1号盘从y轴移动至z轴；,2) 将 n号盘从 x 轴移动至 z 轴；,可递归求解 Hanoi(n-1, x, z, y),又如:,遍历二叉树: Traverse(BT),可递归求解 Traverse(LBT),将 n 个结点分成三个子集(根结点、左子树 和右子树 )，从而产生下列三个子问题：,1) 访问根结点；,3) 遍历右子树;,2) 遍历左子树；,可递归求解 Traverse(RBT),广义表从结构上可以分解成,广义表 = 表头 + 表尾,或者,广义表 = 子表1 + 子表2 + ··· + 子表n,因此常利用分治法求解之。 算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。,广义表的头尾链表存储表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; / 标志域 union AtomType atom; / 原子结点的数据域 struct struct GLNode *hp, *tp; ptr; ; *GList,tag=1,hp tp,ptr,表结点,例一 求广义表的深度,例二 复制广义表,例三 创建广义表的存储结构,广义表的深度=Max 子表的深度 +1,例一 求广义表的深度,可以直接求解的两种简单情况为： 空表的深度 = 1 原子的深度 = 0,将广义表分解成 n 个子表，分别(递归)求得每个子表的深度，,int GlistDepth(Glist L) / 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepth,if (!L) return 1; if (L-tag = ATOM) return 0;,1,1,1,L,for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; ,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,pp-ptr.hp,例二 复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。,将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，,若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp,复制求广义表的算法描述如下:,Status CopyGList(Glist / 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;,例三 创建广义表的存储结构,对应广义表的不同定义方法相应地有不同的创建存储结构的算法。,假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L，建立相应的存储结构。,由于S中的每个子串i定义 L 的一个子表，从而产生 n 个子问题，即分别由这 n个子串 (递归)建立 n 个子表，再组合成一个广义表。,可以直接求解的两种简单情况为： 由串( )建立的广义表是空表； 由单字符建立的子表只是一个原子结点。,如何由子表组合成一个广义表？,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,1,L,指向广义表 的头指针,指向第一个 子表的头指针,再看相邻两个子表之间的关系:,1,1,指向第i+1个 子表的头指针,指向第i个 子表的头指针,可见，两者之间通过表结点相链接。,若 S = ( ) 则 L = NIL； 否则，构造第一个表结点 *L， 并从串S中分解出第一个子串1，对应创建第一个子广义表 L-ptr.hp； 若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 2，对应创建第二个子广义表 ； 依次类推，直至剩余串为空串止。,void CreateGList(Glist /脱去串S的外层括弧 / else ,由sub中所含n个子串建立n个子表;,do sever(sub, hsub); / 分离出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一个子表的表结点*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub); p-ptr.tp = NULL; / 表尾为空表,创建由串hsub定义的广义表p-ptr.hp;,if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 创建单原子结点 else CreateGList(p-ptr.hp, hsub); /递归建广义表,后置递归的设计思想为:,递归的终结状态是，当前的问题可以直接求解，对原问题而言，则是已走到了求解的最后一步。,链表是可以如此求解的一个典型例子。 例如：编写“删除单链表中所有值为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) “a1x”，则余下问题是考虑以 L-next 为头指针的链表,a1,L-next,L-next=p-next,p=L-next,void delete(LinkList / delete,删除广义表中所有元素为x的原子结点,分析: 比较广义表和线性表的结构特点：,相似处：都是链表结构。,不同处：1)广义表的数据元素可能还是个 广义表； 2)删除时，不仅要删除原子结点， 还需要删除相应的表结点。,void Delete_GL(Glist / 考察第一个子表 if (head-tag = Atom) && (head-atom = x) / 删除原子项 x的情况 else / 第一项没有被删除的情况 / Delete_GL, , ,p=L; L = L-ptr.tp; / 修改指针 free(head); / 释放原子结点 free(p); / 释放表结点 Delete_GL(L, x); / 递归处理剩余表项,1,L,0 x,1,p,L,head,if (head-tag = LIST) /该项为广义表 Delete_GL(head, x); Delete_GL(L-ptr.tp, x); / 递归处理剩余表项,1,L,0 a,1,1,head,L-ptr.tp,回溯法是一种“穷举”方法。其基本思想为：,假设问题的解为 n 元组 (x1, x2, , xn)， 其中 xi 取值于集合 Si。 n 元组的子组 (x1, x2, , xi) (in) 称为部分解，应满足一定的约束条件。 对于已求得的部分解 (x1, x2, , xi) ， 若在添加 xi+1Si+1 之后仍然满足约束条件， 则得到一个新的部分解 (x1, x2, , xi+1) , 之后继续添加 xi+2Si+2 并检查之。,例一、皇后问题求解,设四皇后问题的解为 (x1, x2, x3, x4), 其中： xi (i=1,2,3,4) Si=1, 2, 3, 4 约束条件为：其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。,按回溯法的定义，皇后问题求解过程为： 解的初始值为空；首先添加 x1=1, 之后添加满足条件的 x2=3，由于对所有的 x31,2, 3, 4都不能找到满足约束条件的部分解(x1, x2, x3), 则回溯到部分解(x1), 重新添加满足约束条件的x2=4, 依次类推。,void Trial(int i, int n) / 进入本函数时，在n×n棋盘前i-1行已放置了互不攻 / 击的i-1个棋子。现从第 i 行起继续为后续棋子选择 / 满足约束条件的位置。当求得(in)的一个合法布局 / 时，输出之。 if (in) 输出棋盘的当前布局; else for (j=1; j=n; +j) 在第 i 行第 j 列放置一个棋子; if (当前布局合法) Trial(i+1, n); 移去第 i 行第 j 列的棋子; / trial,回溯法求解的算法一般形式：,void B(int i, int n) / 假设已求得满足约束条件的部分解(x1,., xi-1)，本函 /数从 xi 起继续搜索，直到求得整个解(x1, x2, xn)。 if (in) else while ( ! Empty(Si) 从 Si 中取 xi 的一个值 viSi; if (x1, x2, , xi) 满足约束条件 B( i+1, n); / 继续求下一个部分解 从 Si 中删除值 vi; / B,综合几点： 1. 对于含有递归特性的问题，最好设计递归形式的算法。但也不要单纯追求形式，应在算法设计的分析过程中“就事论事”。例如，在利用分割求解设计算法时，子问题和原问题的性质相同；或者，问题的当前一步解决之后，余下的问题和原问题性质相同，则自然导致递归求解。,2. 实现递归函数，目前必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。需要注意的是递归函数递归层次的深度决定所需存储量的大小。,3. 分析递归算法的工具是递归树，从递归树上可以得到递归函数的各种相关信息。例如：递归树的深度即为递归函数的递归深度；递归树上的结点数目恰为函数中的主要操作重复进行的次数；若递归树蜕化为单支树或者递归树中含有很多相同的结点，则表明该递归函数不适用。,例如: n=3的梵塔算法中主要操作move的执行次数可以利用下列递归树进行分析:,move(3, a, b, c),move(2, a, c, b),move(2, b, a, c),move(1, a, b, c),move(1, c, a, b),move(1, b, c, a),move(1, a, b, c),上图递归树的中序序列即为圆盘的移动操作序列。,又如: 求n!的递归函数的递归树已退化为一个单枝树;而计算斐波那契递归函数的递归树中有很多重复出现的结点。,n,n-1,1,0,。,F5,F4,F3,F3,F2,F2,F1,F1,F0,F1,F0,。,4. 递归函数中的尾递归容易消除。 例如：先序遍历二叉树可以改写为： void PreOrderTraverse( BiTree T) While (T) Visit(T-data); PreOrderTraverse(T-lchild); T = T-rchild; / PreOrderTraverse,void delete(LinkList ,又如:,void delete(LinkList ,可改写为,5. 可以用递归方程来表述递归函数的 时间性能。 例如: 假设解n个圆盘的梵塔的执行 时间为T(n) 则递归方程为： T(n) = 2T(n-1) + C， 初始条件为： T(0) = 0,1. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。