数组和广义表新幻灯片.ppt

《数组和广义表新幻灯片.ppt》由会员分享，可在线阅读，更多相关《数组和广义表新幻灯片.ppt（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数组和广义表新第1页，共120页，编辑于2022年，星期六5.1 数组的定义数组的定义5.3 矩阵的压缩存储矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构5.7 广义表操作的递归函数广义表操作的递归函数5.6 m m元多项式的表示元多项式的表示本章主要内容：本章主要内容：第2页，共120页，编辑于2022年，星期六5.1 数组的定义数组的定义ADT Array 数据对象数据对象：Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n n(0)称为数组的维数，bi是数组第i维的长度，ji

2、是数组元素的第i维下标，数据关系数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n 基本操作基本操作:ADT Array 第3页，共120页，编辑于2022年，星期六二维数组的定义二维数组的定义:数据对象数据对象: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)

3、Assign(&A,e,index1,.,indexn)第4页，共120页，编辑于2022年，星期六 InitArray(&A,n,bound1,.,boundn 操作结果：操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：操作结果：销毁数组A。Value(A,&e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若各下标不超界，则e赋值为所指定的A 的元素值，并返回OK。第5页，共120页，编辑于2022年，星期六 Assign(&A,e,index1,.,i

4、ndexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。第6页，共120页，编辑于2022年，星期六5.2 数组的顺序表示和实现数组的顺序表示和实现 类型特点类型特点:1）只有引用型操作，没有加工型操作；2）数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:1）以行序为主序（低下标优先）；2）以列序为主序（高下标优先）。第7页，共120页，编辑于2022年，星期六例如：例如：称为基地址基地址或基址以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中

5、任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)La0,1a0,0a0,2a1,0a1,1a1,2二维数组存储结构a0,1a0,0a0,2a1,0a1,1a1,2L第8页，共120页，编辑于2022年，星期六 推广到一般情况，可得到推广到一般情况，可得到 n 维数组数据元素存储位维数组数据元素存储位置的映象关系置的映象关系 称为 n 维数组的映象函数。数组元素的存储位置是数组元素的存储位置是其下标的线性函数。其下标的线性函数。其中 cn=L，ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n第9页，共1

6、20页，编辑于2022年，星期六/数组的顺序存储表示数组的顺序存储表示#include#include /标准头文件，提供宏标准头文件，提供宏va_startva_start、va_argva_arg和和va_end,va_end,用于存取用于存取变长参数表变长参数表#define MAX_ARRAY_DIM 8#define MAX_ARRAY_DIM 8 /假设数组维数的最大值为假设数组维数的最大值为8 8typedef structtypedef struct ElemType*base;ElemType*base;/数组元素地址，由数组元素地址，由InitArrayInitArray分

7、配分配 int dim;int dim;/数组维数数组维数 int*bounds;int*bounds;/数组维界基址，由数组维界基址，由InitArrayInitArray分配分配 int*constants;int*constants;/数组映像函数常量基址，由数组映像函数常量基址，由InitArrayInitArray分配分配Array;Array;第10页，共120页，编辑于2022年，星期六/基本操作的函数原型说明基本操作的函数原型说明Status InitArray(Array&A,int dimStatus InitArray(Array&A,int dim););/若维数若维数

8、dimdim和随后的各维长度合法，则构造相应的数组和随后的各维长度合法，则构造相应的数组A A，并返回，并返回OKOK。int DestroyArray(Array&A);int DestroyArray(Array&A);/销毁数组销毁数组A A int StrCompare(Array&A,ElemType&e,int StrCompare(Array&A,ElemType&e,)/A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n各下标值。各下标值。/若各下标不超界，则将若各下标不超界，则将e e的值赋给所指定的的值赋给所指定的A A的元素，并返的元素，并返

9、回回OKOK。第11页，共120页，编辑于2022年，星期六/基本操作的算法描述基本操作的算法描述Status InitArray(Array&A,int dim,);/若维数若维数dimdim和随后的各维长度合法，则构造相应的数组和随后的各维长度合法，则构造相应的数组A A，并返回，并返回OKOK。if(dimMAX.ARRAY_DIM)return ERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int);if(!A.bounds)exit(OVERFLOW);/若各维长度合法，则存入若各维长度合法，则存入A.boundsA.bounds，

10、并求出，并求出A A的元素总数的元素总数elemtotalelemtotal elemtotal=1;va_start(ap,dim);/ap为为va_list类型，是存放变长参数表信息的数组类型，是存放变长参数表信息的数组 for(i=0;idim;+i)A.boundsi=va.arg(ap,int);if(A.bounds i=0;-i)A.constantsi=A.boundsi+1 A.constantsi+1;return OK;第13页，共120页，编辑于2022年，星期六Status DestroyArray(Array&A)/销毁数组A if(!A.base)return E

11、RROR;free(A.base);A.base=NULL;if(!A.bounds)return ERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)return ERROR;free(A.constants);A.constants=NULL;return OK;第14页，共120页，编辑于2022年，星期六 Status Locate(Array A,va_list ap,int&off)/若ap指示的各下标值合法，则求出该元素 在A中相对地址off off=0;for(i=0;iA.dim;+i)ind=va_arg(ap,int);i

12、f(ind=A.boundsi)return OVREFLOW;off+=A.constantsi*ind;return OK;第15页，共120页，编辑于2022年，星期六 Status Value(Array A,ElemType&e,)/A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n各下标值。各下标值。/若各下标不超界，则若各下标不超界，则e e赋值为所指定的赋值为所指定的A A的元素的元素 值，并返回值，并返回OKOK va_start(ap,e);if(result=Loate(A,ap,off)=0)return result;e=*(A.base

13、+off);return OK;第16页，共120页，编辑于2022年，星期六 Status Assign(Array&A,ElemType e,)/A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n各下标值。各下标值。/若各下标不超界，则若各下标不超界，则e e赋值为所指定的赋值为所指定的A A的元素值，并返回的元素值，并返回OKOK va_start(ap,e);if(result=Loate(A,ap,off)=0)return result;*(A.base+off)=e;return OK;第17页，共120页，编辑于2022年，星期六5.3 5.3 矩

14、阵的压缩存储矩阵的压缩存储 在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或零元素。有时为节省空间，可以对这类矩阵进行压缩存储压缩存储。假设值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵特殊矩阵；反之，称为稀疏矩阵稀疏矩阵。第18页，共120页，编辑于2022年，星期六 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下

15、标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。第19页，共120页，编辑于2022年，星期六 若n阶矩阵A中的元素满足下述性质 aij=aji 1=i,j=j 对角线下方对角线下方j(j-1)2+i-1 当当ij 对角线上方对角线上方 对于任意给定一组下标(i，j)，均可在sa中找到矩阵元素aij，反之，对所有的k=0,1,2,(n(n+1)/2-1,都能确定sak 中的元在矩阵中的位置(i，j)。由此称san(n+1)/2 为n阶对称矩阵A的压缩存储第21页，共120页，编辑于2022年，星期六 这种压缩存储的方法同样也适应于三角矩阵和对角矩阵。5.3.2 5.3.2

16、稀疏矩阵稀疏矩阵 假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子稀疏因子。通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。何谓稀疏矩阵？何谓稀疏矩阵？nmt=第22页，共120页，编辑于2022年，星期六/稀疏矩阵的三元组顺序表存储表示稀疏矩阵的三元组顺序表存储表示#define MAXSIZE 12500/最大非零元个数 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZ

17、E+1;/非零元三元组表 int mu,nu,tu;/矩阵的行数、列数和非零元个数 TSMatrix;/稀疏矩阵类型稀疏矩阵类型第23页，共120页，编辑于2022年，星期六如何求稀疏矩阵的转置矩阵？如何求稀疏矩阵的转置矩阵？-028003600070500140-005280000007143600转置例如，稀疏矩阵第24页，共120页，编辑于2022年，星期六用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其中，其中，M为原稀疏矩阵，为原稀疏矩阵，T为转置后的稀疏矩阵，为转置后的稀疏矩阵，其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)fo

18、r(row=1;row=mu;+row)Tcolrow=Mrowcol;第25页，共120页，编辑于2022年，星期六用用“三元组三元组”表示时如何实现？表示时如何实现？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28a.datab.data第26页，共120页，编辑于2022年，星期六 假设a和b是TSMatrix型的变量，分别表示矩阵M和T。可以有两种处理方法：（1）按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。换句话说，按照矩阵M的列序来进行转置。为了找到M的每一列中所有的非零元素，需要

19、对其三元组表a.data 从第一行起整个扫描一遍，由于a.data 是以M的行序为主序来存放每个非零元的，由此得到的恰是b.data应有顺序。具体算法如具体算法如5.1所示所示第27页，共120页，编辑于2022年，星期六Status TransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1 for(col=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(m.datap.j=col)T.dataq.i=M.datap

20、.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;/if return OK;/TransposeSMatrix算法算法 5.15.1第28页，共120页，编辑于2022年，星期六 该算法主要工作是在p和col的两重循环中完成的，故算法的时间复杂度为O(nu*tu)O(nu*tu)。当非零元的个数tu和mu*nu同数量级时，算法5.1的时间复杂度就为O(nu*nuO(nu*nu2 2)了。（2）按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中的准确位

21、置，则对a.data中的三元组依次转置时，便可直接放到b.data中恰当的位置上。第29页，共120页，编辑于2022年，星期六 需附设num和cpot两个向量。numcol表示矩阵M中第col列中非零元的个数，cpotcol指示M中第col列的第一个非零元在b.data中的恰当位置。cpot1=1cpot1=1；cpotcol=cpotcol-1+numcol-1cpotcol=cpotcol-1+numcol-1第30页，共120页，编辑于2022年，星期六 例如：例如：下面稀疏矩阵的三元组表示对应各向量值如下：cpot1=1;for(col=2;col=M.nu;+col)cpotcol

22、=cpotcol-1+numcol-1;col12345Numcol12011Cpotcol12445该转置方法称为快速转置，如算法5.2所示。第31页，共120页，编辑于2022年，星期六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;/求M中每一 cpot1=1;/列非零元个数 for(col=2;col=M.nu;+col)cpotc

23、ol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix 转置矩阵元素算法算法 5.25.2第32页，共120页，编辑于2022年，星期六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 转置矩阵元素：第33页，共120页，编辑于2022年，星期六 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为:O(M.nu+M.tu)for(

24、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)第34页，共120页，编辑于2022年，星期六 三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处便于进行依行顺序处理的矩阵运算理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。为便于随机存取某一行中的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵算法中建立的，指示行信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种

25、带行链接信息的三元组表为行逻辑链接的顺序表。二、行逻辑联接的顺序表二、行逻辑联接的顺序表第35页，共120页，编辑于2022年，星期六#define MAXMN 500 typedef struct Triple dataMAXSIZE+1;/非零元三元组表 int rposMAXRC+1;/各行第一个非零元的位置表 int mu,nu,tu;/矩阵的行数、列数和非零元个数 RLSMatrix;/行逻辑链接顺序表类型行逻辑链接的顺序表的类型描述如下：第36页，共120页，编辑于2022年，星期六例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M,int r,

26、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第37页，共120页，编辑于2022年，星期六矩阵乘法的精典算法:for(i=1;i=m1;+i)for(j=1;j=m2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1m2n1)两个矩阵相乘的经典算法。若设 Q=M*N其中，M是m1*n1矩阵，N是n1*m2矩阵，则第38页，共120页，编辑于2022年

27、，星期六（1）乘积矩阵Q中元素 Q(i,j)=M(i,k)*N(k,j)在经典算法中，不论M(i,k)和N(k,j)的值是否为零，都要进行一次乘法运算，这两者有一个为零，其乘积也为零。在对稀疏矩阵进行运算时，应免去这种无效操作。即为求Q的值，只需在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。两个稀疏矩阵相乘两个稀疏矩阵相乘（Q Q M M N N）的过程可大致描述如下：的过程可大致描述如下：若两个矩阵是稀疏矩阵并用三元组表作存储结构时，就不能套用上述算法。第39页，共120页，编辑于2022年，星期六 在稀疏矩阵的行逻辑

28、连接的顺序表中，N.rpos提供了有关信息。rposrow指示矩阵N的第row行中第一个非零元在N.data中的序号，则rposrow+1-1指示矩阵N的第row行中最后一个非零元在N.data中的序号。而最后一行中最后一个非零元在N.data中的序号就是N.tu了。第40页，共120页，编辑于2022年，星期六 （2）稀疏矩阵相乘的基本操作是：对于M.data P(P=1,2M.tu)找到N中所有满足条件M.data P.j=N.data q.i的元素N.data q，求得M.data p.v和N.data q.v 的乘积，这个乘积只是Qij中的一部分。为便于操作，应对每个元素设一累计和变量

29、，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。第41页，共120页，编辑于2022年，星期六 （3）两个稀疏矩阵的乘积不一定是稀疏矩阵。反之，即使每个分量值M(i,k)*N(k,j)不为零，其累加值Qij也可能为零。因此乘积矩阵Q中的元素是否为非零元，只有在求得累加和后才能确定。由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去。第42页，共120页，编辑于2022年，星期六 Q初始化；If(Q是非零矩阵）/逐行求积逐行求积 for(arow

30、=1;arow=M.tu;+arow /处理处理M M每一行每一行 ctemp=0;/累加器清零累加器清零 计算Q中第arow行的积并存入ctemp中；将ctemp中非零元压缩存储到Q.data;/for arow /if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q Q M M N N）的过程可大致描述）的过程可大致描述如下：如下：第43页，共120页，编辑于2022年，星期六 StatusStatus MultSMatrix (RLSMatrix M,RLSMatrix N,RLSMatrix&Q)ifif(M.nu!=!=N.mu)return ERROR;return ERROR;Q.mu=

31、M.mu;Q.nu=N.nu;Q.tu=0;ifif(M.tu*N.tu!=!=0)/Q是非零矩阵 forfor(arow=1;arow=M.mu;+arow)/处理M的每一行 /for arow /if return OK return OK;/MultSMatrix算法算法 5.35.3第44页，共120页，编辑于2022年，星期六 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;e

32、lse 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 ERRORERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if处理 的每一行M第45页，共120页，编辑于2022年，星期六分析上述算法的时间复杂度分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为O(M.muN.nu)，求Q的所有非零元的时间复杂度为

33、O(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为O(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是O O(M M.mu N N.nu+M M.tu N N.tu/N N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu=Mmn，N中非零元的个数 N.tu=Nnp，相乘算法的时间复杂度就是 O(mp(1+nMN)，当M0.05 和N0.05及 n i=i;p-j=j;p-e=e;/生成结点生成结点 if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;else /寻查在行表中的

34、插入位置寻查在行表中的插入位置 for(q=M.rheadi;(q-right)&q-right-jright);p-right=q-right;q-right=p;/完成行插入完成行插入 if(M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p;else /寻查在行表中的插入位置寻查在行表中的插入位置 for(q=M.cheadi;(q-down)&q-down-jdown);p-down=q-down;q-down=p;/完成列插入完成列插入 return OK;/CreateSMatrix_ OL第51页，共120页，编辑于2022年

35、，星期六5.4 广义表的定义广义表的定义ADT Glist 数据对象数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：数据关系：LR|ei-1,eiD,2in ADT Glist基本操作基本操作:顾名思义，广义表是线性表的推广，也称其为列表。第52页，共120页，编辑于2022年，星期六 广义表是递归递归定义的线性结构线性结构，广义表一般记作：LS=(1,2,n)其中：n是它的长度，i 或为原子 或为广义表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。称1为LS的表头，其余元素组成的表(2,n)是LS的表尾。

36、例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,)第53页，共120页，编辑于2022年，星期六广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E,F)其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce第54页，共120页，编辑于2022年，星期六广义表广义表 LS=(1,2,n)的结构特点的结构特点:1)广义表中的数据元素有相对次序次序；2)广义表的长度长度定义为最外层包含元素个数；3)广义表的深度深度定义为所含括弧的重数；注意：“原子”的深度为 0 “空表”的深度为 1 4)广义表可以共享共享；5)

37、广义表可以是一个递归递归的表。递归表的深度是无穷值，长度是有限值。第55页，共120页，编辑于2022年，星期六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)=()第56页，共120页，编辑于2022年，星期六 结构的创建和

38、销毁结构的创建和销毁 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();基本操作：基本操作：第57页，共120页，编辑于2022年，星期六5.5 5.5 广义表的存储结构广义表的存储结构通常采用头、尾指

39、针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data第58页，共120页，编辑于2022年，星期六1)表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法:若表头为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。否则，依次类推。第59页，共120页，编辑于2022年，星期六第60页，共120页，编辑于2022年，星期六L=(a,(x,y),(x)a(x,y)()1 LL=()0 a 1 1 1 1 1 0 x ()x(x,y),(x)(x)(x,

40、y)(x)(x)第61页，共120页，编辑于2022年，星期六/广义表的头尾链表存储表示广义表的头尾链表存储表示typedef enumATOM,LISTElemTag;/ATOM=0:ATOM=0:原子，原子，LIST=1:LIST=1:子表子表typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结公共部分，用于区分原子结点和表结点点和表结点 union /原子结点和表结点的联合部原子结点和表结点的联合部分分 AtomType atom;/atomatom是原子结点的值域，是原子结点的值域，AtomTypeAtomType由用户定义由用户定义 stru

41、ct struct GLNode*hp,*tp;ptr;/ptrptr是表结点的指针域，是表结点的指针域，ptr.hpptr.hp和和ptr.tpptr.tp分别指向表头和表尾分别指向表头和表尾 ;*GList;/广义表类型广义表类型第62页，共120页，编辑于2022年，星期六A=NILBCDE1e011a01b01d01c01a01111图图5.9 5.9 广义表的存储结构示例广义表的存储结构示例第63页，共120页，编辑于2022年，星期六2)子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表 1 指向子表1 的指针tag=0 data tp否则，依次类推

42、。否则，依次类推。1 指向子表2 的指针 1 指向子表n 的指针ls 第64页，共120页，编辑于2022年，星期六例如例如:a (x,y)(x)LS=(a,(x,y),(x)ls第65页，共120页，编辑于2022年，星期六/广义表的扩展线性链表存储表示广义表的扩展线性链表存储表示typedef enumATOM,LISTElemTag;/ATOM=0:ATOM=0:原子，原子，LIST=1:LIST=1:子表子表typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点公共部分，用于区分原子结点和表结点 union /原子结点和表结点的联合部分

43、原子结点和表结点的联合部分 AtomType atom;/是原子结点的值域是原子结点的值域 struct GLNode*hp;/表结点的表头指针表结点的表头指针 ;struct GLNode*tp;/相当于线性链表的相当于线性链表的nextnext，指向下一个，指向下一个元素结点元素结点*GList;/广义表类型广义表类型GListGList是一种扩展的线性链表是一种扩展的线性链表第66页，共120页，编辑于2022年，星期六ABCDE1c011图图5.11 5.11 列表的另一种链表表示列表的另一种链表表示11e0111a01b01a0d0第67页，共120页，编辑于2022年，星期六 一个

44、m元多项式的表示就是广义表应用的典型实例。例如三元多项式 p(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15,可以改写为：p(x,y,z)=(x10+2x6)y3+3x5y2)z2+(x4+6x3)y4+2y)z+15 即 p(x,y,z)=Az2+Bz+15 其中 A=(x10+2x6)y3+3x5y2)B=(x4+6x3)y4+2y)A、B 又是关于x、y的多项式，依次类推，上述多项式可以表示为：5.6 m元多项式的表示元多项式的表示第68页，共120页，编辑于2022年，星期六 p=z(A,2),(B,1),(15,0)其中：A=y(

45、C,3),(D,2)C=x(1,10),(2,6)D=x(3,5)B=y(E,4),(F,1)E=x(1,4),(6,3)F=x(2,0)第69页，共120页，编辑于2022年，星期六 可类似于广义表的第二种存储结构来定义表示m元多项式的广义表的存储结构。链表的结点结构为：其中exp为指数域,coef为系数域,hp指向其系数子表,tp指向同一层的下一结点。其形式定义说明如下：tag=1exphptp表结点tag=0expcoeftp原子结点第70页，共120页，编辑于2022年，星期六typedef struct MPNode ElemTag tag;/区分原子结点和表结点区分原子结点和表结点

46、 int exp;/指数域指数域 union float coef;/系数域系数域 struct MPNode*hp;/表结点的表头指针表结点的表头指针 ;struct MPNode*tp;/相当于线性链表的相当于线性链表的nextnext，指向指向下一个元素结点下一个元素结点*MPList;/m m元多项式广义表类型元多项式广义表类型第71页，共120页，编辑于2022年，星期六P图5.12 三元多项式的存储结构示意图312111111111131001531214100 250 3100 160 240 130 6xyz第72页，共120页，编辑于2022年，星期六5.7 广义表操作的递归

47、函数广义表操作的递归函数递归函数递归函数 一个含直接或间接调用本函数语句含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1)在每一次调用自己时，必须是(在某种意义上)更接近于解更接近于解;2)必须有一个终止终止处理或计算的准则准则。第73页，共120页，编辑于2022年，星期六例如例如:梵塔的递归函数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);/递归调用 第74页，共120页

48、，编辑于2022年，星期六二叉树的前序遍历二叉树的前序遍历 void PreOrderTraverse(BiTree T,void(Visit)(BiTree P)if(T)Visit(T-data);(PreOrderTraverse(T-lchild,Visit);(PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse第75页，共120页，编辑于2022年，星期六一、分治法一、分治法(Divide and Conquer)(又称分割求解法又称分割求解法)如何设计递归函数如何设计递归函数？二、后置递归法二、后置递归法(Postponing th

49、e work)三、回溯法三、回溯法(Backtracking)第76页，共120页，编辑于2022年，星期六 对于一个输入规模为 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;算法 5.5第83页，共120页，编辑于2022年，星期六 1 1 1 L for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GlistDepth(pp-ptr.hp);if

50、(dep max)max=dep;例如例如:pppp-ptr.hppppppp-ptr.hppp-ptr.hp具体例子，讲义具体例子，讲义P114 P114 图图5.13 5.13 第84页，共120页，编辑于2022年，星期六5.7.2 复制广义表复制广义表新的广义表由新的表头和表尾构成。新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为：空表复制求得的新表自然也是空表空表复制求得的新表自然也是空表;原子结点可以直接复制求得。原子结点可以直接复制求得。前面提到，任何一个非空广义表均可分解成表头和表尾；反之，一对确定的表头和表尾可惟一确定一个广义表。将广义表分解成表头和表尾两部分，分