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

【数据结构入门】一、数组

news 来源：原创 2025/5/10 6:28:40

一、数组的概念

数组：一种由相同类型的数据元素组成的基本数据类型，为引用类型

二、数据的顺序

这里很奇怪，讲了一个寻址函数，就是怎样用坐标求该元素的内存地址。说实话我不知道求这个能干什么，但是感觉还挺好玩的，所以就看了看。

1.一维数组：

设有一维数组A1[b,b+1,b+2,…,b+n-1]，如果每个数组元素占据s个地址单元，那么寻址函数为：
Loc(i) = Loc(b)+(i-b)xs

2.二维数组：

设有二维数组A2[r,r+1,r+2,…r+m-1][c,c+1,c+2,…c+n-1]；
分两种情况：
（1）以行优先
Loc(i,j)=Loc(r,c)+[(i-r)xn+(j-c)]xs
解释一下，这里从第一行开始算起，我求的这个元素是(i,j)，那么已经占了(i-r)行，每行都已经被占满了，占的数量就是n，因此xn，最后一行没占满，只占到j列，那么就是(j-c)列，最后每个元素占s个地址单元，再乘以s，加上初始的第一个元素的内存地址，就能算出当前的内存地址是多少了
（2）以列优先
跟上面的规则一样，只是这次我们从第一列开始算起，因此可得公式:
Loc(i,j)=Loc(r,c)+[(j-c)xm+(i-r)]xs
如果还没理解的，我在下面举个例子，自己算一遍就懂了：

     设二维数据a[1...10][2...8]的基地址为1024，每个元素占2个存储单元，若以行优先顺序存储，则元素a[5,3]的地址是多少？若是列优先呢？解：行优先：1024+[(5-1)X(8-2+1)+(3-2)]X2=1082列优先：1024+[(3-2)X(10-1+1)+(5-1)]X2=1052

3.三维数组：

更多维度的逻辑也都是一样的，因为目前涉及较少，所以暂时没有分析。

三、矩阵的压缩存储

(这里的矩阵指二维数组)

1.特殊矩阵

这里介绍了三种特殊矩阵，用一种新的方式把这三大矩阵压缩起来存储，省空间。我觉得这个没必要在新手期去了解，所以跳过了，在这介绍下这三种矩阵：
（1）对称矩阵：很明显，就是有一半都是相同元素，以主对角线做轴对称
（2）三角矩阵：分为上三角矩阵和下三角矩阵，三角中的元素都为常数
（3）对角矩阵：只有在以主对角线为中心的带状区域中有数，其他地方的元素都为0
【这矩阵也太特殊了点，谁正常人创建这样的数组，拿来干啥的我都不知道，是我太初级了么】

2.稀疏矩阵

我理解了一下，意思就是，一个二维数组，大部分都是0，星崩有那么两个位置有数字，就跟扫雷差不多，一百个格子里有十个雷，其他都是空。当然这个0也可以换成一个其他的常量，谁都行。这样我们就可以只表示那些有值的格子。
表示方法：
（1）三元组顺序表：

   row    col    value0        1       7 1        4       41        4       6

很明显什么意思，我就不解释了
（2）十字链表：

row    col   valuedown  right

看见了吧，一共有五个值，前三个很好理解，第四个down是下边的，也就是同一列下一行的元素，第五个right是右边那个，也就是下一列同行的元素。这一个链表表示一个元素，根据二维数组的坐标系把每个元素都用链表表示，就组成了一个大十字。