第五部分数组和广义表教学ppt课件

1、第五章第五章 数组和广义表数组和广义表 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表第五章第五章 数组和广义表数组和广义表5.1 数组的定义数组的定义5.3 矩阵的紧缩存储矩阵的紧缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的定义广义表的定义5.5 广义表的存储构造广义表的存储构造 5.6 m元多项式的表示元多项式的表示 5.7 广义表的递归算法广义表的递归算法第五章第五章 数组和广义表数组和广义表5.1 数组的定义数组特点数组特点数组构造固定数组构造固定数据元素同构数据元素同构数组运算数组运算给定一组下标，存取相应的数据元素给定一组下标，存取

2、相应的数据元素给定一组下标，修正数据元素的值给定一组下标，修正数据元素的值( )( )( )( )( )aj = (a0j,a1j, , am-1j)( )( )( )( )ai = (ai0,ai1, , ain-1)数组的定义=m* nAm-1n-1m-1n-2n-1aaaaaa.1111001a00a10am-10笼统数据类型数组的定义如下：笼统数据类型数组的定义如下：ADT List ADT List 数据对象：数据对象：数据关系：数据关系：D D a | n(n0) a | n(n0)称为数组的维数，称为数组的维数，bibi是是 数组第数组第i i维的长度，维的长度，jiji是数组元

3、素的第是数组元素的第i i维维 下标下标a ElemSet a ElemSet ji =0,.,bi -1, ji =0,.,bi -1, i=1,2,.,n i=1,2,.,n j1j2jnj1j2jnR1R1 | | 0 0 jk jk bk -1, 1 bk -1, 1 k k n n 且且k k i, i, 0 0 ji ji bi -2, i=2,.,n, 0 bi -2, i=2,.,n, 0 ji ji bi -2, bi -2,j1 jijnj1 ji+1jn数组的定义数组的定义二维数组的定义二维数组的定义:数据对象数据对象: : D = aij | 0ib1-1, 0 jb2

4、-1 D = aij | 0ib1-1, 0 jb2-1数据关系数据关系: : R = ROW, COL R = ROW, COL ROW = | 0ib1-2, ROW = | 0ib1-2, 0jb2-10jb2-1 COL = | 0ib1-1, 0 COL = | 0ib1-1, 0 jb2-2jb2-2InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)根本操作：根本操作：数组的

5、定义=m* nAm-1n-1m-1n-2n-1aaaaaa.1111001a00a10am-10数组的定义有两种顺序映象的方式有两种顺序映象的方式:以行序为主序以行序为主序(低下标优先低下标优先)以列序为主序以列序为主序(高下标优先高下标优先)数组的顺序表示和实现数组的顺序表示和实现Loc( aij)=Loc(a00)+i*n+j*l 按行序为主序存放按行序为主序存放 am-10am-11 . am-1n-1 a00 a01 . a0n-1 a10 a11 . a0n-1 .n-1 am-1n-1 . am-10 am-10 . a1n-1 . a11 a10 a0n-1 . a01 a000

6、1m*n-1n数组的顺序表示和实现数组的顺序表示和实现 按列序为主序存放按列序为主序存放01m-1m*n-1m am-1n-1 . a1n-1 a0n-1 . am-11 . a11 a01 am-10 . a10 a00 a00 a01 . a0n-1 a10 a11 . a1n-1 am-10am-11 am-1n-1 .Loc(aij)=Loc(a00)+j*m+i*l 数组的顺序表示和实现数组的顺序表示和实现4.3 矩阵的紧缩存储特殊矩阵特殊矩阵 所谓特殊矩阵是指非零元素或零元素的所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊分布有一定规律的矩阵，下面我们

7、讨论几种特殊矩阵的紧缩存储。矩阵的紧缩存储。1 1、对称矩阵、对称矩阵 在一个在一个n n阶方阵阶方阵A A中，假设元素满足下中，假设元素满足下述性质：述性质： aij=aji 0 aij=aji 0i,ji,jn-1n-1那么称那么称A A为对称矩阵。为对称矩阵。矩阵的紧缩存储 a00 a01 . . a0n-1 a10 a11 . . a1n-1 an-10 an-11 . an-1n-1 . 元素总数为元素总数为: : n(n+1)/2n(n+1)/2将这些元素存放在一个向量将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中中矩阵的紧缩存储aijaij和和

8、saksak之间对应关系之间对应关系 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)/2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：矩阵的紧缩存储a11 a21 a22 a31 a32 an1 ann .k=

9、0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：ij 那么那么aij是在上三角矩阵中。由于是在上三角矩阵中。由于aij=aji，所以只需交换上述对应关系式中的所以只需交换上述对应关系式中的i和和j即可得即可得到：到： k=j*(j+1)/2+i 0 k(k-1)/2 (k-1)/2 ，那么元素，那么元素 aij=0 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，对角矩阵可按行优先顺序或对角线的顺序，将其紧缩存储到一个向量中，并且也能找到每个将其紧缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。非零元素和向量下标的对应关系。Loc(

10、aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：矩阵的紧缩存储假设 m 行 n 列的矩阵含 t 个非零元素，那么称 为稀疏因子。通常以为 0.05 的矩阵为稀疏矩阵。nmt稀疏矩阵稀疏矩阵7600070015000001800000240001400003000000000009120M矩阵的紧缩存储7600070015000001800000240001400003000000000009120MM由(1,2,12), (1,3,9), (3,1,

11、-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数6,7独一确定定义：非零元较零元少，且分布没有一定规律的矩阵定义：非零元较零元少，且分布没有一定规律的矩阵紧缩存储原那么：只存矩阵的行列维数和每个非零元的紧缩存储原那么：只存矩阵的行列维数和每个非零元的行列下标及其值行列下标及其值矩阵的紧缩存储稀疏矩阵的紧缩存储方法稀疏矩阵的紧缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字链表矩阵的紧缩存储三元组表所需存储单元个数为三元组表所需存储单元个数为3(t+1)其中其中t为

12、非零元个数为非零元个数6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分别存放分别存放矩阵行列维数和非零元个数矩阵行列维数和非零元个数行列下标行列下标非零元值非零元值7600070015000001800000240001400003000000000009120M三元组顺序表三元组顺序表矩阵的紧缩存储 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标该非零元的行下标和

13、列下标 ElemType e; / 该非零元的值该非零元的值 Triple; / 三元组类型三元组类型typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型矩阵的紧缩存储 求转置矩阵求转置矩阵 问题描画：知一个稀疏矩阵的三元组表，问题描画：知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表求该矩阵转置矩阵的三元组表 问题分析问题分析 普通矩阵转置算法：普通矩阵转置算法：for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol;T(n)

14、=O(mn)矩阵的紧缩存储 其时间复杂度为其时间复杂度为: O(munu)7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5

15、6 7 8mb?矩阵的紧缩存储处理思绪：只需做到处理思绪：只需做到 将矩阵行、列维数互换将矩阵行、列维数互换 将每个三元组中的将每个三元组中的i i和和j j互相互换互相互换 重排三元组次序，使重排三元组次序，使mbmb中元素以中元素以N N的行的行(M(M的的列列) )为主序为主序方法一：按方法一：按M的列序转置的列序转置 即按即按mb中三元组次序依次在中三元组次序依次在ma中找到相中找到相应的三元组进展转置。应的三元组进展转置。 为找到为找到M中每一列一切非零元素，需对其中每一列一切非零元素，需对其三元组表三元组表ma从第一行起扫描一遍。由于从第一行起扫描一遍。由于ma中中以以M行序为主序

16、行序为主序,所以由此得到的恰是所以由此得到的恰是mb中应中应有的顺序有的顺序矩阵的紧缩存储)()(2nmOnT算法分析：T(n)=O(M的列数n非零元个数t) 假设 t 与mn同数量级，那么矩阵的紧缩存储6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1co

17、l=2矩阵的紧缩存储方法二：快速转置方法二：快速转置 即按即按mama中三元组次序转置，转置结果放入中三元组次序转置，转置结果放入b b中中恰当位置恰当位置 此法关键是要预先确定此法关键是要预先确定M M中每一列第一个非零中每一列第一个非零元在元在mbmb中位置，为确定这些位置，转置前应先求得中位置，为确定这些位置，转置前应先求得M M的每一列中非零元个数的每一列中非零元个数 实现：设两个数组实现：设两个数组numcolnumcol：表示矩阵：表示矩阵M M中第中第colcol列中非零元个数列中非零元个数cpotcolcpotcol：指示：指示M M中第中第colcol列第一个非零元在列第一个

18、非零元在mbmb中位置中位置显然有：显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col a.nu)矩阵的紧缩存储1357889colnumcolcpotcol122232415061707600070015000001800000240001400003000000000009120MStatus FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / FastTransposeSMatrix矩阵的紧缩存储T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) /

19、if return OK;for (col=1; col=M.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) 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为: O(M.nu+M.tu): O(M.nu+M.tu)for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t)

20、for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 矩阵的紧缩存储6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753矩阵的紧缩存储 三元组顺序表又称有序的双下

21、标法，它的特点是，三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进展依行顺非零元在表中按行序有序存储，因此便于进展依行顺序处置的矩阵运算。然而，假设需随机存取某一行中序处置的矩阵运算。然而，假设需随机存取某一行中的非零元，那么需从头开场进展查找。的非零元，那么需从头开场进展查找。行逻辑联接的顺序行逻辑联接的顺序表表链式存储构造链式存储构造带行指针向量的单链表表示带行指针向量的单链表表示每行的非零元用一个单链表存放每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非设置一个行指针数组，指向本行第一个非零元结点；假设本行无非零元，那么指针零元结点；假

22、设本行无非零元，那么指针为空为空表头结点与单链表结点类型定义表头结点与单链表结点类型定义矩阵的紧缩存储 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型行逻辑链接顺序表类型0200000000000210010070003A1 35 73 -11 -12 -24 2需存储单元个数为3t+m矩阵的紧缩存储例如：给定一组下标，求矩阵的元素值例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatri

23、x M, int r, int c) p = M.rposr; while (M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; else return 0; / 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(m1n2n1)矩阵的紧缩存储 Q Q初始

24、化；初始化； if Qif Q是非零矩阵是非零矩阵 / / 逐行求积逐行求积 for (arow=1; arow=M.mu; +arow) for (arow=1; arow=M.mu; +arow) / / 处置处置M M的每一行的每一行 ctemp = 0; / ctemp = 0; / 累加器清零累加器清零 计算计算Q Q中第中第arowarow行的积并存入行的积并存入ctemp ctemp 中；中； 将将ctemp ctemp 中非零元紧缩存储到中非零元紧缩存储到Q.dataQ.data； / for arow / for arow / if / if 两个稀疏矩阵相乘两个稀疏矩阵相乘

25、QMN 的过程可大致描画如下：的过程可大致描画如下：矩阵的紧缩存储 Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) / MultSMatrix矩阵的紧缩存储if (M.nu != N.mu) return ERROR; 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的每一行的每一行 / for arow / if return OK; ctemp

26、= 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元 / 求得Q中第crow( =arow)行的非零元 处置 的每一行M矩阵的紧缩存储brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+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 qfor

27、 (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if矩阵的紧缩存储分析上述算法的时间复杂度分析上述算法的时间复杂度累加器累加器ctempctemp初始化的时间复杂度为初始化的时间复杂度为 (M.mu(M.muN.nu)N.nu)求求Q Q的一切非零元的时间复杂度为的一切非零元的时间复杂度为 (M.tu(M.tuN.tu/N.mu) N.tu/N.mu) 进展紧缩存储的时间复杂度为进展紧缩存储的时间复杂度为 (M.mu(M.muN.nu)N.nu) 总的时间复杂度就是总的时间复杂度就是 (M.

28、mu(M.muN.nu+M.tuN.nu+M.tuN.tu/N.mu)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，即本行空，那么rhr-1=s;b、假设p=NULL,q!=NULL，即走到行末，那么q-right=sc

29、、假设c=p-col，那么修正p-vald、假设ccol且q=NULL，那么在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s; s-right=p;e、假设ccol且q!=NULL，那么在p之前插入s， 即 s-right=p; q-right=s;从键盘接纳信息建立十字链表算法从键盘接纳信息建立十字链表算法矩阵的紧缩存储418234m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225矩阵的紧缩存储5.4 5.4 广义表的定义广义表的定义 广义表广义表Lists，又称列表是线性表的推行。，又称列表是线性表的推行。 广义表是广义表是n(n=0)个元素个元

30、素a1,a2,a3,an的有限序的有限序列，其中列，其中ai或者是原子项，或者是一个广义表。通常或者是原子项，或者是一个广义表。通常记作记作:广义表的定义广义表的定义LS=a1,a2,a3,an) LS是广义表的名字，是广义表的名字，n为它的长度。假设为它的长度。假设ai是广义是广义表，那么称它为表，那么称它为LS的子表。的子表。 假设广义表假设广义表LSn=1)非空，那么非空，那么a1是是LS的表头，的表头，其他元素组成的表其他元素组成的表(a1,a2,an)称为称为LS的表尾。表尾的表尾。表尾ADT Glist 数据对象：数据对象：Dei | i=1,2,.,n; n0; eiAtomSe

31、t 或或 eiGList, AtomSet为某个数据对象为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in广义表的定义广义表的定义 ADT Glist 构造的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 形状函数形状函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L,

32、 e); DeleteFirst_GL(&L, &e); 遍历遍历 Traverse_GL(L, Visit();根本操作：根本操作：广义表的定义广义表的定义广义表是递归定义的线性构造，广义表是递归定义的线性构造， 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

33、, F)其中其中: : E=(a, (b, c) E=(a, (b, c) F=(d, (e) F=(d, (e)DEFa( )d( )bce广义表的定义广义表的定义广义表广义表 LS = ( 1, 2, , n )的构造特点的构造特点:1) 广义表中的数据元素有相对次序；广义表中的数据元素有相对次序；2) 广义表的长度定义为最外层包含元素个数；广义表的长度定义为最外层包含元素个数；3) 广义表的深度定义为所含括弧的重数；广义表的深度定义为所含括弧的重数； 留意：留意：“原子的深度为原子的深度为 0 “空表的深度为空表的深度为 1 4) 广义表可以共享；广义表可以共享；5) 广义表可以是一个递

34、归的表。广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。递归表的深度是无穷值，长度是有限值。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)

35、 Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )广义表的定义广义表的定义5.5 5.5 广义表的存储构造广义表的存储构造通常采用头、尾指针的链表构造通常采用头、尾指针的链表构造表结点表结点: :原子结点：原子结点：tag=1 hp tptag=0 atom广义表的存储构造广义表的存储构造typedef enum ATOM,LIST ElemTag; / ATOM = 0:原子，原子，LIST=1：子表：子表广义表的存储构造广义表的存储构造t

36、ypedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp,*top ptr; ; *Glist; 1) 表头、表尾分析法：表头、表尾分析法：构造存储构造的两种分析方法构造存储构造的两种分析方法: :假设表头为原子，那么为假设表头为原子，那么为空表空表 ls=NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 atom否那么，依次类推。否那么，依次类推。广义表的存储构造广义表的存储构造 L=(a, (x, y), (x) ) a (x, y), (x) ) (x, y)

37、( (x) ) x (y) (x) ( )y ( ) (x) ( )x ( )例如例如:L=(a, (x, y), (x) ) 1 L0 a 1 1 1 1 1 0 a 广义表的存储构造广义表的存储构造2) 2) 子表分析法：子表分析法：假设子表为原子，那么为假设子表为原子，那么为空表空表 ls=NIL非空表非空表 1 指向子表1 的指针tag=0 data否那么，依次类推。否那么，依次类推。 1 指向子表2 的指针 1 指向子表n 的指针ls 广义表的存储构造广义表的存储构造例如例如: a (x, y) (x) LS=( a, (x,y), (x) )ls广义表的存储构造广义表的存储构造5.

38、7 5.7 广义表的递归函数广义表的递归函数递归函数递归函数 一个含直接或间接调用本函数语句的函数被一个含直接或间接调用本函数语句的函数被称之为递归函数，它必需满足以下两个条件：称之为递归函数，它必需满足以下两个条件：1)在每一次调用本人时，必需是在每一次调用本人时，必需是(在某在某 种意义上种意义上)更接近于解更接近于解;2)必需有一个终止处置或计算的准那么。必需有一个终止处置或计算的准那么。例如例如: : 梵塔的递归函数梵塔的递归函数void hanoi (int n, char x, char y, char z) if (n=1) move(x, 1, z); else hanoi(n

39、-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); 如何设计递归函数？如何设计递归函数？二、后置递归法二、后置递归法(Postponing the work)三、回溯法三、回溯法(Backtracking)一、分治法一、分治法 (Divide and Conquer) (又称分割求解法又称分割求解法) 对于一个输入规模为对于一个输入规模为 n n 的函数或问题，的函数或问题，用某种方法把输入分割成用某种方法把输入分割成 k(1kn) k(1ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max

40、= dep; return max + 1; / GlistDepthif (!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; 例如例如:pppp-ptr.hppppppp-ptr.hp例二例二 复制广义表复制广义表新的广义表由新的表头和表尾构成。新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。

41、 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，假设假设 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 (

42、 !(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.hpCopyGList(T-ptr.tp, L-ptr.tp); / 复制求得表尾复制求得表尾

43、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指向广义表指向广义表的头指针的头指针指向第一个指向第一个子表的头指针子表的头指针再看相邻两个子表之间的关