第02章线性表(Java版)

第2章线性表2.1线性表抽象数据类型2.2线性表的顺序存储和实现2.3线性表的链式表示和实现2.4线性表的应用：多项式的表示及运算目的：实现线性表抽象数据类型。要求：掌握顺序、链式两种存储结构实现线性表。重点：顺序表，单链表，循环双链表。难点：使用“对象引用”方式实现链式存储结构。实验：掌握MyEclipse环境的程序调试技术。2.1线性表抽象数据类型2.2线性表的顺序存储和实现2.3线性表的链式表示和实现2.4线性表的应用：多项式的表示及运算目的：实现线性表抽象数据类型。要求：掌握顺序、链式两种存储结构实现线性表。重点：顺序表，单链表，循环双链表。难点：使用“对象引用”方式实现链式存储结构。实验：掌握MyEclipse环境的程序调试技术。2.1线性表抽象数据类型线性表（LinearList）(a0，a1，…，an-1)是由n（≥0）个类型相同的数据元素组成的有限序列，其中，元素类型可以是基本类型或类；n是线性表长度（Length），即元素个数。若n=0，空表；若n>0，（0<i<n-1）有且仅有一个前驱元素和一个后继元素，a0没有前驱元素，an-1没有后继元素。ADTList<T>//线性表抽象数据类型，数据元素的数据类型为T{booleanisEmpty()//判断线性表是否为空intsize()//返回线性表长度

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

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

intinsert(inti,Tx)//插入x作为第i个元素

intinsert(Tx)//在线性表最后插入x元素ADTList<T>

Tremove(inti)//删除第i个元素

voidclear()//删除所有元素

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

booleanequals(Objectobj)//比较是否相等voidaddAll(List<T>list)//添加list所有元素}2.2线性表的顺序存储和实现2.2.1线性表的顺序存储结构2.2.2顺序表2.2.3排序顺序表习图2.1线性表的存储结构

2.2.1线性表的顺序存储结构数组数组是实现顺序存储结构的基础。数组（Array）存储具有相同数据类型的元素集合。一维数组占用一块内存空间，每个存储单元的地址是连续的，计算第i个元素地址所需时间复杂度是一个常量，与元素序号i无关。存取任何一个元素的时间复杂度是O(1)的数据结构称为随机存取结构。因此，数组是随机存取结构。2.顺序表（SequentialList）采用一维数组存储数据元素，数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。顺序表是随机存取结构。顺序表类声明、存取操作及效率分析顺序表插入操作顺序表删除操作顺序表查找操作顺序表的浅拷贝与深拷贝顺序表比较相等2.2.2顺序表publicclassSeqList<T>//顺序表类，泛型类{protectedObject[]element;//对象数组

protectedintn;//元素个数（长度）

publicSeqList(intlength)//构造空表publicSeqList()//构造方法重载

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

}publicSeqList(T[]values)//由values数组提供元素publicbooleanisEmpty()//判断顺序表是否空publicintsize()//返回元素个数}顺序表类SeqList<T>

SeqList<T>类设计说明泛型类隐藏成员变量构造方法析构方法对象引用赋值存取操作，当指定元素序号不正确时的处理原则遍历输出及运行时多态操作的效率分析（1）泛型类与创建实例Stringvalues[]={"A","B","C","D","E"};SeqList<String>lista=newSeqList<String>(values); //lista引用顺序表实例，元素是String对象【例2.1】求解约瑟夫环问题。（5）存取操作，当指定元素序号不正确时的处理原则publicTget(inti)//返回第i个元素，0≤i<n。若i越界，返回nullpublicvoidset(inti,Tx)//设置第i个元素为x，0≤i<n。若i越界，抛出序号越界异常；若x==null，抛出空对象异常list.get(-1).toString()//get()方法返回null时抛出空对象异常（6）遍历输出及运行时多态//返回顺序表所有元素的描述字符串，形式为“(,)”。//覆盖Object类的toString()方法publicStringtoString(){Stringstr=this.getClass().getName()+"(";//返回类名

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

returnstr+")"; //空表返回()}（7）操作的效率分析isEmpty()、size()、get(i)、set(i,x)方法，时间复杂度为O(1)。toString()方法需要遍历顺序表，时间复杂度为O(n)。【思考题2-1】publicObjectget(inti){returnthis.element[i];//习题解答}SeqList<Integer>list=newSeqList<Integer>(n);Objectobj=list.get(0);//引用子类实例obj.toString()//调用Object方法Value()//编译错，//obj不能调用Integer类的成员方法((T)obj).intValue()//(T)obj是Integer类的对象【思考题2-1】publicTget(inti){return(T)this.element[i];}SeqList<Integer>list=newSeqList<Integer>(n);Integeriobj=list.get(0);//iobj引用本类实例iobj.toString()Value()//iobj能够调用Integer类的成员方法2.顺序表插入操作intinsert(inti,Tx)//插入x作为第i个元素intinsert(Tx)//尾插入x元素。重载2.顺序表插入操作若数组满，则扩充顺序表的数组容量3.顺序表删除操作Tremove(inti)//返回删除第i（0≤i<n）个元素voidclear()//删除线性表所有元素【例2.1】求解约瑟夫环问题。（1）泛型类与创建实例MyEclipse开发环境，配置编译路径（BuildPath），引用其他项目中的类。

【例2.1】采用单链表求解约瑟夫环问题。（1）顺序查找算法

//顺序查找首次出现的与key相等元素，返回元素序号i；查找不成功返回-1。publicintsearch(Tkey){for(inti=0;i<this.n;i++)if(key.equals(this.element[i]))//执行T类的equals(Object)，运行时多态

returni;return-1; //空表或未找到时}【思考题2】若if(this.element[i].equals(key))，查找结果会怎样？为什么？4.顺序表查找操作【答】执行Object类的equals(Object)（2）比较对象相等的方法Object类publicboolean

equals(Object

obj){return(this==obj);//若两个对象引用同一个实例，返回true}publicfinalclassIntegerextendsNumberimplementsComparable<Integer>{privatefinalintvalue;publicboolean

equals(Object

obj)//覆盖Object类的方法

{

if(obj

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

returnfalse;}}【思考题2-2】基于查找算法的操作booleancontains(Tkey)//包含{returnthis.search(key)!=-1;}//插入不重复元素。查找不成功时，尾插入intinsertDifferent(Tx){returnthis.search(x)==-1?this.insert(x):-1;}Tremove(Tkey)//删除首个与key相等元素{returnthis.remove(this.search(key));

//先查找，再调用remove(i)。若查找不成功，返回-1，不删除}3.多态原则，子类覆盖父类成员方法顺序表的静态特性很好，动态特性很差，具体说明如下。①顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序，顺序表是一种随机存取结构。get()、set()方法时间复杂度是O(1)。②插入和删除操作效率很低。如果在各位置插入元素的概率相同，则有顺序表小结5.顺序表的浅拷贝与深拷贝类的拷贝构造方法声明格式如下，方法名同类名，参数为本类对象。没有默认。类(类对象)//拷贝构造方法

{this.成员变量=参数对象.成员变量; //逐域赋值，以参数的实例值初始化当前实例}（1）顺序表的浅拷贝publicSeqList(SeqList<T>list)//浅拷贝构造方法{

this.n=list.n;//int整数赋值，复制了整数值

this.element=list.element;//数组引用赋值，两个变量共用一个数组，错误}图2.6顺序表的浅拷贝及其错误SeqList<String>listb=newSeqList<String>(lista);lista.remove(0);（2）顺序表的深拷贝复制数组（2）顺序表的深拷贝复制数组，复制对象6.顺序表比较相等习题2-5SeqList类以下声明有什么错误？为什么？publicboolean

equals(Object

obj)//比较两个顺序表是否相等，覆盖{returnthis.n==list.n

&&this.element==obj.element;}两个线性表相等是指，它们各对应元素相等并且长度相同。比较两个顺序表对象是否相等//习题解答2-5比较两个顺序表对象是否相等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.3排序顺序表子类继承原则子类不能继承父类的构造函数多态原则，子类覆盖父类成员方法比较对象大小的方法类型的多态，子类对象即是父类对象排序顺序表排序线性表是指，各数据元素按照关键字值递增或递减排列。排序线性表是一种特殊的线性表。

//排序顺序表类（升序），T或T的某个祖先类实现Comparable<T>接口，比较对象大小publicclass

SortedSeqList<TextendsComparable<?superT>> extendsSeqList<T>1.子类继承原则子类重定义父类成员包括：重定义父类的成员变量，则隐藏父类的成员变量；重定义父类的成员方法，如果参数列表相同，则覆盖（Override）父类的成员方法，返回值类型必须与父类方法赋值相容；如果参数列表不同，则重载（Overload）父类的成员方法。子类使用“super引用”，语法格式如下：super.成员变量

//当子类隐藏父类成员变量时， //引用父类同名成员变量super.成员方法([参数列表])//当子类覆盖父类成员方法时， //调用父类同名成员方法2.子类不能继承父类的构造方法publicSortedSeqList()//构造空表{super();//默认调用SeqList()}publicSortedSeqList(intlength)//构造空表，容量为length{super(length);//调用SeqList(length)

//若省略，默认调用super()}publicSortedSeqList(T[]values)//构造，由数组提供元素，{super(values.length);for(inti=0;i<values.length;i++)this.insert(values[i]);//插入元素}3.多态原则，

子类覆盖父类成员方法（1）排序顺序表的插入操作//插入x，x!=null，根据x大小确定插入位置，返回x序号。调用T的compareTo()方法比较对象大小。覆盖父类insert(Tx)，参数列表和返回值相同publicintinsert(Tx)//插入不重复元素。查找不成功时，插入。覆盖publicintinsertDifferent(Tx)【思考题2-2】顺序表基于查找算法的操作子类不能删除父类成员//不支持父类方法，覆盖并抛出异常publicvoidset(inti,Tx)//元素只读{thrownewUnsupportedOperationException("set(inti,Tx)");}publicintinsert(inti,Tx)//任意位置插入（2）编译时多态与运行时多态【例2.3】顺序表与排序顺序表的插入操作。Integer[]values={70,20,80,30,60};SeqList<Integer>list1=newSeqList<Integer>(values);SortedSeqList<Integer>slist1=newSortedSeqList<Integer>(list1);//由顺序表构造排序顺序表list1.insert(0,10);//调用insert(i,x)方法，顺序表插入list1.insert(50);//父类对象调用父类方法，顺序表尾插入slist1.insert(50);//子类对象调用子类方法，

//排序顺序表按值插入，覆盖slist1.insert(0,90);//排序顺序表插入，抛出异常（3）排序顺序表查找操作//顺序查找首次出现的与key相等元素，返回元素序号i。覆盖publicintsearch(Tkey){for(inti=start;i<this.n&&pareTo(this.get(i))>=0;i++)if(pareTo(this.get(i))==0)//对象相等，运行时多态

returni;return-1;//空表或未找到时}（3）排序顺序表删除操作publicTremove(Tkey)//继承

{returnthis.remove(this.search(key));//先查找，再调用remove(i)。若查找不成功，返回-1，则不删除

//其中this.search(key)运行时多态，子类对象调用子类的查找方法}【实验2-2】SortedSeqList<T>类声明成员方法//插入关键字不重复元素，返回插入位置。使用顺序查找算法按值比较，寻找插入位置。//不能调用search(Tkey)方法，因为查找不成功其返回-1，不能确定插入位置。publicintinsertDifferent(Tx)4.比较对象大小的方法publicinterfaceComparable<T>//可比较接口{intcompareTo(Tobj)//比较对象大小，//返回0、正、负整数，分别表示相等、大、小}publicfinalclassIntegerimplementsComparable<Integer>

{publicintcompareTo(Integeriobj)}publicfinalclassStringimplementsComparable<String>{publicintcompareTo(Strings)}5.类型的多态，

子类对象即是父类对象子类对象即是父类对象，赋值相容SeqList<Integer>list=newSortedSeqList<Integer>(value); //父类对象list引用子类实例list.insert(50);//运行时根据list引用实例的类型，确定执行父类或子类方法，排序顺序表插入//子类对象即是父类对象，反之则不然。SortedSeqList<Integer>slist=newSeqList<Integer>(value);//编译错方法参数和返回值的传递原则也是赋值相容SeqList<Integer>list2=newSeqList<Integer>(slist1);//顺序表深拷贝，由排序顺序表slist1构造顺序表publicbooleanequals(Objectobj)//继承{if(objinstanceofSeqList<?>)//若obj引用SortedSeqList<T>实例……}（2）重载拷贝构造方法publicSortedSeqList(SeqList<?extendsT>list) //由顺序表构造排序顺序表，O(n2){super(); //默认调用SeqList()for(inti=0;i<list.n;i++)this.insert(list.get(i));//调用子类方法，按值插入，O(n)}publicSortedSeqList(SortedSeqList<?extendsT>list) //排序顺序表的拷贝构造方法，深拷贝，O(n){super(list); //调用SeqList(SeqList<T>)，//list引用子类实例，参数类型赋值相容}图2.8由顺序表list构造排序顺序表this，共用list的对象SortedSeqList(SeqList<?extendsT>list)【例2.4】对象信息的分类统计、查找和排序操作。目的：①声明类作为泛型参数T的实际参数，比较对象相等及大小。②分别使用顺序表、排序顺序表存储对象序列，按姓名查找，按成绩排序。③在顺序表类之外定义对顺序表进行特定操作的函数，顺序表作为函数参数。（1）Student类publicclassStudentextendsObjectimplementsComparable<Student> //学生类（2）对象信息的分类统计、查找、删除、排序等操作//分类统计线性表list的元素信息，分段信息存于grade数组，返回保存统计结果的数组int[]groupCount(SeqList<Student>list,intgrade[])voidprintCount(SeqList<Student>list,Stringtitles[],intresult[])//输出【例2.5】使用线性表表示集合，实现集合运算。目的：①线性表表示集合的特性，以集合并为例实现集合运算；②泛型的继承性。（1）（排序）线性表表示集合的特性顺序表表示可重复的无序集合。因为元素间具有线性次序，所以，可以采用序号识别关键字重复的数据元素。排序顺序表表示可重复的排序集合，元素按关键字大小排序。集合并SeqList<T>类声明，SortedSeqList<T>类继承。publicvoidaddAll(SeqList<?extendsT>list) //在this之后添加list的所有元素，集合并{for(inti=0;i<list.n;i++)this.insert(list.get(i));//运行时多态，顺序表尾插入；排序顺序表按值插入}（2）泛型的继承性泛型声明[修饰符]class类<类型参数列表>[extends父类][implements接口列表][public]interface接口<类型参数列表>[extends父接口列表][public][static]<类型参数列表>

返回值类型方法([参数列表])[throws异常类列表]<类型参数列表>：类型变量

[extends

父类型列表]通配符“?”称为通配符，表示通配类型。用法：?extendsT//?表示T及其任意一种子类型，T称为?的上界?superT//?表示T及其任意一种父类型，T称为?的下界SeqList<?>（即<?extendsObject>）是所有SeqList<T>的父类型。SeqList<T>类声明覆盖publicbooleanequals(Objectobj)TextendsComparable<T>publicclassPerson

implementsComparable<Person>{publicintcompareTo(Person)}

//符合上述语法publicclassStudentextendsPerson[implementsComparable<Person>]{publicintcompareTo(Person)}//不符合上述语法TextendsComparable<T>publicclassStudent

implementsComparable<Student>{publicintcompareTo(Student)}//符合TextendsComparable<T>语法publicclassStudentextendsPersonimplementsComparable<Student>[，Comparable<Person>]//语法错TextendsComparable<?superT>publicclassPerson

implementsComparable<Person>{publicintcompareTo(Person)}

//符合publicclassStudentextendsPerson[implementsComparable<Person>]{publicintcompareTo(Person)}//符合2.2.3排序顺序表图2.9SeqList<T>类与子类SortedSeqList<T>

成员方法的关系【思考题2-4】SeqList<T>类声明以下方法，子类SortedSeqList<T>是否可用？为什么？//返回将this与list所有元素合并连接的顺序表SeqList<T>

union(SeqList<?extendsT>list)习题解答{SeqList<T>result=newSeqList<T>(this);

//深拷贝this，无法创建子类实例result.addAll(list);//顺序表合并连接，尾插入

returnresult;//只能返回SeqList<T>对象}//子类不可用SeqList<T>addAll(SeqList<?extendsT>list)

//语法错，参数列表相同时不能重载SortedSeqList<T>类声明覆盖union(list)方法SortedSeqList<T>union(SeqList<?extendsT>list)

//覆盖，值类型不同但赋值相容。与父类实例运算{SortedSeqList<T>result=new SortedSeqList<T>(this);//创建子类实例，深拷贝

result.addAll(list);//继承父类方法，运行时多态，//排序顺序表合并，按值插入returnresult;//返回SortedSeqList<T>对象}实验题2-2

元素互异的（排序）顺序表类publicclassDifferentSeqList<T>extendsSeqList<T> //互异顺序表类publicclassDifferentSortedSeqList<TextendsComparable<?superT>>

extendsSortedSeqList<T> //互异排序顺序表类（升序）2.3线性表的链式表示和实现2.3.1线性表的链式存储结构2.3.2单链表2.3.3双链表第2章线性表2.3.2单链表单链表结点类2.单链表的基本操作3.带头结点的单链表4.单链表操作的效率分析5.单链表的浅拷贝与深拷贝6.排序单链表7.循环单链表publicclassNode<T>//单链表结点类{publicTdata;//数据域，保存数据元素

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

publicNode(Tdata,Node<T>next)//构造结点publicNode()publicStringtoString()}//继承析构方法，不需要拷贝构造方法。习题解答实验2.1Node<String>p,q;p=newNode<String>("A",null);q=newNode<String>("B",null);p.next=q;1.单链表结点类习题2-6写出以下数据结构的声明。习题解答Node<T>table[]; //一维数组，元素为结点SinglyList<T>table[]; //一维数组，元素为单链表SeqList<Node<T>>table;//顺序表，元素为结点SeqList<SinglyList<T>>table;//顺序表，元素为单链表

2.单链表的基本操作（1）单链表的遍历操作Node<T>p=head;while(p!=null){p.data.toString()//执行访问p结点的相关操作p=p.next;}【思考题2-5】如果语句p=p.next写成p.next=pp.next=p;使p.next指向p结点自己，改变了结点间的链接关系。遍历算法死循环。习题解答（2）单链表的插入操作空表插入/头插入if(head==null)

//空表插入head=newNode<T>(x,null);else //头插入{Node<T>p=newNode<T>(x,null);

p.next=head;head=p;}即head=newNode<T>(x,head);②中间插入/尾插入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-6】图2.11（b）、（c）中，如果①②两句次序颠倒，将会怎样？

Node<T>p=newNode<T>(x,null);front.next=p;//①p.next=front.next;//②习题解答（3）单链表的删除操作头删除head=head.next;中间/尾删除if(front.next!=null)

front.next=front.next.next;3.带头结点的单链表头结点的作用是，使所有链表（包括空表）的头指针非空，则对单链表的插入、删除操作不需要区分操作位置。3.带头结点的单链表头插入和头删除操作不会改变head指针。单链表类publicclassSinglyList<T>{publicNode<T>head;//头指针publicSinglyList()//构造空表publicSinglyList(T[]values)

publicbooleanisEmpty()publicTget(inti)//返回第i个元素

publicvoidset(inti,Tx)//设置第i个元素为x

publicintsize()//长度publicStringtoString()单链表类SinglyList<T>

publicNode<T>insert(inti,Tx)//插入x作为第i个元素publicNode<T>insert(Tx)//尾插入publicTremove(inti)//删除第i个元素publicvoidclear()//删除所有元素}【思考题2-7】①单链表成员方法voidset(inti,Tx)//设置第i个元素为xintsize()//长度Node<T>search(Tkey)//查找booleancontains(Tkey)//包含Node<T>insertDifferent(Tx)//插入不重复元素，查找不成功时尾插入Tremove(Tkey)//删除【思考题2-7】②基于查找操作SinglyList<T>类的insertDifferent(x)和remove(key)方法能否调用search(key)方法确定操作位置？为什么？都不能。因为单链表的插入和删除需要修改前驱结点的next域，而search(key)方法返回key结点，无法操作。insertDifferent(x)方法要求查找不成功时，尾插入。而search(key)方法查找不成功时返回null，失去操作位置信息。【思考题2-7】③使用单链表例2.1，采用单链表求解约瑟夫环问题。

SinglyList<String>list=newSinglyList<String>();例2.4，分类统计学生成绩。

int[]groupCount(SinglyList<Student>list,

intgrade[])分析各操作效率。修改对顺序表操作的方法，使其对单链表操作的效率最佳。【思考题2-7】③

【例2.1】采用单链表求解Josephus问题。【例2.1】求解约瑟夫环问题。newJosephus(5,0,3)4.单链表操作的效率分析isEmpty()方法的时间复杂度是O(1)。size()、toString()等，遍历单链表，O(n)。get(i)和set(i)，遍历部分单链表，O(n)，不是随机存取结构。insert(i,x)和remove(i)，查找i，O(n)。在front结点之后插入、删除图2.13在p结点之前插入q结点，要寻找p的前驱结点front图2.13删除p结点，要寻找p的前驱结点front

（4）提高单链表操作效率的措施插入操作对序号容错Node<T>insert(Tx) //尾插入{returninsert(this.size(),x); //需两次遍历单链表，效率较低}returninsert(Integer.MAX_VALUE,x);//遍历一次，必须容错i超长②单链表不能调用get(i)方法遍历。//返回数值线性表的平均值doubleaverage(SinglyList<Integer>list){intsum=0;for(inti=0;i<list.size();i++)//size()的O(n)sum+=list.get(i).intValue();//get(i)的O(n)return(double)sum/list.size();//实数除，存在除数为0错误}//顺序表，O(n)；单链表，O(n2)③增加属性成员变量n表示单链表长度，插入，n++；删除，n--，则size()时间为O(1)。成员变量rear作为单链表的尾指针，则尾插入的时间是O(1)。【例2.6】单链表逆转。publicstatic<T>voidreverse(SinglyList<T>list)reverse(SinglyList<T>list)publicstatic<T>voidreverse(SinglyList<T>list){Node<T>p=list.head.next,succ=null,front=null;//head必须声明为publicwhile(p!=null){succ=p.next;//设置succ是p结点的后继结点

p.next=front; //使p.next指向p结点的前驱结点

front=p;p=succ;//p向后走一步

}list.head.next=front;}构造反序单链表//头插入，单链表元素次序与数组元素次序相反<T>SinglyList<T>createReverse(T[]values){SinglyList<T>list=newSinglyList<T>();

for(inti=0;i<values.length;i++)list.head.next=newNode<T>(values[i],list.head.next); //头插入

returnlist;//返回单链表对象引用}5.单链表的浅拷贝与深拷贝SinglyList(SinglyList<T>list)//浅拷贝{this.head=list.head;//对象引用赋值//导致两个引用变量指向同一个结点}单链表的深拷贝SinglyList(SinglyList<T>list)//深拷贝{this();//创建空单链表，只有头结点

Node<T>rear=this.head;for(Node<T>p=list.head.next;p!=null;p=p.next)

{rear.next=newNode<T>(p.data,null);rear=rear.next;//指向this单链表尾

}}单链表的深度拷贝，复制对象【思考题2-8】②单链表比较相等两条单链表相等是指，它们各对应元素相等并且长度相同。publicbooleanequals(Objectobj)//覆盖【习题解答例2.1】集合并运算，单链表深拷贝的应用。理解单链表的深拷贝。理解对象引用参数。//在this单链表之后连接list单链表，集合并voidconcat(SinglyList<T>list)合并连接单链表//在this单链表之后连接list单链表；设置list为空；集合并publicvoidconcat(SinglyList<T>list){Node<T>rear=this.head;while(rear.next!=null)

rear=rear.next;rear.next=list.head.next;

list.head.next=null;}单链表深拷贝//复制list单链表中所有结点插入到this单链表之后publicvoidaddAll(SinglyList<T>list){this.concat(newSinglyList<T>(list)); //先执行单链表深拷贝，再连接复制的list}返回并集//返回复制this和list合并连接的单链表，并集，//不改变this和listpublicSinglyList<T>union(SinglyList<T>list){SinglyList<T>result=newSinglyList<T>(this);

result.addAll(list);returnresult;}返回并集publicSinglyList<T>union(SinglyList<T>list)6.排序单链表图2.16构造排序单链表（升序）排序单链表类（升序），

继承单链表类publicclassSortedSinglyList<TextendsComparable<?superT>>extendsSinglyList<T>//T或T的某个祖先类实现Comparable<T>接口{SortedSinglyList()//构造空表SortedSinglyList(T[]values)//构造，按值插入SortedSinglyList(SortedSinglyList<T>list)//深拷贝SortedSinglyList(SinglyList<T>list)//重载深拷贝，由单链表构造SortedSinglyList<T>voidset(inti,Tx)//不支持父类方法，覆盖并抛出异常

Node<T>insert(inti,Tx)//不支持父类方法，覆盖

Node<T>insert(Tx)//插入x，按值比较，覆盖

//【思考题2-9】

Node<T>search(Tkey)//查找，覆盖

Node<T>insertDifferent(Tx)//插入不重复元素，覆盖

Tremove(Tkey)//删除key元素，覆盖voidaddAll(SinglyList<T>list)//将list中所有元素插入 到this单链表，不改变list，集合并。覆盖}insertDifferent(Tx)//插入不重复元素，返回插入结点；覆盖publicNode<T>insertDifferent(Tx){Node<T>front=this.head,p=front.next;

while(p!=null&&pareTo(p.data)>0)

{front=p;p=p.next;}if(p!=null&&pareTo(p.data)==0)returnnull;

front.next=newNode<T>(x,p);

returnfront.next;}7.循环单链表head.next=head;rear.next=head;publicclassCirSinglyList<T>{publicNode<T>head;//头指针

publicCirSinglyList()//构造空表

{this.head=newNode<T>();//创建头结点

this.head.next=this.head;//构成环形}publicbooleanisEmpty()//判空

{returnthis.head.next==this.head;}publicStringtoString()

{//遍历，循环条件改变了for(Node<T>p=this.head.next;p!=this.head;p=p.next)}}【思考题2-10】能否使用以下语句创建循环单链表的头结点？为什么？publicCirSinglyList()//构造空表{

head=newNode<T>(null,head);}习题解答【答】不能。因为申请结点存储空间时head没有初始化，实际语义需要的是将该结点地址作为其next域值，做不到。2.3.3双链表双链表结点类2.双链表的特性和操作3.循环双链表4.排序循环双链表1.双链表结点类publicclassDoubleNode<T>{publicTdata;

publicDoubleNode<T>prev,next;//前驱，后继

publicDoubleNode(Tdata,DoubleNode<T>prev, DoubleNode<T>next)//构造方法重载

publicDoubleNode(Tdata)publicDoubleNode()publicStringtoString()}//继承析构方法，不需要拷贝构造方法。习题2-11DoubleNode类不能声明如下，继承单链表结点类。publicclassDoubleNode<T>extendsNode<T> {DoubleNode<T>prev;//前驱结点//Node<T>next;//数据类型错误}//习题解答2.双链表的特性和操作双链表结构和特性空双链表，只有头结点。head.next==null且head.prev==null非空双链表，设p指向双链表中非两端的某个结点，有：

p=p.next.prev=p.prev.next（2）双链表的插入操作//在p结点之前插入q=newDoubleNode<T>(x);q.prev=p.prev;q.next=p;①p.prev.next=q;//因有p.prev!=NULL②p.prev=q;//【思考题2-11】两句次序颠倒，将会怎样？【思考题2-11】在p结点之后插入q=newDoubleNode<T>(x);q.prev=p;q.next=p.next;if(p.next!=NULL)//中间插入p.next.prev=q;p.next=q;//与上句次序颠倒，将会怎样？习题解答（3）双链表的删除操作p.prev.next=p.next;//有p.prev!=nullif(p.next!=null)

//中间删除p.next.prev=p.prev;3.循环双链表空循环双链表有head.next==head且head.prev==head循环双链表类CirDoublyListpublicclassCirDoublyList<T>//循环双链表类{DoubleNode<T>head;//头指针

CirDoublyList()//构造空表

booleanisEmpty()//判空

DoubleNode<T>insert(inti,Tx)//插入x为第i个元素

DoubleNode<T>insert(Tx)//尾插入x

//实现以下方法

StringtoPreviousString()//反序输出

TremoveLast()//删除最后一个元素}插入x为第i个元素

publicDoubleNode<T>insert(inti,Tx)

尾插入x元素，O(1)//尾插入x元素，返回x结点。在头结点之前插入publicDoubleNode<T>insert(Tx)习题2-13循环双链表类能否声明如下，继承单链表类，继承了head成员变量？为什么？classCirDoublyList<T>extendsSinglyList<T>实现循环双链表类的size()等其他成员函数。习题解答【答】不能。等价于以下：{Node<T>head;//继承基类的成员变量，//数据类型错误，应该是DoubleNode<T>};删除元素Tremove(inti)//删除第i个元素TremoveLast()//删除最后一个元素{DoubleNode<T>p=this.head.prev;//p指向头结点的前驱结点

if(p!=head){p.prev.next=this.head;//删除p结点，由JVM稍后释放

this.head.prev=p.prev;returnp.data;//返回p结点元素

}returnnull;//当i<0或i>表长时}习题解答【习2.3】

循环双链表合并连接publicvoidconcat(CirDoublyList<T>list)4.排序循环双链表图2.22构造排序循环双链表（升序）排序循环双链表类（升序），

继承循环双链表类publicclassSortedCirDoublyList<TextendsComparable<?superT>>extendsCirDoublyList<T>//T或T的某个祖先类实现Comparable<T>接口{//插入x，x!=null，根据x对象大小顺序查找确定插入位置，插入在等值结点之前。

//返回插入结点。O(n)。覆盖

publicDoubleNode<T>insert(Tx)}排序循环双链表类（升序）SortedCirDoublyList()//构造空表SortedCirDoublyList(T[]values)//构造，数组对象按值插入SortedCirDoublyList(SortedCirDoubly