特殊矩阵的压缩存储
标签: 数据结构
学习人数: 9130


全屏播放
赞赏支持

数据结构中,提供针对某些特殊矩阵的压缩存储结构。

 

这里所说的特殊矩阵,主要分为以下两类:

含有大量相同数据元素的矩阵,比如对称矩阵
含有大量 0 元素的矩阵,比如稀疏矩阵、上(下)三角矩阵

 

针对以上两类矩阵,数据结构的压缩存储思想是:矩阵中的相同数据元素(包括元素 0)只存储一个。

 


对称矩阵

上图中的矩阵中,数据元素沿主对角线对应相等,这类矩阵称为对称矩阵。
矩阵中有两条对角线,其中上图中的对角线称为主对角线,另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。

 

结合数据结构压缩存储的思想,我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等,因此数组中只需存储对角线一侧(包含对角线)的数据即可。

 

对称矩阵的实现过程是,若存储下三角中的元素,只需将各元素所在的行标 i 和列标 j 代入下面的公式:

存储上三角的元素要将各元素的行标 i 和列标 j 代...

登录查看完整内容


课后作业

课后习题

 

【2018年真题】设有一个12 ×12 的对称矩阵M ,将其上三角部分的元素mi,j( 1≤ i ≤ j ≤1)按行优先存入C语言的一维数组N 中,元素m6, 6 在N 中的下标是。        
A . 50        B. 51        C. 55        D. 66

参考答案:A

 

【2017年真题】适用于压缩存储稀疏矩阵的两种存储结构是()
A.三元组表和十字链表            B.三元组表和邻接矩阵
C.十字链表和二叉链表            D.邻接矩阵和十字链表

参考答案:A

 

【2016年真题】有一个100阶的三对角矩阵M,其原始mi,j(1<=i<=100,1<=j<=100)按行优先次序压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是()
A.86        B.87        C.88        D.89

参考答案:B


登录后发布评论

3 条评论
100
2021年7月21日 14:09

才弄懂三对角矩阵的意思,怪不得看视频一脸懵,寻思着3哪来的?哈哈……

BlueSocks
2020年12月19日 17:31

【2016年真题】有一个100阶的对角矩阵M,其原始mi,j(1<=i<=100,1<=j<=100)按行优先次序压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是()
A.86        B.87        C.88        D.89

题目少了个字 三队角矩阵 怪不得 看不懂

Clarksvia
2020年5月19日 17:57

很好,什么时候能更新完哇