|
多维数组和广义表是一种复杂的非线性结构它们的逻辑特征是一个数据元素可能有多个直接前驱和多个直接后继 多维数组 数组（向量）——常用数据类型 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素 同一数组的不同元素通过不同的下标标识 （aa…an) 二维数组 二维数组Amn可视为由m个行向量组成的向量或由n个列向量组成的向量 二维数组中的每个元素aij既属于第i行的行向量又属于第j列的列向量 多维数组三维数组Amnp可视为以二维数组为数据元素的向量四维数组可视为以三维数组为数据元素的向量…… 三维数组中的每个元素aijk都属于三个向量四维数组中的每个元素都属于四个向量…… 数组的顺序存储方式 由于计算机内存是一维的多维数组的元素应排成线性序列后存人存储器 数组一般不做插入和删除操作即结构中元素个数和元素间关系不变化一般采用顺序存储方法表示数组 （）行优先顺序 将数组元素按行向量排列第i+个行向量紧接在第i个行向量后面 【例】二维数组Amn的按行优先存储的线性序列为 aa…anaa…an……amam…amn 注意 ①PASCAL和C语言中数组按行优先顺序存储 ②行优先顺序推广到多维数组可规定为先排最右的下标 （）列优先顺序 将数组元素按列向量排列第i+个列向量紧接在第i个列向量后面 【例】二维数组Amn的按列优先存储的线性序列为 aa…amaa…am……anan…amn 注意 ①FORTRAN语言中数组按列优先顺序存储 ②列优先顺序推广到多维数组可规定为先排最左的下标 数组元素的地址计算公式（）按行优先顺序存储的二维数组Amn地址计算公式 LOC(aij)=LOC(a)+[(i)×n+j]×d 其中 ①LOC(a)是开始结点的存放地址（即基地址） ②d为每个元素所占的存储单元数 ③由地址计算公式可得数组中任一元素可通过地址公式在相同时间内存取即顺序存储的数组是随机存取结构 （）按列优先顺序存储的二维数组Amn地址计算公式 LOC(aij)=LOC(a)+[(j)×m+i]×d （）按行优先顺序存储的三维数组Amnp地址计算公式 LOC(aijk)=LOC(a)+[(i)×n×p+(j)×p+k]×d （）下界不为的二维数组的地址计算公式 ①二维数组A[cdcd]的地址计算公式 LOC(aij)=LOC(acc)+[(ic)×(dc+)+jc]×d ②下界为的二维数组的地址计算公式（C语言中使用） LOC(aij)=LOC(a)+[i×(d+)+j]×d 注意 以下讨论的数组存储结构都以C语言下标表示 |
