数组的基本概念

数组:按一定格式排列起来的,具有相同类型的数据元素的集合。

一维数组:若线性表中的数据元素为非结构的简单元素,则称为一维数组。

一维数组的逻辑结构:线性结构。定长的线性表。

声明格式:数据类型 变量名称[长度];

例如:int num[5] = {0,1,2,3,4};

二维数组:若一维数组中的数据元素又是一维数组结构,则称为二维数组。

image-20220908161228949

image-20220908161358290

声明格式:数据类型 变量名称[行数][列数]

例如:int num[5][8];

在C语言中,一个二维数组类型也可以定义为一维数组类型(其分量类型为一维数组类型),即:

typedef elemtype array2[m][n];

等价于:

typedef elemtype array1[n];
typedef array1 array2[m];

三维数组:若二维数组中的元素又是一个一维数组,则称作三维数组。

n维数组:n-1 维数组中的元素又是一个一维数组结构,则称作 n 维数组。

结论:线性表结构是数组结构的一个特例,而数组结构又是线性表结构的扩展。

数组特点:结构固定——定义后,维数和维界不再改变。

数组基本操作:除了结构的初始化和销毁之外,只有取元素和修改元素值的操作。

数组的顺序存储

因为

  • 数组特点:结构固定——维数和维界不变。
  • 数组基本操作:初始化、销毁、取元素、修改元素值。一般不做插入和删除操作。

所以:一般都是采用顺序存储结构来表示数组。
注意:数组可以是多维的,但存储数据元素的内存单元地址是一维的,因此,在存储数组结构之前,需要解决将多维关系映射到一维关系的问题。

  • 一维数组

例,有数组定义: int a[5];每个元素占用 4 字节,假设 a[0] 存储在2000单元,a[3]地址是多少?

image-20220908164253208

  • 二维数组

image-20220908165837707

存储单元是一维结构,而数组是个多维结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题。、

image-20220908170451469

以行序为主序:

设数组开始存储位置 LOC(0,0) ,存储每个元素需要 L 个存储单元

数组元素a[i][j]的存储位置是:$LOC( i, j)= LOC(0,0)+(n*i+j)*L$

  • 三维数组

按页/行/列存放,页优先的顺序存储

image-20220908171210593

  • a[m1][m2] [m3] 各维元素个数为 $m,_1 m_2, m_3$
  • 下标为 $i_1, i_2,i_3$的数组元素的存储位置:

image-20220908171949331

特殊矩阵的压缩存储

矩阵:一个由 $m\times n$ 个元素排成的 $m$ 行 $n$ 列的表。

矩阵的常规存储:将矩阵描述为一个二维数组。

矩阵的常规存储的特点:

  • 可以对其元素进行随机存取;
  • 矩阵运算非常简单;存储的密度为1。

不适宜常规存储的矩阵:值相同的元素很多且呈某种规律分布;零元素多。

矩阵的压缩存储:

  • 为多个相同的非零元素只分配一个存储空间;
  • 对零元素不分配空间。

1.什么是压缩存储?

若多个数据元素的值都相同,则只分配一个元素值的存储空间,且零元素不占存储空间。

2.什么样的矩阵能够压缩?

一些特殊矩阵,如:对称矩阵,对角矩阵,三角矩阵,稀疏矩阵等。

3.什么叫稀疏矩阵?

矩阵中非零元素的个数较少(一般小5%)

对称矩阵

[特点] 在 $n\times n$的矩阵 $a$ 中,满足如下性质:

$$ a_{ij}=a_{ji} (1\leq i, j\leq n) $$

[存储方法] 只存储下(或者上)三角(包括主对角线)的数据元素。共占用 $n(n+1)/2$ 个元素空间。

[对称矩阵的存储结构]

对称矩阵上下三角中的元素数均为 $n(n+1)/2$ 个

可以以行序为主序将元素存放在一个一维数组 sa[n(n+1)/2]中。

image-20220909095704575

三角矩阵

[特点] 对角线以下(或者以上)的数据元素(不包括对角线)全部为常数 c

[存储方法] 重复元素 c 共享一个元素存储空间,共占用 $n(n+1)/2+1$ 个元素空间: sa[1.. n(n+1)/2+1]

image-20220909102317057

对角矩阵(带状矩阵)

[特点] 在 $n\times n$ 的方阵中,所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为0,则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。

image-20220909103204673

[存储方法] 以对角线的顺序存储

  • 以对角线的顺序存储

image-20220909103529276

稀疏矩阵

稀疏矩阵: 设在 $m\times n$的矩阵中有 $t$ 个非零元素。令 $\delta= t/(m\times n)$
当 $\delta \leq 0.05$ 时称为稀疏矩阵。

顺序存储结构:三元组法

image-20220909104233804

注意: 为更可靠描述,通常再加一个“总体”信息:即总行数、总列数、非零元素总个数。

三元组顺序表又称有序的双下标法。

三元组顺序表的优点:非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。

三元组顺序表的缺点:不能随机存取,若按行号存取某一行中的非零元,则需从头开始进行查找。

链式存储结构:十字链表

优点:它能够灵活地插入因运算而产生的新的非零元素。删除因运算而产生的新的零元素,实现矩阵的各种运算。

在十字链表中,矩阵的每一个非零元素用一个结点表示,该结点除了 (row,col,value) 以外,还要有两个域;

  • right:用于链接同一行中的下一个非零元素;
  • down:用以链接同一列中的下一个非零元素。十字链表中结点的结构示意图:

十字链表中结点的结构示意图:

image-20220909105605138

🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/99.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 09 月 24 日
赏杯咖啡