(5)--lecture5数据结构数据结构.ppt

《(5)--lecture5数据结构数据结构.ppt》由会员分享，可在线阅读，更多相关《(5)--lecture5数据结构数据结构.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第5章章 数组和广义表数组和广义表数数组组可以可以认为认为是是线线性表在性表在维维数上的一种拓展，依然属数上的一种拓展，依然属于于线线性性结结构，但在存构，但在存储结储结构的构的实现实现方面方面较线较线性表性表为为复复杂杂。数。数组组是在高是在高级语级语言言层层面已面已经实现经实现的数据的数据类类型，在型，在数据数据结结构中再构中再讨论讨论它它们们是是为为了深入理解了深入理解实现实现它它们们的基的基础础技技术术。讲讲授本章授本章课课程大程大约约需需4 4课时课时。5.1 数数组的的类型定型定义5.3 稀疏矩稀疏矩阵的的压缩存存储 5.2 数数组的的顺序表示和序表示和实现5.4 广广义表表

2、3数数组的定的定义:数组是线性表的一种扩充，一维数组即为线性表，二维数组定义为“其数组元素为一维数组”的线性表:i=0,1,m-1其中4 也可视为一个由m行n列构成的一个阵列Amn=多维数组可以此类推 a11 a12 a1n a21 a22 a2n am1 am2 amnA=A=a11 a12 a1na21 a22 a2nam1 am2 amna11 a21 am1a12 a22 am2a1n a2n amnA=图图5-1 二维数组图例形式二维数组图例形式(a)矩阵表示形式矩阵表示形式(b)行行向量的一维数组形式向量的一维数组形式(c)列向量的一维数组形式向量的一维数组形式5.1 数数组的的类

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 ADT Array 基本操作基本操作:二维数组的定义二维数组的定义:数据数据对象象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL COL=|0ib1-2,0jb2-1 ROW=|0ib1-1,0 jb2-28数组数组的基本操作：的基本操作：InitArray(&A,n,bound1,.,boundn)Destro

4、yArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)9 InitArray(&A,n,bound1,.,boundn)操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并 返回OK。10 DestroyArray(&A)操作结果：销毁数组A。11 Value(A,&e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。12 Assign(&A,e,index1,.,indexn)初始条件：A是n维

5、数组，e为元素变量，随后是n 个下标值。操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。135.2数数组的的顺序表示序表示和和实现 类型特点型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是 一个一维的结构。有两种有两种顺序映象的方式序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。通常有两种通常有两种顺序存序存储方式方式 行行优先先顺序序(Row Major Order)：将数将数组元素按行元素按行排列，第排列，第i+1个行向量个行向量紧接在第接在第i个行向量后面。个行向量后面。对二二维数数组，按行，按行优先先顺

6、序存序存储的的线性序列性序列为：a11,a12,a1n,a21,a22,a2n ,am1,am2,amn PASCAL、C是按行是按行优先先顺序存序存储的，如的，如图5-2(b)示。示。列列优先先顺序序(Column Major Order)：将数将数组元素元素按列向量排列，第按列向量排列，第j+1个列向量个列向量紧接在第接在第j个列向量之后，个列向量之后，对二二维数数组，按列，按列优先先顺序存序存储的的线性序列性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm FORTRAN是按列是按列优先先顺序存序存储的，如的，如图5-2(c)。图图5-2 二维数组及其顺序存

7、储图例形式二维数组及其顺序存储图例形式 a11 a12 a1n a21 a22 a2n am1 am2 amnA=(a)二维数组的表示形式二维数组的表示形式(b)行优先顺序存储行优先顺序存储(c)列列优先顺序存储优先顺序存储a11 a12 a1n第第 1行行a21 a22 a2n第第 2行行am1 am2 Amn 第第 m行行a11 a21 am1第第 1列列a12 a22 am2第第 2列列a1m a2m amn第第 n列列16例如：称为基地址基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0

8、,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 17 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中 cn=L，ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n 在高级语言的层次，计算地址的任务已由编译系统解决，可以通过多维的数组下标直接存取元素，例如A2,5,8。18假设 m 行 n 列的矩阵含 t 个非零元素，则称为稀疏因子稀疏因子。通常认为 0.05 的矩阵为稀疏矩阵。5.3稀疏矩稀疏矩阵的的压缩存存储何

9、谓稀疏矩阵？19 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。201)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i,j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。211)特殊矩特殊矩阵 非零元在矩阵中的分布有一定规则例如:三角矩阵 对角矩阵2)随机稀疏矩随机稀疏矩阵 非零元在矩阵中随机出现有两有两类稀疏矩稀疏矩阵：22随机稀疏矩随机稀疏矩阵的的压缩存存储方法方法:一、一、三元三元组顺序表序表二、二、行行逻

10、辑联接的接的顺序表序表三、三、十字十字链表表23#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型一、三元一、三元组顺序表序表typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型241 2 141 5 -52 2 -73 1 363 4 2812345原稀疏矩原稀疏矩阵三元三元组表示表示的稀疏矩的稀疏矩阵 三元三元组表示的稀疏表示的稀疏矩矩阵节省了空省了空间，便，便于于实现矩矩阵运算运算

11、吗？025如何求如何求转置矩置矩阵？26用常规的原二维数组时的转置算法 其其时间复复杂度度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;271 2 141 5 -52 2 -73 1 363 4 28123452 1 145 1 -52 2 -71 3 364 3 2812345简单调换行值和列值将破坏有序性不可行不可行用三元组实现同样功能的办法28用“三元组”表示时如何实现？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 2829 首

12、先应该确定每一行的第一个非零元在三元组中的位置。cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;30void 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

13、=1;p=M.tu;+p)/if/FastTransposeSMatrix 转置矩阵元素 31Col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol转置矩阵元素的程序段：32 分析算法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)33 三元组顺序表又称

14、有序的双下有序的双下标法法，它的特点是，非零元在表中按行序有序存储，因此便于便于进行依行行依行顺序序处理的矩理的矩阵运运算算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行二、行逻辑联接的接的顺序表序表34#define MAXMN 500 typedef struct Triple dataMAXSIZE+1;int rposMAXMN+1;int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。35例如：给定一组下标，求矩阵的元素值ElemType value(RLSM

15、atrix 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;/累加器

16、清零 计算Q中第arow行的积并存入ctemp 中；将ctemp 中非零元压缩存储到Q.data；/for arow /if 两个稀疏矩两个稀疏矩阵相乘（相乘（Q M N）的的过程可大致描述如下：程可大致描述如下：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

17、;/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 E

18、RROR;Q.dataQ.tu=arow,ccol,ctempccol;/if处理 的每一行M分析上述算法的分析上述算法的时间复复杂度度累加器ctemp初始化的时间复杂度为(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 1000时

19、，相乘算法的时间复杂度就相当于(mp)。41三、三、十字十字链表表M.cheadM.rhead3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 1 2 42 十字十字链链表表的的类类型描述型描述:typedef struct OLNode int i,j;/该非零元的行和列下标 ElemType e;struct OLNode*rnext,*cnext;/该非零元所在行表和列表的后继链域 OLNode;*OLink;43typedef struct OLink*rhead,*chead;/行和列链表头指针向量基址 /在建立存储结构时分配.int mu,nu,tu;/稀

20、疏矩阵的行数、列数和非零元个数 CrossList;44void CrossSearch(CrossList&M,ElemType x)/在十字链表中查找所有值为x的元素并输出（i,j）i=0;/从第1行开始扫描 p=*(M.rhead+i);/p指向第1行的第一个十字链表结点 while(iM.mu)/对所有的行 if(!p)i+;p=*(M.rhead+i);/p指向下一行 的第一个非零元结点 else if(p.e=x)cout(i,j)rnext;/继续查找本行的下一个结点/else /while/CrossSearch5.4 广义表广义表 广广义表是表是线性表的推广和性表的推广和扩充

21、，在人工智能充，在人工智能领域中域中应用十分广泛。用十分广泛。在第在第2章中，我章中，我们把把线性表定性表定义为n(n 0)个元素个元素a1,a2,an的有的有穷序列，序列，该序列中的所有元素具有相同的序列中的所有元素具有相同的数据数据类型且只能是原子型且只能是原子项(Atom)。所。所谓原子原子项可以是一可以是一个数或一个个数或一个结构，是指构，是指结构上不可再分的构上不可再分的。若放松。若放松对元元素的素的这种限制，容种限制，容许它它们具有其自身具有其自身结构，就构，就产生了广生了广义表的概念。表的概念。广广义表表(Lists，又称又称为列表列表)：是由：是由n(n 0)个个元素元素组成的

22、有成的有穷序列：序列：LS=(a1，a2，an)其中其中ai或者是原子或者是原子项，或者是一个广，或者是一个广义表。表。LS是广是广义表的名字，表的名字，n为它的它的长度。若度。若ai是广是广义表，表，则称称为LS的子表。的子表。习惯上：原子用上：原子用小写字母小写字母，子表用，子表用大写字母大写字母。若广若广义表表LS非空非空时：a1(表中第一个元素表中第一个元素)称称为表表头；其余元素其余元素组成的子表称成的子表称为表尾表尾；(a2，a3，an)广广义表中所包含的元素表中所包含的元素(包括原子和子表包括原子和子表)的个数称的个数称为表的表的长 度。度。广广义表中括号的最大表中括号的最大层数

23、称数称为表深表深(度度)。有关广有关广义表的表的这些概念的例子如表些概念的例子如表5-2所示。所示。表表5-2 广义广义表及其示例表及其示例广广 义义 表表表长表长n 表深表深hA=()01B=(e)11C=(a,(b,c,d)22D=(A,B,C)33E=(a,E)2F=()12abecdABCD图图5-12 广义广义表的图形表示表的图形表示广广义表的重要表的重要结论：广广义表的元素可以是原子，也可以是子表，子表表的元素可以是原子，也可以是子表，子表的元素又可以是子表，的元素又可以是子表，。即即广广义表是一个多表是一个多层次次的的结构。构。表表5-2中的中的广广义表表D的的图形表示如形表示如

24、图5 5-12所示所示。(2)(2)广广义表可以被其它广表可以被其它广义表表所共享所共享，也可以，也可以共享共享其其它广它广义表。广表。广义表表共享共享其它广其它广义表表时通通过表名引用。表名引用。(3)(3)广广义表本身可以是一个表本身可以是一个递归表。表。(4)(4)根据根据对表表头、表尾、表尾的定的定义，任何一个非空广，任何一个非空广义表表的的表表头可以是原子，也可以是子表，可以是原子，也可以是子表，而表尾而表尾必定是必定是广广义表。表。5.4.1 广义表的存储结构广义表的存储结构 由于广义表中的数据元素具有不同的结构，通常由于广义表中的数据元素具有不同的结构，通常用链式存储结构用链式存

25、储结构表示，每个数据元素用一个结点表示。表示，每个数据元素用一个结点表示。因此，广义表中就有两类结点：因此，广义表中就有两类结点：一类是一类是表结点表结点，用来表示广义表项，由标志域，用来表示广义表项，由标志域，表头指针域，表尾指针域组成表头指针域，表尾指针域组成;另一类是另一类是原子原子结点结点，用来表示原子项，由标志域，用来表示原子项，由标志域，原子的值域组成。原子的值域组成。如图如图5-13所示所示。只要广义表非空，都是由只要广义表非空，都是由表头和表尾组成表头和表尾组成。即一个。即一个确定的确定的表头和表尾就唯一确定一个表头和表尾就唯一确定一个广义表。广义表。相应的数据结构定义如下：相

26、应的数据结构定义如下：typedef struct GLNode int tag;/*标志域，为标志域，为1：表结点：表结点;为为0：原子结点：原子结点 */union elemtype value;/*原子结点的原子结点的值域值域 */struct struct GLNode *hp,*tp;ptr;/*ptr和和atom两成员共用两成员共用 */Gdata;GLNode;/*广义表广义表结点类型结点类型 */标志标志tag=0 原子的原子的值值 标志标志tag=1 表头指针表头指针hp 表尾指针表尾指针tp 图图5-13 广义广义表的链表结点结构示意图表的链表结点结构示意图(b)表结点表结

27、点(a)原子结点原子结点例例：对对A=()，B=(e)，C=(a,(b,c,d)，D=(A,B,C)，E=(a,E)的广义表的存储结构的广义表的存储结构如图如图5 5-14所示所示。A=NULL1 0 eB10 aC10 b1 10 c1 0 dD1 11 10 aE1 图图5-14 广义广义表的存储结构示意图表的存储结构示意图1 对于上述存于上述存储结构，有如下几个特点：构，有如下几个特点：(1)若广若广义表表为空，表空，表头指指针为空空；否否则，表，表头指指针总是指向一个表是指向一个表结点，其中点，其中hp指向广指向广义表的表表的表头结点点(或或为原子原子结点，或点，或为表表结点点)，tp

28、指向广指向广义表的表表的表尾尾(表尾表尾为空空时，指，指针为空，否空，否则必必为表表结点点)。(2)这种种结构求构求广广义表的表的长度度、深度深度、表表头、表尾的表尾的操作十分方便。操作十分方便。(3)表表结点太多点太多，造成空造成空间浪浪费。也可用。也可用图5 5-15所示所示的的结点点结构构。图图5-15 广义广义表的链表结点结构示意图表的链表结点结构示意图(b)表结点表结点(a)原子结点原子结点tag=1 表头指针表头指针hp 表尾指针表尾指针tp tag=0 原子的原子的值值 表尾指针表尾指针tp 广义表广义表v广广义表的两个推表的两个推论w表可以被其他表共享，如表表可以被其他表共享，

29、如表C=（B,B,()）中，表）中，表B同同时作作为C的两个子表。的两个子表。w表可以表可以递归，如表，如表D=（a,D）。）。v广广义表的表的应用用w讨论一个多元多一个多元多项式的表示式的表示问题w其中：每项可用一具有4个域的结构体表示：53广义表广义表w表示方法表示方法1：按以上方法需要：按以上方法需要为一元多一元多项式定式定义一个一个结构构体，再体，再为二元多二元多项式定式定义一个一个结构体，等等构体，等等w表示方法表示方法2：定：定义一个包含一个包含许多指数域的多指数域的结构体，并使用构体，并使用需要的域。需要的域。w以上两者都不是好的解决方案以上两者都不是好的解决方案v尝试新方法新方

30、法w这样可以把可以把P(x,y,z)看作看作为一个广一个广义表，每个多表，每个多项式都可式都可以写成以写成这种形式。种形式。54广义表广义表w其方法是先因式分解出一个主其方法是先因式分解出一个主变量量z，再分解第，再分解第2个个变量量yw此此时，再，再观察多察多项式式P，可，可见：w变量z，多项式P变为：w而C和D又都是关于变量 x 和 y 的多项式：w继续这种分解，可以得出种分解，可以得出结论如下：如下：55广义表结点的表示广义表结点的表示w继续这种分解，可以得出种分解，可以得出结论如下：如下：w每个多项式的项都由一个变量和若干个“系数指数”对构成w每个系数又是一个多项式（少一个变量），把数

31、字系数看作是一个零元多项式。例例：其中的其中的“2y”一一项就是一个数字系数就是一个数字系数w所以，每个多所以，每个多项式，无式，无论包含多少包含多少变量，都可以用量，都可以用PolyNode 类型的型的结点点 GenListNode 来表示，每个来表示，每个结点点结构如下：构如下：56trio(var/ptr/no)vble/down/coefExp(0/exp)next57本章学习要点本章学习要点58了了解解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地地址址计算方法算方法。了了解解对特殊矩阵进行压缩存储时的下下标变换公式公式。熟熟悉悉稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三三元元组表表示示稀稀疏疏矩矩阵时进行矩阵运算采用的处理方法。