第5章　数组和广义表[视频讲解]

5.1　数组的定义

视频二维码（扫码观看）

数组是由n（n＞1）个具有相同数据类型的数据元素a₁，a₂，…，a_n组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。

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

数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。

数组中的数据元素个数是固定的。

1抽象数据类型定义

ADT Array
{
    数据对象：jk＝0，…，bi－1，i＝1，2，…，n，D＝{aj1j2…jn|n＞0称为数组的维数，bi是数组第i维的长度，ji是数组元素第i维的下标，aj1j2…jn∈ElemSet}
    数据关系：R＝{R1，R2，…，Rn}，其中Ri＝{＜aj1…ji…jn，aj1 …ji＋1…jn＞|0≤jk≤bk－1，1≤k≤n且k≠i，0≤ji≤bi－2，aj1…ji…jn，aj1…ji＋1…jn∈D，i＝1，2，…n}
    基本操作：
        ①InitArray（&A，n，bound1，…，boundn）
            操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。
        ②DestroyArray（&A）
            操作结果：销毁数组A。
        ③Value（A，&e，index1，…，indexn）
            初始条件：A是n维数组，e为元素变量，随后是n个下标值。
            操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。
        ④Assign（&A，e，index1，…，indexn）
            初始条件：A是n维数组，e为元素变量，随后是n个下标值。
            操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。
}ADT Array

2直观的n维数组

以二维数组为例讨论，将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。

设二维数组A＝（a_ij）_m×n，则A＝（α₀，α₁，…，α_p），其中，p＝m－1或n－1。

每个数据元素α_j是一个列向量（线性表）：α_j＝（a_0j，a_1j，…，a_m－1，j），其中，0≤j≤n－1

或是一个行向量：α_i＝（a_i0，a_i1，…，a_i，n－1），其中，0≤i≤m－1

A_m×n＝（（a₀₀，a₀₁，…，a_0，n－1），（a₁₀，a₁₁，…，a_1，n－1），…，（a_m－1，0，a _m－1，1，…，a _{m－1，n－1}））