数据结构(其四)--特殊矩阵的存储

目录

11.特殊矩阵的压缩存储

(1).一维数组的储存结构

(2).二维数组的存储结构

(3).普通矩阵的存储

(4).特殊矩阵的压缩存储

        i.对称矩阵

        ii.三角矩阵

        iii.三对角矩阵

        iiii.稀疏矩阵


11.特殊矩阵的压缩存储

(1).一维数组的储存结构

        int a[10];

        一维数组的地址是连续的,只要知道了起始地址(LOC,默认是a[0]的地址),就可以知道所有元素的地址。

        

        a[i] 地址的计算 :LOC + i * sizeof(int) .

        注意:有时候给出的LOC可能不是a[0] 的,此时,就要在上式子的i 中减去,如给出的是a[1]的,则计算公式变为 LOC + (i - 1) * sizeof(int).

(2).二维数组的存储结构

        int b[2][4]

        二维数组在内存中有两种存储方法,行优先和列优先。

        当然,从逻辑视角上看,将数据配列成矩阵的样式,更方便进行操作。

        有int b[M][N],b[0][0] 的地址为LOC,则b[i][j]

        行优先:LOC + (i*N + j)*sizeof(int)

        列优先:LOC + (j*M + i)*sizeof(int) 

(3).普通矩阵的存储

        一般是用二维数组

        需要注意的是,矩阵的下标是从(1, 1) 开始的,数组是从(0, 0) 开始的。

(4).特殊矩阵的压缩存储

        i.对称矩阵

        · 是方阵(n阶),

        · 恒有 aij == aji,

        因为对称,所以可以只存储下三角区和对称轴(或上三角区和对称轴)(这样就是所谓的压缩存储)

        

        按行优先将各元素存入一维数组(也可以列优先),

        如此便要思考,

        数组的大小,显然,第一行一个元素,第二行两个元素...第N行N个元素,总数就是n*(n+1)/2.

        数据的调用,因为矩阵的下标与数组的下标规则不同,可以写一个简单的映射函数进行转换

        aij => b[k]

        总结上图,可知

        k = (i+1)*i/2 + j - 1 ,

        即当前元素行数往上为等差数列求和,再加上列数,就是在数组中的第几个元素,再减一,就成了数组下标。(如果,题干给出的数组起始下标为1,k就不需要减去那个1)

        ii.三角矩阵

        

        压缩存储策略:储存aij的三角区,将常数储存在数组最后一位。(以下三角为例)

        数组大小,n*(n+1)/2 + 1.

        aij的ij 与数组下标之间的相互转换与上文相同。

        获取常数项,数组下标就是 n*(n+1)/2。

         值得一提的,在上三角中,求aij是数组中的第几个元素,观察图可知,每行的元素数由N个依次递减。所以,aij 前面有 [n + ... + (n - i + 2)] + (j - i)个元素,中括号里的是此行往上的,那个j-i是当前行内aij 之前的元素。

        iii.三对角矩阵

       以行优先为例,

        数组大小3n - 2

        数组下标(对于aij),前(i - 1)行,有3(i - 1) - 1个元素(每行有三个元素,但第一行只有两个);第i 行中,aij是第j - i + 2个元素,所以aij 就是第2i + j - 2(前后相加)。

        k = 2i + j - 3

        由数组下标逆推矩阵下标ij

        已知b[k]

        是第k + 1个元素,在前i-1行,与前i行之间,3(i - 1) - 1 < k + 1 <= 3i - 1

        i >= (k + 2)/3,左式算出结果后向上取整就是i 值

        (向上取整:如1.2,向上取整就是2,向下就是1) 

        iiii.稀疏矩阵

        压缩策略:

         ① 顺序存储------设置一个类,其中包含三个数组,分别存储i、j、非零数据。

        ② 十字链表法----此为链式存储,

        结点中,包含行、列、值以及两个指针。

        两个指针分别指向同一列的下一个结点和同一行的下一个结点。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/392884.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java多商户新零售超市外卖商品系统

解锁新零售奥秘&#xff0c;多商户外卖超市商品系统大揭秘&#xff01; &#x1f31f; 开篇&#xff1a;新零售时代的浪潮 在这个日新月异的数字化时代&#xff0c;新零售已悄然成为商业变革的新风口。想象一下&#xff0c;足不出户就能逛遍全城商家&#xff0c;心仪商品一键…

力扣——238.移动零

题目 思路 利用双指针&#xff0c;先找到第一个为0的地方指向&#xff0c;指针2指向下一个&#xff0c;指针1之前是已经处理好的数据&#xff0c;指针2进行遍历&#xff0c;遇到非零则与指针1数据交换&#xff0c;然后指针1。 代码 class Solution { public:void moveZeroes(…

离心机转子适配器容量转换器的作用

离心机转子是离心机的核心部件&#xff0c;离心机中的所有系统都配置为保证转子在一定条件下安全运行。转子不仅直接影响分离效果&#xff0c;而且也是离心机技术中的主要承力部件&#xff0c;对离心机的安全性极为重要。 简而言之&#xff0c;离心机可分为两部分&#xff1a;…

Java Web——第二天

什么是JavaScript? JavaScript(简称:JS) 是一门跨平台、面向对象的脚本语言。是用来控制网页行为的&#xff0c;它能使网页可交互 JavaScript和Java是完全不同的语言&#xff0c;不论是概念还是设计。但是基础语法类似 JavaScript在1995年由 Brendan Eich 发明&#xff0c;…

【MySQL】索引概念解析

1.什么是索引&#xff1f; MySQL中的索引是一种数据结构&#xff0c;用于帮助MySQL数据库管理系统快速查询数据。索引的主要目的是提高数据检索的速度&#xff0c;减少数据库系统需要扫描的数据量。 优点&#xff1a; 索引可以极大的提高数据检索效率&#xff0c;降低数据库…

C语言——预处理和指针

C语言——预处理和指针 预处理宏宏定义宏的作用域带参的宏 文件包含条件编译 指针指针的概念指针的定义 预处理 编程的流程分为&#xff1a;编辑、编译、运行、调试四个阶段&#xff1b; 预处理属于编译阶段&#xff0c;编译过程又可以分为&#xff1a;预处理、编译、汇编、链…

TikTok达人效应:品牌出海中的文化桥梁与本土化策略

在全球化的浪潮下&#xff0c;品牌出海已成为企业拓展市场的必经之路。然而&#xff0c;跨越文化差异、实现品牌本土化传播一直是企业面临的巨大挑战。TikTok作为一款全球流行的短视频平台&#xff0c;其庞大的用户基础和强大的影响力&#xff0c;为品牌出海提供了新的机遇。在…

大数据技术复习--大数据与云计算、物联网、人工智能

云计算 ** 概念&#xff1a;美国国家标准技术研究院“一种无处不在的、便捷的且按需的对一个共享的可配置的计算资源&#xff08;如网络&#xff0c;服务器、存储、应用和服务&#xff09;进行网络访问的模式&#xff0c;他能够通过少量的管理或服务供应商的互动实现计算资源的…

CTFHub技能树web——XSS——DOM反射

根据框里的内容 直接右键查看网页源代码 看到 了其闭合方式 然后去网页测试一下alert&#xff08;1&#xff09;反射 ;</script><script>alert(1)</script> 看到 确实存在 去xssaq.cn 创建一个项目 把src粘过来 在第一个输入框中 再将返回回来的url 复…

MATLAB计算心理声学烦恼度例子

在这个例子中&#xff0c;您测量发动机噪音&#xff0c;并使用心理声学指标来模拟其感知响度、尖锐度、波动强度、粗糙度和总体烦扰程度。然后&#xff0c;模拟添加隔音材料&#xff0c;重新计算总体噪音水平。最后&#xff0c;比较恼人程度&#xff0c;并显示应用隔音材料后的…

【LabVIEW学习篇 - 12】:通知器

文章目录 通知器案例一案例二案例三&#xff08;在不同VI中用同一个通知器&#xff09; 通知器 同步技术&#xff1a;同步技术用来解决多个并行任务之间的同步或通信问题。 通知器比较适合一对多的操作&#xff0c;类似于广播&#xff0c;一点发出的通知消息&#xff0c; 其它…

Spring Boot 3.3 新特性介绍

1. 引言 Spring Boot 3.1.x 停止维护了&#xff0c;而 3.3.x 作为最新发布的版本&#xff0c;带来了许多新特性和改进。本篇文章将详细介绍这些新特性&#xff0c;并通过样例代码加以解释&#xff0c;帮助开发者更好地掌握和应用这些新功能。 Spring Boot 3.3现已正式发布&…

Android studio配置代码模版

一、背景&#xff1a; 在工作中&#xff0c;总是要写一些重复的代码&#xff0c;特别是项目有相关规范时&#xff0c;就会产生很多模版代码&#xff0c;每次要么复制一份&#xff0c;要么重新写一份新的&#xff0c;很麻烦&#xff0c;于是我就在想&#xff0c;能不能像创建一…

小程序开发入门:第一天的学习和实践指南

目录 一. 理解小程序的基本概念 1. 无需安装 2. 快速启动 3. 界面简洁 4. 独立性和封闭性 5. 数据安全 6. 框架结构 7. 生命周期 8. 全局配置 9. API支持 10. 发布和更新 二、选择合适的开发工具 1. 微信开发者工具 2. Visual Studio Code 3. Sublime Text 4. …

Tensor安装和测试

1: 打开git官方 https://github.com/NVIDIA/TensorRT 2: 下载得到&#xff1a;TensorRT-10.2.0.19.Linux.x86_64-gnu.cuda-11.8.tar.gz 3: 下载后配置环境变量&#xff0c;上面地址记得改成真实地址。 4: 如果想python使用tensorrt&#xff0c;那么 解压后目录&#xff0c…

【HTML入门】第二十三课 - 【实战】做一个简单的图书详情页

这一节&#xff0c;我们继续用纯HTML来做一个实战小案例。 我找了一个图书详情的页面&#xff0c;就像这样&#xff1a; 这一小节&#xff0c;我们用纯HTML标签&#xff0c;来实现一下这个图书详情的内容。 目录 1 布局分析 2 用到的标签 3 实战代码 1 布局分析 我们看这张…

吴恩达机器学习-C1W3L2-逻辑回归之S型函数

可选实验:逻辑回归 在这个不评分的实验中&#xff0c;你会 探索sigmoid函数(也称为logistic函数)探索逻辑回归;哪个用到了s型函数 import numpy as np %matplotlib widget import matplotlib.pyplot as plt from plt_one_addpt_onclick import plt_one_addpt_onclick from l…

Flutter 插件之http(介绍、使用、二次封装)

背景 在我们日常开发过程中,经常会使用到网络请求,而在Flutter插件中,最常用的请求插件一共两个,分别是: 1、dio 2、http 其中dio我已经做过详细介绍了(post、get等请求、文件上传、请求重试等),这里就不做过多阐述,下面附上文章链接,如有需要可前往查看。 http…

如何申请一年期IP地址SSL证书

在数字化的时代&#xff0c;网络安全越来越重要&#xff0c;SSL证书已经成为网站的标配&#xff0c;它承担着保护网站安全的重大作用。一般申请SSL证书都是用域名来申请的&#xff0c;不过当没有域名或者域名无法使用时&#xff0c;就需要使用IP地址来申请SSL证书了&#xff0c…

Cursor搭配cmake实现C++程序的编译、运行和调试

Cursor搭配cmake实现C程序的编译、运行和调试 Cursor是一个开源的AI编程编辑器&#xff0c;开源地址https://github.com/getcursor/cursor &#xff0c;它其实是一个集成了Chat-GPT的VS Code。 关于VS Code和VS的对比可以参考这篇文章VS Code 和 Visual Studio 哪个更好&…