当前位置: 首页 > news >正文

数据结构-4.1.特殊矩阵的压缩存储


一.一维数组的存储结构:

1.知道一维数组的起始地址,就可以求出任意下标对应的元素所在的地址;

2.注:如果数组下标从1开始,上述公式的i就要改为i-1;

3.数组里的元素类型相同,因此所占空间也相同。


二.二维数组的存储结构:

1.注:数组的存储是连续(计算机的存储是线性的)的,针对非线性的二维数组,为了将其拉成线性结构,就有了行优先列优先两种存储方式;

2.将非线性的二维数组整成线性的好处就是可以实现随机存取;

3.行优先时计算存储地址:公式中i为行,j为列

4.列优先时计算存储地址:公式中i为行,j为列


三.普通矩阵的存储:


四.对称矩阵(行数=列数且关于主对角线对称)的压缩存储:

由于对称矩阵关于主对角线对称,因此在存储对称矩阵的数据时只需要存储对称的一部分即可。

以只存储主对角线+下三角区域为例:

1.数组大小即数组存储的数据个数;

2.行优先中计算某个元素是第几个元素的公式推导:i为行,j为列,i和j全从1开始(一定要注意下标起始位置)

该元素上方有i-1行,第i行有i个元素(第i-1行有i-1个元素),因此前i-1行共有1+2+...+(i-1)个元素,

该元素所在行从第一个元素到该元素需要j个元素,所以该元素位置公式为[1+2+...+(i-1)]+j

根据对称性,下三角区域的元素将下标的行和列互换位置就可以访问上三角区域的元素:

总结:

要注意出题内容,以进行对应的分析:


五.三角矩阵的压缩存储:

1.下三角矩阵:除了主对角线和下三角区域外,都是常量且值相同;

2.上三角矩阵:除了主对角线和上三角区域外,都是常量且值相同;

3.对于是常量且值相同的那一部分,是无需重复存放那么多数据的,因此只需要处理主对角线和对应的三角区域(不是常量的一部分)即可;

4.将主对角线和对应的三角区域(不是常量的一部分)的数据存入一维数组,需要的内存大小为(1+2+...+n)+1:

公式解读:第n行有n个元素,所以n行需要1+2+...+n,最后还需要一个空间存放常量,因此

总内存大小为(1+2+...+n)+1

注:上三角区域的数据都是值相同的常量,被存放在同一个空间中,在一维数组中下标都一样

同理,对于上三角矩阵,第一行有n个元素,第二行有n-1个元素,由此可得第i行有n-(i-1)个元素

所以第i-1行有n-[(i-1)-1]=n-i+2个元素,前i-1行有1+2+...+(n-i+2)个元素


六.三对角矩阵的压缩存储:

i为行,j为列

1.存储时只需要存储三对角矩阵中的非0元素即可;

2.对于上述图片中三对角矩阵里蓝色框内的部分,第一行和最后一行只有两个元素,其他行都有三个元素,

因此,共有n行,共有2+3(n-2)+2=3n-2个元素,存储三对角矩阵的一维数组的长度为3n-2;

3.求前i-1行有几个元素时,只需要考虑第一行仅两个元素即可,因为重点在前几行,因此

前i-1行有2+3(i-1-1)=3(i-1)-1个元素

4.此时第i行就是当前行,所以小于或者等于;第i-1行就是上面的行,比他们大,不可能取等;

王道书中的k可以理解为要找的元素前总共有k个元素:


七.稀疏矩阵的压缩存储:

1.对于顺序存储稀疏矩阵,可以创建一个结构体,里面创建变量记录行,列,值,也就是该结构体对应一个数据,

再创建一个与该结构体对应的一维数组,就可以顺序的存储稀疏矩阵,

缺点:顺序存储稀疏矩阵访问其中的元素时只能依次遍历,无法随机存取:

2.对于十字链表法,定义如下图的数组,数组里存指针(指针数组),都指向非0元素:


八.总结:


http://www.lryc.cn/news/453188.html

相关文章:

  • Hive数仓操作(十四)
  • SpringBoot技术:实现古典舞在线交流平台的秘诀
  • 自动驾驶系列—全面解析自动驾驶线控制动技术:智能驾驶的关键执行器
  • YOLO11改进|卷积篇|引入可变核卷积AKConv
  • 推荐 uniapp 相对好用的海报生成插件
  • MySQL表操作(进阶)
  • 【设计模式】软件设计原则——接口隔离迪米特
  • 【C++】——list的介绍和模拟实现
  • B树系列解析
  • docker 部署 WEB IDE
  • 【Android】数据存储
  • 个人网络安全的几个重点与防御
  • python爬虫 - 初识爬虫
  • tomcat版本升级导致的umask问题
  • Golang | Leetcode Golang题解之第455题分发饼干
  • vscode+stfp插件,实现远程自动同步文件代码
  • python 实现djb2哈希算法
  • 文件夹作为普通文件而非子模块管理
  • 7c结构体
  • 浅聊前后端分离开发和前后端不分离开发模式
  • RabbitMQ篇(死信交换机)
  • HBase 的 MemStore 详解
  • 【嵌入式软件-数据结构与算法】01-数据结构
  • Windows应用开发-解析AVI视频文件
  • 探索TCP协议的奥秘:Python中的网络通信
  • 每日学习一个数据结构-树
  • 简单PCL库读文件(linux vscode编译)
  • 【自动驾驶】最近计划看的论文
  • vue3学习:axios输入城市名称查询该城市天气
  • 影刀RPA实战:Excel拆分与合并工作表