当前位置:首页 >> 学科竞赛 >>

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案


§5
§5.1 特殊矩阵 §5.1.1 三角矩阵与对称矩阵

矩阵的压缩存储
a11 0 0 0 0 a21 a22 0 0 0 a31 a32 a33 0 0 a41 a42 a43 a44 0 a51 a52 a53 a54 a55 上三角矩阵 a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45 a51 a52 a53 a54 a55 对称矩阵

设有矩阵 A : array [1..n , 1..n] of Atype; 三角矩阵: 若 A 的对角线以上(或以下)的元素均为零。 对称矩阵: 若 A 中的元素满足: aij = aji (1≤i,j≤n) , 则称为 n 阶对称矩阵。 为了节省存储空间, 三角矩阵和对称矩阵都不需存储对角线以上 (或以下)的元素,一般采用一维数组的结构。 V: 1 a11 2 a21 3 a22 4 a31 5 a32 6 a33 7 a41 8 a42 9 a43 10 a44 …… ……

此时需要

个元素的存储空间。

若将上三角矩阵中的元素按行顺序存储到 V 中,则 V[k]与 A[i, j]的对应关系是: k = ①

若将下三角矩阵中的元素按行顺序存储到 V 中,则 V[k]与 A[i, j]的对应关系是: k= ② a11 a12 a13 a14 a15 0 a22 a23 a24 a25 0 0 a33 a34 a35 0 0 0 a44 a45 0 0 0 0 a55 下三角矩阵

§5.1.2 带状矩阵

在 n×n 的矩阵中, 若所有非零元素均集中在以对角线为中的带状 区中,该带状区包括主对角线上面和下面各 k 条对角线以及主对角线上的元素,这种矩阵 称带状矩阵。
k 条对角线

k 条对角线

11 4 5 0 0 0
主对角线

2 2 12 20 0 0

3 0 10 13 7 6 17 9 6 1 0 2

0 0 8 11 14 18

0 0 0 15 21 3

k=2 的带状矩阵

金山中学计算机竞赛班教程·数据结构

在带状矩阵 A 中,i – j > k 或

③ 时,A[ i , j ] = 0 。

对于带状区以外的 0 元素可不必存储,而只存储带状区中的元素。带状区中有 ④ 个元素,但为了方便起见,每行当作 2k+1 个元素来存 储,此时存储的元素个数为 (2k+1)×n 个。 【参考答案】 : ① ② ③ ④ i×(i-1) / 2 + j (n+(n-i+1))×(i-1) + (j-i+1) j - i > k n×n – (n-k)×(n–k–1)

§5.2 稀疏矩阵 大多数元素的值为零的矩阵称为稀疏矩阵,为了节省存储空间,可以采取三元组或十 字链表等方法来存储。 §5.2.1 三元组表示法 三元组表示法是用三元组(i , j , v)表示矩阵的每个非零元素。 第一行的 i , j , v 分别表示矩阵 A 的行数、列数、非零元素个数,第二行开始的 i , j , v 分别表示矩阵 A 中每个非零元素的行下标、列下标、元素的值。 【例 5.2_1】 15 0 A= 0 0 91 0 0 11 0 0 0 0 0 3 0 0 28 22 0 0 0 0 0 0 0 0 0 - 15 0 0 0 0 0 T= 6 1 1 1 2 2 3 5 6 6 1 4 6 2 3 4 1 3 8 15 22 -15 11 3 -6 91 28

0 -6 0

§5.2.2 三元组矩阵转置 对矩阵的运算有许多,如两个矩阵相加、相乘、转置……等。转置是一种简单的矩阵 运算,对于一个 m×n 的矩阵 M,它的转置矩阵 N 是一个 n×m 的矩阵,且 M(i , j)=N (j , i) 。 【例 5.2_2】 1 2 3 M= 4 5 6 这里只讨论三元组的转置算法。 三元组的转置只需做到: (1)将三元组中的行列值相互交换; (2)将 i、j 相互调换; (3)重排三元组中的次序
5-2

N=

1 4 2 5 3 6

金山中学计算机竞赛班教程·数据结构

就可实现三元组的矩阵转置。 这里关键是如何重排三元组里的次序。 6 1 1 1 2 2 3 5 6 6 1 4 6 2 3 4 1 3 8 15 22 -15 11 3 -6 91 28 6 1 4 6 2 3 4 1 3 6 1 1 1 2 2 3 5 6 8 15 22 -15 11 3 -6 91 28 6 1 1 2 3 3 4 4 6 6 1 5 2 2 6 1 3 1 8 15 91 11 3 28 22 -6 -15

T=

=>

B=

§5.2.2 矩阵相乘 两个矩阵相乘是另一种常用的矩阵运算。 设: C = A × B A=(aij)为 m×s 的矩阵,B=(bij)是 s×n 的矩阵,则矩阵 A 与矩阵 B 相乘将得到一 个 m×n 的矩阵 C=(cij),其中 cij=ai1b1j + ai2b2j + …… + aisbsj 对于非压缩矩阵,算法如下: for i := 1 to m do for j := 1 to n do begin C[ i , j ] := 0; for k := 1 to s do C[ i , j ] := C[ i , j ] + A[ i , k ] * B[ k , j ]; end; 当 A 和 B 是稀疏矩阵,并分别用三元组 M、N 存储时,应如何处理? 注意 1:两个稀疏矩阵相乘的积不一定是稀疏矩阵; 2:即使 cij=ai1b1j + ai2b2j + …… + aisbsj 中的每个分项 aikbkj 均不为零,其累加 值 Cij 也有可能为零。 【练习】输入 M、N 两个三元组,分别表示 A、B 两个稀疏矩阵,请计算 A、B 的乘积 C, 输出 C 的(压缩存储)三元组 Y。 输入格式: (输入文件 syz.in) 第 1 行: i1 j1 第 2 至 v1+1 行: ai 第 v1+2 行: i2 j2 v1 aj v2 bj (分别表示 A 的行数、列数、非零元素个数) av (行下标、列下标、元素的值) (B 的行数、列数、非零元素个数) bv (i = 1 , 2 ,…, m j = 1 , 2 , … , n)

第 v1+3 至 v1+v2+2 行:bi 输出格式: (输出文件 syz.out) 第 1 行: i3 j3 v3

(C 的行数、列数、非零元素个数)
5-3

金山中学计算机竞赛班教程·数据结构

第 2 至 v3+1 行: ci

cj

cv

5-4


赞助商链接
相关文章:
更多相关标签: