3-5矩阵的压缩存储

3-5矩阵的压缩存储v第三章栈、队列和数组对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储学什么？稀疏矩阵的压缩存储特殊矩阵的压缩存储3-5-1特殊矩阵的压缩存储v第三章栈、队列和数组特殊矩阵什么是特殊矩阵？

特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律特殊矩阵如何压缩存储？为值相同的元素分配一个存储空间特殊矩阵压缩存储后有什么要求吗？保证随机存取，即在O(1)时间内寻址3647862842481697460582957A＝对称矩阵特点：aij=aji如何压缩存储对称矩阵呢？只存储下三角部分的元素对称矩阵aij在一维数组中的序号=

i×(i-1)/2+j∵一维数组下标从0开始∴aij在一维数组中的下标k=i×(i-1)/2+j-1

1…

i

n1…j…n

aij第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2-1对称矩阵下三角中的元素aij（i≥j）：k＝i×(i-1)/2＋j-1压缩存储后的寻址方法上三角中的元素aij（i＜j），k＝j×(j-1)/2＋i

-1如何压缩存储三角矩阵呢？3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩阵34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩阵相同的常数只存储一个下（上）三角部分的元素三角矩阵下三角矩阵的压缩存储第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2c下三角中的元素aij（i≥j）：k＝i×(i

-1)/2+j-1上三角中的元素aij（i＜j）：k＝n×(n+1)/2下三角矩阵压缩存储后的寻址方法上三角矩阵的压缩存储请仿此给出三角矩阵对角矩阵对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，所有其他元素都为零。

a11a120

00a21a22

a23000a32

a33a34000

a43

a44

a45000a54

a55A=如何压缩存储对角矩阵呢？只存储非零元素

元素aij在一维数组中的序号=2+3(i-2)+(j-i+2)=2i+j-2∵一维数组下标从0开始∴元素aij在一维数组中的下标=

2i+j-3a11a12000a21a22

a23000a32a33

a34000

a43a44

a45

000a54a55A=

a11a12a21a22a23a32a33a34a43a44a45a54a550123456789101112第1行第2行第3行对角矩阵3-5-2稀疏矩阵的压缩存储v第三章栈、队列和数组稀疏矩阵什么是稀疏矩阵？

稀疏矩阵：矩阵中有很多零元素，并且分布没有规律稀疏矩阵如何压缩存储？只存储非零元素，零元素不分配存储空间如何只存储非零元素？

三元组：（行号，列号，非零元素值）300700

10200000000008A=如何存储三元组表？

三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表((1,1,3),(1,4,7),(2,3,1),(3,1,2),(5,4,8))template<typenameDataType>structelement{

introw,col;

DataTypeitem};

三元组：（行号，列号，非零元素值）稀疏矩阵300700

10200000000008A=

三元组顺序表：采用顺序存储结构存储三元组表三元组顺序表三元组顺序表需要预留存储单元吗？300700

10200000000008A=稀疏矩阵的修改操作三元组表的插入/删除操作((1,1,3),(1,4,7),(2,3,1),(3,1,2),(5,4,8))

113147231312548空空空闲闲闲rowcolitem01234MaxTerm-1

5（非零元个数）

5（矩阵的行数）

6（矩阵的列数）能唯一表示稀疏矩阵吗？constintMaxTerm=100;structSparseMatrix{elementdata[MaxTerm];intmu,nu,tu;};三元组顺序表

113147231312548空空空闲闲闲rowcolitem01234MaxTerm-1

5（非零元个数）

5（矩阵的行数）

6（矩阵的列数）十字链表十字链表：采用链接存储结构存储三元组表三元组顺序表不适合什么情况？稀疏矩阵的加法、乘法等操作，非零元素的个数及位置都会发生变化，则在三元组顺序表中就要进行插入和删除操作，顺序存储就十分不便rowcolitemdown