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

第第2 2章章 顺序表与数组顺序表与数组 数据结构数据结构 一维数组一维数组 数组的定义：存储于一个数组的定义：存储于一个连续存储连续存储空间的空间的 相同类型相同类型的数据元素的集合。的数据元素的集合。 一维数组：长度（大小）为一维数组：长度（大小）为n 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 一维数组a5 二维数组b35 三维数组c354 ai bij cijk 复合线性结构复合线性结构 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, i3i1, i2, i3的数组元素的存储地址：（的数组元素的存储地址：（ 按页按页/ /行行/ /列存放）列存放） LOC(i1,i2,i3) = LOC(0,0,0) + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前i1页总 元素个数 第i1页的 前i2行总 元素个数 第i2行 前i3列元 素个数 线性表线性表 (Linear List)(Linear List) 定义：定义：n n个数据元素的有限序列；个数据元素的有限序列； n n为线性为线性 表的长度，当表的长度，当n n0 0时为空表。时为空表。 特点：特点： 除第一个元素外，其他每一个元素有一个且仅除第一个元素外，其他每一个元素有一个且仅 有一个直接前驱。有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且除最后一个元素外，其他每一个元素有一个且 仅有一个直接后继。仅有一个直接后继。 原则上讲，线性表中表元素的数据类型可以不相原则上讲，线性表中表元素的数据类型可以不相 同。但采用的存储表示可能会对其有限制。同。但采用的存储表示可能会对其有限制。 顺序表顺序表 (Sequential List)(Sequential List) 定义：将线性表中的元素相继存放在一定义：将线性表中的元素相继存放在一 个连续的存储空间中。可利用一个连续的存储空间中。可利用一 维维数组数组或或链表链表作为其存储结构。作为其存储结构。 特点：顺序存取特点：顺序存取 限制：所有元素有相同数据类型限制：所有元素有相同数据类型 顺序表的遍历：顺序表的遍历： 顺序表结构顺序表结构 listarray 0 1 size-1 MaxSize size 数组下标 数组变量操作算法 MaxSize-1 . . . . . . . . . 初始化操作 插入操作 删除操作 查找操作 排序操作 . . . . . . 顺序表顺序表(SeqList)(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 Objectsz; 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) public int MoreDataDelete(SeqList L, Object x) 顺序表的查找（搜索）顺序表的查找（搜索） public int Find ( Object x ) int i = 0; while ( i = size ) return -1; else return i; 搜索函数 int Find ( Object x ) 在顺序表中从头向尾查找结点值等于给定值x的结点 顺序搜索图示顺序搜索图示 25 34 57 16 48 09 0 1 2 3 4 5 搜索 16 i 25 34 57 16 48 09 i 25 34 57 16 48 09 i 25 34 57 16 48 09 i 搜索成功 listarray 25 34 57 16 48 0 1 2 3 4 搜索 50 i 25 34 57 16 48 i 25 34 57 16 48 i 25 34 57 16 48 i 25 34 57 16 48 i 搜索失败 listarray 搜索成功的平均比较次数搜索成功的平均比较次数 若搜索概率相等，则若搜索概率相等，则 最好情况，查找目标为第一个元素，比较最好情况，查找目标为第一个元素，比较1 1次；次； 最坏情况：搜索不成功最坏情况：搜索不成功 数据比较数据比较 n 次。次。 情况i时的 比较次数 情况i发生 的概率 顺序表的插入操作顺序表的插入操作 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 50插入 x = 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 50 i listarray listarray 顺序表的插入操作成员函数顺序表的插入操作成员函数 public void insert(int i,Object obj) throws Exception if (size = maxSize) throw new Exception(“顺序表已满无法插入！“); if (i size) throw new Exception(“参数错误！“); for(int j = size; j i; j-) listArrayj = listArrayj-1; listArrayi = obj; size+; 顺序表的删除操作顺序表的删除操作 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 listarray16 删除 x 25 34 57 50 48 09 63 0 1 2 3 4 5 6 7 listarray 顺序表的删除操作成员函数（顺序表的删除操作成员函数（1 1） public Object delete(int i) throws Exception if(size = 0) throw new Exception(“顺序表已空无法删除！“); if (i size-1) throw new Exception(“参数错误！“); Object it = listArrayi; for(int j = i; j 表示， 并用一顺序表（一维数组）来存放上述三元组. class Trituple /三元组 int row, col; /非零元素行号/列号 double value; /非零元素的值 矩阵的三元组表示矩阵的三元组表示( (压缩压缩) ) 顺序表 下标 行 (row) 列 (col) 值 (value ) 0 0322 1 0615 2 1111 3 1517 4 23-6 5 3539 6 4091 7 5228 稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型 class Trituple /三元组 private int row, col; /非零元素行号/列号 private double value; /非零元素的值 class SparseMatrix /稀疏矩阵类定义 int Rows, Cols, Terms; /行，列，非零元素数 final int MaxTerms=20; Trituple smArray =new TritupleMaxTerms; /三元组表 public SparseMatrix (int MaxRow, int Maxcol); /构造函数 /转置、相加、相乘 public SparseMatrix Transpose(SparseMatrix a); public SparseMatrix Add (SparseMatrix a, SparseMatrix b); public SparseMatrix Multiply(SparseMatrix a, SparseMatrix b); 特殊矩阵的表示特殊矩阵的表示( (压缩压缩) ) a11 a12 . a1n a12 a22 . an2 a1n a2n ann . a11 a12 a22 an1 ann . k=0 1 2 n n(n-1)/2 n(n+1)/2-1 按行序为主序： 对称矩阵 特殊矩阵的表示特殊矩阵的表示( (压缩压缩) ) a11 0 0 0 a21 a22 0 0 an1 a