第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問題?！纠?.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)?！纠?.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