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

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


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
广东省汕头市金山中学高中信息技术竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术竞赛班数据结构专项培训教程04串教案_小学作文_小学教育_教育专区。§4 串§4.1 串的匹配 子串的定位操作称为串的模式匹配, 是...
...汕头市金山中学信息学竞赛班数据结构专项培训教程—...
【全国百强校】广东省汕头市金山中学信息竞赛班数据结构专项培训教程—— 01数据结构概论_学科竞赛_高中教育_教育专区。金山中学计算机竞赛班教程·数据结构与算法...
...汕头市金山中学信息学竞赛班数据结构专项培训教程—...
【全国百强校】广东省汕头市金山中学信息竞赛班数据结构专项培训教程—— 07树_学科竞赛_高中教育_教育专区。金山中学计算机竞赛班教程·数据结构与算法设计 §7§...
...汕头市金山中学信息学竞赛班数据结构专项培训教程—...
【全国百强校】广东省汕头市金山中学信息竞赛班数据结构专项培训教程—— 08图_学科竞赛_高中教育_教育专区。信息学奥赛,NOIP,信息学 ...
广东省汕头市金山中学高中信息技术 pascal教程05 第五...
广东省汕头市金山中学高中信息技术 pascal教程05 第五课 基本语句(三)教案_其它课程_高中教育_教育专区。第五课 基本语句(三)§5.1 FOR 语句 FOR 语句用于循环...
广东省汕头市金山中学高中信息技术 pascal教程09 第九...
广东省汕头市金山中学高中信息技术 pascal教程09 第九课 字符串教案_其它课程_高中教育_教育专区。第九课 字符串§9.1 字符串类型,其一般形式: TYPE <标识符>=...
广东省汕头市金山中学高中信息技术 pascal教程06 第六...
广东省汕头市金山中学高中信息技术 pascal教程06 第六课 基本语句(四)教案_其它课程_高中教育_教育专区。第六课 基本语句(四)§6.1 while 语句 其一般形式: ...
广东省汕头市金山中学高中信息技术 pascal教程03 第三...
广东省汕头市金山中学高中信息技术 pascal教程03 第三课 基本语句(一)教案_其它课程_高中教育_教育专区。第三课 基本语句(一)§3.1 程序的三种结构 从程序结构化...
2016-2017学年广东省汕头市金山中学高一上学期入学考试...
汕头市金山中学 2016~2017 学年度上学期高一新生入学测试 英语科试卷第一卷 选择题部分(满分 90 分) 第一部分 英语知识运用(共两节,满分 45 分) 第一节 ...
更多相关标签: