第02章 数组和稀疏矩阵

1、第第2章章 数组数组数组数组稀疏矩阵稀疏矩阵数数 组组n定义定义 相同类型的数据元素的集合。相同类型的数据元素的集合。n一维数组的一维数组的示例示例35 27 49 18 60 54 77 83 41 020 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 0 a, i = 0 a+i*la二维数组二

2、维数组111101121202111101101000mnananamaaamaaamaaaa行优先存放：行优先存放： 设数组开始存放位置设数组开始存放位置 LOC( 0, 0 ) = a, 每个元每个元素占用素占用 l 个存储单元个存储单元 LOC ( i, j ) = a + ( i * m + j ) * l三维数组三维数组各维元素个数为各维元素个数为 m1, m2, m3 下标为下标为 i1, i2, i3的数组元素的存储地址：的数组元素的存储地址： （按页（按页/行行/列存放）列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 +

3、 i3 ) * l 前前i1页总页总元素个数元素个数第第i1页的页的前前i2行行总总元素个数元素个数n 维数组维数组各维元素个数为各维元素个数为 m1, m2, m3, , mn 下标为下标为 i1, i2, i3, , in 的数组元素的存储地的数组元素的存储地址：址： limianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 二维数组二维数组 三维数组三维数组行向量行向量 下标下标 i 页向量页向量 下标下标 i列向量列向量 下标下标 j 行向量行向量 下标

4、下标 j 列向量列向量 下标下标 k特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储的元素，如零元素或对称元素，不再存储。存储。对称矩阵对称矩阵三对角矩阵三对角矩阵对称矩阵的压缩存储对称矩阵的压缩存储设有一个设有一个 n n 的对称矩阵的对称矩阵 A。11121110122221201112111010020100Annn

5、nnnnnaaaaaaaaaaaaaaaa在矩阵中，在矩阵中，aij = ajin为节约存储空间，只存对角线及对角线以为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为的元素。前者称为上三角矩阵，后者称为下三角矩阵。下三角矩阵。n把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B 中，中，称之为对称矩阵称之为对称矩阵 A 的压缩存储方式。的压缩存储方式。n数组数组 B 共有共有 n + ( n - - 1 ) + + 1 = n*(n+1)/2 个元素。个元素。上三角矩阵下三角矩阵33323

6、130232221201312111003020100aaaaaaaaaaaaaaaa33323130232221201312111003020100aaaaaaaaaaaaaaaa11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵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在数组在数组B中的存放位置中的存放位置为为 1 + 2 + + i + j = (i + 1)* i / 2

7、+ j前前i行行元素总数元素总数 第第i行第行第j个个元素前元素个数元素前元素个数若若 i j，数组元素，数组元素Aij在矩阵的下三角在矩阵的下三角部分，在数组部分，在数组 B 中没有存放。因此，找它中没有存放。因此，找它的对称元素的对称元素Aji。 Aji在数组在数组 B 的第的第 (2*n- -j- -1) * j / 2 + i 的位置中找到。的位置中找到。三对角矩阵的压缩存储三对角矩阵的压缩存储1121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22

8、a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10n三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下最下最临近的两条对角线上的元素外，所有其它元素临近的两条对角线上的元素外，所有其它元素均为均为0。总共有。总共有3n- -2个非零元素。个非零元素。n将三对角矩阵将三对角矩阵A中三条对角线上的元素按行存放中三条对角线上的元素按行存放在一维数组在一维数组 B 中，且中，且a00存放存放于于B0。n在三条对角线上的元素在三条对角线上的元素aij 满足满足 0 i n- -1, i- -1 j i+1n在一维数组在一维数组 B 中中 Aij

9、 在第在第 i 行，它前面有行，它前面有 3*i- -1 个非零元素个非零元素, 在本行中第在本行中第 j 列前面有列前面有 j- -i+1 个，所以元素个，所以元素 Aij 在在 B 中位置为中位置为 k = 2*i + j。 0000280000000091039000000006000017000110150022000A76稀疏矩阵稀疏矩阵 (Sparse Matrix)非零元素个数非零元素个数远远少于矩阵元素个数远远少于矩阵元素个数稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型template class SparseMatrix;template class Trituple /三元

10、组三元组friend class SparseMatrix private: int row, col; /非零元素行号非零元素行号/列号列号 Type value; /非零元素的值非零元素的值template class SparseMatrix /稀疏矩阵类定义稀疏矩阵类定义 int Rows, Cols, Terms; /行行/ /列列/ /非零元素数非零元素数 Trituple smArrayMaxTerms; public: /三元组表三元组表 SparseMatrix (int MaxRow, int Maxcol); SparseMatrix& Transpose (Sp

11、arseMatrix&); /转置转置 SparseMatrix& Add (SparseMatrix a, SparseMatrix b); /相加相加 SparseMatrix& Multiply(SparseMatrix a, SparseMatrix b); /相乘相乘 0000280000000091039000000006000017000110150022000稀疏矩阵稀疏矩阵 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6

12、 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 80000015003901700000000006022280000000001100910000 转置矩阵转置矩阵 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 4 4 9 91 1 1 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 3 3 0 0

13、 2 22 2 4 3 3 2 2 - - - -6 6 5 5 5 1 1 1 17 7 6 5 5 3 3 3 39 9 7 6 6 0 0 1 16 6 7 6 8用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5

14、 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 - - - -6 6 4 3 3 2 2 - - - -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6 6 7 8 7 6 8v稀疏矩阵转置算法思想稀疏矩阵转置算法思想n设矩阵列数为设矩阵列数为 Cols，对矩阵三元组表扫描，对矩阵三元组表扫描

15、Cols 次。第次。第 k 次检测列号为次检测列号为 k 的项。的项。n第第 k 次扫描找寻所有列号为次扫描找寻所有列号为 k 的项，将其的项，将其行号变列号、列号变行号，顺次存于转置行号变列号、列号变行号，顺次存于转置矩阵三元组表。矩阵三元组表。v稀疏矩阵的转置稀疏矩阵的转置 template SparseMatrix& SparseMatrix : Transpose (SparseMatrix& a) SparseMatrix b (a.Cols, a.Rows); b.Rows = a.Cols; b.Cols = a.Rows; b.Terms = a.Terms;

16、/转置矩阵的列数转置矩阵的列数, ,行数和非零元素个数行数和非零元素个数 if ( a.Terms 0 ) int CurrentB = 0; /转置三元组表存放指针转置三元组表存放指针 for ( int k = 0; k a.Cols; k+ ) /对所有列号处理一遍对所有列号处理一遍 for ( int i = 0; i 0时，时，表的第一个表元素称为广义表表的第一个表元素称为广义表 的表头的表头(head)，除此之外，其它表元素组，除此之外，其它表元素组 成的表称为广义表的表尾成的表称为广义表的表尾(tail)。 A=( );/A是一个空是一个空表表 B=(e);/表表B有一个原子有一个原子 C=(a,(b,c,d);/两个元素为原子两个元素为原子a和子表和子表(b,c,d) D=(A,B,C);/有三个元素均为列表有三个元素均为列表 E=(a,