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