数据结构5PPT学习教案

1、会计学1 数据结构数据结构5 2 5.1 数组的类型定义数组的类型定义 5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现 5.4 广义表的类型定义广义表的类型定义 5.5 广义表的表示方法广义表的表示方法 5.6 广义表操作的递归函数广义表操作的递归函数 第1页/共112页 3 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

2、 ADT Array 基本操作基本操作: 第2页/共112页 4 二维数组的定义二维数组的定义: 数据对象数据对象: : D = aij | 0ib1-1, 0 jb2-1 数据关系数据关系: : R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2 第3页/共112页 5 InitArray( 2) 数组是多维的结构，而存储空间是数组是多维的结构，而存储空间是 一个一维的结构。一个一维的结构。 有两种顺序映象的方式有两种顺序映象的方式: 1)以行序为主序以行序为主序(低下标优先低下标优先); 2)以列序为主序以列序为主序(高下

3、标优先高下标优先); 第9页/共112页 11 例如：例如： 称为基地址或基址。称为基地址或基址。 以以“行序为主序行序为主序”的存储映象的存储映象 二维数组二维数组A中任一元素中任一元素ai,j 的存储位置的存储位置 LOC(i,j) = LOC(0,0) + (b2ij) a0, 1 a0, 0 a0, 2 a1, 0 a1, 1 a1, 2 a0,1a0,0a0,2a1,0a1,1a1,2 L L 第10页/共112页 12 推广到一般情况，可得到推广到一般情况，可得到 n 维数组数据维数组数据 元素存储位置的映象关系元素存储位置的映象关系 称为称为 n 维数组的映象函数。数组元素维数组

4、的映象函数。数组元素 的存储位置是其下标的线性函数的存储位置是其下标的线性函数 其中其中 cn = L，ci-1 = bi ci , 1 i n。 LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i= 1 n 第11页/共112页 13 假设假设 m 行行 n 列列的矩阵含的矩阵含 t 个非零元素个非零元素， 则称则称 为为稀疏因子稀疏因子 通常认为通常认为 0.05 的矩阵为稀疏矩阵的矩阵为稀疏矩阵 nm t 何谓稀疏矩阵？何谓稀疏矩阵？ 第12页/共112页 14 以常规方法，即以二维数组表示以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题高阶

5、的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间零值元素占了很大空间; 2) 计算中进行了很多和零值的运算，计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零遇除法，还需判别除数是否为零; 第13页/共112页 15 1) 尽可能少存或不存零值元素尽可能少存或不存零值元素; 解决问题的原则解决问题的原则: 2) 尽可能减少没有实际意义的运算尽可能减少没有实际意义的运算; 3) 操作方便操作方便; 即即: 能尽可能快地找到与能尽可能快地找到与 下标值下标值(i,j)对应的元素对应的元素; 能尽可能快地找到同能尽可能快地找到同 一行或同一列的非零值元一行或同一列的非零值元; 第14页

6、/共112页 16 1) 特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则非零元在矩阵中的分布有一定规则 例如例如: 三角矩阵三角矩阵 对角矩阵对角矩阵 2) 随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现非零元在矩阵中随机出现 第15页/共112页 17 下三角中的元素，让每两个对称的 元素共享一个存储空间，这样，能 节约近一半的存储空间。不失一般 性，我们按“行优先 第16页/共112页 18 2 ) 1( 1 nn i n i 第17页/共112页 19 之间找一个对应关系。 若ij，则ai j在下三角形中。 ai j之前的i-1行 （从第1行到第i-1行）一共有1+2+(i-1)=i

7、(i- 1)/2个元素，在第i行上， ai j之前恰有j-1个元素 （即ai1,ai2,aij-1），因此有： k=i*(i-1)/2+j-1 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所 以只要交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关 系可统一为： k=I*(I-1)/2+J-1 0 kn(n+1)/2 第18页/共112页 20 因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=

8、LOC(sa0+I*(I-1)/2+J-1*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 例如a32和a23均存储在 sa4中，这是因为 k=I*(I-1)/2+J-1=3*(3-1)/2+2-1=4 a11a21a22a31an 1 ann 第19页/共112页 21 2、三角矩阵、三角矩阵 以主对角线划分，三角矩阵

9、有上三角和下三角两种以主对角线划分，三角矩阵有上三角和下三角两种 。 上三角矩阵如图所示，它的下三角（不包括主对角线）上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数，如图所示。在大多数情况下，角线上方均为常数，如图所示。在大多数情况下， 三角矩阵常数为零。三角矩阵常数为零。 a11 a12 a 1 n a11 c c c a22 a 2 n a21 a22 c . c c a n n an1 an 2 an n (a) (a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵

10、图图5.2 5.2 三角矩阵三角矩阵第20页/共112页 22 k= 2 ) 22)(1( ) 1( 1 1 ini pn i p 第21页/共112页 23 k = 第22页/共112页 24 对角矩阵可按行优先顺序或对角矩阵可按行优先顺序或 对角线的顺序，将其压缩存储到对角线的顺序，将其压缩存储到 一个向量中，并且也能找到每个一个向量中，并且也能找到每个 非零元素和向量下标的对应关系。非零元素和向量下标的对应关系。 第23页/共112页 25 a11a12 a21a22a23a32 a n n-1a n n K=0 1 2 3 4 5 3n-2 3n-1 数组数组sa中的元素中的元素sak

11、与三对角带状矩阵中的元素与三对角带状矩阵中的元素 aij存在一一对应关系，在存在一一对应关系，在aij之前有之前有i-1行行,共有共有3*(i-1)- 1个非零元素，在第个非零元素，在第i行，有行，有j-i+1个非零元素，这样个非零元素，这样 ，非零元素，非零元素aij的地址为：的地址为： 第24页/共112页 26 第25页/共112页 27 smsmn n），则称），则称A A为稀疏矩阵。为稀疏矩阵。 第26页/共112页 28 此，稀疏矩阵可由表示非零元的此，稀疏矩阵可由表示非零元的 三元组及其行列数唯一确定。三元组及其行列数唯一确定。 第27页/共112页 29 随机稀疏矩阵的压缩存储

12、方法随机稀疏矩阵的压缩存储方法: 第28页/共112页 30 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e; / 该非零元的值该非零元的值 Triple; / 三元组类型三元组类型 typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; / 行、列和非零元行、列和非零元 数数 TSMatrix; / 稀疏矩阵类型稀疏矩阵类型第29页/共112页 31 如何求转置矩阵？如何求转置矩阵？ 0280036 00070 5001

13、40 005 2800 000 0714 3600 第30页/共112页 32 用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol; 第31页/共112页 33 用用“三元组三元组”表示时如何实现？表示时如何实现？ 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 第32页/共112页 34 首先应该确定每一行的第

14、一个非零首先应该确定每一行的第一个非零 元在三元组中的位置。元在三元组中的位置。 1 2 15 1 5 -5 2 2 -7 3 1 36 3 4 28 col12345 Numpos 12011 Cpotcol 12445 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; 第33页/共112页 35 Status FastTransposeSMatrix (TSMatrix M, TSMatrix T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M

15、.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) return OK; 转置矩阵元素转置矩阵元素 第34页/共112页 36 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 第

16、35页/共112页 37 分析算法分析算法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) 第36页/共112页 38 三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法 ，它的特点是，非零元在表中按行序有，它的特点是，非零元在表中按行序有 序存储，因此序存储，因此便于进行依行顺序处理的便于进行依行顺序处理的

17、 矩阵运算矩阵运算。然而，若需。然而，若需随机随机存取某一行存取某一行 中的非零元，则需从头开始进行查找。中的非零元，则需从头开始进行查找。 第37页/共112页 39 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类行逻辑链接顺序表类 型型 修改前述的稀疏矩阵的结构定义修改前述的稀疏矩阵的结构定义 ，增加一个数据成员，增加一个数据成员rpos, 其值在稀疏其值在稀疏 矩阵的初始化函数中确定。矩阵的初始化函数中确定。

18、 第38页/共112页 40 例如例如：给定一组下标，求矩阵的元素值给定一组下标，求矩阵的元素值 ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r if (M.datap.i=r else return 0; 第39页/共112页 41 矩阵乘法的经典算法矩阵乘法的经典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为其时间复杂度为: O(m1n2n1)

19、 第40页/共112页 42 Q初始化初始化; if Q是非零矩阵是非零矩阵 / 逐行求积逐行求积 for (arow=1;arow=M.mu;+arow) / 处理处理M的每一行的每一行 ctemp = 0; / 累加器清零累加器清零 计算计算Q中第中第arow行的积并存入行的积并存入ctemp中中 ； 将将ctemp 中非零元压缩存储到中非零元压缩存储到Q.data； 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N） 的过程可大致描述如下：的过程可大致描述如下： 第41页/共112页 43 Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSM

20、atrix Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 return OK; 第42页/共112页 44 ctemp = 0; / 当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元对当前行中每一个非零元 brow=M.datap.j; if (brow N.nu ) t = N.rposbro

21、w+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在乘积元素在Q中列号中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得求得Q中第中第crow( =arow)行的非零元行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; 处理 的每一行 M 第43页/共112页 45 分析上述算法的时间复杂度分析上述算法的时间复杂度 累加器ctemp初

22、始化初始化的时间复杂度为(M.muN.nu)， 求求Q的所有非零元的所有非零元的时间复杂度为(M.tuN.tu/N.mu) ， 进行压缩存储压缩存储的时间复杂度为(M.muN.nu)， 总时间复杂度是总时间复杂度是 (M.mu N.nu+M.tu N.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 p-col时，时，p和和q右右 移移 (2)插入：插入： a. 若若p=NULL且且q=NULL，即本行

23、空，即本行空，则，则rhr-1=s; b. 若若p=NULL,q!=NULL，即走到行末，则即走到行末，则q-right=s c. 若若c=p-col，则修改则修改p-val d. 若若ccol且且q=NULL，则在则在p之前插入之前插入s， 即即s是行链表中第一个结点，令是行链表中第一个结点，令rhr-1=s; s- right=p; e. 若若ccol且且q!=NULL，则在则在p之前插入之前插入s， 即即 s-right=p; q-right=s; 算法分析算法分析： T(n) = O(ts) 其中，其中，t为为非零元个数，非零元个数，s= max(m,n) 第49页/共112页 51

24、4 1 8 2 3 4 m=4,n=3 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7 11 3 2 1 7 2 2 5 第50页/共112页 52 ADT GList 数据对象数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in 基本操作基本操作: ADT GList 第51页/共112页 53 广义表是递归递归定义的线性结构线性结构， LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表 例如例如: A = ( ) F = (d, (

25、e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ) 第52页/共112页 54 广义表是一个多层次多层次的线性结构线性结构 例如： D=(E, F) 其中: E=(a, (b, c) F=(d, (e) D EF a( )d( ) bc e 第53页/共112页 55 广义表广义表 LS = ( 1, 2, , n )的结构特点的结构特点: 1) 广义表中的数据元素有相对次序次序; 2) 广义表的长度长度定义为最外层包含元素个数; 3) 广义表的深度深度定义为所含括弧的重数; 注意:“原子”的深度为 0 ; “空

26、表”的深度为 1 。 4) 广义表可以共享共享; 5) 广义表可以是一个递归递归的表; 递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值 。 第54页/共112页 56 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( (

27、 b, c) ) = ( b, c) Tail( ( b, c) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) 第55页/共112页 57 结构的创建和销毁结构的创建和销毁 InitGList( DestroyGList( CreateGList( CopyGList( 基本操作基本操作 状态函数状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入

28、和删除操作 InsertFirst_GL( DeleteFirst_GL( 遍历遍历 Traverse_GL(L, Visit(); 第56页/共112页 58 头、尾指针的链表结构 表结点表结点: tag=1 hp tp 原子结点：原子结点： tag=0 data 第57页/共112页 59 1) 空表 ls= NULL 非空表 ls 1 表尾 表头 构造存储结构的两种分析方法构造存储结构的两种分析方法: : 若表头为原子，则为 0 data 否则，依次类推。 第58页/共112页 60 例如例如: L=(a, (x, y), (x) ) a (x, y), (x) ) (x, y) ( (

29、x) ) x (y) (x) ( ) y ( ) (x) ( ) x ( ) 第59页/共112页 61 L=(a, (x, y), (x) L (x, y), (x) (x) 1 1 a (x, y) 第60页/共112页 62 2) 空表 ls = NULL 非空表 LS=(1, 2, , n) ls 1 1 1 子表1 子表2 子表n 若子表为原子，则为 0 data 否则，依次类推。 第61页/共112页 63 例如例如: a (x, y) (x) LS=( a, (x,y), (x) ) 第62页/共112页 64 递归函数递归函数 一个含直接或间接调用本函数语句含直接或间接调用本函

30、数语句 的函数被称之为递归函数，它必须满足 以下两个条件: 1)在每一次调用自己时，必须是(在某种 意义上)更接近于解更接近于解; 2)必须有一个终止终止处理或计算的准则准则。 第63页/共112页 65 例如例如: : 梵塔的递归函数 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); 第64页/共112页 66 二叉树的遍历二叉树的遍历 void PreOrderTraverse( Bi

31、Tree T, void (Visit*)(BiTree P) if (T) Visit(T-data); PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); 第65页/共112页 67 一一. 分治法分治法 (Divide and Conquer) (又称分割求解法又称分割求解法) 如何设计递归函数如何设计递归函数？ 二二. 后置递归法后置递归法(Postponing the work) 三三. 回溯法回溯法(Backtracking) 第66页/共112页 68 对于一个对于一个输入规模为输入规模为 n

32、 的函数或问题，的函数或问题， 用某种方法把输入用某种方法把输入分割成分割成 k(1ptr.tp) dep = GListDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; if (!L) return 1; if (L-tag = ATOM) return 0; 第75页/共112页 77 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 pppp

33、 pp-ptr.hppp-ptr.hp 第76页/共112页 78 例二例二 复制广义表复制广义表 新的广义表由新的表头和表尾构成。新的广义表由新的表头和表尾构成。 可以直接求解的两种简单情况为: 空表复制求得的新表自然也是空表空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分， 分别(递归)复制求得新的表头和表尾， 第77页/共112页 79 若若 ls= NULL 则则 newls = NULL 否则否则 构造结点构造结点 newls, 由由 表头表头ls-ptr.hp 复制得复制得 newhp 由由 表尾表尾 ls-pt

34、r.tp 复制得复制得 newtp 并使并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp 复制求广义表的算法描述如下复制求广义表的算法描述如下: 第78页/共112页 80 Status CopyGList(GList / 复制空表 else if ( !(T = (GList)malloc(sizeof(GLNode) ) exit(OVERFLOW); / 建表结点 T-tag = L-tag; if (L-tag = ATOM) T-atom = L-atom; / 复制单原子结点 else return OK; 分别复制表头和表尾分别复制表头和

35、表尾 第79页/共112页 81 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; 第80页/共112页 82 例三例三 创建广义表的存储结构创建广义表的存储结构 对应广义表的不同不同定义方法 相应地有不同不同的创建存储结构

36、的算法。 第81页/共112页 83 假设以字符串 S = (1, 2, , n ) 的形 式定义广义表 L，建立相应的存储结构。 由于由于S中的每个子串中的每个子串 i定义定义 L 的一个的一个子表子表， 从而产生从而产生 n 个子问题，即分别由这个子问题，即分别由这 n个子串个子串 ( 递归递归)建立建立 n 个子表，再个子表，再组合组合成一个广义表。成一个广义表。 可以直接求解的两种简单情况为: 由串由串 ( ) 建立的广义表是建立的广义表是空表空表; 由单字符建立的子表只是一个原子结点由单字符建立的子表只是一个原子结点 。 第82页/共112页 84 首先分析广义表和子表在存储结构中首

37、先分析广义表和子表在存储结构中 的关系。的关系。 先看第一个子表和广义表的关系先看第一个子表和广义表的关系: 1 L 指向第一个指向第一个 子表的头指针子表的头指针 第83页/共112页 85 再看相邻两个子表之间的关系再看相邻两个子表之间的关系: 1 1 指向第指向第i+1个个 子表的头指针子表的头指针 指向第指向第i个个 子表的头指针子表的头指针 可见，两者之间通过表结点相链接。可见，两者之间通过表结点相链接。 第84页/共112页 86 若若 S = ( ) 则则 L = NULL 否则 构造第一个表结点 *L, 并从串S中分解出第一个子串1, 对 应 创建第一个子广义表 L-ptr.h

38、p; 若剩余串非空，则构造第二个表结点 L-ptr.tp, 并从串S中分解出第二个子 串 2, 对应建第二个子广义表 ; 依次类推，直至剩余串为空串止。 第85页/共112页 87 void CreateGList(Glist / 创建空表 else L=(Glist) malloc(sizeof(GLNode); L-tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); /脱去串S的外层括弧 / else 第86页/共112页 88 do sever(sub, hsub); / 分离出子表串hsub=i if (!StrEmpty(sub) p-

39、ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一个子表的表结点*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub); p-ptr.tp = NULL; / 表尾为空表 创建由串创建由串hsub定义的广义表定义的广义表p-ptr.hp; 第87页/共112页 89 if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 创建单原子结点 else CreateGList(p-p

40、tr.hp, hsub); /递归建广义表递归建广义表 第88页/共112页 90 假如某个问题的求解过程可以分成 若干步进行，并且当前这一步的解可 以直接求得，则先先求求出出当当前前这这一一步步的的 解解，对于余余下下的的问问题题，若问题的性质 和原问题类似，则又可递递归归求求解解。 第89页/共112页 91 递归的终结状态终结状态是，当前的问题可 以直接求解直接求解，对原问题而言，则是已走 到了求解的最后一步最后一步。 链表是可以如此求解的一个典型例子 。 例如:编写“ ”的算法。 第90页/共112页 92 1) 单链表是一种顺序结构，必须从第 一个结点起，逐个检查每个结点的数 据元素

41、; 分析分析: 2) 从另一角度看，链表又是一个递归 结构，若 L 是线性链表 (a1, a2, , an) 的头指针，则 L-next是线性链表 (a2, , an)的头指针。 第91页/共112页 93 a1 a2 a3 an L 例如例如: a1 a2 a3 an L a1 a2 a3 an L 已知下列链表已知下列链表 1) “a1=x”, 则 L 仍为删除 x 后的链表头指针 2) “a1x”, 则余下问题是考虑以 L-next 为头 指针的链表 L a1 L-next L-next=p-next p 第92页/共112页 94 void delete(LinkList L-next

42、=p-next; free(p); delete(L, x); else delete(L-next, x); 第93页/共112页 95 删除广义表中所有元素为删除广义表中所有元素为x x的原子结点的原子结点 分析分析: : 比较广义表和线性表的结构特点比较广义表和线性表的结构特点: : 相似处相似处: :都是链表结构。都是链表结构。 不同处不同处: :1)1)广义表的数据元素可能还是个广义表的数据元素可能还是个 广义表广义表; ; 2) 2)删除时，不仅要删除原子结点，删除时，不仅要删除原子结点， 还需要删除相应的表结点。还需要删除相应的表结点。 第94页/共112页 96 void De

43、lete_GL(Glist / 考察第一个子表 if (head-tag = Atom L = L-ptr.tp; / 修改指针 free(head); / 释放原子结点 free(p); / 释放表结点 Delete_GL(L, x); / 递归处理剩余表项 1 L 0 x 1 p L head 第96页/共112页 98 if (head-tag = LIST) /该项为广义 表 Delete_GL(head, x); Delete_GL(L-ptr.tp, x); / 递归处理剩余表项 1 L 0 a 1 1 head L-ptr.tp 第97页/共112页 99 回溯法回溯法是一种是一

44、种“穷举穷举”方法。方法。 其基本思想为其基本思想为: 假设问题的解为假设问题的解为 n 元组元组 (x1, x2, , xn)， 其中其中 xi 取值于集合取值于集合 Si。 n 元组的子组元组的子组 (x1, x2, , xi) (in)的一个合法布局的一个合法布局 / 时，输出之。时，输出之。 if (in) 输出棋盘的当前布局输出棋盘的当前布局; else for (j=1; jn) ; else while ( ! Empty(Si) 从从 Si 中取中取 xi 的一个值的一个值 vi Si; if (x1, x2, , xi) 满足约束条件满足约束条件 B( i+1, n); / 继续求下一个部分解继续求下一个部分解 从从 Si 中删除值中删除值 vi; 第102页/共112页 104 综合几点：综合几点