数据结构线性表

1、数数 据据 结结 构构 第第 2 章章 线性表线性表 .2 线性结构是最常用、最简单的一种数据结构。而线性 表是一种典型的线性结构。其基本特点是线性表中的数据 元素是有序且是有限的有序且是有限的。 线性结构基本特征： 存在一个唯一唯一的被称为“第一个第一个”的数据元素的数据元素； 存在一个唯一唯一的被称为“最后一个最后一个”的数据元素的数据元素； 除第一个元素外，每个元素均有唯一一个直接前驱唯一一个直接前驱； 除最后一个元素外，每个元素均有唯一一个直接后唯一一个直接后 继继。 线性结构线性结构 .3 主要内容主要内容 2.1 线性表抽象数据类型线性表抽象数据类型 2.2 线性表的顺序表示和实现

2、线性表的顺序表示和实现 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.4 线性表的应用：多项式的表示及运算线性表的应用：多项式的表示及运算 .4 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的定义线性表的定义 n线性表线性表是指是指n (n=0)个个类型相同类型相同的数据元素的数据元素 a0,a1,.an-1组成的组成的有限有限序列，其一般描述为：序列，其一般描述为： LinearList=(a0，a1，an 1)。 。 l其中LinearList称为线性表的名称 l每个ai（n-1i0）称为线性表的数据元素，可以是整数、 浮点数、字符或类 l表中相邻元素之间存在着顺序关系

3、：将 ai-1 称为 ai 的前 驱（Predecessor），ai+1 称为 ai 的后继（Successor）。 a0没有前驱元素，an-1没有后继元素 l具体n的值称为线性表中包含有数据元素的个数，也称 为线性表的长度（Length） l当n的值等于0时，表示该线性表是空表 .5 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的定义线性表的定义 线性表的定义中每个线性表的定义中每个数据元素数据元素ai的含义在不同情的含义在不同情 况下各不相同，它们可能是一个字母、一个数字、况下各不相同，它们可能是一个字母、一个数字、 也可以是一条记录等。一般情况下，在线性表中也可以是一条记录等。一

4、般情况下，在线性表中 每个每个ai描述的是一组描述的是一组相同属性相同属性的数据的数据，例如： l英文字母表（A，B，C，Z）是一个长度为26 的线性表，其中的每一个字母就是一个数据元素 l某公司2015年每月产值表（400，420，500， 600，650）(单位：万元)是一个长度为12的线性表， 其中的每一个数值就是一个数据元素 l在一些复杂的线性表中，每一个数据元素又可以由 若干个数据项组成，在这种情况下，通常将数据元 素称为记录（record），比如学生信息记录 .6 l线性表的离散（数学）定义离散（数学）定义如下： B=,其中A包含n个结点的集合(a0， a1，an1) ，R是关系的

5、集合 (ai-1,ai)|i=1,2,.n-1，可见R只有一种类 型的关系，即线性关系线性关系 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的定义线性表的定义 .7 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的特征线性表的特征 从线性表的定义可以看出线性表的特征：从线性表的定义可以看出线性表的特征： 有且仅有一个开始结点(表头结点)a0，它没有 直接前驱，只有一个直接后继; 有且仅有一个终端结点(表尾结点)an-1，它没 有直接后继，只有一个直接前驱; 其它结点都有一个直接前驱和直接后继； 元素之间为一对一的线性关系。 .8 l线性表的抽象数据类型定义抽象数据类型定义如下：

6、ADT LinearList 数据对象:Dai|ai元素集合,i=0,1,2,.n-1n=1 数据关系:R=|ai-1,ai 元素集合,i=1,2,.n-1 基本操作：插入，删除，查找等 ADTlist 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的抽象数据类型线性表的抽象数据类型 .9 线性表的基本操作线性表的基本操作 l求长度：求线性表的数据元素个数。 l访问：对线性表中指定位置的数据元素进行存取、替 换等操作。 l插入：在线性表指定位置上，插入一个新的数据元素， 插入后仍为一个线性表。 l删除：删除线性表指定位置的数据元素，同时保证更 改后的线性表仍然具有线性表的连续性。 l复制

7、：重新复制一个线性表。 l合并：将两个或两个以上的线性表合并起来，形成一 个新的线性表。 l查找：在线性表中查找满足某种条件的数据元素。 l排序：对线性表中的数据元素按关键字值，以递增或 递减的次序进行排列。 l遍历：按次序访问线性表中的所有数据元素，并且每 个数据元素恰好访问一次。 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的抽象数据类型线性表的抽象数据类型 .10 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的抽象数据类型线性表的抽象数据类型 声明线性表抽象数据类型声明线性表抽象数据类型 ADT List /线性表抽象数据类型，数据元素的数据类型为T boolean is

8、Empty() /判断线性表是否为空 int size() /返回线性表长度 T get(int i) /返回第i个元素 void set(int i, T x) /设置第i个元素为x String toString() /所有元素的描述字符串 int insert(int i, T x) /插入x作为第i个元素 .11 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的抽象数据类型线性表的抽象数据类型 int insert(T x) /在线性表最后插入x元素 T remove(int i) /删除第i个元素 void clear() /删除所有元素 int search(T key) /

9、查找与key相等元素 boolean contains(T key) /判断是否包含key元素 int insertDifferent(T x) /插入不重复元素 T remove(T key) /删除与key相等元素 boolean equals(Object obj) /比较是否相等 void addAll(List list) /添加list所有元素 .12 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的分类线性表的分类 线性表有两种存储方式，对应地把线性线性表有两种存储方式，对应地把线性 表分成了两类：表分成了两类： l顺序存储结构的顺序表（或称向量存储、一维 数组存储） l链

10、式存储结构的链表 l线性表的实现： lpublic class SeqList /顺序表类 lpublic class SinglyLinkedList /单链表类 .13 线性表的存储结构线性表的存储结构 2.1 线性表抽象数据类型线性表抽象数据类型 线性表的分类线性表的分类 .14 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 线性表的顺序存储结构线性表的顺序存储结构 l数组 ：是实现顺序存储结构的基础。 数组（Array）存储具有相同数据类型的元素集合。 一维数组占用一块内存空间，每个存储单元的地 址是连续的，计算第i个元素地址所需时间复杂度 是一个常量， 与元素序号i无关。 存

11、取任何一个元素的时间复杂度是O(1)的数据结 构称为随机存取结构。 因此，数组是随机存取结构。 .15 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 线性表的顺序存储结构线性表的顺序存储结构 l数组的特点： l通过下标识别元素，下标是其存储单元序号，表 示元素在数组中的位置 lN维数组有n个下标 l数组地址和容量不能更改 .16 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表定义顺序表定义 l顺序存储方法： l即用一组连续的内存单元依次存放线性表中的 数据元素（元素在内存的物理存储次序与它们 在线性表中的逻辑次序相同） l在内存中开辟一片连续存储空间，但该连

12、续存 储空间的大小要大于或等于顺序表的长度，然 后让线性表中第一个元素存放在连续存储空间 第一个位置，第二个元素紧跟着第一个之后， 其余依此类推 l顺序表定义顺序表定义： l用顺序存储方法存储的线性表简称为顺序表 （Sequential List） .17 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表定义顺序表定义 l在程序设计语言中，通常利用一维数组一维数组来 表示顺序表的数据存储区域数据存储区域，这是因为数 组具有如下特点： l数据中的元素间的地址是连续的 l数组中所有元素的数据类型是相同的 l这与线性表的顺序存储结构(顺序表)是类似的 l考虑：数组存储有什么

13、缺点？ .18 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表定义顺序表定义 采用一维数组存储数 据元素，数据元素在 内存的物理存储次序 反映了线性表数据元 素之间的逻辑次序。 ciaLocaLoc i )()( 0 顺序表是顺序表是随机存取结构随机存取结构 .19 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表定义顺序表定义 若定义数组An= a0，a1，a2，an-1，假设每一个数组元 素占用d个字节，则数组元素A0，A1，A2，An-1的 地址分别为Loc(A0)，Loc(A0)+d，Loc(A0)+2d， Loc(A0)+（n-1

14、）d 。其结构如图所示 ： .20 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表定义顺序表定义 l由上可知，数据的存储逻辑位置由数组的下标决定。 所以相邻的元素之间地址的计算公式为（假设每个数 据元素占有d个存储单元）： LOC（ai）=LOC（ai-1）+d l对线性表的所有数据元素，假设已知第一个数据元 素a0的地址为LOC（a0） ，每个结点占有d个存储 单元， 则第i个数据元素ai的地址为： LOC（ai）=LOC（a0）+i*d l线性表的第一个数据元素的位置通常称做起始位置 或基地址。 l在使用一维数组时，数组的下标起始位置根据给定 的问题确定，或者根

15、据实际的高级语言的规定确定。 .21 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的实现顺序表的实现 l顺序表的实现定义: l顺序表可以直接使用一维数组描述为： type arrayname；/type的类型根据实际需要确定/ l该代码只是对应用数组的声明，还没有对该数组分配空 间，因此不能访问数组。只有对数组进行初始化并申请 内存资源后，才能够对数组中元素进行使用和访问 larrayname= new typearraysize l其作用是给名称为arrayname的数组分配arraysize个类 型为type大小的空间 l其中arraysize表示数组的长度，

16、它可以是整型的常量和 变量；如果arraysize是常量，则分配固定大小的空间， 如果是变量，则表示根据参数动态分配数组的空间 .22 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的实现顺序表的实现 书上P18定义的顺序表 /顺序表类，实现ADT List声明的方法，T表示数据元素 /的数据类型 public class SeqList extends Object /顺序表类。 /public class SeqList extends MyAbstractList（继承抽象列表类） protected Object element; /对象数组，保护成员 pr

17、otected int n; /顺序表元素个数（长度） .23 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的实现顺序表的实现 lP18书上定义的顺序表注意： ln=element.length（书上错误！），顺序表元素个数 lSeqList 类声明为实现线性表接口ADT List的 泛型类，T表示线性表元素的数据类型。当声明 SeqList类的一个对象并创建实例时，指定泛型参数T 为一个确定的类，如 SeqList list=new SeqList(); l泛型T的实际参数必须是类，不能是基本数据类型 l成员变量是保护类型 l数据元素不能是空对象（null） l

18、注意回忆理解Java类是引用数据类型（与基本数据类 型相区别） .24 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 初始化操作（由构造函数实现）：初始化操作（由构造函数实现）： 创建顺序表对象为其分配内存空间，另外，还需要设定当前顺序 表的长度 算法如下算法如下（注意书上（注意书上P20下对下对Java语言构造函数的解释！）语言构造函数的解释！） /1. 构造、存取 public SeqList(int length) /构造容量为length的空表 this.element = new Objectlength; /申请数组的存储空间

19、，元素为null。 /若length0，Java抛出异常 java.lang.NegativeArraySizeException this.n = 0; public SeqList() /创建默认容量的空表，构造方法重载 this(64); /调用本类已声明的指定参数列表的构造方法 .25 初始化操作（由构造函数实现）：初始化操作（由构造函数实现）： public SeqList(T values) /构造顺序表，由values数组提供元素，忽略其中空对象 this(values.length); /创建容量为values.length的空表 /若values=null，用空对象调用方法，

20、Java抛出空对象异常NullPointerException for (int i=0; ivalues.length; i+) /复制数组元素，O(n) this.elementi = valuesi; /对象引用赋值 this.n = element.length; /也可 this.insert(valuesi); /尾插入，this.n+。暂且不用，因为还没有讲到 /也可 for (T x : values) /数组逐元循环 / this.insert(x); /尾插入，this.n+1 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本

21、操作 .26 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 String values=A,B,C,D,E; SeqList lista = new SeqList(values); /lista引用顺序表实例，元素是String对象 泛型类与创建实例 .27 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 释放操作（由析构函数实现）：释放操作（由析构函数实现）： Java类不需要声明析构方法 .28 判断顺序表的空与满：判断顺序表的空与满： 顺序表为空：n=0; 顺序表为满：n=el

22、ement.length 算法如下：算法如下： public boolean isEmpty() /判断顺序表是否空，若空返回true，O(1) return this.n=0; 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .29 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 返回顺序表的长度：返回顺序表的长度： n是长度 算法如下：算法如下： public int size() /返回顺序表元素个数，O(1) return this.n; .30 2.2 线性表的顺序存储和实现线

23、性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 获得（获得（get）顺序表的顺序表的第第i个个数据元素值：数据元素值： 需要注意i的有效性，然后根据数组的下标从0开始， 来考虑到底返回哪一个元素 算法如下：算法如下： /存取操作 public T get(int i) /返回第i个元素，0i=0 /返回数组元素引用的对象，传递对象引用 / return this.elementi; 编译错，Object对象不能返回T对象注意前面的定 / 义Object element; return null; .31 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-

24、顺序表的基本操作顺序表的基本操作 设置（设置（set）顺序表的顺序表的第第i个个数据元素值为数据元素值为x： 需要注意x的有效性，考虑如下： 1）如果x已经是被赋值的元素，如何处理 2）如果x还没有被赋值，如何处理 .32 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 设置（设置（set）顺序表的顺序表的第第i个个数据元素值：数据元素值： 算法如下：算法如下： /设置第i个元素为x，0i=0 /执行T类的toString()方法，运行时多态 for (int i=1; ithis.n; i+) str += , +this.element

25、i.toString(); /执行T类的toString()方法，运行时多态 return str+) ; /空表返回() 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .34 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 toString()采用字符串形式描述对象的属性值（遍历）：采用字符串形式描述对象的属性值（遍历）： /返回顺序表所有元素的描述字符串，形式为“(,)”。覆盖Object类的 / toString()方法方法2 / 可行，效率同上 public String to

26、String() String str=(; if (this.n!=0) for(int i=0; ithis.n-1; i+) str += this.get(i).toString()+, ; str += this.get(this.n-1).toString(); / 单独追加最后一个元素，不加逗号 return str+); .35 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 lisEmpty()、size()、get(i)、set(i,x)方法，时 间复杂度为O(1) 。为什么？ ltoString()方法需要遍历顺序表，

27、时间复杂 度为O(n)。为什么？ 操作的效率分析操作的效率分析 .36 插入操作：插入操作： 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表: (a0，a1，. ，ai-1，ai，ai+1，. ，an1) 成为表长为 n+1 表: (a0，a1，. ，ai-1，x，ai，ai+1，. ，an1) i 的取值范围为0=i=n 。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .37 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 插入操作：插入操作

28、： .38 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 插入操作插入操作 算法设计： l参数： l插入位置 i l插入元素x l操作步骤： 书上例子中先对i值进行修正（也可以直接报错） 将aian-1 顺序向下移动，为新元素让出位置 将x 置入空出的第i个位置 修改表长 .39 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 插入操作插入操作 算法设计： l注意： l当插入一个元素时，如果数组element已满，为了能使插 入操作正常进行，insert ()方法创建一个容量为原数组两

29、 倍的新数组，并将原数组中的元素复制到新数组中 l若使用new申请存储空间失败，java虚拟机将产生内存 溢出，并终止程序 l边界的取值 l方法实现： pint insert(int i, T x) /插入x作为第i个元素 pint insert(T x) /尾插入x元素。重载 .40 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 插入操作插入操作 若数组满，则扩充顺序表的数组容量 .41 插入操作插入操作 数组扩容，理解对象引用赋值 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .

30、42 插入操作插入操作 /插入x作为第i个元素，x!=null，返回x序号。若x=null，抛出空对象异常。O(n) /对序号i采取容错措施，若in，插入x在最后 public int insert(int i, T x) if (x=null) throw new NullPointerException(x=null); /抛出空对象异常 if (ithis.n) i=this.n; /插入在最后 Object source = this.element; /数组变量引用赋值，source也引用element数组 if (this.n=element.length) /若数组满，则扩充顺序

31、表的数组容量 this.element = new Objectsource.length*2; /重新申请一个容量更大的数组 for (int j=0; j=i; j-) /从i开始至表尾的元素向后移动，次序从后向前 this.elementj+1 = sourcej; this.elementi = x; this.n+; return i; /返回x序号 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .43 插入操作插入操作 public int insert(T x) /顺序表尾插入x元素，返回x序号。成 员方法重载 return

32、 this.insert(this.n, x); /插入操作中， this.n加1 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .44 插入操作 当在顺序存储结构的线当在顺序存储结构的线 性表中某个位置上插入一性表中某个位置上插入一 个数据元素时个数据元素时, ,其时间消其时间消 耗主要在移动元素上耗主要在移动元素上, ,而而 移动元素的个数取决于插移动元素的个数取决于插 入或者删除元素的位置入或者删除元素的位置 考虑考虑，时间复杂度？时间复杂度？ )( 2 2 ) 1( 1 1 )( 1 1 ) )( 0 0 nO n nn n in

33、 n inp n i n i i 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .45 删除操作删除操作 ： 线性表的删除运算是指将表中第 i 个元素从线性表中去 掉，删除后使原表长为 n 的线性表： (a0，a1，. ，ai-1，ai，ai+1，. ，an1) 成为表长为 n1 的线性表： (a0，a1，. ，ai-1，ai+1，. ，an1) i 的取值范围为：0=i=n-1 。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .46 删除操作删除操作 ： 2.2 线性表的顺序存储

34、和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .47 顺序表上完成这一运算的步骤如下： 找到要删除的位置i 依次将ai+1an-1 顺序向上移动 修改表长 方法实现： pT remove(int i) /返回删除第i（0in）个元素 pvoid clear() /删除线性表所有元素 删除操作删除操作 ： 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .48 本算法注意以下问题： 删除第i个元素，i的取值为 0=i=element.length-1否 则第i个元素不存在，因此，要检查删除位置的有效 性。 当表

35、空(element.length=0)时不能做删除。 1.删除 ai 之后，该数据已不存在，如果需要，先取出 ai ，再做删除。 删除操作删除操作 ： 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .49 顺序表的删除操作顺序表的删除操作 public T remove(int i) /删除第i个元素，0i0 /old中存储被删除元素 for (int j=i; jthis.n-1; j+) this.elementj = this.elementj+1; /元素前移一个位置 this.elementthis.n-1=null; /设置数

36、组元素对象为空，释放原引用 实例 this.n-; return old; /返回old局部变量引用的对象，传递对象引用 return null; /throw new IndexOutOfBoundsException(i+); /抛出序号越界异常 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .50 public void clear() /删除线性表所有元素 this.n=0; /设置长度为0，未释放数组空间 删除操作删除操作 ： 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作

37、.51 当在顺序存储结构的线性表中某个位置上当在顺序存储结构的线性表中某个位置上 删除一个数据元素时删除一个数据元素时, ,其时间消耗主要在移其时间消耗主要在移 动元素上动元素上, ,而移动元素的个数取决于插入或而移动元素的个数取决于插入或 者删除元素的位置者删除元素的位置. . 考虑：时间复杂度？考虑：时间复杂度？ 删除元素平均移动次数（删除元素平均移动次数（n-1n-1）/2/2 时间复杂度为时间复杂度为 O(n)O(n) 删除操作删除操作 ： 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .52 【例2.1】 求解约瑟夫环问题 约瑟

38、夫环（约瑟夫环（JosephusJosephus）问题）问题： 1.古代某法官要判决N个犯人的死刑，他有一条荒唐的法律， 将犯人站成一个圆圈，从第S个人开始数起，每数到第D个犯 人，就拉出来处决，然后再数D个，数到的在处决直到 剩下的最后一个可赦免。 2.设编号为1、2、n的n个人围坐一圈，约定编号为 k(1=k=n)的人从1开始报数，数到m的那个人出列，他的 下一位又从1开始报数，数到m的那个人出列，依次类推，知 道所有人出列为止，由此产生一个出队编号的序列。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .53 使用顺序表求解Jose

39、phus环 number=5 start=0 distance=2时的执行示意图 如何设计算法？ 【例例2.1】 求解约瑟夫环问题求解约瑟夫环问题 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .54 /注意：泛型的实际参数只能是类，不能是基本类型char、int等 /import dataStructure.*; /声明导入指定包中的类或接口 public class Josephus /【例2.1】求解Josephus环问题。 /创建Josephus环并求解，参数指定环长度、起始位置、计数 public Josephus(int nu

40、mber, int start, int distance) System.out.print(Josephus(+number+,+start+,+distance+)，); SeqList list = new SeqList(number); /创建顺序表实例，元素类型是字符串，构造方法参数指定顺序表容量，省略 /时取默认值 for (int i=0; i1) /多于一个元素时循环，计数O(1) i = (i+distance-1) % list.size(); /按循环方式对顺序表进行遍历 System.out.print(删除+list.remove(i).toString()+，)

41、; /删除i位置对象，O(n) System.out.println(list.toString(); System.out.println(被赦免者是+list.get(0).toString();/get(0)获得元素，O(1) 【例例2.1】 求解约瑟夫环问题求解约瑟夫环问题 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .56 public static void main(String args) /【例2.1】求解Josephus环问题。 new Josephus(5,0,2); 【例例2.1】 求解约瑟夫环问题求解约瑟夫环问

42、题 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .57 /* 程序运行结果如下： Josephus(5,0,2)，(A, B, C, D, E) 删除B，(A, C, D, E) 删除D，(A, C, E) 删除A，(C, E) 删除E，(C) 被赦免者是C Josephus(5,0,2)，SeqList(A, B, C, D, E) 删除B，SeqList(A, C, D, E) 删除D，SeqList(A, C, E) 删除A，SeqList(C, E) 删除E，SeqList(C) 被赦免者是C 【例例2.1】 求解约瑟夫环问题求

43、解约瑟夫环问题 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .58 查找操作查找操作 /顺序查找算法 /顺序查找首次出现的与key相等元素，返回元素序号i；查找不成功返回-1。 /若key=null，Java抛出空对象异常NullPointerException public int search(T key) for (int i=0; ithis.n; i+) if (key.equals(this.elementi) /执行T类的equals(Object)方法，运行时多态 return i; return -1; /空表或未找到

44、时 boolean contains(T key) /包含 return this.search(key)!=-1; 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .59 /插入不重复元素。查找不成功时，尾插入插入不重复元素。查找不成功时，尾插入 int insertDifferent(T x) return this.search(x)=-1 ? this.insert(x) : -1; T remove(T key) /删除首个与删除首个与key相等元素相等元素 return this.remove(this.search(key);

45、 /先查找，再调用先查找，再调用remove(i)。 /若查找不成功，返回若查找不成功，返回- -1，则不删除，则不删除 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 查找操作查找操作 .60 Object类 public boolean equalsequals(Object obj) return (this = obj); /若两个对象引用同一个实例，返回true Object类中equals(Object)函数比较两个是对象是否引用同一个实例。其他类继 承Object类时会覆盖equals(Object)方法，例如： public

46、 final class IntegerInteger extends Number implements Comparable private final int value; public boolean equals(Object obj) /覆盖Object类的方法 if (obj instanceof Integer) return value = (Integer)obj).intValue(); /比较两个Integer对象的值 return false; 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 查找操作查找操作 .6

47、1 考虑线性表的其他基本操作：考虑线性表的其他基本操作： 置表为空置表为空 遍历顺序表并输出遍历顺序表并输出 求前驱求前驱 求后继求后继 复制复制 合并合并 排序排序 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .62 顺序表的静态特性很好，动态特性很差，具体说明 如下： 顺序表元素的物理存储顺序直接反映线性表元素的 逻辑顺序，顺序表是一种随机存取结构。get()、set() 方法时间复杂度是 O(1)。 插入和删除操作效率很低（O(n)）。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 小结 顺序表顺序表-顺序表的基本操作顺序

48、表的基本操作 .63 顺序表的浅拷贝与深拷贝（自学） 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .64 比较相等操作 习题2-5 SeqList类以下声明有什么错误？为什么？ public boolean equals(Object obj) /比较两个顺序表是否相等，覆盖 return this.n=list.n 注意：注意： 1. 1.使用使用“=”比较两个对象时，比较的是两个对象的内存地址，比较两个对象时，比较的是两个对象的内存地址， 所以不相等即使它们内容相等，但是不同对象的内存地址也是所以不相等即使它们内容相等，但是不同对象

49、的内存地址也是 不相同的。不相同的。 2. 2.两个线性表相等是指，它们各对应元素相等并且长度相同两个线性表相等是指，它们各对应元素相等并且长度相同 ( (使用使用equal()equal()函数函数) )。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .65 /习题解答习题解答2-5 比较相等操作比较相等操作 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .66 比较相等操作比较相等操作 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的

50、基本操作 .67 /SeqList类声明覆盖 public boolean equals(Object obj) if (this=obj) /引用同一个实例 return true; if (obj instanceof SeqList) /若obj引用顺序表实例。 /SeqList是所有SeqList的父类 SeqList list = (SeqList)obj; if (this.n=list.n) /比较长度 for (int i=0; ithis.n; i+) /比较所有元素 if (!(this.get(i).equals(list.get(i) /运行时多态 return fal

51、se; return true; return false; 比较相等操作比较相等操作 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的基本操作顺序表的基本操作 .68 线性表的顺序存储结构中任意数据元素线性表的顺序存储结构中任意数据元素 的存储地址可由公式直接导出，因此顺的存储地址可由公式直接导出，因此顺 序存储结构的线性表是可以序存储结构的线性表是可以随机存取随机存取其其 中的任意元素。中的任意元素。 也就是说定位操作可以直接实现。也就是说定位操作可以直接实现。 高级程序设计语言提供的数组数据类型高级程序设计语言提供的数组数据类型 可以直接定义顺序存储结构的线性

52、表，可以直接定义顺序存储结构的线性表， 使其程序设计十分方便。使其程序设计十分方便。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的存储结构优点顺序表的存储结构优点 .69 n但是，顺序存储结构也有一些不便之处，表现在： n数据元素最大个数需预先确定，使得高级程序设计语言 编译系统需预先分配相应的存储空间。 n插入与删除运算的效率很低。为了保持线性表中的数据 元素的顺序，在插入操作和删除操作时需移动大量数据。 这对于插入和删除操作频繁的线性表、以及每个数据元 素所占字节较大的问题将导致系统的运行速度难以提高。 n顺序存储结构的线性表的存储空间不便于扩充。当一个 线

53、性表分配顺序存储空间后，如果线性表的存储空间已 满，但还需要插入新的元素，则会发生“上溢”错误。 在这种情况下，如果在原线性表的存储空间后找不到与 之连续的可用空间，则会导致运算的失败或中断。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺序表顺序表-顺序表的存储结构缺点顺序表的存储结构缺点 .70 从线性表的顺序存储结构的讨论中可知，对于大的 线性表，特别是元素变动频繁的大线性表不宜采用 顺序存储结构，而应采用链式存储结构 。 线性表的链式存储结构线性表的链式存储结构就是用若干地址分散地址分散的存储 单元（可以是不连续的）存储线性表的数据元素。 采用链式存储结构表示的线性表称为线性

54、链表线性链表 在链式存储结构方式下，存储数据元素的结点结点空间 可以不连续，各数据结点的存储顺序与数据元素之 间的逻辑关系可以不一致（逻辑上相邻的数据元素逻辑上相邻的数据元素 在物理位置上不一定相邻！在物理位置上不一定相邻！），而数据元素之间的 逻辑关系由指针域（地址域）指针域（地址域）来确定。 2.3 线性表的链式存储和实现线性表的链式存储和实现 线性表的链式存储结构线性表的链式存储结构 .71 对线性表中的每一个结点结点，都至少需用两部分来 存储：一部分用于存放数据元素值，称为数据域； 另一部分用于存放直接前驱或直接后继结点的地 址（指针），称为地址域（指针域），我们把这 种存储单元称为结

55、点。 用结点结点来存储线性表中的每一个数据元素。数据元素。 2.3 线性表的链式存储和实现线性表的链式存储和实现 线性表的链式存储结构线性表的链式存储结构-结点结点 .72 线性表的链式存储结构L=(a1,a2,an) 示意图 （单链表），其中(a)为非空表，(b)为空表。 2.3 线性表的链式存储和实现线性表的链式存储和实现 线性表的链式存储结构线性表的链式存储结构-带头结点链表带头结点链表 .73 2.3 线性表的链式存储和实现线性表的链式存储和实现 线性表的链式存储结构线性表的链式存储结构-不带头结点（带头指针）链表不带头结点（带头指针）链表 .74 下面将介绍几个线性链表（linear

56、 linked list） 类型的实现： 单链表（singly linked list） 双链表（doubly linked list） 循环链表（circular linked list） 2.3 线性表的链式存储和实现线性表的链式存储和实现 线性表的链式存储结构线性表的链式存储结构-链表分类链表分类 .数据结构（Java版）（第4版）第2章 75 每个结点只有一个地址域的线性链表称为每个结点只有一个地址域的线性链表称为单链表单链表 任意存储单元（结点）存储单向链表的数据元素时，其形式如 下图所示： DATANEXT 其中data 是数据域，存放数据元素的值；next是地址域， 存放相邻的下

57、一个结点的地址 单向链表是指结点中的指针域只有一个沿着同一个方向 表示的链式存储结构。 因为结点是一个独立的对象，所以能够实现独立的结点 类。 2.3 线性表的链式存储和实现线性表的链式存储和实现 单链表单链表 .76 单链表是由多个元素（结点）组成的 前驱结点和后继结点 链表的存贮方式是：在内存中利用存贮单 元(可以不连续)来存放元素值及相关元素在 内存中的地址，各个元素的存放顺序及位 置都可以以任意顺序进行，原来相邻的元 素存放到计算机内存后不一定相邻，从一 个元素找下一个元素必须通过地址(指针)才 能实现。故不能像顺序表一样可随机访问， 而只能按顺序顺序访问 2.3 线性表的链式存储和实

58、现线性表的链式存储和实现 单链表单链表 .77 a2 180 a4 170 a6 NULL a1 110 a5 140 a3 130 150 地址 data 域 next 域 110 120 130 140 150 160 170 180 head 头指针头指针 a1 a2 a3 a4 a5 a6 单链表的逻辑表示 逻辑表示示意图 单链表物理存储物理存储示意图 head 2.3 线性表的链式存储和实现线性表的链式存储和实现 单链表单链表 .78 考虑：考虑： 如何实现单链表类？如何实现单链表类？ 关键在于结点关键在于结点 如何实现单链表结点类？如何实现单链表结点类？ 成员变量包含哪些？成员变量

59、包含哪些？ 构造函数如何定义？构造函数如何定义？ 有哪些常用的操作？有哪些常用的操作？ 2.3 线性表的链式存储和实现线性表的链式存储和实现 单链表单链表-单链表的类实现单链表的类实现 .79 成员变量： 结点元素是一个自引用的数据，当前结点对象 中具有下一个结点元素的对象 构造方法： 构造一个结点元素时，其值被存储到对象中， 并且结点元素包括一个指向链表中下一个元素 的引用 其他方法： 访问一个类对象的数据时，使用所给方法直接 访问（读或写）数据域及引用域 2.3 线性表的链式存储和实现线性表的链式存储和实现 单链表单链表-单链表的结点类实现单链表的结点类实现 .80 /1. 单链表结点类

60、public class Node /单链表结点类，T指定结点的元素类型 public T data; /数据域，存储数据元素 public Node next; /地址域，引用后继结点 public Node(T data, Node next) /构造结点，data指定数据元素，next指定后继结点 this.data = data; /T对象引用赋值 this.next = next; /Node对象引用赋值 public Node() this(null, null); 2.3 线性表的链式存储和实现线性表的链式存储和实现 单链表单链表-单链表的结点类实现单链表的结点类实现 .81 p