数据结构第五章数组与广义表.ppt

《数据结构第五章数组与广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构第五章数组与广义表.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构课程中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院数据结构第五章第五章数组与广义表数组与广义表本章内容5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构5-2 中国科大数据结构pp数组和广义表可看成是一种特殊的线性表。表中的元数组和广义表可看成是一种特殊的线性表。表中的元数组和广义表可看成是一种特殊的线性表。表中的元数组和广义表可看成是一种特殊的线性表。表中的元素本身也是一种数据结构。素本身也是一种数据结构。素本身也是一种数据结构。素本身也是一种数据结构。pp数组的的数据元

2、素是数组；广义表的数据元素可以是数组的的数据元素是数组；广义表的数据元素可以是数组的的数据元素是数组；广义表的数据元素可以是数组的的数据元素是数组；广义表的数据元素可以是原子类型，也可以是广义表，分别称为广义表的原子原子类型，也可以是广义表，分别称为广义表的原子原子类型，也可以是广义表，分别称为广义表的原子原子类型，也可以是广义表，分别称为广义表的原子项和子表项和子表项和子表项和子表数组和广义表简单描述5-3 中国科大数据结构 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，唯一

3、可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：二维数组：5.1 数组的定义Amn=a11 a12 a1na21 a22 a2n am1 am2 amn5-4 中国科大数据结构5.1 数组的定义p二维数组二维数组n二维数组可以看成是由若干个行向量组成的向量，也可以看成是若干二维数组可以看成是由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。个列

4、向量组成的向量。n在在C C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，的一维数组类型，也就是说，typedef elemtype array2mn;等价于：等价于：typedef elemtype array1n;typedef array1 array2m;p多维数组：多维数组：用一维顺序结构线性表实现多维数组用一维顺序结构线性表实现多维数组struct Array ElemType*buffer;/数据区数据区 int dims;/维数维数 int*L;/各维长度各维长度;5-5 中国科大数

5、据结构5.2 数组的顺序表示和实现p设一设一3 3维数组维数组A423A423，存贮，存贮在一个顺序线性表在一个顺序线性表S S中，结构如中，结构如下所示：下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A00001234567.2223A000A001A002A

6、010A011A012A100A101.A311A3125-6 中国科大数据结构5.2 数组的顺序表示和实现p两种顺序存储方式：两种顺序存储方式：n行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量紧接在第个行向量紧接在第i i个行向量后面。以二维数组为例，按行优先顺序存储的线性序个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：列为：a11,a12,a1n,a21,a22,a2n,am1,am2,amn。在。在PASCAL、C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。行优先顺行优先顺序推广到多维数组，可规定为先排最右的

7、下标。序推广到多维数组，可规定为先排最右的下标。n列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列向量紧接个列向量紧接在第在第j j个列向量之后，个列向量之后，A A的的m*nm*n个元素按列优先顺序存储的线性序个元素按列优先顺序存储的线性序列为：列为：a11,a21,am1,a12,a22,am2,an1,an2,anm 。在在FORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。列优先顺列优先顺序推广到多维数组，可规定为先排最左的下标。序推广到多维数组，可规定为先排最左的下标。5-7 中国科大数据结构5.2 数组的顺序

8、表示和实现p二维数组元素的存取二维数组元素的存取n二维数组二维数组A Amnmn按按“行优先顺序行优先顺序”存储在内存中，假设每个元素占存储在内存中，假设每个元素占用用L L个存储单元。个存储单元。n元素元素a aijij的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在a aijij前面的元素所前面的元素所占用的单元数。因为占用的单元数。因为a aijij位于第位于第i i行、第行、第j j列，前面列，前面 i-1 行一共有行一共有(i-1)n 个元素，第个元素，第i i行上行上a aijij前面又有前面又有j-1j-1个元素，故它前面一个元素，故它前面一共有共有(i-1)

9、n+j-1个元素，因此，个元素，因此，aij的地址计算函数为：的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)*n+j-1*L5-8 中国科大数据结构5.2 数组的顺序表示和实现p例：二维数组例：二维数组AcAc1 1.d.d1 1,c,c2 2.d.d2 2 的存取的存取n分析：分析：a aijij前一共有前一共有i-ci-c1 1行，二维数组一共有行，二维数组一共有d d2 2-c-c2 2+1+1列，故这列，故这i-i-c c1 1行共有行共有(i-c(i-c1 1)*(d)*(d2 2-c-c2 2+1)+1)个元素，第个元素，第i i行上行上a aijij前一共有前一

10、共有j-cj-c2 2个元个元素，因此，素，因此，a aijij的地址计算函数为：的地址计算函数为：LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*Ln在在C C语言中，数组各维下标的下界是语言中，数组各维下标的下界是0 0，因此二维数组，因此二维数组A Am m n n的地址的地址计算公式为：计算公式为：LOC(aij)=LOC(a00)+(i*n+j)*L5-9 中国科大数据结构5.3 矩阵的压缩存储p在高级语言编制程序时，将一个矩阵描述为一个二维数组。在高级语言编制程序时，将一个矩阵描述为一个二维数组。p矩阵在这种存储表示之下，可以对其元素进行随机存

11、取，各种矩阵矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为密度仍为1 1，但实际上占用了许多单元去存储重复的非零元素或零，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费元素，这对高阶矩阵会造成极大的浪费.p为了节省存储空间，为了节省存储空间，对这类矩阵进行压缩存储：即为多个相同的对这类矩阵进行压缩存储：即为多个

12、相同的非零元素只分配一个存储空间；对零元素不分配空间。非零元素只分配一个存储空间；对零元素不分配空间。5-10 中国科大数据结构5.3 矩阵的压缩存储 特殊矩阵特殊矩阵所谓所谓特殊矩阵特殊矩阵特殊矩阵特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。下面我们讨论几种特殊矩阵的压缩存储。1 1、对称矩阵、对称矩阵 2 2、对角矩阵、对角矩阵5-11 中国科大数据结构5.3 矩阵的压缩存储p对称矩阵对称矩阵在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质：aij=aji 0i,jn-

13、1 则称则称A A为为对称矩阵对称矩阵。如下图是一个。如下图是一个5 5阶对称矩阵。阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如上图示。存储主对角线（包括对角线）以下的元素，其存储形式如上图示。1 5 1 3 7 a005 0 8 0 0 a

14、10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 .7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-15-12 中国科大数据结构5.3 矩阵的压缩存储p对称矩阵的存储表示对称矩阵的存储表示n在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为：(i+1)=n(n+1)/2n因此，我们可以按行优先的次序将这些元素存放在一个向量因此，我们可以按行优先的次序将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。中。pa aijij和和sak sak 之

15、间对应关系之间对应关系n若若ijij，则，则a ai ji j在下三角形中。在下三角形中。a ai ji j之前的之前的i i行（从第行（从第0 0行到第行到第i-i-1 1行）一共有行）一共有 1+2+i=i(i+1)/2 个元素，在第个元素，在第i i行上，行上，a ai ji j之前之前恰有恰有j j个元素（即个元素（即 ai0,ai1,ai2,aij-1），因此有：），因此有：k=i*(i+1)/2+j 0kn(n+1)/2n若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只要交换上，所以只要交换上述对应关系式中的述对应

16、关系式中的i i和和j j即可得到：即可得到：k=j*(j+1)/2+i 0 k1i-j1时，元素时，元素a aijij=0=0。n由此可知，一个由此可知，一个k k对角矩阵对角矩阵(k(k为奇数为奇数)A)A是满足下述条件的矩阵：是满足下述条件的矩阵：若若i-j(k-1)/2 i-j(k-1)/2，则元素，则元素 a aijij=0=0。n对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。个向量中，并且也能找到每个非零元素和向量下标的对应关系。5-17 中国科大数据结构5.3 矩

17、阵的压缩存储在三对角矩阵里附满足条件在三对角矩阵里附满足条件i=0i=0，j=0j=0、1 1，或，或i=n-1j=n-2i=n-1j=n-2、n-1n-1或或1in-1,j=i-11in-1,j=i-1、i i、i+1i+1的元素的元素a aijij外，其余元素都是零。外，其余元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第对这种矩阵，我们也可按行优序为主序来存储。除第0 0行和第行和第n-n-1 1行是行是2 2个元素外，每行的非零元素都是个元素外，每行的非零元素都是3 3个，因此，需存储的元素个个，因此，需存储的元素个数为数为3n-23n-2。数组数组sasa中的元素中的元素s

18、aksak与三对角带状矩阵中的元素与三对角带状矩阵中的元素a aijij存在一一存在一一对应关系，在对应关系，在a aijij之前有之前有i i行行,共有共有3*i-13*i-1个非零元素，在第个非零元素，在第i i行，有行，有j-j-i+1i+1个非零元素个非零元素.a n-1 n-1a n-1 n-2a21 a12a11a10a01 a00K=0 1 2 3 4 5 3n-2 3n-15-18 中国科大数据结构5.3 矩阵的压缩存储 稀疏矩阵稀疏矩阵p定义：设矩阵定义：设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩阵元素的总数远远小于矩阵元素的总数（即（即smns

19、0 0 时，表的时，表的时，表的时，表的第一个表元素第一个表元素第一个表元素第一个表元素称为广义表的称为广义表的称为广义表的称为广义表的表头表头表头表头(headheadheadhead)，除此，除此，除此，除此之外，之外，之外，之外，其它表元素组成的表其它表元素组成的表其它表元素组成的表其它表元素组成的表称为广义表的称为广义表的称为广义表的称为广义表的表尾表尾表尾表尾(tailtailtailtail)。pp广义表举例广义表举例广义表举例广义表举例1.A=（）（）/空表，长度空表，长度n=0，d=12.B=（a,b）/n=2,d=1.(线性表线性表)3.C=（a,(b,c,d)/n=2,d=

20、2.a1为原子，为原子，a2为子表为子表4.D=（A，B，C）/n=3,d=2.a1，a2,a3为子表为子表5.E=(a,E）/n=2,d=5-30 中国科大数据结构5.4 广义表p任意一个非空广义表，均可分解为表头和表尾。任意一个非空广义表，均可分解为表头和表尾。p对于一个非空广义表，其表头可能是对于一个非空广义表，其表头可能是原子原子，也可能是，也可能是子表子表；而表尾；而表尾一定是一定是子表子表。5-31 中国科大数据结构5.4 广义表p性质性质n n广义表是一个广义表是一个广义表是一个广义表是一个多层次多层次多层次多层次结构结构结构结构;n n广义表的深度广义表的深度广义表的深度广义表

21、的深度 d d 定义为所含括弧的重数定义为所含括弧的重数定义为所含括弧的重数定义为所含括弧的重数;l l“原子原子原子原子”的深度为的深度为的深度为的深度为0 0;l l“空表空表空表空表”的深度为的深度为的深度为的深度为1 1n n 广义表可以广义表可以广义表可以广义表可以共享共享共享共享;也可以是一个也可以是一个也可以是一个也可以是一个递归递归递归递归的表的表的表的表;各种广义表的示意图各种广义表的示意图各种广义表的示意图各种广义表的示意图B662线性表线性表线性表线性表B5a纯表纯表纯表纯表2 xA空表空表空表空表E5再入表再入表再入表再入表D2 xa6B2CAD63递归表递归表递归表递

22、归表子表结点用圈子表结点用圈表示，表示，原子结原子结点用方框表示点用方框表示5-32 中国科大数据结构5.5 广义表的存储结构由于广义表的元素类型不同，难以用顺序结构表示，常用链接由于广义表的元素类型不同，难以用顺序结构表示，常用链接存储方法存储广义表，并称之为存储方法存储广义表，并称之为广义链表广义链表广义链表广义链表。广义表中有两种数据元素，广义表中有两种数据元素，原子原子或或子表子表，需要两种结构的结点：，需要两种结构的结点：一种是表结点，一种是原子结点。一种是表结点，一种是原子结点。p扩展的线性链表表示法扩展的线性链表表示法n表结点表结点由三个域组成：标志域、表头指针域和下一个元素的指

23、由三个域组成：标志域、表头指针域和下一个元素的指针域；针域；n原子结点原子结点的三个域为：标志域、值域和下一个元素的指针域。的三个域为：标志域、值域和下一个元素的指针域。表结点表结点 tp hp tag=1原子结点原子结点 tag=0 tpatom5-33 中国科大数据结构5.5 广义表的存储结构typedef enumatom,listelemtag;typedef struct GLnode Elemtag tag;unionunion AtomType atom;struct GLnode *hp;/表结点的表头指针 ;struct GLnode *tp;/指向下一个元素结点*GList

24、GList;5-34 中国科大数据结构5.5 广义表的存储结构p广义表的运算广义表的运算n创建空的广义表创建空的广义表:initGList(&L);n销毁广义表销毁广义表:destroyGList(&L);n复制广义表复制广义表:copyGList(&T,L);n求广义表的长度求广义表的长度:length(L);n求广义表的深度求广义表的深度:depth(L);n求广义表的表头求广义表的表头:getHead(L);n求广义表的表尾求广义表的表尾:getTail(L);n插入一个元素使其成为新的表头插入一个元素使其成为新的表头:insertFirst(&L,e);n删除表头元素删除表头元素:de

25、leteFirst(&L,&e);n判断表是否空判断表是否空:isEmpty(L);5-35 中国科大数据结构5.5 广义表的存储结构p广义表作为广义表作为ADTADT Glist 数据对象数据对象:D=ei|i=1,2,n;n 0,ei AtomSet 或或ei Glist 数据关系数据关系:R=(ei-1,ei)|ei D 基本操作基本操作:initGList(&L);操作结果操作结果:创建空表创建空表;destroyGList(&L);初始条件初始条件:广义表广义表L已存在已存在 操作结果操作结果:销毁广义表销毁广义表 ./Glist;5-36 中国科大数据结构5.5 广义表的存储结构p

26、求广义表的深度求广义表的深度设：设：LS=(a1,a2,an)，例如，对于广义表例如，对于广义表 E(B(a,b),D(B(a,b),C(u,(x,y,z),A()按递归算法分析：按递归算法分析：Depth(E)=1+Max Depth(B),Depth(D)Depth(B)=1+Max Depth(a),Depth(b)=1 Depth(D)=1+Max Depth(B),Depth(C),Depth(A)5-37 中国科大数据结构5.5 广义表的存储结构Depth(C)=1+Max Depth(u),Depth(x,y,z)Depth(A)=1Depth(u)=0Depth(x,y,z)=

27、1+Max Depth(x),Depth(y),Depth(z)=1 Depth(C)=1+Max Depth(u),Depth(x,y,z)=1+Max 0,1=2 Depth(D)=1+Max Depth(B),Depth(C),Depth(A)=1+Max 1,2,1=3Depth(E)=1+Max Depth(B),Depth(D)=1+Max 1,3=45-38 中国科大数据结构5.5 广义表的存储结构Int depth(GList*ls)/广义表广义表ls 用扩展的线性链表存储，函数返回用扩展的线性链表存储，函数返回ls的深度的深度 if(ls=NULL)return 1;/空表空表 GList*temp=ls;int m=0;/m 表示当前层元素的最大深度表示当前层元素的最大深度 while(temp!=NULL)/横扫广义表的每个元素横扫广义表的每个元素 if(temptag=LIST)/子表深度子表深度 int n=depth(temphp);if(nm)m=n;/不是子表不加深度不是子表不加深度 temp=temptp;/temp指向下一个元素指向下一个元素 return m+1;5-39 中国科大数据结构习题p本章习题参见教师网页：本章习题参见教师网页：http:/