java数据结构第05章 数组和广义表.ppt

文档介绍：数据结构（Java版）
1
嘉兴学院信息工程学院
第五章 数组、集合和矩阵
2
数组
数组的定义
数组是n（n≥1）个相同数据类型的数据元素a0,a1,a2,...,an-1构成的占用一块地址连续的内存单元的有限集合。
数组与线性表的比较：
同：同类型的数据元素组成的有限有序序列
异：存储空间的连续性；
数据元素的逻辑原子性；
数据元素的存取方式。
3
数组的实现机制
存储空间连续
数组元素名即数组元素在内存中的地址
计算数组元素内存地址
对一个有n个数据元素的一维数组，设a0是下标为0的数组元素，Loc(a0)是a0的内存单元地址，是每个数据元素为x个字节，则数组元素a[i]的内存单元地址Loc(ai)可由下面公式求出：
Loc(ai) = Loc(a0) + i × x ( 0≤i＜n )
4
多维数组的存储
用一维的内存空间存储多维数组
——逐行（逐列）存储
5
称为基地址或基址。
以“行序为主序”的顺序存储映象(遍历)
二维数组A[m][n]中任一元素ai,j 的存储位置
LOC(i,j) = LOC(0,0) + (n×i＋j)×
a0,1
a0,0
a0,2
a1,0
a1,1
a1,2
a0,1
a0,0
a0,2
a1,0
a1,1
a1,2
x
x
同理，在"以列为主"的顺序映象中的存储地址为：
a2,0
a2,1
a2,2
a2,0
a2,1
a2,2
LOC(i,j) = LOC(0,0) + (m ×j +i) ×x
6
类似地，假设三维数组 R[p][m][n] 中每个数据元素占x个存储地址，并以 LOC(i,j,k) 表示下标为(i,j,k) 的数据元素的存储地址，则该数组中任何一对下标(i,j,k) 对应的数据元素在“以行为主”的顺序映象中的存储地址为：
LOC(i,j,k)
= LOC(0,0,0) + (i×m n + j×n+k)×x
7
数组抽象数据类型
数据集合 数组的数据集合可以表示为a0, a1, a2, ..., an-1，且限定数组元素必须存储在地址连续的内存单元中。
操作集合：
（1）分配内存空间acclocate()
（2）取数组长度getLength()
（3）存数组元素set(i, x)
（4）取数组元素get(i)
8
Java语言支持的数组功能
1 基本数据类型的数组
由于数组是非常基础的程序设计语言要素，所以Java语言设计实现了数组功能。
支持的数组操作有：
（1）分配内存空间
（2）获得数组长度
（3）存数组元素
（4）取数组元素
9
2 对象数组
除了可以定义基本数据类型的数组外，Java语言还可以定义对象数组。
对象数组的存取操作
10