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

NO.4数据结构数组和矩阵|一维数组|二维数组|对称矩阵|三角矩阵|三对角矩阵|稀疏矩阵

![[Pasted image 20250712141812.png]]

数组的储存

【定义】

数组: 由 n(≥1) 个相同类型的数据元素构成的有限序列, 是线性表的推广。
一旦被定义, 维数和长度就不可再改变, 一般对其只有元素的存取和修改操作。

一维数组

Arr[a0,…,an−1] Arr[a_{0},\dots,a_{n-1}] Arr[a0,,an1]
计算 ai 的位置: pos(ai) = pos(a0) + i *L (ai 前面有 i 个元素)

二维数组

——可看作元素是一维数组的一维数组。 假设为 n*m 大小。
行优先
![[Pasted image 20250712143114.png]]

列优先
![[Pasted image 20250712143127.png]]

特殊矩阵的压缩

——多个值相同的元素只分配一个存储空间, 对零元素不分配空间。

对称矩阵

aij = aji
![[Pasted image 20250712143241.png]]

若从 a1,1 开始, 则 ai,j 在一维数组中存储下标

一般存储下三角矩阵
下三角区域(含主对角线)
第一行:1个元素
第二行:2个元素
第i-1行:i-1个元素
第i行:j-1个元素
故 aij 为第i(i-1)/2+j个元素

i(i-1)/2+j-1, i >= j 下三角区和主对角线
j(j-1)/2+i-1, i < j 上三角区

三角矩阵

——上三角区 or 下三角区全为同一常量 => 会浪费一半的存储空间。
![[Pasted image 20250712162901.png]]

![[Pasted image 20250712162909.png]]

下三角矩阵元素 aij 和数组下标的关系
n(n+1)/2, i < j 上三角区
i(i-1)/2+j-1, i ≥ j 下三角区和主对角线
![[Pasted image 20250713031706.png]]

上三角矩阵元素 aij 和数组下标的关系

上三角区域 (包含主对角线)
第一行:n个元素
第二行:n-1个元素
第i-1行:n-i+2个元素
第i行:j-i个元素
ai;为第(n+n-i+2)(i-1)/2 + j-i+1=(i-1)(2n-i+2)/2+j-i+1个元素

n(n+1)/2, i > j 下三角区
(i-1)(2n-i+2)/2 + (j-i), i ≤ j 上三角区和主对角线

三对角矩阵

——也称带状矩阵, 对于 ai,j,当|i-j|>1 时, 有 ai,j = 0
![[Pasted image 20250713032036.png]]

除第1行和第i行外,每行都有三个元素,
第i行有j-i+2个元素,
故aij为第(i-2)*3+2+j-i+2=2i+j-2个元素

三对角矩阵的顺序存储
![[Pasted image 20250713032112.png]]

三对角矩阵元素 aij 和数组下标的关系
k = 2i + j -3

稀疏矩阵储存方式

顺序储存(三元组表示法&伪地址表示法)
链式存储(邻接表表示法&十字链表表示法)
![[Pasted image 20250713032510.png]]

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

相关文章:

  • 【Docker基础】Dockerfile指令速览:环境与元数据指令详解
  • 【保姆级图文详解】Spring AI 中的工具调用原理解析,工具开发:文件操作、联网搜索、网页抓取、资源下载、PDF生成、工具集中注册
  • leetGPU解题笔记(1)
  • 【CMake】CMake创建、安装、使用静态库和动态库
  • LeetCode|Day8|1047. 删除字符串中的所有相邻重复项|Python刷题笔记
  • java.net.InetAddress
  • 嵌入式 Linux开发环境构建之安装 SSH 软件
  • MongoDB数据基本介绍
  • 小白成长之路-LVS
  • 【VSCode+LaTeX】科研写作环境搭建
  • C语言的一些随笔
  • 面试150 填充每个节点的下一个右侧节点指针Ⅱ
  • 006_测试评估与安全实践
  • 2025上海市“星光计划“信息安全管理与评估赛项二三阶段任务书
  • RAG篇(RAG的流程)
  • STM32-第六节-TIM定时器-2(输出比较)
  • Linux驱动开发2:字符设备驱动
  • iOS UI视图面试相关
  • 哪些行业的“反内卷”前景更好?
  • ADB 调试日志全攻略:如何开启与关闭 `ADB_TRACE` 日志
  • 【Datawhale夏令营】用AI做带货视频评论分析
  • [附源码+数据库+毕业论文+答辩PPT+部署教程+配套软件]基于SpringBoot+MyBatis+MySQL+Maven+Vue实现的交流互动管理系统
  • 每天学一个八股(二)——详解HashMap
  • 26-计组-指令执行过程
  • HTML5 离线存储
  • MyBatis04-MyBatis小技巧
  • Typecho后台编辑器自定义按钮开发实战指南
  • Spring Boot 集成 Spring Security 完整示例
  • Sping AI Alibaba
  • 《区间dp》