数据结构(第二章-线性表)

数据结构第2章线性表

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。线性结构基本特征：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后继。线性结构主要内容2.1线性表抽象数据类型2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用：多项式的表示及运算2.1线性表抽象数据类型线性表的定义线性表是指n(n>=0)个类型相同的数据元素a0,a1,...an-1组成的有限序列，其一般描述为：LinearList=(a0，a1，…，an－1)。

其中LinearList称为线性表的名称每个ai（n-1≥i≥0）称为线性表的数据元素，可以是整数、浮点数、字符或类表中相邻元素之间存在着顺序关系：将ai-1

称为ai

的前驱（Predecessor），ai+1

称为ai

的后继（Successor）。a0没有前驱元素，an-1没有后继元素具体n的值称为线性表中包含有数据元素的个数，也称为线性表的长度（Length）当n的值等于0时，表示该线性表是空表2.1线性表抽象数据类型线性表的定义线性表的定义中每个数据元素ai的含义在不同情况下各不相同，它们可能是一个字母、一个数字、也可以是一条记录等。一般情况下，在线性表中每个ai描述的是一组相同属性的数据，例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素某公司2015年每月产值表（400，420，500，…，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），比如学生信息记录线性表的离散（数学）定义如下：B=<A,R>,其中A包含n个结点的集合(a0，a1，…，an－1)，R是关系的集合 {(ai-1,ai)|i=1,2,..n-1}，可见R只有一种类型的关系，即线性关系2.1线性表抽象数据类型线性表的定义2.1线性表抽象数据类型线性表的特征从线性表的定义可以看出线性表的特征：有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继;有且仅有一个终端结点(表尾结点)an-1，它没有直接后继，只有一个直接前驱;其它结点都有一个直接前驱和直接后继；元素之间为一对一的线性关系。线性表的抽象数据类型定义如下：ADT LinearList{数据对象:D＝{ai|ai∈元素集合,i=0,1,2,..n-1 n>=1}数据关系:R={<ai-1,ai>|ai-1,ai∈元素集合,i=1,2,..n-1}基本操作：{插入，删除，查找等}} ADT list2.1线性表抽象数据类型线性表的抽象数据类型线性表的基本操作求长度：求线性表的数据元素个数。访问：对线性表中指定位置的数据元素进行存取、替换等操作。插入：在线性表指定位置上，插入一个新的数据元素，插入后仍为一个线性表。删除：删除线性表指定位置的数据元素，同时保证更改后的线性表仍然具有线性表的连续性。复制：重新复制一个线性表。合并：将两个或两个以上的线性表合并起来，形成一个新的线性表。查找：在线性表中查找满足某种条件的数据元素。排序：对线性表中的数据元素按关键字值，以递增或递减的次序进行排列。遍历：按次序访问线性表中的所有数据元素，并且每个数据元素恰好访问一次。2.1线性表抽象数据类型线性表的抽象数据类型2.1线性表抽象数据类型线性表的抽象数据类型声明线性表抽象数据类型ADTList<T>//线性表抽象数据类型，数据元素的数据类型为T{booleanisEmpty()//判断线性表是否为空intsize()//返回线性表长度

Tget(inti)//返回第i个元素

voidset(inti,Tx)//设置第i个元素为xStringtoString()//所有元素的描述字符串

intinsert(inti,Tx)//插入x作为第i个元素2.1线性表抽象数据类型线性表的抽象数据类型

intinsert(Tx)//在线性表最后插入x元素Tremove(inti)//删除第i个元素

voidclear()//删除所有元素

intsearch(Tkey)//查找与key相等元素booleancontains(Tkey)//判断是否包含key元素

intinsertDifferent(Tx)//插入不重复元素

Tremove(Tkey)//删除与key相等元素

booleanequals(Objectobj)//比较是否相等voidaddAll(List<T>list)//添加list所有元素}2.1线性表抽象数据类型线性表的分类线性表有两种存储方式，对应地把线性表分成了两类：顺序存储结构的顺序表（或称向量存储、一维数组存储）链式存储结构的链表线性表的实现：publicclassSeqList<T>//顺序表类publicclassSinglyLinkedList<T>//单链表类线性表的存储结构

2.1线性表抽象数据类型线性表的分类2.2线性表的顺序存储和实现线性表的顺序存储结构数组：是实现顺序存储结构的基础。数组（Array）存储具有相同数据类型的元素集合。一维数组占用一块内存空间，每个存储单元的地址是连续的，计算第i个元素地址所需时间复杂度是一个常量，与元素序号i无关。存取任何一个元素的时间复杂度是O(1)的数据结构称为随机存取结构。因此，数组是随机存取结构。2.2线性表的顺序存储和实现线性表的顺序存储结构数组的特点：通过下标识别元素，下标是其存储单元序号，表示元素在数组中的位置N维数组有n个下标数组地址和容量不能更改2.2线性表的顺序存储和实现顺序表-顺序表定义顺序存储方法：即用一组连续的内存单元依次存放线性表中的数据元素（元素在内存的物理存储次序与它们在线性表中的逻辑次序相同）在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推顺序表定义：用顺序存储方法存储的线性表简称为顺序表（SequentialList）2.2线性表的顺序存储和实现顺序表-顺序表定义在程序设计语言中，通常利用一维数组来表示顺序表的数据存储区域，这是因为数组具有如下特点：数据中的元素间的地址是连续的数组中所有元素的数据类型是相同的这与线性表的顺序存储结构(顺序表)是类似的考虑：数组存储有什么缺点？？？2.2线性表的顺序存储和实现顺序表-顺序表定义采用一维数组存储数据元素，数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。顺序表是随机存取结构

2.2线性表的顺序存储和实现顺序表-顺序表定义若定义数组A[n]={a0，a1，a2，…，an-1}，假设每一个数组元素占用d个字节，则数组元素A[0]，A[1]，A[2]，…，A[n-1]的地址分别为Loc(A[0])，Loc(A[0])+d，Loc(A[0])+2d，…，Loc(A[0])+（n-1）d。其结构如图所示：2.2线性表的顺序存储和实现顺序表-顺序表定义由上可知，数据的存储逻辑位置由数组的下标决定。所以相邻的元素之间地址的计算公式为（假设每个数据元素占有d个存储单元）：LOC（ai）=LOC（ai-1）+d对线性表的所有数据元素，假设已知第一个数据元素a0的地址为LOC（a0），每个结点占有d个存储单元，则第i个数据元素ai的地址为：LOC（ai）=LOC（a0）+i*d线性表的第一个数据元素的位置通常称做起始位置或基地址。在使用一维数组时，数组的下标起始位置根据给定的问题确定，或者根据实际的高级语言的规定确定。2.2线性表的顺序存储和实现顺序表-顺序表的实现顺序表的实现定义:顺序表可以直接使用一维数组描述为：typearrayname[]；//type的类型根据实际需要确定//该代码只是对应用数组的声明，还没有对该数组分配空间，因此不能访问数组。只有对数组进行初始化并申请内存资源后，才能够对数组中元素进行使用和访问arrayname=newtype[arraysize]其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间其中arraysize表示数组的长度，它可以是整型的常量和变量；如果arraysize是常量，则分配固定大小的空间，如果是变量，则表示根据参数动态分配数组的空间2.2线性表的顺序存储和实现顺序表-顺序表的实现书上P18定义的顺序表//顺序表类，实现ADTList<T>声明的方法，T表示数据元素//的数据类型publicclassSeqList<T>extendsObject//顺序表类。//publicclassSeqList<T>extendsMyAbstractList<T>（继承抽象列表类）{

protectedObject[]element;//对象数组，保护成员

protectedintn;//顺序表元素个数（长度）2.2线性表的顺序存储和实现顺序表-顺序表的实现P18书上定义的顺序表注意：n<=element.length（书上错误！），顺序表元素个数SeqList<T>类声明为实现线性表接口ADTList<T>的泛型类，T表示线性表元素的数据类型。当声明SeqList类的一个对象并创建实例时，指定泛型参数T为一个确定的类，如 SeqList<String>list=newSeqList<String>();泛型T的实际参数必须是类，不能是基本数据类型成员变量是保护类型数据元素不能是空对象（null）注意回忆理解Java类是引用数据类型（与基本数据类型相区别）2.2线性表的顺序存储和实现顺序表-顺序表的基本操作初始化操作（由构造函数实现）：创建顺序表对象为其分配内存空间，另外，还需要设定当前顺序表的长度算法如下（注意书上P20下对Java语言构造函数的解释！）

//1.构造、存取

publicSeqList(intlength)//构造容量为length的空表

{this.element=newObject[length];//申请数组的存储空间，元素为null。 //若length<0，Java抛出异常java.lang.NegativeArraySizeExceptionthis.n=0;}publicSeqList()//创建默认容量的空表，构造方法重载

{this(64);//调用本类已声明的指定参数列表的构造方法

}初始化操作（由构造函数实现）：publicSeqList(T[]values)//构造顺序表，由values数组提供元素，忽略其中空对象

{this(values.length);//创建容量为values.length的空表

//若values==null，用空对象调用方法，Java抛出空对象异常NullPointerExceptionfor(inti=0;i<values.length;i++)//复制数组元素，O(n)this.element[i]=values[i];//对象引用赋值

this.n=element.length;//也可this.insert(values[i]);//尾插入，this.n++。暂且不用，因为还没有讲到

//也可for(Tx:values)//数组逐元循环//this.insert(x);//尾插入，this.n+1}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作Stringvalues[]={"A","B","C","D","E"};SeqList<String>lista=newSeqList<String>(values); //lista引用顺序表实例，元素是String对象泛型类与创建实例2.2线性表的顺序存储和实现顺序表-顺序表的基本操作释放操作（由析构函数实现）： Java类不需要声明析构方法判断顺序表的空与满： 顺序表为空：n=0;

顺序表为满：n>=element.length算法如下：publicbooleanisEmpty()//判断顺序表是否空，若空返回true，O(1){returnthis.n==0;}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作返回顺序表的长度：

n是长度算法如下：publicintsize()//返回顺序表元素个数，O(1){returnthis.n;}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作获得（get）顺序表的第i个数据元素值： 需要注意i的有效性，然后根据数组的下标从0开始，来考虑到底返回哪一个元素算法如下：//存取操作

publicTget(inti)//返回第i个元素，0≤i<n。若i越界，返回null。O(1){if(i>=0&&i<this.n)return(T)this.element[i];//返回数组元素引用的对象，传递对象引用//returnthis.element[i];编译错，Object对象不能返回T对象注意前面的定//义Object[]element;

returnnull;}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作设置（set）顺序表的第i个数据元素值为x： 需要注意x的有效性，考虑如下：

1）如果x已经是被赋值的元素，如何处理

2）如果x还没有被赋值，如何处理

2.2线性表的顺序存储和实现顺序表-顺序表的基本操作设置（set）顺序表的第i个数据元素值：算法如下：//设置第i个元素为x，0≤i<n。若i越界，抛出序号越界异常；若x==null，抛出空对象异常。O(1)publicvoidset(inti,Tx){if(x==null)thrownewNullPointerException("x==null");//抛出空对象异常

if(i>=0&&i<this.n)this.element[i]=x;elsethrownewjava.lang.IndexOutOfBoundsException(i+"");//抛出序号越界异常

}toString()采用字符串形式描述对象的属性值（遍历）：//返回顺序表所有元素的描述字符串，形式为“(,)”。覆盖Object类的//toString()方法1，注意P21下的解释—运行时多态！

publicStringtoString(){Stringstr=this.getClass().getName()+"(";//返回类名//Stringstr="(";if(this.n>0)str+=this.element[0].toString();//执行T类的toString()方法，运行时多态

for(inti=1;i<this.n;i++)str+=","+this.element[i].toString();//执行T类的toString()方法，运行时多态

returnstr+")";//空表返回()}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作toString()采用字符串形式描述对象的属性值（遍历）：//返回顺序表所有元素的描述字符串，形式为“(,)”。覆盖Object类的//toString()方法2//可行，效率同上

publicStringtoString(){Stringstr="(";if(this.n!=0){for(inti=0;i<this.n-1;i++)str+=this.get(i).toString()+",";str+=this.get(this.n-1).toString();//单独追加最后一个元素，不加逗号}returnstr+")";}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作isEmpty()、size()、get(i)、set(i,x)方法，时间复杂度为O(1)。为什么？toString()方法需要遍历顺序表，时间复杂度为O(n)。为什么？操作的效率分析插入操作： 线性表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表:(a0，a1，...，ai-1，ai，ai+1，...，an－1)

成为表长为n+1表:(a0，a1，...，ai-1，x，ai，ai+1，...，an－1) i的取值范围为0<=i<=n

。2.2线性表的顺序存储和实现顺序表-顺序表的基本操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作：

2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作算法设计：参数：插入位置i插入元素x操作步骤：书上例子中先对i值进行修正（也可以直接报错）将ai～an-1

顺序向下移动，为新元素让出位置将x置入空出的第i个位置修改表长2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作算法设计：注意：当插入一个元素时，如果数组element已满，为了能使插入操作正常进行，insert()方法创建一个容量为原数组两倍的新数组，并将原数组中的元素复制到新数组中若使用new申请存储空间失败，java虚拟机将产生内存溢出，并终止程序边界的取值方法实现：intinsert(inti,Tx)//插入x作为第i个元素intinsert(Tx)//尾插入x元素。重载2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作若数组满，则扩充顺序表的数组容量插入操作数组扩容，理解对象引用赋值2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作

//插入x作为第i个元素，x!=null，返回x序号。若x==null，抛出空对象异常。O(n)//对序号i采取容错措施，若i<0，插入x在最前；若i>n，插入x在最后

publicintinsert(inti,Tx){if(x==null)thrownewNullPointerException("x==null");//抛出空对象异常

if(i<0)i=0;//插入位置i容错，插入在最前

if(i>this.n)i=this.n;//插入在最后

Object[]source=this.element;//数组变量引用赋值，source也引用element数组

if(this.n==element.length)//若数组满，则扩充顺序表的数组容量

{this.element=newObject[source.length*2];//重新申请一个容量更大的数组

for(intj=0;j<i;j++)//复制当前数组前i-1个元素

this.element[j]=source[j];}for(intj=this.n-1;j>=i;j--)//从i开始至表尾的元素向后移动，次序从后向前

this.element[j+1]=source[j];this.element[i]=x;this.n++;returni;//返回x序号

}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作publicintinsert(Tx)//顺序表尾插入x元素，返回x序号。成员方法重载{returnthis.insert(this.n,x);//插入操作中，this.n加1}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作插入操作当在顺序存储结构的线性表中某个位置上插入一个数据元素时,其时间消耗主要在移动元素上,而移动元素的个数取决于插入或者删除元素的位置考虑，时间复杂度？？？2.2线性表的顺序存储和实现顺序表-顺序表的基本操作删除操作：线性表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的线性表： (a0，a1，...，ai-1，ai，ai+1，...，an－1)

成为表长为n－1的线性表：

(a0，a1，...，ai-1，ai+1，...，an－1) i的取值范围为：0<=i<=n-1

。2.2线性表的顺序存储和实现顺序表-顺序表的基本操作删除操作：2.2线性表的顺序存储和实现顺序表-顺序表的基本操作顺序表上完成这一运算的步骤如下：找到要删除的位置i依次将ai+1～an-1

顺序向上移动修改表长方法实现：Tremove(inti)//返回删除第i（0≤i<n）个元素voidclear()//删除线性表所有元素删除操作：2.2线性表的顺序存储和实现顺序表-顺序表的基本操作本算法注意以下问题：删除第i个元素，i的取值为0=<i=<element.length-1否则第i个元素不存在，因此，要检查删除位置的有效性。当表空(element.length==0)时不能做删除。删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。删除操作：2.2线性表的顺序存储和实现顺序表-顺序表的基本操作顺序表的删除操作

publicTremove(inti)//删除第i个元素，0≤i<n，返回被删除元素。若i越界，返回null。//？？若i越界，抛出序号越界异常

{if(this.n>0&&i>=0&&i<this.n){Told=(T)this.element[i];//old中存储被删除元素

for(intj=i;j<this.n-1;j++)this.element[j]=this.element[j+1];//元素前移一个位置

this.element[this.n-1]=null;//设置数组元素对象为空，释放原引用实例

this.n--;returnold;//返回old局部变量引用的对象，传递对象引用

}returnnull;//thrownewIndexOutOfBoundsException(i+"");//抛出序号越界异常

}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作publicvoidclear()//删除线性表所有元素

{this.n=0;//设置长度为0，未释放数组空间}删除操作：2.2线性表的顺序存储和实现顺序表-顺序表的基本操作

当在顺序存储结构的线性表中某个位置上删除一个数据元素时,其时间消耗主要在移动元素上,而移动元素的个数取决于插入或者删除元素的位置.考虑：时间复杂度？？？删除元素平均移动次数（n-1）/2时间复杂度为O(n)删除操作：2.2线性表的顺序存储和实现顺序表-顺序表的基本操作【例2.1】求解约瑟夫环问题约瑟夫环（Josephus）问题：1.古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的在处决……直到剩下的最后一个可赦免。2.设编号为1、2、···、n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人出列，依次类推，知道所有人出列为止，由此产生一个出队编号的序列。2.2线性表的顺序存储和实现顺序表-顺序表的基本操作使用顺序表求解Josephus环number=5start=0distance=2时的执行示意图如何设计算法？【例2.1】求解约瑟夫环问题2.2线性表的顺序存储和实现顺序表-顺序表的基本操作//注意：泛型<T>的实际参数只能是类，不能是基本类型char、int等//importdataStructure.*;//声明导入指定包中的类或接口publicclassJosephus{//【例2.1】求解Josephus环问题。

//创建Josephus环并求解，参数指定环长度、起始位置、计数

publicJosephus(intnumber,intstart,intdistance){System.out.print("Josephus("+number+","+start+","+distance+")，");SeqList<String>list=newSeqList<String>(number);//创建顺序表实例，元素类型是字符串，构造方法参数指定顺序表容量，省略//时取默认值

for(inti=0;i<number;i++)

list.insert((char)(‘A’+i)+“”);//顺序表尾插入，O(1),char类型+””转化为string类型System.out.println(list.toString());//输出顺序表的描述字符串，O(n)【例2.1】求解约瑟夫环问题2.2线性表的顺序存储和实现顺序表-顺序表的基本操作inti=start;//计数起始位置

while(list.size()>1)//多于一个元素时循环，计数O(1){i=(i+distance-1)%list.size();//按循环方式对顺序表进行遍历 System.out.print("删除"+list.remove(i).toString()+"，"); //删除i位置对象，O(n)System.out.println(list.toString());}System.out.println("被赦免者是"+list.get(0).toString());//get(0)获得元素，O(1)}【例2.1】求解约瑟夫环问题2.2线性表的顺序存储和实现顺序表-顺序表的基本操作publicstaticvoidmain(Stringargs[]){

//【例2.1】求解Josephus环问题。

newJosephus(5,0,2);}【例2.1】求解约瑟夫环问题2.2线性表的顺序存储和实现顺序表-顺序表的基本操作/*程序运行结果如下：Josephus(5,0,2)，(A,B,C,D,E)删除B，(A,C,D,E)删除D，(A,C,E)删除A，(C,E)删除E，(C)被赦免者是CJosephus(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】求解约瑟夫环问题2.2线性表的顺序存储和实现顺序表-顺序表的基本操作查找操作//顺序查找算法//顺序查找首次出现的与key相等元素，返回元素序号i；查找不成功返回-1。//若key==null，Java抛出空对象异常NullPointerExceptionpublicintsearch(Tkey){for(inti=0;i<this.n;i++)if(key.equals(this.element[i])) //执行T类的equals(Object)方法，运行时多态

returni;return-1; //空表或未找到时}booleancontains(Tkey)//包含{ returnthis.search(key)!=-1;}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作//插入不重复元素。查找不成功时，尾插入intinsertDifferent(Tx){ returnthis.search(x)==-1?this.insert(x):-1;}Tremove(Tkey)//删除首个与key相等元素{returnthis.remove(this.search(key));//先查找，再调用remove(i)。//若查找不成功，返回-1，则不删除}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作查找操作Object类publicbooleanequals(Objectobj){ return(this==obj);//若两个对象引用同一个实例，返回true}Object类中equals(Object)函数比较两个是对象是否引用同一个实例。其他类继承Object类时会覆盖equals(Object)方法，例如：publicfinalclassIntegerextendsNumberimplementsComparable<Integer>{privatefinalintvalue;publicbooleanequals(Objectobj)//覆盖Object类的方法

{

if(objinstanceofInteger)returnvalue==((Integer)obj).intValue();//比较两个Integer对象的值

returnfalse;}}2.2线性表的顺序存储和实现顺序表-顺序表的基本操作查找操作考虑线性表的其他基本操作：置表为空遍历顺序表并输出求前驱求后继复制合并排序2.2线性表的顺序存储和实现顺序表-顺序表的基本操作顺序表的静态特性很好，动态特性很差，具体说明如下：①顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序，顺序表是一种随机存取结构。get()、set()方法时间复杂度是O(1)。②插入和删除操作效率很低（O(n)）。2.2线性表的顺序存储和实现小结顺序表-顺序表的基本操作顺序表的浅拷贝与深拷贝（自学）2.2线性表的顺序存储和实现顺序表-顺序表的基本操作比较相等操作习题2-5SeqList类以下声明有什么错误？为什么？publicbooleanequals(Objectobj)//比较两个顺序表是否相等，覆盖{returnthis.n==list.n&&this.element==obj.element;}注意：1.使用“==”比较两个对象时，比较的是两个对象的内存地址，所以不相等即使它们内容相等，但是不同对象的内存地址也是不相同的。2.两个线性表相等是指，它们各对应元素相等并且长度相同(使用equal()函数)。2.2线性表的顺序存储和实现顺序表-顺序表的基本操作//习题解答2-5比较相等操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作比较相等操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作//SeqList<T>类声明覆盖

publicbooleanequals(Objectobj){ if(this==obj)//引用同一个实例

returntrue;if(objinstanceofSeqList<?>)//若obj引用顺序表实例。//SeqList<?>是所有SeqList<T>的父类

{

SeqList<T>list=(SeqList<T>)obj;

if(this.n==list.n) //比较长度

{for(inti=0;i<this.n;i++)//比较所有元素

if(!(this.get(i).equals(list.get(i))))//运行时多态

returnfalse;returntrue;}}returnfalse;}比较相等操作2.2线性表的顺序存储和实现顺序表-顺序表的基本操作线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。也就是说定位操作可以直接实现。高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。2.2线性表的顺序存储和实现顺序表-顺序表的存储结构优点但是，顺序存储结构也有一些不便之处，表现在：数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间。插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需移动大量数据。这对于插入和删除操作频繁的线性表、以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高。顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。2.2线性表的顺序存储和实现顺序表-顺序表的存储结构缺点从线性表的顺序存储结构的讨论中可知，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。线性表的链式存储结构就是用若干地址分散的存储单元（可以是不连续的）存储线性表的数据元素。采用链式存储结构表示的线性表称为线性链表在链式存储结构方式下，存储数据元素的结点空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致（逻辑上相邻的数据元素在物理位置上不一定相邻！），而数据元素之间的逻辑关系由指针域（地址域）来确定。2.3线性表的链式存储和实现线性表的链式存储结构对线性表中的每一个结点，都至少需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为地址域（指针域），我们把这种存储单元称为结点。用结点来存储线性表中的每一个数据元素。2.3线性表的链式存储和实现线性表的链式存储结构-结点线性表的链式存储结构L=(a1,a2,……,an)示意图（单链表），其中(a)为非空表，(b)为空表。2.3线性表的链式存储和实现线性表的链式存储结构-带头结点链表2.3线性表的链式存储和实现线性表的链式存储结构-不带头结点（带头指针）链表下面将介绍几个线性链表（linearlinkedlist）类型的实现：单链表（singlylinkedlist）双链表（doublylinkedlist）循环链表（circularlinkedlist）2.3线性表的链式存储和实现线性表的链式存储结构-链表分类每个结点只有一个地址域的线性链表称为单链表任意存储单元（结点）存储单向链表的数据元素时，其形式如下图所示：DATANEXT其中data是数据域，存放数据元素的值；next是地址域，存放相邻的下一个结点的地址单向链表是指结点中的指针域只有一个沿着同一个方向表示的链式存储结构。因为结点是一个独立的对象，所以能够实现独立的结点类。2.3线性表的链式存储和实现单链表单链表是由多个元素（结点）组成的前驱结点和后继结点链表的存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及相关元素在内存中的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问，而只能按顺序访问2.3线性表的链式存储和实现单链表

a2180

a4170

a6NULL

a1110

a5140

a3130

150

地址

data域

next域

110

120

130

140

150

160

170

180

head

头指针

a1

a2

a3

a4

a5

a6

^

单链表的逻辑表示示意图

单链表物理存储示意图

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

publicNode<T>next;//地址域，引用后继结点

publicNode(Tdata,Node<T>next)//构造结点，data指定数据元素，next指定后继结点

{this.data=data;//T对象引用赋值

this.next=next;//Node<T>对象引用赋值

}publicNode(){this(null,null);}2.3线性表的链式存储和实现单链表-单链表的结点类实现publicStringtoString()//返回结点数据域的描述字符串

{returnthis.data.toString();}}//教材没有写，没有直接调用

publicbooleanequals(Objectobj)//比较两个结点值是否相等，覆盖Object类的equals(obj)方法

{returnobj==this||objinstanceofNode<?>&&this.data.equals(((Node<T>)obj).data);}2.3线性表的链式存储和实现单链表-单链表的结点类实现注意：Node<T>有两个成员变量，data表示结点的数据域，保存数据元素本身，数据类型是T；next表示结点的地址域，保存后继结点的地址Node类中成员变量next的数据类型是Node<T>类自己，Node类是“自引用的类”自引用的类(Self-referentialClass)是指一个类声明包含引用当前类实例的成员变量2.3线性表的链式存储和实现单链表-单链表的结点类实现注意：一个Node<T>类的实例只表示链表中的一个结点，如何将两个结点链接起来？成员变量设计为共有，合适否？其他方法需要否，比如直接访问（读或写）数据域及引用域？单链表的头指针如何设定？2.3线性表的链式存储和实现单链表-单链表的结点类实现一个Node<T>类的实例只表示链表中的一个结点，如何将两个结点链接起来？通过next域将两个结点链接起来语句如下：Node<String>p,q;p=newNode<String>("A",null);q=newNode<String>("B",null);p.next=q;所以若干结点通过next链指定相互之间的顺序关系，形成一条单链表2.3线性表的链式存储和实现单链表-单链表的结点类实现成员变量设计为公有，合适否？便于访问（更改结点间的链接关系）根据封装性，应该设置为private或protected2.3线性表的链式存储和实现单链表-单链表的结点类实现其他方法需要否，比如直接访问（读或写）数据域及引用域？如果将Node类的data和next封装成私有成员，则必须提供一组公有的getData()、getNext()、setData()、setNext()等方法2.3线性表的链式存储和实现单链表-单链表的结点类实现单链表的头指针如何设定？单链表的头指针head也是一个结点引用，声明如下： Node<T>head=null;当head==null时，表示空单链表2.3线性表的链式存储和实现单链表-单链表的结点类实现对于单链表来说，整个链表的存取必须是从头指针开始，头指针指示链表中第0个（起始）结点的存储位置。同时由于最后一个数据元素，没有直接后继，则线性链表中最后一个结点的指针为“空”（null）。2.3线性表的链式存储和实现单链表-单链表的实现开始时单链表为空表建立单链表时依次在链表尾部插入一个新建的结点考虑：如何实现关键的尾部插入？插入的第一个结点是否单独处理？结论：需要使用new创建Node类型的对象，并依次链入链表的尾部，注意参数的值是什么需要对第一个结点单独处理插入结点作为链表结点的初始化来看待，所以利用构造函数实现建立单链表2.3线性表的链式存储和实现单链表-单链表的实现设rear指向原链表的最后一个结点，q指向新创建的结点，则将q结点链在rear结点之后的语句是：

rear.next=q；

rear=q；需要考虑开始为空的特殊情况建立单链表2.3线性表的链式存储和实现单链表-单链表的实现其他需要考虑的问题：rear可否作为SingLinkedList类的保护成员存在假设插入的元素为随机数建立单链表2.3线性表的链式存储和实现单链表-单链表的实现实现过程：产生随机数新建以随机数为元素的结点，并把新结点链入到第一个位置修改rear产生随机数新建以随机数为元素的结点q把q放到结点的尾部修改rear循环4～7步建立单链表2.3线性表的链式存储和实现单链表-单链表的实现遍历单链表是指从第0个结点开始，沿着结点的next链，依次访问单链表中的每个结点，并且每个结点只访问一次。单链表的遍历操作2.3线性表的链式存储和实现单链表-单链表的实现遍历单链表操作不能改变头指针head，因此需要声明一个变量p指向当前访问结点p从head指向的结点（第0个—引用结点）开始访问，再沿着next链到达后继结点，逐个访问，直到最后一个结点，完成一次遍历单链表的遍历操作2.3线性表的链式存储和实现单链表-单链表的实现单链表的遍历操作Node<T>p=head;while(p!=null){p.data.toString()//执行访问p结点的相关操作p=p.next;}单链表的遍历操作2.3线性表的链式存储和实现单链表-单链表的实现如果语句p=p.next写成p.next=p？p.next=p;使p.next指向p结点自己，改变了结点间的链接关系。遍历算法死循环。单链表的遍历操作（思考）2.3线性表的链式存储和实现单链表-单链表的实现在单链表中插入新的结点，根据插入位置的不同，分四种情况：空表插入头插入尾插入中间插入关键：插入结点时，只要改变结点间的链接关系，不需要移动数据元素。插入结点2.3线性表的链式存储和实现单链表-单链表的实现插入结点2.3线性表的链式存储和实现单链表-单链表的实现假定链表为空（head==null），插入一个结点，链表只有一个结点语句如下：

head=newNode<T>(x,null)；空表插入2.3线性表的链式存储和实现单链表-单链表的实现haveyournamehead头插入结点2.3线性表的链式存储和实现单链表-单链表的实现haveyournameheadq头插入结点2.3线性表的链式存储和实现单链表-单链表的实现haveyournamemayheadq头插入结点2.3线性表的链式存储和实现单链表-单链表的实现haveyournamemayheadq头插入结点2.3线性表的链式存储和实现单链表-单链表的实现haveyournamemayheadq头插入结点2.3线性表的链式存储和实现单链表-单链表的实现过程：构造一个新的Node对象p在新对象中加入需要的值x让其指针域指向列表中的第一个元素head指向新对象p头插入结点2.3线性表的链式存储和实现单链表-单链表的实现若单链表非空（head!=null），则在head结点之前插入值为x的结点的关键语句如下：Node<T>p=newNode<T>(x,null)；p.next=head；head=p；考虑：空表插入和头插入有何相似之处？结论：空表插入和头插入的合并结果head=newNode<T>(x,head);头插入结点2.3线性表的链式存储和实现单链表-单链表的实现链表不为空的情况：lifeonmoon^head尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^phead尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^phead尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^phead尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^pyes^headq尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoonpyes^qhead尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现考虑：如果链表为空，如何操作？可否增设一个尾结点（rear）？尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现实现过程：到达链表尾部构造一个新的Node对象p在新对象中加入需要的值让最后一个结点的指针域指向新对象p尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现关键语句如下：Node<T>p=newNode<T>(x,null)；front.next=p；尾插入结点2.3线性表的链式存储和实现单链表-单链表的实现若将x插入a和b之间，插入结点的指针变化如图所示

①

②

q

a

b

x

p

´

插入结点时的指针修改

中间插入结点2.3线性表的链式存储和实现单链表-单链表的实现基于上图，关键语句如下：Node<T>p=newNode<T>(x,null)；p.next=front.next;front.next=p；

中间插入结点2.3线性表的链式存储和实现单链表-单链表的实现考虑：单链表的插入是否需要移到大量元素对于单链表很方便访问结点的后继结点对于单链表访问结点的前驱结点很不方便，如何实现中间插入结点2.3线性表的链式存储和实现单链表-单链表的实现考虑：中间插入和尾插入有何相似之处？结论：中间插入和尾插入的合并实现设front指向单链表中的某个结点，在front结点后插入值为x结点的语句如下：

Node<T>p=newNode<T>(x,null);p.next=front.next;//p的后继是front的后继front.next=p;//p作为front的后继即:front.next=newNode<T>(x,front.next);中间插入结点2.3线性表的链式存储和实现单链表-单链表的实现【思考】图（c）中，如果①②两句次序颠倒，将会怎样？

Node<T>p=newNode<T>(x,null);front.next=p;//②p.next=front.next;//①

会出现错误，丢失后续链表中间插入结点2.3线性表的链式存储和实现单链表-单链表的实现在单链表中删除已有的结点，根据删除位置的不同，分四种情况：只有一个结点的链表删除头部删除中间删除尾部删除关键：删除单链表中的指定结点，通过改变结点的next域，就可以改变结点间的链接关系，不需要移动元素。Java的资源回收机制将自动释放不再使用的对象，收回其占用的资源。删除结点2.3线性表的链式存储和实现单链表-单链表的实现删除结点2.3线性表的链式存储和实现单链表-单链表的实现删除结点2.3线性表的链式存储和实现单链表-单链表的实现删除单结点链表，只要使链表的引用head为空即可： head=null;删除结点（单结点链表）2.3线性表的链式存储和实现单链表-单链表的实现haveyournamehead头删除2.3线性表的链式存储和实现单链表-单链表的实现haveyournametemphead头删除2.3线性表的链式存储和实现单链表-单链表的实现haveyournametemphead头删除2.3线性表的链式存储和实现单链表-单链表的实现操作过程：将第一个元素复制到一个临时变量中将head指向第二个元素返回原有的第一个元素的值头删除2.3线性表的链式存储和实现单链表-单链表的实现删除单链表head指向的结点，使head引用其后继结点，关键语句如下：head=head.next;考虑：一个结点的删除和头删除有何相似之处？结论：一个结点的删除和头删除的合并

head=head.next;头删除2.3线性表的链式存储和实现单链表-单链表的实现列表不为空的情况：lifeonmoon^head尾删除2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^fingerprevioshead尾删除2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^fingerprevioshead尾删除2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^fingerprevioshead尾删除2.3线性表的链式存储和实现单链表-单链表的实现lifeonmoon^fingerprevios^head尾删除2.3线性表的链式存储和实现单链表-单链表的实现自己考虑如何实现？尾删除2.3线性表的链式存储和实现单链表-单链表的实现表尾操作都是先从头找到表尾，然后开始操作，这种技术称为链表遍历技术。需要注意链表为空这种特殊情况，否则程序出错。编程需要考虑边界条件，软件需要健壮性和正确性。尾删除2.3线性表的链式存储和实现单链表-单链表的实现若将x删除，删除结点的指针变化如图所示