数据结构数组与顺序表.ppt

* * 第2章 顺序表与数组 数据结构 一维数组 数组的定义：存储于一个连续存储空间的 相同类型的数据元素的集合。 一维数组：长度（大小）为n的有限序列 下标，起始下标，元素占用空间，数组占用空间，访问数组元素，...... 35 27 49 18 60 54 77 83 41 02 下标 0 1 2 3 4 5 6 7 8 9 ??? ??? ? 多维数组及其顺序存储 多维数组是一维数组的推广 i i j i k 一维数组a[5] 二维数组b[3][5] 三维数组c[3][5][4] a[i] b[i][j] c[i][j][k] 复合线性结构 j ??? ? 一维数组连续存储方式 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l LOC(i) = LOC(i-1)+l = LOC(i-1)+ i*l LOC(i) = LOC(0) +i*l, i 0 LOC(0) , i = 0 a+i*l a ??? 二维数组连续存储方式 行优先存放： LOC(j, k) = LOC(0, 0) + ( j * m + k ) * l 每个元素占用的存储单元 第一个元素的存储地址 ?? 三维数组连续存储方式 各维元素个数为 m1, m2, m3。 下标为 i1, i2, i3的数组元素的存储地址：（按页/行/列存放） LOC(i1,i2,i3) = LOC(0,0,0) + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前i1页总 元素个数 第i1页的 前i2行总元素个数 第i2行 前i3列元素个数 ? 线性表 (Linear List) 定义：n个数据元素的有限序列； n为线性 表的长度，当n＝0时为空表。 特点： 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制。 ??? ?? 顺序表 (Sequential List) 定义：将线性表中的元素相继存放在一 个连续的存储空间中。可利用一 维数组或链表作为其存储结构。 特点：顺序存取 限制：所有元素有相同数据类型 顺序表的遍历： ??? ? 顺序表结构 listarray 0 1 size-1 MaxSize size 数组下标 数组 变量 操作算法 MaxSize-1 . . . . . . . . . 初始化操作 插入操作 删除操作 查找操作 排序操作 . . . . . . ??? 顺序表(SeqList)类的定义 public class SeqList { final int defaultSize = 10; int maxSize; int size; Object[ ] listArray; private void initiate(int sz){ maxSize = sz; size = 0; listArray = new Object[sz]; } public SeqList(int size){ initiate(size); } public SeqList(){ initiate(defaultSize); } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } public int Find ( Object x ) { …… } public void insert(int i,Object obj) { …… } public Object delete(int i) { …… } public Object getData(int i) { …… } pub