数据结构--第五章数组和广义表分析.ppt

第5章 数组和广义表;5.1 数组的定义和运算;Am×n=;Am×n=;上面二维数组的例子，介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。由于这个性质，使得对数组的操作不象对线性表的操作那样，可以在表中任意一个合法的位置插入或删除一个元素。;数组的抽象数据类型定义（ADT Array）;基本操作：;5.2 数组的顺序存储和实现;对于二维数组Amxn 以行为主的存储序列为：a11 ,a12, … a1n ,a21 ,a22 ,…,a2n , … … ,am1 ,am2 , …, amn 以列为主存储序列为：a11, a21,… am1 ,a12 ,a22 ,… ,am2 ,… … ,a1n ,a2n , … ,amn ; 以二维数组Amn为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc[1,1] 求任意元素aij的地址 ，可由如下计算公式得到： Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1) ;三维数组A（1..r , 1..m , 1..n）可以看成是r个m×n的二维数组 ，如下图所示：; 假定每个元素占一个存储单元，采用以行为主序的方法存放 ，首元素a111的地址为Loc[1,1,1]，ai11的地址为Loc[i,1,1]=Loc[1,1,1]+(i-1)*m*n ，那么求任意元素aijk的地址计算公式为：; 如果将三维数组推广到一般情况，即：用j1，j2，j3代替数组下标i，j，k；并且j1，j2，j3的下限为c1，c2，c3，上限分别为d1，d2，d3，每个元素占一个存储单元。则三维数组中任意元素a(j1，j2，j3)的地址为： Loc[j1，j2，j3]=Loc[c1,c2,c3]+1*(d2-c2+1)*(d3-c3+1)*(j1-c1) +1*(d3-c3+1)*(j2-c2)+1*(j3-c3) 其中l为每个元素所占存储单元数。 ;令α1=1*(d2-c2+1)*(d3-c3+1), α2=1*(d3-c3+1), α3=1，则：;5.3 特殊矩阵的压缩存储;对于下三角矩阵，按“行序为主序”进行存储，得到的序列为：a11,a21,a22,a31,a32,a33…an1,an2…ann。由于下三角矩阵的元素个数为n(n+1)/2，所以可压缩存储到一个大小为n(n+1)/2的一维数组中。下三角矩阵中元素aij(ij)，在一维数组A中的位置为： LOC[ i ,j]= LOC[1,1]+ i (i -1)/2+ j-1 ; 同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(ij)在数组C中的存储位置为： Loc[i,j]= Loc[1,1]+j(j -1)/2+ i-1;5.3.2 带状矩阵; 三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。其方法为：;5.3.3 稀疏矩阵;1. 稀疏矩阵的三元组表表示法;三元组表的类型说明：;1）用三元组表实现稀疏矩阵的转置运算;实现转置的简单方法：;算法一、;算法二、;用三元组表实现稀疏矩阵的乘法运算; 根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：; 经典算法中，不论M[i][k]，N[k][j]是否为零，都要进行一次乘法运算，而实际上，这是没有不必要的。采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素做存储，所以可以采用固定三元组a中元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元组b中找所有行号为k的的对应元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）进行相乘、累加从而得到Q[i][j]。即：以三元组a中的元素为基准，依次求出其与三元组b的有效乘积。 ;注意：两个稀疏矩阵相乘的结果不一定是稀疏矩阵。反之，相乘的每个分量M[i，k]×N[k，j]不为零，但累加的结果Q[i，j]可能是零。 例如：;#define MAXSIZE 1000 /*非零元素的个数最多为1000*/ #define MAXROW 1000 /*矩阵最大行数为1000*/ typedef struct {int row, col; /*该非零元素的行下标和列下标*/ ElementType e； /*该非零元素的值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /* 非零元素的三元组表，data[0]