5-数组

5-数组

数组其实是比较熟悉的一种数据类型,但其实数组本身也是一种数据结构。

前面 讨论的线性表结构的顺序存储结构都是借用一维数组来实现的,

一维数组是一种顺序表结构,多维数组是一种特殊的线性结构,是线性表的推广。

数组是用于储存多个相同类型数据的集合。

1.数组的顺序存储结构

由于数组可以是多维的,而顺序存储结构是一维的,因此数组中数据的存储要制定一个先后次序。

通常,数组中数据的存储有两种先后存储方式:

①以行序为主(先行后序):按照列号从小到大的顺序,依次存储每一行的元素。

②以列序为主(先列后行):按照行号从小到大的顺序,依次存储每一列的元素

假设有一个 m 行 n 列 的二维数组,每个元素占S个存储单元

按行优先存储的查找方法:

Loc(i,j) = Loc(1,1) + [ (i-1) *n + (j-1) ]*S

按列优先存储的查找方法:

Loc(i,j) = Loc(1,1) + [ (j-1) *m + (i-1) ]*S

2.特殊矩阵的压缩

这里所说的特殊矩阵,主要分为以下两类:

含有大量相同数据元素的矩阵,比如对称矩阵;

含有大量 0 元素的矩阵,比如稀疏矩阵、上(下)三角矩阵;

我们可以使用一维数组存储对称矩阵

由于矩阵中沿对角线两侧的数据相等,因此数组中只需存储对角线一侧包含对角线)的数据,

每一对对称元素共享一个存储空间。

则对于原来就在下三角区域的元素,(i>=j), 看成按行存储第 i 行上 有 i个元素

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

令 k= i*(i-1)/2 + (j-1)这就是存储下三角元素的一维数组的索引

原来就在上三角区域的元素( i< j), 看成按列存储, 第 j 列 上有 j 个元素

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

则令 k=j *(j-1)/2 + (i-1),这就是存储上三角元素的一维数组的索引

上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

3、稀疏矩阵

稀疏矩阵是指其中有大量 0 元素,可以只保存这些非零元素以节省存储空间。

①采用三元组存储法:

保存非零元素的 行值,列值, 和元素本身值。

例如有一个4 x 5的矩阵A 则对应的压缩矩阵为:

1 0 0 0 0 4,5, 6, //第一行一定为 m , n , 非零元素个数

0 0 12 0 0 0,0 , 1

0 3 0 0 0 -----》 1, 2 ,12

2 0 0 0 0 2 ,1 ,3

3 ,0 ,2

如此一来原本要20个元素,现在只需要存储15个元素,我这里只举了个简单的例子,当稀疏矩阵规模更大时,节约内存更明显。每行一定是3个元素,这可以当成一个结点保存下来,每个结点 当成一个元素存在顺序表里,所以称为三元组法,相应的顺序表称为三元组顺序表。

②行逻辑链接的顺序表

三元组顺序表每次提取指定元素都需要遍历整个数组,运行效率很低。

另一种存储矩阵的方法——行逻辑链接的顺序表。它可以看作是三元组顺序表的升级版,

即在三元组顺序表的基础上改善了提取数据的效率

它比三元组多了一个 用于记录矩阵中每行第一个非 0 元素在三元组中的存储位置的一维数组 rpos, 以上例举例

rops [1, 2, 3, 4] 这就是每行第一个非零元素,在三元组中出现在第几个结点,

我这里例子里,由于原矩阵每行只有一个非零元素,所以没有太大的感觉。

此时,如果想从行逻辑链接的顺序表(三元组)中提取元素,则可以借助 rpos 数组提高遍历数组的效率,

③十字链表法

对于压缩存储稀疏矩阵,无论是使用三元组顺序表,还是使用行逻辑链接的顺序表,归根结底是使用数组存储稀疏矩阵。介于数组 "不利于插入和删除数据" 的特点,以上两种压缩存储方式都不适合解决类似 "向矩阵中添加或删除非 0 元素" 的问题。

使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。

各个链表中节点的结构应如图:

结点的C语言代码

typedef struct OLNode{

int i, j; //元素的行标和列标

int data; //元素的值

struct OLNode * row ,*column;//两个指针域

}OLNode;

十字链表结构的 C 语言代码

typedef struct

{

OLink *rhead, *chead; //行和列链表头指针

int m , n , t; //矩阵的行数,列数和非零元的个数

}CrossList;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 斯坦福CS229机器学习笔记-Lecture2-线性回归+梯度下降+正规方程组

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    TeeyoHuang
  • 生成对抗网络GAN系列(二)Conditional Generative Adversarial Nets(cGAN 条件GAN)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    TeeyoHuang
  • 8-2 图的存储结构

    图结构的元素之间虽然具有“多对多”的关系,但是同样可以采用顺序存储,即使用数组有效地存储图。

    TeeyoHuang
  • 数组和广义表 原

    数组是存储同一类型数据的数据结构,使用数组时需要定义数组的大小和存储数据的数据类型。

    云飞扬
  • 全能詹: Jenkins Matrix 应用实践

    Matrix 项目的概念是在不同的版本中测试多种类型的相似技术。Matrix构建相互独立,因此可以并行运行。例如,可能要跨多个Java版本构建其项目测试。

    泽阳
  • .NET程序员必备的58个提高效率工具

    1. Visual Studio Visual Studio Productivity Power tool:Visual Studio 专业版(及以上)的扩展...

    BestSDK
  • 忍法,scroll 翻滚之术!

    但其实随着时间的推移, web api 以及 css 规范的不断改进,那些我们曾经认为实现起来很麻烦的功能也变得简单了起来。下面我们可以一起来探讨一下这些改进的...

    陈大鱼头
  • 微信小程序实践:2.3 可滚动的容器组件之 scroll-view

    说什么真理无穷,进一寸有一寸的欢喜。大家好,我是石桥码农,今天继续为大家分享微信小程序实践相关的技术内容。

    李艺
  • XSS跨站脚本攻击的原理分析与解剖

    《xss攻击手法》一开始在互联网上资料并不多(都是现成的代码,没有从基础的开始),直到刺的《白帽子讲WEB安全》和cn4rry的《XSS跨站脚本攻击剖析与防...

    奶糖味的代言
  • 使用 sroll-snap-type 优化滚动

    根据 CSS Scroll Snap Module Level 1 规范,CSS 新增了一批能够控制滚动的属性,让滚动能够在仅仅通过 CSS 的控制下,得到许多...

    Sb_Coco

扫码关注云+社区

领取腾讯云代金券