一维数组多维数组特殊矩阵的压缩存储稀疏矩阵广义表.PPT

1、一维数组多维数组特殊矩阵的压缩存储 稀疏矩阵广义表,第五章 数组与广义表,一维数组,定义 相同类型的数据元素的集合。一维数组的示例与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素。,35 27 49 18 60 54 77 83 41 02,0 1 2 3 4 5 6 7 8 9,数组的定义和初始化,main ( ) int a13 = 3, 5, 7 , *elem; for ( int i = 0; i 3; i+ ) printf ( “%d”, a1i, “n” ); /静态数组 elem = a1; for ( int i = 0; i 3; i+ ) printf (

2、“%d”, *elem, “n” ); /动态数组 elem+; ,数组溢出的处理,一维数组的问题在于：如果其空间大小已经分配，一旦空间占满，再加入新元素将产生溢出。已知一维数组的大小为 MaxSize，其定义和分配如下： typedef int ElemType; ElemType *data = new ElemTypeMaxSize;现已产生溢出，那么处理溢出的方法为：,const int NewSize = 100;ElemType * newArray = new ElemTypeNewSize; if ( newArray = NULL ) printf (“存储分配错!n” );

3、 exit (1); int n = ( NewSize = MaxSize ) ? NewSize : MaxSize;ElemType *srcptr = data;ElemType *destptr = newArray;while ( n- ) *destptr+ = *srcptr+;free (data);data = newArray;,多维数组,多维数组是一维数组的推广多维数组是一种非线性结构。其特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。,二维数组 三维数组,行向量 下标 i 页向量 下标 i

4、列向量 下标 j 行向量 下标 j 列向量 下标 k,二维数组,行优先存放： 设数组开始存放位置 LOC( a00 ) = a, 每个元素占用 l 个存储单元 LOC( ajk ) = a + ( j * m + k ) * l,列优先存放： 设数组开始存放位置 LOC( a00 ) = a, 每个元素占用 l 个存储单元 LOC( ajk ) = a + ( k * n + j ) * l,三维数组,各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地址： （按页/行/列存放）,LOC ( ai1i2i3 ) = a + ( i1* m2 * m3 + i2*

5、 m3 + i3 ) * l,前 i1 页总元素个数,第 i1 页的前 i2 行总元素个数,第 i2 行前 i3 列元素个数,n 维数组,各维元素个数为 m1, m2, m3, , mn 下标为 i1, i2, i3, , in 的数组元素的存储地址：,LOC ( ai1i2 , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l,特殊矩阵的压缩存储,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩

6、阵三对角矩阵,对称矩阵的压缩存储,设有一个 nn 的对称矩阵 A。,在矩阵中，aij = aji,为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。,下三角矩阵,上三角矩阵,把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。数组 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 个元素。,下三角矩阵,B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1,0 1 2 3 4 5 6 7 8 n(n+1)/2-1,若 i j, 数组元素Aij在数组

7、B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j,前i行元素总数 第i行第j个元素前元素个数,若 i j，数组元素 Aij 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素Aji：= j *(j +1) / 2 + i 若已知某矩阵元素位于数组 B 的第 k个位置，可寻找满足 i (i + 1) / 2 k (i + 1)*(i + 2) / 2的 i, 此即为该元素的行号。 j = k - i * (i + 1) / 2此即为该元素的列号。 例，当 k = 8, 3*4 / 2 = 6 k j，数组元素Aij在矩阵的下三角部分，在数组

8、 B 中没有存放。因此，找它的对称元素Aji。 Aji在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。,三对角矩阵的压缩存储,B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1,0 1 2 3 4 5 6 7 8 9 10,三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B0。在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1在一维数组 B 中 Aij 在第

9、 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 Aij 在 B 中位置为 k = 2*i + j。,若已知三对角矩阵中某元素 Aij 在数组 B 存放于第 k 个位置，则有 i = (k + 1) / 3 j = k - 2 * i例如，当 k = 8 时， i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 当 k = 10 时， i = (10+1) / 3 = 3, j = 10 - 2*3 = 4,行数 m = 6, 列数 n = 7, 非零元素个数 t = 8,稀疏矩阵 (Sparse Matrix),稀疏矩阵的定义

10、,设矩阵 Amn 中有 t 个非零元素，若 t 远远小于矩阵元素的总数 mn，则称矩阵A 为稀疏矩阵。为节省存储空间，应只存储非零元素。非零元素的分布一般没有规律，应在存储非零元素时，同时存储该非零元素的行下标 row、列下标 col、值 value。每一个非零元素由一个三元组唯一确定： ( 行号 row, 列号 col, 值 value ),#define MaxSize 100; /由用户定义typedef int MatrixData; /由用户定义typedef struct /三元组定义 int row, col; /非零元素行号, 列号 MatrixData value; /非零元

11、素的值 Triple;typedef struct Triple dataMaxSize; /三元组表 int m, n, t; /行/列/非零元素数 TSMatrix;,稀疏矩阵(SparseMatrix)的结构定义,稀疏矩阵的转置,一个 mn 的矩阵 A，它的转置矩阵 B 是一个 nm 的矩阵，且 Aij = Bji。即矩阵 A 的行成为矩阵 B 的列，矩阵 A 的列成为矩阵 B 的行。在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。稀疏矩阵的转置运算要转化为对应三元组表的转置。,稀疏矩阵,转置矩阵,用三元组表表示的稀疏矩阵及其转置,稀疏矩阵转置算法,设矩

12、阵列数为 n，对矩阵三元组表扫描 n 次。第 k 次检测列号为 k 的项。第 k 次扫描找寻所有列号为 k 的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。void Trans ( TSMatrix *A, TSMatrix *B) B-m = A-n; B-n = A-m; B-t = A-t; /转置矩阵的列数,行数和非零元素个数,if ( A-t 0 ) int s = 0; /转置三元组表存放指针 for ( int k = 0; k n; k+ ) for ( int i = 0; i t; i+ ) if ( A-datai.col = k ) B-datas.row

13、= k; B-datas.col = A-datai.row; B-datas.value = A-datai.value; s+; ,快速转置算法,设矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( n* t )。若矩阵有 200 行，200 列，10,000 个非零元素，总共有 2,000,000 次处理。为加速转置速度，建立辅助数组 num 和 cpot，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 cpot 表, 按查到的位置直接将该项存入转置三元组表中,for ( int i = 0; i n;

14、 i+ ) numi = 0; for ( i = 0; i t; i+ ) numA-datai.col+; cpot0 = 0; for ( i = 1; i n; i+ ) cpoti = cpoti-1+numi-1;,稀疏矩阵的快速转置void FastTrans ( TSMatrix *A, TSMatrix *B ) int *num = new intA-n; int *cpot = new intA-n; B-m = A-n; B-n = A-m; B-t = A-t; if ( A-t 0 ) for (int i = 0; i n; i+) numi = 0; for (

15、 i = 0; i t; i+ ) numA-datai.col+; cpot0 = 0; for ( i = 1; i n; i+ ) cpoti = cpoti-1+numi-1;,for ( i = 0; i t; i+ ) int j = cpotA-datai.col; B-dataj.row = A-datai.col; B-dataj.col = A-datai.row; B-dataj.value = A-datai.value; cpotA-datai.col+; delete num; delete cpot;,带行指针数组的二元组表,转置时间代价为 O(max(A-t,

16、A-n) )。若矩阵有 200 列，10000 个非零元素，总共需要10000 次处理。,稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第 i 个元素的数组下标 i代表矩阵的第 i 行，元素的内容即为稀疏矩阵第 i 行的第一个非零元素在二元组表中的存放位置。,二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。,广义表 (General Lists ),广义表的概念 广义表是n ( 0 )个表元素的有限序列，记作 LS (a0, a1, a2, , an-1) LS是表名, ai 是表元素, 它可以是表 (称为

17、子表)，可以是数据元素 (称为原子)。n为表的长度。n = 0 的广义表为空表。n 0时, 表的第一个表元素称为广义表的表头 (head), 除此之外, 其它表元素组成的表称为广义表的表尾 (tail)。,广义表的特性,有次序性有长度,A( )B( u, v ) head(B) = u, tail(B) =(v)C( a, ( x, y, z ) ) head(C) = aD( B, C, A ) tail(C) = ( ( x, y, z ) )E( B, D )F( d, F ),有深度可共享,可递归,A,B,C,u v,D,空表,线性表,再入表,纯表,F,递归表,d,广义表的头尾表示,当

18、结点标志tag = 1时，该结点为表结点 hp为指示表头元素结点的指针 tp为指示表尾 (为广义表) 结点的指针当结点标志tag = 0时，该结点为原子结点 atom存放原子结点的值,tag=1 hp tp,tag=0 atom,表结点 原子结点,A,1,B,F,1,1,0 d,E,B,D,1,1,1,C,1,D,1,1,1,NULL,0 a,1,1,1,0 x,0 y,0 z,1,0 u,0 v,广义表的层次表示,当结点标志tag = 1时，该结点为表结点 hp为指示表头元素结点的指针 tp为指示同一层下一结点的指针当结点标志tag = 0时，该结点为原子结点 atom存放原子结点的值 tp为指示同一层下一结点的指针,tag=1 hp tp,tag=0 atom tp,表结点 原子结点,A,0 z,1,C,0 a,1,0 x,0 y,1,