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

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 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 a3

2 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


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案_学科竞赛_高中教育_教育专区。§5 §5.1 特殊矩阵 §5.1.1 三角矩阵与...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 ...用这两种结点结构所得的二叉树的存储结构分别称为...0.05 n a<70 y 60~69 D 0.15 70~79...
广东省汕头市金山中学高中信息技术 pascal教程02 第二课 读懂程序教案
广东省汕头市金山中学高中信息技术 pascal教程02 第二课 读懂程序教案_其它课程_高中教育_教育专区。第二课 读懂程序接下来,我们要学着去读懂程序。 我们用上节课...
广东省汕头市金山中学2013届高三上学期期末语文试题
汕头市金山中学 2012-2013 学年度第一学期期末考试 ...上各种竞赛班, 真是费尽心思,但往往心劳日拙,...随着社会的开放与进步,高中生谈恋爱在校园已成普遍...
更多相关标签:
广东省汕头市金山中学 | 广东省汕头市潮阳区 | 广东省汕头市 | 广东省汕头市邮编 | 广东省汕头市潮南区 | 广东省汕头市澄海区 | 广东省汕头市金平区 | 广东省汕头市地图 |