文档介绍：数组
数组的定义
二维数组是一个复杂的线性表:
A=(a1,a2,a3,……,ap) (p=m 或 n)
p=m时,每个数组元素是由第i行元素组成的线性表
ai=(ai1,ai2,ai3,……,ain)
p=n时,每个数组元素是由第j列元素组成的线性表
aj=(a1j,a2j,a3j,……,amj)
i
j
1
第二章常用数据结构及其运算
数组
数组的定义
数组的逻辑结构
B=(K, R)
K={Kij| 1<=i<=m, 1<=j<=n}
R={ROW,COL}
ROW={(Kij,Kij+1) |1<=i<=m,1<=j<=n-1}
COL={(Kij,Ki+1j) |1<=i<=m-1,1<=j<=n}
2
第二章常用数据结构及其运算
数组
数组的定义
二维数组是一个线性表,其中每个元素是一个1维数组
三维数组是一个线性表,其中每个元素是一个2维数组
n维数组是一个线性表,其中每个元素是一个n-1维数组
…
a1
a2
a3
ap
3
第二章常用数据结构及其运算
数组
数组的顺序存储结构
1. 按行优先顺序存放
二维数组
Loc(aij)=Loc(a11)+[(i-1)×n+(j-1)]×C
--1<=i<=m, 1<=j<=n, 每个元素占C个存储单元
计算机存储单元是一维结构,而数组是多维结构,顺序存储问题即是:多维->一维的问题。
a11
a12
a1n
a21
a22
am1
am2
amn
a2n
…
…
…
…
第1行
第2行
第m行
Loc(a11)
4
第二章常用数据结构及其运算
数组
数组的顺序存储结构
1. 按行优先顺序存放
三维数组:At,m,n
t=2,m=3,n=4时,存储顺序为:
a111a112a113a114a121a122a123a124a131a132a133a134a211a212……a231a232a233a234
则:
Loc(aijk)=Loc(a111)+[(i-1)×m×n+(j-1)×n+(k-1)]×C
--1<=i<=t,1<=j<=m,1<=k<=n, 每个元素占C个存储单元
5
第二章常用数据结构及其运算
数组
数组的顺序存储结构
2. 按列优先顺序存放
二维数组
Loc(aij)=Loc(a11)+[(j-1)×m+(i-1)]×C
--1<=i<=m, 1<=j<=n, 每个元素占C个存储单元
a11
a21
am1
a12
a22
a1n
a2n
amn
am2
…
…
…
…
第1列
第2列
第n列
Loc(a11)
6
第二章常用数据结构及其运算
数组
数组的顺序存储结构
2. 按列优先顺序存放
三维数组:At,m,n
Loc(aijk)=Loc(a111)+[(k-1)×t×m+(j-1)×t+(i-1)]×C
--1<=i<=t,1<=j<=m,1<=k<=n, 每个元素占C个存储单元
7
第二章常用数据结构及其运算
数组
数组的顺序存储结构
例1:二维数组Aij, 0<=i<=5, 1<=j<=7,问按行存储A35 和按列存储哪一个矩阵元素在相同位置?
解: 3×7+(5-1)=6(j-1)+i ,
0<=i<=5,
1<=j<=7,
=> i=1, j=5,
即: A15
8
第二章常用数据结构及其运算
数组
数组的顺序存储结构
例2:一维数组P[k],其第15个数据元素的存储终地 址是1164H,如第m个数据元素占m个字节, 求第一个数据元素的存储起始地址。
解: 1到第15个元素的总存储空间为:
1+2+3+……+15=120=78 H
则起始地址为:
1164 H – 78 H + 1 = 10ED H
9
第二章常用数据结构及其运算
数组
数组的顺序存储结构
3. 特殊矩阵的存放
下三角矩阵
按行优先存放:a11 a21 a22 a31 a32 a33 … ai1 ai2 ai3 … an1 an2 … ann ,
则非零元素总个数为:
Loc(aij)=Loc(a11)+[i(i-1)/2+(j-1)]×C,
--1<=j<=i<=n, i(i-1)/2为第一至第i-1行非零元素个数
10
第二章常用数据结构及其运算