数组

一、数组的定义

数组是由n(n>1)个相同类型的数据元素a0,a1,…,an-1组成的有限序列,且该有限序列存储在一块地址连续的内存单元中,因而数组一般采用顺序存储结构。

对于一维数组,一旦a0的存储地址Loc(a0)确定,每个数据元素的存储单元大小为k,则任一数据元素ai的存储地址Loc(ai)可由以下公式求出:

Loc(ai) = Loc(a0) + i x k,其中 0 ≤ i < n。

对于二维数组,可将其转化为一维数组来考虑,下图为一个m行n列的二维数组,可以看做线性表:

二维数组示例:A = (a0, a1, …, an-1)
二维数组示例
其中,每个数据元素ai = (ai0, ai1, …, ai(n-1)),0 ≤ i < m

显然,二维数组同样满足数组的定义。一个二维数组可以看做每个数据元素都是相同类型的一维数组的一维数组。以此类推,一个三维数组可以看做一个没个数据元素都是相同类型的二维数组的一维数组。

因此,数组具有以下特点:

  1. 数组中的数据元素具有相同的数据类型
  2. 数组是一种随机存储结构,可以根据给定的一组小标直接访问对应的数组元素
  3. 一旦建立了数组,则数组中的数据元素个数和元素之间的关系就不再发生变化

二、数组的内存映像

一维数组使用内存中一段连续的存储空间进行存储,它的存储结构关系为:

Loc(ai) = Loc(a0) + i x k,其中 0 ≤ i < n。

由于计算机的内存结构是一维的,因此用一维内存表示多维数组,就必须按某种次序将数组元素排成一个序列,然后将这个线性序列存放在存储器中。

对于二维数组,其存储可按行或列的次序用一组连续存储单元存放数组中的数组元素。

二维数组的两种存储形式:

二维数组的两种存储形式

在一个以行序为主序的计算机系统中,若二维数组第一个数据元素a00的存储地址为Loc(a00),假定每个数据元素占k个存储单元,则该二维数组中任一数据元素的存储地址可由下式确定:

Loc(aij) = Loc(a00) + (i x n + j) x k

同理,可写出更高维数组的数据元素存储位置的计算公式。

用户头像
登录后发表评论