首页 > 其他分享 >数据结构之特殊矩阵的压缩存储

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

时间:2024-08-04 09:27:44浏览次数:15  
标签:存储 元素 三角 矩阵 非零 对角线 数据结构

1. 对称矩阵的压缩存储

定义:若n阶矩阵A满足a(ij) = a(ji)(1≤i,j≤n),则称A为n阶对称矩阵。
压缩存储方法:由于对称矩阵上三角和下三角的元素相同(主对角线上的元素只存储一次),因此可以只存储上三角(或下三角)的元素和主对角线上的元素。
存储方式:通常使用一维数组来存储这些元素。若采用下三角存储,元素a(i,j)在一维数组中的位置k可以通过公式k = i*(i-1)/2 + j - 1计算得出(假设数组下标从0开始)。

2. 三角矩阵的压缩存储

定义:
上三角矩阵:下三角(不含对角线)的元素均为常数或零的矩阵。
下三角矩阵:上三角(不含对角线)的元素均为常数或零的矩阵。
压缩存储方法:对于上三角矩阵,只需存储主对角线及其以上的元素以及下三角的常数项(如果常数项不为零)。下三角矩阵的存储方法类似,只是存储的内容变为主对角线及其以下的元素和上三角的常数项。
存储方式:同样使用一维数组进行存储,上三角矩阵的存储可以看作是对称矩阵以列为主的压缩存储。

3. 对角矩阵的压缩存储

定义:所有非零元素集中在主对角线两侧的带状区域内的矩阵称为对角矩阵。特别地,如果非零元素仅位于主对角线上,则称为三对角矩阵。
压缩存储方法:只存储非零元素及其位置信息(行号和列号)。对于三对角矩阵,由于其非零元素仅分布在主对角线及其上、下两条对角线上,因此可以直接按行或列的顺序存储这些元素。
存储方式:使用一维数组存储非零元素,并使用额外的数据结构(如三元组表)来记录非零元素的行号、列号和值。

4. 稀疏矩阵的压缩存储

定义:矩阵中非零元素的个数远小于矩阵元素的总数(通常定义为非零元素的比例小于某个阈值,如0.05)时,称该矩阵为稀疏矩阵。
压缩存储方法:只存储非零元素及其位置信息(行号和列号),不存储零元素。
存储方式:常见的稀疏矩阵存储方式有三元组表、行逻辑链接的顺序表和十字链表等。其中,三元组表是最简单也是最常用的存储方式,它包含非零元素的行号、列号和值。

标签:存储,元素,三角,矩阵,非零,对角线,数据结构
From: https://blog.csdn.net/qq_39311377/article/details/140672463

相关文章

  • Open3D 计算点云的归一化协方差矩阵
    目录一、概述1.1原理1.2实现步骤1.3应用二、代码实现2.1关键函数2.2完整代码三、实现效果3.1原始点云3.2数据显示Open3D点云算法汇总及实战案例汇总的目录地址:Open3D点云算法与点云深度学习案例汇总(长期更新)-CSDN博客一、概述        计算点云的归一......
  • 数据结构之《二叉树》(中)
    在数据结构之《二叉树》(上)中学习了树的相关概念,还了解的树中的二叉树的顺序结构和链式结构,在本篇中我们将重点学习二叉树中的堆的相关概念与性质,同时试着实现堆中的相关方法,一起加油吧!1.实现顺序结构二叉树在实现顺序结构的二叉树中通常把堆使用顺序结构的数组来存储,因......
  • 数据结构 -- 栈和队列
    数据结构--栈和队列1.栈1.1栈的概念及结构1.2栈的实现2.队列2.1队列的概念及结构2.2队列的实现3.栈和队列面试题4.概念选择题1.栈1.1栈的概念及结构栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端......
  • 矩阵学习笔记
    矩阵引入矩阵引入来源于简洁表示线性方程组例如:\[\begin{cases}2x+5y=10\\4x+9y=39\end{cases}\]可以表示为:\[\begin{bmatrix}2&5\\4&9\end{bmatrix}\times\begin{bmatrix}x\\y\end{bmatrix}\]矩阵乘法定义矩阵\(A\)为\(n\timesm\)的矩阵,\(B\)为\(......
  • 「字符串」实现Trie(字典树|前缀树)的功能 / 手撕数据结构(C++)
    概述在浏览器搜索栏里输入几个字,就弹出了以你的输入为开头的一系列句子。浏览器是怎么知道你接下来要输什么的?来看看字典树干了什么。字典树是一种高效记录字符串和查找字符串的数据结构。它以每个字符作为一个节点对字符串进行分割记录,节点形成树状结构,在录入或查找时只......
  • 矩阵树定理学习笔记
    用来求和一个图的生成树个数相关的算法,时间复杂度\(O(n^3)\)。你要会求一个矩阵的行列式,这是和行列式有关的前置知识。定理阐述对于无向图定义度数矩阵\(D_{i,j}=[i=j]\deg_i\),其中\(\deg_i\)表示\(i\)的度数。定义邻接矩阵为\(E_{i,j}\)为边\((i,j)\)的个数。定......
  • MySQL数据分析进阶(八)存储过程
    ※食用指南:文章内容为‘CodeWithMosh’SQL进阶教程系列学习笔记,笔记整理比较粗糙,主要目的自存为主,记录完整的学习过程。(图片超级多,慎看!)【中字】SQL进阶教程|史上最易懂SQL教程!10小时零基础成长SQL大师!!https://www.bilibili.com/video/BV1UE41147KC/?spm_id_from=333.1007.0.......
  • 【数据结构】二叉树和堆
     一、二叉树1.二叉树的基本概念在C语言中,二叉树是一种基础的数据结构,它由节点组成,每个节点包含数据元素以及指向其他节点的指针。下面是二叉树的基本概念以及如何在C语言中表示和操作它。节点(Node):二叉树的每个元素称为节点,每个节点都有一个数据域和两个指针域,通常称为左指......
  • 数据结构-------------------二叉排序树的查找
    #include<stdio.h>#include<stdlib.h>typedefstructBSTNode{intkey;structBSTNode*lchild;structBSTNode*rchild;}BSTNode,*BSTTree;//递归实现二叉排序树的查找操作BSTNode*BSTSearch(BSTTreeT,intkey){if(T......
  • Android Studio开发学习(二、注册存储)
    用户注册首先我们创建一个新的Activity,将他命名为RegisterActivity我们还是先设计注册界面布局(根据自身喜好),我这里延用了上一篇透明框布局bg_username、btn_left、btn_right上一篇我们已经简单介绍了LinearLayout、TextView、EditText功能,这里补充一下Button布局,它决定按钮......