数据结构之特殊矩阵的压缩存储

简介: 数据结构之特殊矩阵的压缩存储

前言


矩阵存储主要还是将线性代数矩阵性质存储到一维或是多维数组中,题目一般都是问在数组的下标是几和下标与矩阵系数的对应关系,对于这种题目画个图设置一个简单的参数代进选项中的公式验证就好了。


有不足之处或是不懂之处尽请评论区留言。

一、数组的存储方式

以一维数组A[0...n-1]为例,其存储结构关系式为:

gif.gif

其中L是每个数组元素所占的存储方式。

对于多维数组,有两种映射方法:按行优先和按列优先。


1.按行优先


设二维数组的行下标与列下标的范围分别为[0,h1]与[0,h2]。


gif.gif


1.按列优先

gif.gif


二、特殊矩阵的压缩存储


1.对称矩阵


76a3d761cede4b08b04b66c4af02e843.png


20180307142930261.png

很明显对于该矩阵a12与之对应相等的值是a21,也就是说可以二者同指向数组同一个下标便可压缩存储。那么我们只需要存储下三角的元素即可,上三角的元素只需要i,j互换就好了,因此元素下标之间的对应关系如下:

20150329215829182.png



2.三角矩阵


对于下三角矩阵:

494bbf6661a94af9963b1d70dda5fa59.png


根据等差数列前n行的元素为i*(i+1)/2,与下标我们需除去自身一行,既i=i-1.


78b0ae1e8d15423e8df7afc0da204cb5.png



对于上三角矩阵:


d506c4ebf9dd4fb2bc4489f208c2e5ea.png

与下三角矩阵相反,为n+n-1+...+1.

第i-1行有n-i+2个元素。

8278955ea35b41299a06672316acb8a4.png



3.三对角矩阵


在三对角矩阵中,所有非零元素都集中在主对角线为中心的3条对角线的区域,其他区域的元素都为零。


c0e6800db09542fcbe1172a8a2409d1b.png


由此可以计算矩阵A三条对角线的元素a_{i,j}在一维数组B中存放的下标为:


gif.gif

公式不推荐背,因为真的很好算,画个图思路痕清晰。


4.稀疏矩阵


矩阵中非零元素个数x,而整个矩阵中总元素个数为t,则当S=x/t\leq 0.05时称为稀疏矩阵。

稀疏矩阵的三元组既可以采用数组存储:

a027fa3c150f4f6d8941b3f866139b04.png

也可以采用十字链表法存储:



20200209210236475.jpg


目录
相关文章
|
13天前
|
存储 安全 数据库
除了 HashMap,还有哪些数据结构可以实现键值对存储?
【10月更文挑战第11天】 除了`HashMap`,其他常见支持键值对存储的数据结构包括:`TreeMap`(基于红黑树,键有序)、`LinkedHashMap`(保留插入顺序)、`HashTable`(线程安全)、`B-Tree`和`B+Tree`(高效存储大量数据)、`SkipList`(通过跳跃指针提高查找效率)及`UnorderedMap`(类似`HashMap`)。选择合适的数据结构需根据排序、并发、存储和查找性能等需求。
|
2月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
1天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
2月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
279 8
|
2月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
2月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
2月前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
19天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
19天前
初步认识栈和队列
初步认识栈和队列
44 10
|
13天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1