数组和广义表 .ppt

《数组和广义表 .ppt》由会员分享，可在线阅读，更多相关《数组和广义表 .ppt（49页珍藏版）》请在三一文库上搜索。

1、第5章 数组和广义表,主要内容,数组的定义 数组的顺序表示和实现 矩阵的压缩存储及典型算法 广义表及其应用（选讲）,主要内容,数组的逻辑特征 一个数据元素可能有多个直接前趋和多个直接后继,重点与难点,本章的重点 二维数组的存储方式、几种特殊矩阵的存储方式（对称矩阵、上/下三角矩阵、稀疏矩阵）、稀疏矩阵的快速转置算法 本章的难点 稀疏矩阵的三元组表示及其三元组表示下的快速转置、相乘算法,5.1 数组的定义,数组的特点 数组中各元素具有统一的类型。 数组元素的下标一般具有固定的上界和下界。 可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 二维数组Amn 每个数据元素可以又是一

2、个线性表结构。,5.1 数组的定义,每个数据元素可以又是一个线性表结构。,5.1 数组的定义,在C语言中，一个二维数组类型可定义为其分量类型为一维数组类型的一维数组类型 elemtype array2mn; 等价于： elemtype array1n; array1 array2m;,5.1 数组的定义,数组的定义 若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。 线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。,5.1 数组的定义,抽象数

3、据类型数组的ADT定义 ADT Array 数据对象: ji=0,.,bi-1,i=1,2,.,n; D=aj1j2.jn|n(0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2.jn (-ElemSet 数据关系:R=R1,R2,.Rn Ri=| 0i, 0=ji=bi-2, aj1.ji.jn,aj1.ji+1 .jn(-D,i=2,.n),5.1 数组的定义,抽象数据类型数组的ADT定义 基本操作: InitArray(&A,n,bound1,.,boundn) 操作结果：若维数和各维长度合法,则构造相应数组A,返回OK。 DestroyArray(&A)

4、 操作结果:销毁数组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。 ADT Array,5.2 数组的顺序表示和实现,存储结构 顺序存储：（多）对数组一般不做插入和删除操作 链式存储：（少）对稀疏矩阵 计算机的存储结构是一维的，而数组一般是多维的，怎样存放？ 事先约定按某种

5、次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。 二维数组 行优先顺序（Row Major Order） BASIC、PL/1、COBOL、PASCAL和C语言 列优先顺序（Column Major Order） FORTRAN语言,5.2 数组的顺序表示和实现,列优先 行优先,5.2 数组的顺序表示和实现,无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）： 开始结点的存放地址（即基地址）； 维数和每维的上、下界； 每个数组元素所占用的单元数 二维数组Ac1d1, c2d2，行优先存储 LOC(aij)=LOC(ac1,c

6、2)+(i-c1)*(d2-c2+1)+j-c2)*L 列优先存储 LOC(aij)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+i-c1)*L,5.2 数组的顺序表示和实现,例：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 例：设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。,288,8950,LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*2,5.3 矩阵的压缩存储,如何

7、存储矩阵的元，从而使矩阵的各种运算能有效地进行？ 用高级语言编制程序时，用二维数组来存储矩阵元，可以随机存取元素，存储的密度为1。 在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中非零元素呈某种规律分布或者出现大量的零元素，看起来存储密度仍为1，但实际上占用了许多单元存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，可对这类矩阵进行压缩存储： 为多个相同的非零元素只分配一个存储空间； 对零元素不分配空间。,5.3 矩阵的压缩存储,两种矩阵的压缩存储 特殊矩阵值相同的元素或者零元素在矩阵中的分布有一定规律。 对称矩阵：不存相同元素 三角矩阵：不存相同元素 对角矩阵：

8、只存非0元素 稀疏矩阵存在大量的零元素，但分布没有规律。 三元组顺序表：存非0元素的位置和值 行逻辑链接的顺序表：存非0元素的位置、值和每行非零元素在三元组表中的起始位置,5.3 矩阵的压缩存储特殊矩阵,对称矩阵 n阶方阵A若满足下述性质，则称A为对称矩阵。 aij=aji 0i,jn-1,只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，能节约近一半的存储空间。 元素总数为：1+2+3+n=n(n+1)/2,5.3 矩阵的压缩存储特殊矩阵,对称矩阵A的压缩存储san(n+1)/2 aij和sak之间的对应关系。,当ij,5.3 矩阵的压缩存储特殊矩阵,三角矩阵 分为上

9、三角、下三角,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-10 an-11 an-1n-1,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)/2中，其中c存放在向量的最后一个分量中。 元素总数为：1+2+3+n+1=n(n+1)/2+1,5.3 矩阵的压缩存储特殊矩阵,下三角矩阵 A的压缩存储san(n+1)/2 下三角矩阵 A中aij和sak之间的对应关系。,当ij,n(n-1),5.3 矩阵的压缩存储特殊矩阵,对角矩阵 所有的非

10、零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如：三对角矩阵,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵 设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵 稀疏因子 e 0.05 (e=s/(m*n) ) 如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？ 对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。 具体实现：将每个非零元素用一个三元组 （i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。,5.3 矩阵的压缩存储稀疏矩阵

11、,稀疏矩阵A67 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 表示方法 三元组顺序表 用线性表表示：不能随机存取 用三元组矩阵表示：不能随机存取 行逻辑链接的顺序表可随机存取,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的三元组顺序表表示 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 用线性表表示：(1,2,12)，(1,3,9

12、)，(3,1,-3)，(3,6,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7),用三元组矩阵表示：,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的三元组顺序表存储结构 #define maxsize 12500 typedef struct int i,j; ElemType e; Triple; typedef struct Triple datamaxsize+1; / data0未用 int mu,nu,tu; TSMatrix;,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的转置 一个mn的矩阵M，它的转置T是一个nm的矩阵，且aij=bji，0im，0jn 0

13、 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 M 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的转置,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的一般转置算法 方法一：将M转置为T，即将M的三元组表M.data置换为T的三元组表T.data。可以简单地交换M.data中i和j的内容，

14、得到T.data是一个按列优先顺序存储的稀疏矩阵T，必须重新排列三元组T的顺序，得到按行优先顺序存储的T.data。(不可取，为什么？) 对M中的每一列 col(0coln-1)，通过从头至尾扫描三元组表M.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入T.data中，即可得到T的按行优先的压缩存储表示。（算法5.1）,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的一般转置算法（P98 算法5.1） Status TransposeSMatrix(TSMatrix M, TSMatrix /TransposeSMatrix,5.3 矩阵的压缩存储稀疏矩阵,算法5.1

15、分析 算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;+col) for(row=0;row=m;+row) Tcolrow=Mrowcol; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法TransposeSMatrix的时间复杂度为O(n*n2)。 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于 tu=mu*nu 的情况。,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的快速转置算法（P100 算法5.

16、2） 算法思想：对M.data扫描一次，按M.data第二列提供的列号一次确定位置装入B的一个三元组。 具体实现：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。 为了预先确定矩阵M中的每一列的第一个非零元素在数组T中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组T中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num0n和cpot0n,5.3 矩阵的压缩存储稀疏矩阵,两个一维数组num0n和cpot0n： num0n：统计M中每列非零元素的个数，nu

17、mcol的值可以由A的第二列求得。 cpot0n：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 （ 2= col = M.nu） 矩阵M和相应的三元组M.data可以求得: col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的快速转置算法（P100 算法5.2） Status FastTransposeSMatrix(TSMatrix M, TSMatrix / Fa

18、stTransposeSMatrix,5.3 矩阵的压缩存储稀疏矩阵,算法5.2分析 算法的时间复杂度为O(mu*nu)，与一般传统矩阵的转置算法的时间复杂度相同。 三元组顺序表又称“有序的双下标法”，其特点： 非零元在表中按行序有序存储，方便依行顺序处理的矩阵运算，但不能进行随机存取，需从头开始进行查找。 引入行逻辑链接的顺序表可随机存取,5.3 矩阵的压缩存储稀疏矩阵,稀疏矩阵的行逻辑链接的顺序表存储结构 #define maxsize 12500 typedef struct int i,j; ElemType e; Triple; typedef struct Triple datam

19、axsize+1; / 非零元三元组表 int rposMAXRC+1; / 各行第一个非零元的位置表 int mu,nu,tu; / 矩阵的行数、列数和非零元个数 TSMatrix;,5.3 矩阵的压缩存储稀疏矩阵,两个稀疏矩阵相乘算法 从两个稀疏矩阵相乘的例子，容易看出行逻辑链接的顺序表表示方法的优越性。 两个矩阵相乘的经典算法：若设Q=M*N，其中，M是m1*n1矩阵，N是m2*n2矩阵，当n1=m2时，有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0 for(k=1;k=n1;+k) qij+=mik*nkj; 此算法的复杂度为O(m1*n1*n2)

20、。,5.3 矩阵的压缩存储稀疏矩阵,两个稀疏矩阵相乘算法 3 0 0 5 0 2 0 6 M = 0 1 0 0 N = 1 0 Q = -1 0 2 0 0 0 -2 4 0 4 0 0 i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 2 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4,5.3 矩阵的压缩存储稀疏矩阵,两个稀疏矩阵相乘算法（P102 算法5.3） 设计思想:对M中每个元素，找到N中所有满足条件的元素，求得和的乘积，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一

21、累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。 Q初始化； if (Q是非零矩阵) /逐行求积 for (arow = 1; arow = M.mu; +arow) /处理M的每一行 ctemp=0; /累加器清零 计算Q中第arow行的积并存入ctemp 中; 将ctemp 中非零元压缩存储到Q.data; /for arow /if,5.3 矩阵的压缩存储稀疏矩阵,两个稀疏矩阵相乘算法（P102 算法5.3） Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix ,5.3 矩阵的压缩存储稀疏矩

22、阵,for (p=M.rposarow;pMAXSIZE) return ERROR; Q.dataQ.tu=arow,ccol,ctempccol; /if /for arow /if return OK; /MultSMatrix,5.4 广义表的定义,广义表 （Lists，又称列表）是线性表的推广。 线性表定义为n=0个元素a1,a2,a3,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者

23、是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,an)。LS是广义表的名字，n为它的长度。若ai是广义表，称它为LS的子表。,5.4 广义表的定义,抽象数据类型广义表的ADT定义 ADT GList 数据对象: D=i=1,2,.,n=0;ei(-AtomSet或ei(-GList,AtomSet为某个数据对象 数据关系:R1=|ei-1,ei(-D,2=i=n) 基本操作: InitGlist( 初始条件:广义表L存在； 操作结果:销毁广义表L。,5.4 广义表的定义,CopyGlist( 初始条件:广义表L存在； 操作结果:判断广义表L是否为空。,5.4 广义表的定义,Get

24、Head(L); 初始条件:广义表L存在； 操作结果:取广义表L的头。 GetTail(L); 初始条件:广义表L存在； 操作结果:取广义表L的尾。 InsertFirst_GL( 初始条件:广义表L存在； 操作结果:遍历广义表L,用函数Visit处理每个元素。 ADT GList；,5.4 广义表的定义,广义表一般记作:LS=(a1,a2,.,an) LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子和子表。 当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾。,5.4 广义表的定义,广义表的存储结构 广义表的头尾链表存储表示 typedef

25、 emnuATOM,LIST ElemTag; typedef struct GLNode ElemTag tag; union AtomType atom; structstruct GLNode *hp,*tp;ptr; ,5.4 广义表的定义,例：有A、B、C、D、E五个广义表的描述如下： A=() A是一个空表,它的长度为零 B=(e) 列表B只有一个原子e,B的长度为1 C=(a,(b,c,d) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d) D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=(),(e),(a,(b,c,d) E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,.),第5章作业,P95P124 以下题目做在书本上： 5.4.1、 5.4.2（1.8.） 以下题目做在习题本上，必须抄题 例5.1、 例5.5、 5.4.3（2.、4.） 5.4.4（5.）,The End,Data Structure,