数据结构(五)----特殊矩阵的压缩存储

简介: 数据结构(五)----特殊矩阵的压缩存储
1.一维数组的存储结构

一维数组的定义如下:

ElemType a[10];

各数组元素大小相同,且物理上连续存放。

数组元素a[i]的存放地址=LOC+i*sizeof(ElemType)

注:除非题目特别说明,否则数组下标默认从0开始,若题目提醒下标从1开始,则存放地址为

LOC+(i-1)*sizeof(ElemType)

2.二维数组的存储结构

二维数组定义如下:

ElemType b[2][4];

由于内存的存储空间是连续的,线性的,所以把二维数组放到内存中,有两种存放方式,行优先存放(一行一行地存)和列优先存放(一列一列地存)。

M行N列的二维数组 b[M][N]中,若按行优先存储,则

b[i][j]的存储地址 = LOC+(i*N+j)*sizeof(ElemType)

若按列优先存储,则

存储地址 = LOC+(j*M+i)*sizeof(ElemType)

3.普通矩阵的存储

普通矩阵可用二维数组存储,描述矩阵元素时,行、列号通常从1开始;而描述数组时通常下标从0开始。

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

若n阶方阵中任意一个元素 都有 ,则该矩阵为对称矩阵

对称矩阵进行普通存储:n*n二维数组,压缩存储:只存储主对角线+下三角区

行优先原则将各元素存入一维数组中。

存储结构如下:

可以看到,第一行有1个元素,第二行有2个元素,第三行有3个元素,以此类推,第n行有n个元素,所以总共有1+2+3.....+n个元素,数组大小为

那么怎么通过矩阵下标映射到一维数组的下标呢?

例如,按行优先的原则, 是第几个元素?

第一行有1个元素,第二行有2个元素,以此类推,第i-1行就有i-1个元素,所以 是第

个元素,即 个元素,由于数组下标是从0开始,所以

的数组下标为k=

若要得到上三角某个元素,那么可以根据 ,转换为 ,进而得到与下三角相同的存放规律。

进而其一维数组下标为:

总结

按照列优先原则进行存储, 是第几个元素?

如上图所示,第1列有n个元素,第2列有n-1个元素,第j-1列有n-j+2个元素。

技巧:1+n=n+1,2+(n-1)=n+1,(n-1)+(n-j+2)=n+1

第j列有多少元素,用(行号 - 列号+1)即可,可以自己验算一下。

所以 是第

个元素

默认从0开始的话,数组下标在上面的基础上减1即可:

由等差数列易得:

所以 的下标为:

(2)三角矩阵

下三角矩阵:除了主对角线和下三角区,其余的元素都相同。

压缩存储:按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c。

所以一维数组的长度:(1+2+3.....n)+1

若按照行优先的原则, 是第几个元素:

下三角和对称矩阵的运算一样,对于上三角,由于上三角每个元素都是一样的,所以映射到一维数组的最后一个元素,即B[ ]

上三角矩阵:除了主对角线和上三角区,其余的元素都相同。

按照行优先原则, 是第几个元素?

第1行到第i-1行有

第i行有j-i+1个元素:列号(j)-行号(i)得到该元素在第i行的前面有多少元素。

所以 是第

个元素。

其数组下标为:

由等差数列的求和公式易得:

要访问下三角区的话同理,直接映射到一维数组的最后一个位置。

总结:

3)三对角矩阵

三对角矩阵,又称带状矩阵:当|i-j|>1时,有 =0(1≤i,j≤n),通俗点来讲就是,主对角线元素及其上下左右的元素不为0,其余元素的值全为0。

压缩存储:按行优先(或列优先)原则,只存储带状部分。

可以观察到,带状矩阵除了第一行和最后一行是两个元素,其余行都是三个元素。所以要存储的元素个数为:3*n-2

若默认数组下标从0开始,那么最后一个元素的数组下标就为:B[3n-3]

那么按行优先的原则, 是第几个元素?

前 i-1 行共 3(i-1)-1 个元素。

是第i行的 j-i+2 个元素。

那么将两个数加起来: 是第 2i+j-2个元素

为什么有j-i+2呢?

由上三角矩阵我们可以分析得, 的元素在第i行的前面有j-i个元素,例如 ,前面就有:

2-1=1个元素。

对比这里,把三角形往前挪一个位置,可以得到相同的在第i行的前面的元素的个数,所以 在第i行,前面有j-i+1个元素,那么加上它本身 是第i行第j-i+2个元素

我是这么理解的,不管怎么理解,只要自己理解就可以啦~


有些人也会有疑问,是第i行的 j-i+2 个元素针对第一行就不对呀?其实结合前 i-1 行共 3(i-1)-1 个元素,针对第一行计算得到-1,再加上j-i+2 也是对的结果。


例如:


根据式子3(i-1)-1, 前i-1(0)行有-1个元素,再根据式子:是第i行的 j-i+2 个元素,得到


2-1+2=3个元素,那么最后两者相加3+(-1)=2,得到的也是正确的结果,也就是是第2个元素。


那么第k+1个元素,在第几行?第几列?

前 i-1 行共 3(i-1)-1个元素

前 i 行共 3 i-1 个元素

显然,3(i-1)-1< k+1 3i-1

不等式解出来为: ,且

因为i是行号,一定是正整数,将这个式子向上取整,即 i= ,就可以满足i"刚好"大于等于某一行。

王道书中的逻辑:第k+1个元素前有k个元素,并且k满足3(i-1)-1 ≤ k < 3i-1

不等式解出来为: ,且

将这个式子向下取整,即 i= ,即可满足i“刚好”小于等于某一行。

由于我们之前讲到过 是第 2i+j-2个元素,其下标默认从0开始,就是2i+j-3,所以:k=2i+j-3,所以我们就可以从 k 和 i 推出j的值了。

(4)稀疏矩阵的压缩存储

稀疏矩阵就是非零元素远远少于矩阵元素的个数。

压缩存储:

1.顺序存储---三元组<行,列,值>,这里存储的值都是稀疏矩阵中的非0元素。

:此处行、列标从1开始

若用这种方式存储稀疏矩阵,想要访问其中的某个元素,只能顺序依次扫描三元组,会失去随机存取的特性

2.链式存储---十字链表法。如图所示,向下域down指向第j列的第一个元素,向右域 right,指向第i行的第一个元素。

每个非0元素会对应一个结点,这个结点包括该非0元素所在的行,列以及对应的值;还会包含两个指针,第一个指针指向同列的下一个元素,第二个指针指向同行的下一个元素。可以看图自己分析一下。



例如:该结点第一个指针为空,表示该列没有非0元素了;第二个结点指向了同行的下一个元素,即5。


以上公式不建议死记硬背,充分理解之后,考场上也可以推出来的。

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