数组的基本概念和存储结构

不同语境下的数组

●数据结构视角下的数组

    • 数组A是 n (n>1) 个相同类型数据元素a1,a2,...,an 构成的有限序列
    • 数据的逻辑表示 : A = (a1 , a2 , ..., an)
    • 其中 , ai(i<= i <= n )表示数组A中的第 i 个元素

● c/c++ 语言下的数组

    #define N 100
    int a[N]

●维数不同的数组    

• 一维数组 : 由多个数据元素构成

 • 二维数组 : 每个数据元素都是相同类型的一维数组的一维数组

        

 • 多维数组都可以看作一个线性表 , 线性表中的每个数据元素也是一个线性表

---

● d (d>= 3) 维数组 , 看作一个由 d-1 维 数组作为数据元素的线性表 ;

● 数组是一种较复杂的线性表结构 , 由简单的数据结构即线性表辗转合成而得

 ● 数组的基本运算

 • Value(A,index 1, index 2, ...,index d) ------返回各下标指定的A中的对应元素的值

 • A 是已存在的 d 维数组 ,  index1, index 2, ..., index d 是指定的 d 个下标值 , 且这些下界均未越界

• 例 : 对二维数组 : Value(A , i , j)

---

• Assign(A , e , index 1, index 2, ... , index d)-----将e赋值给由各下标指定的 A 中的元素

• A 是已存在的 d 维数组 , e 为元素变量 , index 1, index 2 , index d 是指定的 d 个下标值 , 且这些下标均未越界 .

例如 :  Assign(A , e , i , j)

---

• ADisp (A , b1, b2, ..., bd) :输出d维数组 A 的所有元素值  

数组的存储结构

•要求 

数组的所有元素存储在一块地址连续的内存单元中。

• 实现

几乎所有的计算机语言都支持数组类型

• 数组数据类型的性质（以C/C++语言为例）

（1）数组中的数据元素数目固定，一旦定义,其数据元素数目不再有增减变化。

（2）数组中的数据元素具有相同的数据类型。

（3）数组中的每个数据元素都和一组唯一的下标值对应

一维数组的存储地址

● 条件

  • 一维数组

  • a1 的存储地址：LOC(a1)

  • 每个数据元素占用的存储单元数：k

  •任一数据元素ai的存储地址LOC(ai)为 LOC(ai)=LOC(a1)+(i-1)*k (0≤i≤n)

---

从 LOC(a1)开始 , 再加上元素前面的元素个数 ,当然是 LOC(a1) 加上 (元素标号 -1) 乘以 k

● 特点

•  一维数组中任一数据元素的存储地址可直接计算 得到，即一维数组中任一数据元素可直接     存取(可以通过下标找到)

• 一维数组是一种随机存储结构

---

怎么看？

顺序存储结构用数组实现

                                        ——从占用存储空间角度

数组是随机存取结构

                                        ——从存取数据角度

二位数组的表示和存储

 把二位数组可以看成一维数组 , 有若干行构成 的一维数组 ,或者若干列构成得一维数组

● 以行序为主序的存储方式 : 即先存储第一行 ,然后紧接着存储第二行 , 最后存储第 m 行

        • 行序为主序的线性排列次序 : a11, a12,a13,....., a1n,a21,a22,...., a2n,...., am1,am2,...,amn

        •实际存储就是一维概念

        •任一元素aij 的存储地址:

                Loc(aij) = Loc(a11) + [ (i - 1)* n + (j - 1) * k]

        (我们是从 1 ,开始算的,是逻辑上的位序 , 所以此元素前面的所有行就是 i -1 , 此元素所在行的前面的元素就是 j-1 , 初始地址加上前面的所有元素乘以单个元素所占有的空间就是 此元素的开始地址)

● 以列序为主序的存储方式 :即先存储第一列 , 然后紧接着存储第二列,最后存储第m 列

        •列序为主序的线性排列次序: a11,a12,...,am1,a12,...,am2,...,a1n,a2n,...amn

        •任一数据元素aij的存储地址: Loc(aij) = Loc(a11)+[(j-1)*m+(i-1)]*k

  

 对于此类数组 A[c1..d1, c2...d2]

● 特点

        • 行下标: c1至d1

        •列下标 : c2至d2

●数据元素aij的存储地址

        •以行序为主序: Loc(aij) = Loc(ac1 c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k
        •以列序为主序: Loc(aij) = Loc(ac1 c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k
●例: c/c++中数组float a[5][4] ,起始地址 2000,数据元素长度 4,a[3][2]地址?
    •c1 = 0, d1 = 4, c2=0,d2= 3,Loc(ac1 ac2)=2000, k=4
    •以行序为主序: Loc(a32) = 2000+[3*4+2]*4 = 2056
    •以列序为主序: Loc(a32) = 2000+[2*5+3]*4 = 2052