《数组与广义表》PPT课件.ppt

数组与广义表,主 讲 ： 薛 春 艳,第5章 数组和广义表,【定义】 数组是线性表的结构上的扩展。即线性表中的数据元素本身也是一个数据结构。数组可以看成是数据元素本身就是线性表的线性表。,5.1 数组的定义和运算,一维数组是一个线性表，其每个元素是一个不可分割的最小单位。 二维数组可以看成是一个线性表，线性表中的每个数据元素也是一个线性表。 n维数组是一个线性表，其每个数据元素是一个n-1维的数组。,我们可以把二维数组看成一个线性表： A=( 1 2 j n)，其中j（1j n）本身也是一个线性表，称为列向量。矩阵Amn看成包含n个列向量的线性表，即 j= ( a1j , a2j , , amj ),Amn=,a11 a12 a1j a1n a21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amn,我们还可以将数组Amn看成包含m个行向量的线性表: B = ( 1，,2,， ，m )，其中i（1i m）本身也是一个线性表，称为行向量，即： i = （ai1，ai2， ，aij ，ain）。,对于数组A，一旦给定其维数n及各维长度bi（1in），则该数组中元素的个数和元素之间的关系就不再发生变化了，既不可以对数组做插入和删除操作，也不涉及移动元素操作。,数组的特点,数组中的数据元素具有相同的数据类型。 数组是一种随机存取结构，只要给定一组下标，就可以访问与其对应的数组元素。 数组中的元素个数是固定的。,【数组的特点】,数组是一组有固定个数的数据元素的集合。,由于数组中的数据元素的个数是固定的，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入和删除一个元素，对于数组的操作一般只有两类：,【数组的操作两类】 （1）给定下标，存取对应位置的元素值； （2）给定下标，修改对应位置的元素值。 因此，数组的操作主要是数据元素的定位，即给定元素的下标，得到该元素在计算机中的存放位置。其实质就是地址计算问题。,数组的运算,数组的顺序存储和实现,由于在数组中数据元素的个数是固定的，因此对于数组而言，采用顺序存储表示比较适合。 在计算机中，内存储器的结构是一维的。对于一维数组可直接采用顺序存储。 用一维的内存存储表示多维数组，就必选按某种次序将数组中的元素排成一个线性序列，然后将这个线性序列存放在一维的内存储器中，这就是数组的顺序存储结构。 数组的顺序存储结构有两种：一种是按行序存储，另一种是按列序存储。,若知道第一个元素的存储地址 Loc(a00), 如果每个元素占size个存储单元 ， 则任意元素aij的地址计算公式为：,Loci,j=Loc0,0 + (ni+j)size,数组元素地址 = 数组首地址 + 数组首地址与所求元素之间的距离,该元素前面的数据元素个数每个数据元素占的存储单元,二维数组Amn中任一元素ai,j 的存储位置: Loc(i,j) = Loc(0,0) + ni + j size,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,size,已知： m=2，n=3，Loc(0,0)=100，i=1，j=1，size=4 Loc(1,1) = Loc(0,0) + 31+14= 100+4*4=116,Loc(aij) = Loc(a00) + m j + i size,若知道第一个元素的存储地址 Loc(a11),如果每个元素占size个存储单元则任意元素aij的地址计算公式为：,【特殊矩阵压缩存储的压缩原则】,5.3 特殊矩阵的压缩存储,特殊矩阵：指其相同元素或零元素在矩阵中的分布具有一定规律的矩阵。,元素分布有特殊规律的矩阵，找到规律对应的公式，实现压缩存储； 非零元素很少的稀疏矩阵，可采用只存储非零元素的方法实现压缩存储。,三角矩阵大体分为： 下三角矩阵：对于一个n阶矩阵A，若当ij时，有aij=0，则此矩阵称为上三角矩阵 对称矩阵 ：若矩阵中的所有元素均满足aij=aji，则称此矩阵为对称矩阵。,三角矩阵的压缩存储,1、对于下三角矩阵，按“行序为主序”进行存储，得到的序列为：a11 , a21 , a22 , a31 , a32 , a33an1 , an2ann。 2、由于下三角矩阵的元素个数为 n(n+1)/2 ，所以可压缩存储到一个大小为 n(n+1)/2 的一维数组中。 3、下三角矩阵中元素aij (ij)，在一维数组A中的位置为： Loc i ,j= Loc1,1+ i (i -1)/2+ j-1 4、下三角矩阵中元素aij (ij)，在一维数组A中对应的下标为： k=i(i-1)/2+j-1 ij (矩阵下三角元素),下三角矩阵：,1、对于上三角矩阵，按“列序为主序”进行存储，得到的序列为：a11 , a12 , a22 , , a1n , a2n , , ann。 2、由于上三角矩阵的元素个数为 n(n+1)/2 ，所以可压缩存储到一个大小为 n(n+1)/2 的一维数组中。 3、上三角矩阵中元素aij (ij)，在一维数组A中的位置为： Loc i , j = Loc1,1+j ( j -1 )/ 2+ i-1 4、上三角矩阵中元素aij (ij)，在一维数组A中对应的下标为： k=j (j-1)/2+i-1 ij (矩阵上三角元素),上三角矩阵：,对称矩阵：,对于对称矩阵，因其元素满足aij=aji，我们可以为每一对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将n2个元素压缩到n(n+1)/2个空间中。,一维数组A中对应的下标为：,带状矩阵：在矩阵A中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。,特点:,时，即| i-j |1，aij非零，其他元素均为零。,带状矩阵的压缩存储,三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。其方法为：,1. 确定存储该矩阵所需的一维向量空间的大小：,三对角带状矩阵中除第一行和最后一行只有两个元素外，其余各行均有3个非零元素。由此可得到一维向量所需的空间大小为：3n-2。,2. 确定非零元素在一维数组空间中的位置：,Loci , j = Loc1,1+3( i-1 )-1+j-i+1 = Loc1,1+2( i-1 )+j-1,3. 矩阵中元素aij 在一维数组A中对应的下标为： k=2(i-1)+j-1 ( 1i , jn，| i - j |1),稀疏矩阵： 矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总数的25%30%,或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。,稀疏矩阵的压缩存储,对于稀疏矩阵的压缩存储要求在存储非零元素的同时，还必须存储该非零元素在矩阵中所处的行号和列号。我们将这种存储方法叫做稀疏矩阵的三元组表示法。,每个非零元素在一维数组中的表示形式：,稀疏矩阵的三元组表表示法,#define MAXSIZE 12500 typedef struct int i, j; ElemType e; Triple; / 三元组类型 typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; /行数、列数、非零元素个数 TSMatrix; / 稀疏矩阵类型,稀疏矩阵的顺序存储C语言实现,三元组顺序表data：,稀疏矩阵的顺序存储,三元组顺序结构： mu=6 nu=7 tu=8 MAXSIZE=8,已知稀疏矩阵M用一个三元组表A来表示它，M矩阵的转置矩阵为N，用三元组表B来表示。 要求： (1)实现稀疏矩阵M的转置；（实质：行列下标值互换） (2)转置后的矩阵N仍然是以“行序为主序”存放到三元组表B中。 实现： 第一步：将存储矩阵M的三元组表A中所有col=1的三元组，转置后（即行列下标值互换）依次存放到三元组表B中； 第二步：将三元组表A中所有col=2的三元组，转置后（即行列下标值互换）依次存放到三元组表B中； 依此类推 直到将A中所有元素按照col递增的次序都存放到三元组表B中为止。,三元组表实现稀疏矩阵的转置运算,row,col,len,1,3,-3,1,6,15,2,1,12,2,5,18,3,4,24,3,1,9,4,6,-7,6,3,14,三元组表B,优点：能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。,结点结构： 在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点row, col, value 分别表示某个非零元素所在的行号、列号和元素的值；down 和 right 分别为向下与向右指针： right： 用于链接同一行中的下一个非零元素； down：用以链接同一列中的下一个非零元素。,十字链表中结点的结构示意图：,稀疏矩阵的链式存储：十字链表,同一行的非零元素通过 right域链接成一个单链表。 同一列的非零元素通过down域链接成一个单链表。 矩阵中任一非零元素 aij 所对应的结点既处在第 i 行的行链表上，又处在第 j 列的列链表上，这好像是处在一个十字交叉路口上，所以称其为十字链表。 附设一个存放所有行链表的头指针的一维数组和一个存放所有列链表的头指针的一维数组。,十字链表的构造,typedef struct OLNode int i, j; ElemType e; struct OLNode * right , *down ; OLNode ; *OLink ; typedef struct OLink * rhead, *chead; int mu, nu, tu; CrossList ;,十字链表的C语言实现,稀疏矩阵M,稀疏矩阵的十字链表结构,广义表是线性表的一种推广，是n个数据元素（d1，d2，d3，dn）的有限序列，但不同的是，广义表中的每个数据元素 di 既可以是单个元素，还可以是一个广义表，通常记作： GL=（d1，d2，d3，dn） 若 di 是一个广义表，则称 di 是广义表GL的子表。 在GL中， d1是GL的表头，其余部分组成的表（d2，d3，dn）称为GL的表尾。,5.4 广 义 表,1、A = ( ),2、B = ( e ),3、C = ( a, ( b , c , d ) ),4、D = ( A , A , ( ) ),5、E = ( A , B , C ),6、F = ( a , F ),表示广义表A是一个空表，其长度为0,表示广义表B长度为1，只有一个原子项e,表示广义表C长度为2，两个元素分别为原子项a 和子表(b , c , d)。,表示广义表D长度为3，三个元素都是广义表，分别为A、A 和( )。,表示广义表E长度为3，三个元素A、B、C都是广义表，代入值以后E=( ( ) , (e) , ( a, ( b , c , d ) ) )。,表示广义表F长度为2，两个元素分别是原子项a和子表F。这是一个递归表，相当于无穷广义表 F=（a , F）= (a, (a, (a, , ) ) )。,A,C,B,E,广义表中的数据元素有相对次序。 广义表的元素可以是子表，而子表还可以是子表，由此，广义表是一个多层的结构。 广义表的长度定义为最外层包含元素个数。 广义表的深度定义为所含括弧的重数; 注意: “原子结点”的深度为 0 ; “空表”的深度为 1 。 广义表可以被其他广义表共享。如：B=（A，A，D）广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。 广义表可以是一个递归的表，如： C=（a , C）= (a, (a, (a, , ) ) )， 递归表的深度是无穷值，长度是有限值。,广义表 的结构特点,任何一个非空广义表 GL = ( d1, d2, , dn ) 均可分解为 表头 Head(GL) = d1 和 表尾 Tail(GL) = ( d2, , dn) 两部分,例如: 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 ) ) = ( ),tag：区分表结点和元素结点的标志； hp：指向表头结点的指针； tp：指向表尾结点的指针； data：数据域，存放单元素。,结点结构,广义表的表示法,typedef enum ATOM, LIST ElemTag; ty