资源描述
第五章第五章 数组和广义表数组和广义表 数组和广义表可看成是数组和广义表可看成是一种特殊的线性表，其特一种特殊的线性表，其特殊在于殊在于:表中的数据元素表中的数据元素本身也是一种线性表本身也是一种线性表 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 D=aij|0ib1-1,0 jb2-1jb2-1数据关系数据关系:R=ROW,COL R=ROW,COL ROW=|0ib1-ROW=|0ib1-2,0jb2-12,0jb2-1 COL=|0ib1-COL=|0ib1-1,0 jb2-21,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)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推行到普通情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中 cn=L，ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n假设 m 行 n 列的矩阵含 t 个非零元素，那么称 为稀疏因子。通常以为 0.05 的矩阵为稀疏矩阵。nmt5.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 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa0.n(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=4a00a10a11a20an-1 0 an-1,n-12、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如下图，它的下三角不包括主对角线中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如下图。在大多数情况下，三角矩阵常数为零。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个，因此，三角矩阵可紧缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第p行(0pjk=下三角矩阵的存储和对称矩阵类似，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-1k=非零元素仅出如今主对角(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。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1K=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由此，我们称sa0.3*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;/稀疏矩阵类型稀疏矩阵类型如何求转置矩阵？如何求转置矩阵？028003600070500140005280000007143600用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;用“三元组表示时如何实现？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28 首先应该确定每一行的第一个非零元在三元组中的位置。1 2 151 5 -52 2 -73 1 363 4 28 col12345Numpos12011Cpotcol12445 cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)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)/if return OK;/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):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&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初始化；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&Q)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;/MultSMatrix 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.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 q /求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol 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)。三、三、十字链表十字链表M.cheadM.rhead3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 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)DEFa()d()bce广义表广义表 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(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);根本操作根本操作 形状函数形状函数 GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和删除操作插入和删除操作 InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍历遍历 Traverse_GL(L,Visit();5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表构造表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data1)表头、表尾分析法：构造存储构造的两种分析方法构造存储构造的两种分析方法:假设表头为原子，那么为假设表头为原子，那么为空表空表 ls=NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否那么，依次类推。否那么，依次类推。例如例如:L=(a,(x,y),(x)a (x,y),(x)(x,y)(x)x (y)(x)()y ()(x)()x ()L=(a,(x,y),(x)a(x,y)()1 LL=()0 a 1 1 1 1 1 0 x ()x2)子表分析法：假设子表为原子，那么为假设子表为原子，那么为空表空表 ls=NIL非空表非空表 1 指向子表1 的指针tag=0 data否那么，依次类推。否那么，依次类推。1 指向子表2 的指针 1 指向子表n 的指针ls 例如例如:a (x,y)(x)LS=(a,(x,y),(x)ls5.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(1ptr.tp)dep=GlistDepth(pp-ptr.hp);if(dep max)max=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.hppp-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&T,Glist L)if(!L)T=NULL;/复制空表复制空表 else if(!(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);/复制求得表尾复制求得表尾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&L,String S)if (空串空串)L=NULL;/创建空表创建空表 else L=(Glist)malloc(sizeof(GLNode);L-tag=List;p=L;sub=SubString(S,2,StrLength(S)-1);/脱去串脱去串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-nextL-next=p-nextp=L-nextvoid delete(LinkList&L,ElemType x)/删除以删除以L为头指针的带头结点的单链表中为头指针的带头结点的单链表中/一切值为一切值为x的数据元素的数据元素 if(L-next)if(L-next-data=x)p=L-next;L-next=p-next;free(p);delete(L,x);else delete(L-next,x);/delete删除广义表中一切元素为删除广义表中一切元素为x x的原子结点的原子结点分析分析:比较广义表和线性表的构造特点：比较广义表和线性表的构造特点：类似处：都是链表构造。类似处：都是链表构造。不同处：不同处：1)1)广义表的数据元素能够还是个广义表的数据元素能够还是个 广义表；广义表；2)2)删除时，不仅要删除原子结点，删除时，不仅要删除原子结点，还需求删除相应的表结点。还需求删除相应的表结点。void Delete_GL(Glist&L,AtomType x)/删除广义表删除广义表L中一切值为中一切值为x的原子结点的原子结点 if(L)head=L-ptr.hp;/调查第一个子表调查第一个子表 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 L0 x 1 pL headif(head-tag=LIST)/该项为广义该项为广义表表 Delete_GL(head,x);Delete_GL(L-ptr.tp,x);/递归处置剩余表项递归处置剩余表项 1 L0 a 1 1 headL-ptr.tp回溯法是一种回溯法是一种“穷举方法。其根本思想为：穷举方法。其根本思想为：假设问题的解为 n 元组(x1,x2,xn)，其中 xi 取值于集合 Si。n 元组的子组(x1,x2,xi)(in)的一的一个合法规划个合法规划 /时，输出之。时，输出之。if(in)输出棋盘的当前规划输出棋盘的当前规划;else for(j=1;jn)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!的递归函数的递归树已退化为一个的递归函数的递归树已退化为一个单枝树单枝树;而计算斐波那契递归函数的递归树中而计算斐波那契递归函数的递归树中有很多反复出现的结点。有很多反复出现的结点。nn-110。F5F4F3F3F2F2F1F1F0F1F0。4.递归函数中的尾递归容易消除。递归函数中的尾递归容易消除。例如：先序遍历二叉树可以改写为：例如：先序遍历二叉树可以改写为：void PreOrderTraverse(BiTree T)While(T)Visit(T-data);PreOrderTraverse(T-lchild);T=T-rchild;/PreOrderTraversevoid delete(LinkList&L,ElemType x)/L为无头结点的单链表的头指针为无头结点的单链表的头指针 if(L)if(L-data=x)p=L;L=L-next;free(p);delete(L,x);else delete(L-next,x);又如又如:void delete(LinkList&L,ElemType x)/L为带头结点的单链表的头指针为带头结点的单链表的头指针 p=L-next;pre=L;while(p)if(p-data=x)pre-next=p-next;free(p);p=pre-next;else pre=p;p=p-next;可改写为可改写为 5.可以用递归方程来表述递归函数的可以用递归方程来表述递归函数的 时间性能。时间性能。例如例如:假设解假设解n个圆盘的梵塔的执行个圆盘的梵塔的执行 时间为时间为T(n)那么递归方程为：那么递归方程为：T(n)=2T(n-1)+C，初始条件为：初始条件为：T(0)=01.1.了解数组的两种存储表示方法，了解数组的两种存储表示方法，并掌握数组在以行为主的存储构造并掌握数组在以行为主的存储构造中的地址计算方法。中的地址计算方法。2.2.掌握对特殊矩阵进展紧缩存储时掌握对特殊矩阵进展紧缩存储时的下标变换公式。的下标变换公式。3.3.了解稀疏矩阵的两类紧缩存储方了解稀疏矩阵的两类紧缩存储方法的特点和适用范围，领会以三元法的特点和适用范围，领会以三元组表示稀疏矩阵时进展矩阵运算采组表示稀疏矩阵时进展矩阵运算采用的处置方法。用的处置方法。4.4.掌握广义表的构造特点及其存掌握广义表的构造特点及其存储表示方法，读者可根据本人的习储表示方法，读者可根据本人的习惯熟练掌握恣意一种构造的链表，惯熟练掌握恣意一种构造的链表，学会对非空广义表进展分解的两种学会对非空广义表进展分解的两种分析方法：即可将一个非空广义表分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解分解为表头和表尾两部分或者分解为为n n个子表。个子表。5.5.学习利用分治法的算法设计思学习利用分治法的算法设计思想编制递归算法的方法。想编制递归算法的方法。
展开阅读全文