JAVA数据结构第二章线性表A.ppt

数据结构课程的内容 逻辑结构唯一 存储结构不唯一 运算的实现依赖 于存储结构 线性表 逻辑结构存储结构 基 本 概 念 抽象 数据 类型 定义 线性表定义 逻辑特征 ADT定义 基本操作 顺 序 存 储 链 接 存 储 其 他 存 储 顺序表的特点 顺序表类定义 基本操作的实 现及时间性能 单链表的特点 单链表类定义 基本操作的实 现及时间性能 比 较 循环链表 双链表 静态链表 线性表的应用 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： （a1, a2, ai-1，ai, ai1 ，, an） 1. 线性表的定义：n(n0)个相同类型数据元 素的有限序列。 n=0时称为 数据元素 线性起点ai的直接前趋ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总个 数，即表长 空表 线性终点 2.1 线性表的逻辑结构 例1 分析26 个英文字母组成的英文表 （ A, B, C, D, , Z） 学号姓名性别年龄班级 2005011810205于春梅女 182005级计信016班 2005011810260何仕鹏男 182005级计信017班 2005011810284王 爽女 182005级通信011班 2005011810360王亚武男 182005级通信012班 ： ： 例2 分析学生情况登记表 数据元素都是记录; 元素间关系是线性 数据元素都是字母; 元素间关系是线性的。 a1a3a4ana2 2、线性表的特性 1）.有限性：线性表中数据元素的个数是有穷的。 2）.相同性：线性表中数据元素的类型是同一的。 3）.顺序性：线性表中相邻的数据元素ai-1和ai之间存 在序偶关系，即ai-1是ai的前驱， ai是ai-1 的后继；a1 无前驱，an无后继，其它每个元素有且仅 有一个前驱和一个后继。 练：判断下列叙述的正误： 1. 数据的逻辑结构是指数据元素之间的逻辑关系 ，是用户按使用需要建立的。 2. 线性表的逻辑结构定义是唯一的，不依赖于计 算机。 3. 线性结构反映结点间的逻辑关系是一对一的。 4.一维向量是线性表，但二维或N维数组不是。 5.“同一数据逻辑结构中的所有数据元素都具有相 同的特性”是指数据元素所包含的数据项的个 数都相等。 3、线性表的操作 线性表接口LList声明如下，描述线性表的取值、置 值、插入、删除等基本操作。 package dataStructure.linearList;/声明属于的包 public interface LList/纯性表接口 boolean isEmpty(); /判断线性表是否为空，若空返回true int length(); /返回线性表长度； E get(int index); /返回序号为index的对象，index初值为0 BACK BACK E set(int index, E element); /设置序号为index对象为element，返回原对象 boolean add(int index, E element); /插入element对象，插入后对象序号为index boolean add(E element); /插入element对象，插入位置没有约定 E remove(int index); /移去序号为index的对象，返回被移动对象 void clear();/清空线性表； 进一步说明: （1）线性表的基本操作根据实际应用而定； （2）复杂的操作可以通过基本操作的组合来实现； （3）对不同的应用，操作的接口可能不同。 BACK 2.2 线性表的顺序存储和实现 2.2.1 顺序表的顺序存储表示 2.2.2 顺序表的实现 2.2.3 顺序表的算法效率分析 本节小结 2.2.1顺序表的顺序存储表示 用一组地址连续的存储单元依 次存储线性表的元素，可通过静态数组 Vn或动态数组来实现。 把逻辑上相邻的数据元素存储 在物理上相邻的存储单元中的存储结构。 线性表的顺序表示又称为顺序存储结构或顺序映像。 顺序存储定义： 顺序存储方法： 简言之，逻辑上相邻，物理上也相邻 “顺序表是一种随机存取的存储结构”的含义为：查 找操作，其时间性能为O(1)。 线性表顺序存储特点： 1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出（利用数组下标）。计算方法 是（参见存储结构示意图）： 设首元素a1的存放地址为LOC(a0)（称为首地址） ， 设每个元素占用存储空间（地址长度）为c字节， 则表中任一数据元素的存放地址为： LOC(ai) = LOC(a0) + i*c LOC(ai+1) = LOC(a0)+ (i+1)*c 注意：JAVA语言中的数组的下标从0开始， 即：Vn的有效范围是V0Vn-1 线性表的顺序存储结构示意图 一个一维数组，下标的范围是到 ，每个数组元素用相邻的个字节存储。存 储器按字节编址，设存储数组元素的 第一个字节的地址是，则的第一 个字节的地址是 113 例3、 因此：LOC( M3 ) = 98 + 35=113 解：地址计算通式为： 2.2.2 顺序表的实现 1）顺序表的存储结构定义(即顺序表类的声明)： package dataStructure.linearlist; import dataStructure.linearlist.Llist; public class SeqList implements Llist /顺序表类SeqList，实现线性表接口 private Object table; /对象数据，私有成员 private int n; /顺序表的长度 public SeqList( ); /指定空表的默认容量 public SeqList(int capacity); /创建指定容量的空表 public boolean isEmpty()；/判断顺序表是否为空 public int length(); /求顺序表的长度 public E get(int index) /返回index位置的对象 public E set(int index, E element) /设置index位置的对象为 element,若成功返回原对象，否则返回null public boolean add(int index, E element); /在第index个位置 插入对象element public void clear(); /清空顺序表 2）顺序表的操作实现(即顺序表类的定义实现P37-40)： public SeqList( ); /指定空表的默认容量 public SeqList(int capacity); /创建指定容量 的空表 public boolean isEmpty()；/判断顺序表是否 为空 public int length(); /求顺序表的长度 public E get(int index) /返回index位置的对象 public E set(int index, E element) /设置index位 置的对象为element,若成功返回原对象，否则返回 null 操作接口public boolean add(int index, E element); /在第index个位置插入对象element 插入前：(a0, , ai-1, ai, , an-1) 插入后：(a0, , ai-1, item , ai, , an-1) 插入操作实现 ai-1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 插入操作图示 33 例如：（35，12，24，42），在index=2的位置上 插入33。 表满：this.n=table.length 合理的插入位置：0indextable.length-1 4 35122442 a0a1a2a3 0 1 2 3 4 422412335 什么时候不能插入？注意边界条件 插入：在顺序表的第index个位置插入一个元素 实现步骤： 将第n-1至第index位的元素向后移动一个位置； 将要插入的元素写到第index个位置； 表长加1。 注意： 事先应判断: 1. 插入位置index是否合法? 2. 表是否已满? JAVA具体实现： public boolean add(int index, E element) if (element=null) return false; /不能插入null if (this.n=table.length) /若数组满，则需要扩充顺序表容量 Object temp=this.table; this.table=new Objecttemp.length*2; for (int i=0;ithis.n) index=this.n; for (int j=this.n-1;j=index;j-)/元素后移 this.tablej+1=this.tablej; this.tableindex=element; this.n+; return true; 操作接口public E remove(int index x) 删除前：(a1, , ai-1,ai,ai+1,an) 删除后：(a1,ai-1,ai+1, ,an) ai-1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 删除操作实现 删除操作图示 例：（35, 33, 12, 24, 42），删除index=2的数据元 素。 5 35 a1a2a3a4 0 1 2 3 4 422412334 a5 122442 表空： this.n=0 合理的删除位置：0index=0 return null; 时间复杂度？ O(1) 2.2.3顺序表的算法效率分析 插入、删除算法时间主要耗费在移动元素的操作 T(n)= O (移动元素次数) 移动元素的次数取决于插入或删除元素的位置。 讨论1：若在长度为 n 的线性表的第 i 位前 插入一元素 ，则向后移动元素的次数f(n)为: f(n) =n i + 1 时间效率分析: 最好情况（ i =n+1）：移动元素次数0次，时间复杂度 为O(1)。 最坏情况（ i =1）：移动元素次数n次，时间复杂度为 O(n)。 平均情况（1in+1）：时间复杂度为O(n)。 +- + = 1 1 )=1( n i i inp +- + + = 1 1 )=1( 1 1 n i in n 2 n O(n) 讨论2：若在长度为n的线性表上删除第i位元素，向 前移动元素的次数f(n)为： f(n) = n i 讨论3：顺序表的插入、删除操作算法空间复杂度 S(n)=O(1) 最好情况（ i =n）：移动元素次数0次，时间复杂度为 O(1)。 最坏情况（ i =1）：移动元素次数n-1次，时间复杂度 为O(n)。 平均情况（1in）：时间复杂度为O(n)。 - =1 )=( n i i inp - =1 )=( 1 n i in n2 n-1 O(n) 应用实例： （上机练习题提示）设有线性表 LA（3,5,8,11）和 LB=（2,6,8,9,11,15,20）； 若LA和LB分别表示两个集合A和B，求新集合 AA U B（并操作，相同元素不保留）； 按规律插入 插入到尾部 预测输出：LA=（3,5,8,