第02章線性表(Java版)

第2章線性表2.1線性表抽象數(shù)據(jù)類型2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4線性表的應(yīng)用：多項(xiàng)式的表示及運(yùn)算目的：實(shí)現(xiàn)線性表抽象數(shù)據(jù)類型。要求：掌握順序、鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表。重點(diǎn)：順序表，單鏈表，循環(huán)雙鏈表。難點(diǎn)：使用“對(duì)象引用”方式實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。實(shí)驗(yàn)：掌握MyEclipse環(huán)境的程序調(diào)試技術(shù)。2.1線性表抽象數(shù)據(jù)類型2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4線性表的應(yīng)用：多項(xiàng)式的表示及運(yùn)算目的：實(shí)現(xiàn)線性表抽象數(shù)據(jù)類型。要求：掌握順序、鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表。重點(diǎn)：順序表，單鏈表，循環(huán)雙鏈表。難點(diǎn)：使用“對(duì)象引用”方式實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。實(shí)驗(yàn)：掌握MyEclipse環(huán)境的程序調(diào)試技術(shù)。2.1線性表抽象數(shù)據(jù)類型線性表（LinearList）(a0，a1，…，an-1)是由n（≥0）個(gè)類型相同的數(shù)據(jù)元素組成的有限序列，其中，元素類型可以是基本類型或類；n是線性表長度（Length），即元素個(gè)數(shù)。若n=0，空表；若n>0，（0<i<n-1）有且僅有一個(gè)前驅(qū)元素和一個(gè)后繼元素，a0沒有前驅(qū)元素，an-1沒有后繼元素。ADTList<T>//線性表抽象數(shù)據(jù)類型，數(shù)據(jù)元素的數(shù)據(jù)類型為T{booleanisEmpty()//判斷線性表是否為空intsize()//返回線性表長度

Tget(inti)//返回第i個(gè)元素

voidset(inti,Tx)//設(shè)置第i個(gè)元素為xStringtoString()//所有元素的描述字符串

intinsert(inti,Tx)//插入x作為第i個(gè)元素

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

Tremove(inti)//刪除第i個(gè)元素

voidclear()//刪除所有元素

intsearch(Tkey)//查找與key相等元素booleancontains(Tkey)//判斷是否包含key元素Tremove(Tkey)//刪除與key相等元素

booleanequals(Objectobj)//比較是否相等voidaddAll(List<T>list)//添加list所有元素}2.2線性表的順序存儲(chǔ)和實(shí)現(xiàn)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.2順序表2.2.3排序順序表習(xí)圖2.1線性表的存儲(chǔ)結(jié)構(gòu)

2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)數(shù)組數(shù)組是實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)。數(shù)組（Array）存儲(chǔ)具有相同數(shù)據(jù)類型的元素集合。一維數(shù)組占用一塊內(nèi)存空間，每個(gè)存儲(chǔ)單元的地址是連續(xù)的，計(jì)算第i個(gè)元素地址所需時(shí)間復(fù)雜度是一個(gè)常量，與元素序號(hào)i無關(guān)。存取任何一個(gè)元素的時(shí)間復(fù)雜度是O(1)的數(shù)據(jù)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。因此，數(shù)組是隨機(jī)存取結(jié)構(gòu)。2.順序表（SequentialList）采用一維數(shù)組存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素在內(nèi)存的物理存儲(chǔ)次序反映了線性表數(shù)據(jù)元素之間的邏輯次序。順序表是隨機(jī)存取結(jié)構(gòu)。順序表類聲明、存取操作及效率分析順序表插入操作順序表刪除操作順序表查找操作順序表的淺拷貝與深拷貝順序表比較相等2.2.2順序表publicclassSeqList<T>//順序表類，泛型類{protectedObject[]element;//對(duì)象數(shù)組

protectedintn;//元素個(gè)數(shù)（長度）

publicSeqList(intlength)//構(gòu)造空表publicSeqList()//構(gòu)造方法重載

{this(64);//調(diào)用本類指定參數(shù)列表的構(gòu)造方法

}publicSeqList(T[]values)//由values數(shù)組提供元素publicbooleanisEmpty()//判斷順序表是否空publicintsize()//返回元素個(gè)數(shù)}順序表類SeqList<T>

SeqList<T>類設(shè)計(jì)說明泛型類隱藏成員變量構(gòu)造方法析構(gòu)方法對(duì)象引用賦值存取操作，當(dāng)指定元素序號(hào)不正確時(shí)的處理原則遍歷輸出及運(yùn)行時(shí)多態(tài)操作的效率分析（1）泛型類與創(chuàng)建實(shí)例Stringvalues[]={"A","B","C","D","E"};SeqList<String>lista=newSeqList<String>(values); //lista引用順序表實(shí)例，元素是String對(duì)象【例2.1】求解約瑟夫環(huán)問題。（5）存取操作，當(dāng)指定元素序號(hào)不正確時(shí)的處理原則publicTget(inti)//返回第i個(gè)元素，0≤i<n。若i越界，返回nullpublicvoidset(inti,Tx)//設(shè)置第i個(gè)元素為x，0≤i<n。若i越界，拋出序號(hào)越界異常；若x==null，拋出空對(duì)象異常list.get(-1).toString()//get()方法返回null時(shí)拋出空對(duì)象異常（6）遍歷輸出及運(yùn)行時(shí)多態(tài)//返回順序表所有元素的描述字符串，形式為“(,)”。//覆蓋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(); //執(zhí)行T類的toString()方法，運(yùn)行時(shí)多態(tài)

returnstr+")"; //空表返回()}（7）操作的效率分析isEmpty()、size()、get(i)、set(i,x)方法，時(shí)間復(fù)雜度為O(1)。toString()方法需要遍歷順序表，時(shí)間復(fù)雜度為O(n)?！舅伎碱}2-1】publicObjectget(inti){returnthis.element[i];//習(xí)題解答}SeqList<Integer>list=newSeqList<Integer>(n);Objectobj=list.get(0);//引用子類實(shí)例obj.toString()//調(diào)用Object方法Value()//編譯錯(cuò)，//obj不能調(diào)用Integer類的成員方法((T)obj).intValue()//(T)obj是Integer類的對(duì)象【思考題2-1】publicTget(inti){return(T)this.element[i];}SeqList<Integer>list=newSeqList<Integer>(n);Integeriobj=list.get(0);//iobj引用本類實(shí)例iobj.toString()Value()//iobj能夠調(diào)用Integer類的成員方法2.順序表插入操作intinsert(inti,Tx)//插入x作為第i個(gè)元素intinsert(Tx)//尾插入x元素。重載2.順序表插入操作若數(shù)組滿，則擴(kuò)充順序表的數(shù)組容量3.順序表刪除操作Tremove(inti)//返回刪除第i（0≤i<n）個(gè)元素voidclear()//刪除線性表所有元素【例2.1】求解約瑟夫環(huán)問題。（1）泛型類與創(chuàng)建實(shí)例MyEclipse開發(fā)環(huán)境，配置編譯路徑（BuildPath），引用其他項(xiàng)目中的類。

【例2.1】采用單鏈表求解約瑟夫環(huán)問題。（1）順序查找算法

//順序查找首次出現(xiàn)的與key相等元素，返回元素序號(hào)i；查找不成功返回-1。publicintsearch(Tkey){for(inti=0;i<this.n;i++)if(key.equals(this.element[i]))//執(zhí)行T類的equals(Object)，運(yùn)行時(shí)多態(tài)

returni;return-1; //空表或未找到時(shí)}【思考題2】若if(this.element[i].equals(key))，查找結(jié)果會(huì)怎樣？為什么？4.順序表查找操作【答】執(zhí)行Object類的equals(Object)（2）比較對(duì)象相等的方法Object類publicboolean

equals(Object

obj){return(this==obj);//若兩個(gè)對(duì)象引用同一個(gè)實(shí)例，返回true}publicfinalclassIntegerextendsNumberimplementsComparable<Integer>{privatefinalintvalue;publicboolean

equals(Object

obj)//覆蓋Object類的方法

{

if(obj

instanceofInteger)returnvalue==((Integer)obj).intValue();//比較兩個(gè)Integer對(duì)象的值

returnfalse;}}【思考題2-2】基于查找算法的操作booleancontains(Tkey)//包含{returnthis.search(key)!=-1;}//插入不重復(fù)元素。查找不成功時(shí)，尾插入intinsertDifferent(Tx){returnthis.search(x)==-1?this.insert(x):-1;}Tremove(Tkey)//刪除首個(gè)與key相等元素{returnthis.remove(this.search(key));

//先查找，再調(diào)用remove(i)。若查找不成功，返回-1，不刪除}3.多態(tài)原則，子類覆蓋父類成員方法順序表的靜態(tài)特性很好，動(dòng)態(tài)特性很差，具體說明如下。①順序表元素的物理存儲(chǔ)順序直接反映線性表元素的邏輯順序，順序表是一種隨機(jī)存取結(jié)構(gòu)。get()、set()方法時(shí)間復(fù)雜度是O(1)。②插入和刪除操作效率很低。如果在各位置插入元素的概率相同，則有順序表小結(jié)5.順序表的淺拷貝與深拷貝類的拷貝構(gòu)造方法聲明格式如下，方法名同類名，參數(shù)為本類對(duì)象。沒有默認(rèn)。類(類對(duì)象)//拷貝構(gòu)造方法

{this.成員變量=參數(shù)對(duì)象.成員變量; //逐域賦值，以參數(shù)的實(shí)例值初始化當(dāng)前實(shí)例}（1）順序表的淺拷貝publicSeqList(SeqList<T>list)//淺拷貝構(gòu)造方法{

this.n=list.n;//int整數(shù)賦值，復(fù)制了整數(shù)值

this.element=list.element;//數(shù)組引用賦值，兩個(gè)變量共用一個(gè)數(shù)組，錯(cuò)誤}圖2.6順序表的淺拷貝及其錯(cuò)誤SeqList<String>listb=newSeqList<String>(lista);lista.remove(0);（2）順序表的深拷貝復(fù)制數(shù)組（2）順序表的深拷貝復(fù)制數(shù)組，復(fù)制對(duì)象6.順序表比較相等習(xí)題2-5SeqList類以下聲明有什么錯(cuò)誤？為什么？publicboolean

equals(Object

obj)//比較兩個(gè)順序表是否相等，覆蓋{returnthis.n==list.n

&&this.element==obj.element;}兩個(gè)線性表相等是指，它們各對(duì)應(yīng)元素相等并且長度相同。比較兩個(gè)順序表對(duì)象是否相等//習(xí)題解答2-5比較兩個(gè)順序表對(duì)象是否相等SeqList<T>類聲明覆蓋

publicbooleanequals(Objectobj){if(this==obj)//引用同一個(gè)實(shí)例

returntrue;if(objinstanceofSeqList<?>)//若obj引用順序表實(shí)例。//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))))//運(yùn)行時(shí)多態(tài)

returnfalse;returntrue;}}returnfalse;}通配符2.2.3排序順序表子類繼承原則子類不能繼承父類的構(gòu)造函數(shù)多態(tài)原則，子類覆蓋父類成員方法比較對(duì)象大小的方法類型的多態(tài)，子類對(duì)象即是父類對(duì)象排序順序表排序線性表是指，各數(shù)據(jù)元素按照關(guān)鍵字值遞增或遞減排列。排序線性表是一種特殊的線性表。

//排序順序表類（升序），T或T的某個(gè)祖先類實(shí)現(xiàn)Comparable<T>接口，比較對(duì)象大小publicclass

SortedSeqList<TextendsComparable<?superT>> extendsSeqList<T>1.子類繼承原則子類重定義父類成員包括：重定義父類的成員變量，則隱藏父類的成員變量；重定義父類的成員方法，如果參數(shù)列表相同，則覆蓋（Override）父類的成員方法，返回值類型必須與父類方法賦值相容；如果參數(shù)列表不同，則重載（Overload）父類的成員方法。子類使用“super引用”，語法格式如下：super.成員變量

//當(dāng)子類隱藏父類成員變量時(shí)， //引用父類同名成員變量super.成員方法([參數(shù)列表])//當(dāng)子類覆蓋父類成員方法時(shí)， //調(diào)用父類同名成員方法2.子類不能繼承父類的構(gòu)造方法publicSortedSeqList()//構(gòu)造空表{super();//默認(rèn)調(diào)用SeqList()}publicSortedSeqList(intlength)//構(gòu)造空表，容量為length{super(length);//調(diào)用SeqList(length)

//若省略，默認(rèn)調(diào)用super()}publicSortedSeqList(T[]values)//構(gòu)造，由數(shù)組提供元素，{super(values.length);for(inti=0;i<values.length;i++)this.insert(values[i]);//插入元素}3.多態(tài)原則，

子類覆蓋父類成員方法（1）排序順序表的插入操作//插入x，x!=null，根據(jù)x大小確定插入位置，返回x序號(hào)。調(diào)用T的compareTo()方法比較對(duì)象大小。覆蓋父類insert(Tx)，參數(shù)列表和返回值相同publicintinsert(Tx)//插入不重復(fù)元素。查找不成功時(shí)，插入。覆蓋publicintinsertDifferent(Tx)【思考題2-2】順序表基于查找算法的操作子類不能刪除父類成員//不支持父類方法，覆蓋并拋出異常publicvoidset(inti,Tx)//元素只讀{thrownewUnsupportedOperationException("set(inti,Tx)");}publicintinsert(inti,Tx)//任意位置插入（2）編譯時(shí)多態(tài)與運(yùn)行時(shí)多態(tài)【例2.3】順序表與排序順序表的插入操作。Integer[]values={70,20,80,30,60};SeqList<Integer>list1=newSeqList<Integer>(values);SortedSeqList<Integer>slist1=newSortedSeqList<Integer>(list1);//由順序表構(gòu)造排序順序表list1.insert(0,10);//調(diào)用insert(i,x)方法，順序表插入list1.insert(50);//父類對(duì)象調(diào)用父類方法，順序表尾插入slist1.insert(50);//子類對(duì)象調(diào)用子類方法，

//排序順序表按值插入，覆蓋slist1.insert(0,90);//排序順序表插入，拋出異常（3）排序順序表查找操作//順序查找首次出現(xiàn)的與key相等元素，返回元素序號(hào)i。覆蓋publicintsearch(Tkey){for(inti=start;i<this.n&&pareTo(this.get(i))>=0;i++)if(pareTo(this.get(i))==0)//對(duì)象相等，運(yùn)行時(shí)多態(tài)

returni;return-1;//空表或未找到時(shí)}（3）排序順序表刪除操作publicTremove(Tkey)//繼承

{returnthis.remove(this.search(key));//先查找，再調(diào)用remove(i)。若查找不成功，返回-1，則不刪除

//其中this.search(key)運(yùn)行時(shí)多態(tài)，子類對(duì)象調(diào)用子類的查找方法}【實(shí)驗(yàn)2-2】SortedSeqList<T>類聲明成員方法//插入關(guān)鍵字不重復(fù)元素，返回插入位置。使用順序查找算法按值比較，尋找插入位置。//不能調(diào)用search(Tkey)方法，因?yàn)椴檎也怀晒ζ浞祷?1，不能確定插入位置。publicintinsertDifferent(Tx)4.比較對(duì)象大小的方法publicinterfaceComparable<T>//可比較接口{intcompareTo(Tobj)//比較對(duì)象大小，//返回0、正、負(fù)整數(shù)，分別表示相等、大、小}publicfinalclassIntegerimplementsComparable<Integer>

{publicintcompareTo(Integeriobj)}publicfinalclassStringimplementsComparable<String>{publicintcompareTo(Strings)}5.類型的多態(tài)，

子類對(duì)象即是父類對(duì)象子類對(duì)象即是父類對(duì)象，賦值相容SeqList<Integer>list=newSortedSeqList<Integer>(value); //父類對(duì)象list引用子類實(shí)例list.insert(50);//運(yùn)行時(shí)根據(jù)list引用實(shí)例的類型，確定執(zhí)行父類或子類方法，排序順序表插入//子類對(duì)象即是父類對(duì)象，反之則不然。SortedSeqList<Integer>slist=newSeqList<Integer>(value);//編譯錯(cuò)方法參數(shù)和返回值的傳遞原則也是賦值相容SeqList<Integer>list2=newSeqList<Integer>(slist1);//順序表深拷貝，由排序順序表slist1構(gòu)造順序表publicbooleanequals(Objectobj)//繼承{if(objinstanceofSeqList<?>)//若obj引用SortedSeqList<T>實(shí)例……}（2）重載拷貝構(gòu)造方法publicSortedSeqList(SeqList<?extendsT>list) //由順序表構(gòu)造排序順序表，O(n2){super(); //默認(rèn)調(diào)用SeqList()for(inti=0;i<list.n;i++)this.insert(list.get(i));//調(diào)用子類方法，按值插入，O(n)}publicSortedSeqList(SortedSeqList<?extendsT>list) //排序順序表的拷貝構(gòu)造方法，深拷貝，O(n){super(list); //調(diào)用SeqList(SeqList<T>)，//list引用子類實(shí)例，參數(shù)類型賦值相容}圖2.8由順序表list構(gòu)造排序順序表this，共用list的對(duì)象SortedSeqList(SeqList<?extendsT>list)【例2.4】對(duì)象信息的分類統(tǒng)計(jì)、查找和排序操作。目的：①聲明類作為泛型參數(shù)T的實(shí)際參數(shù)，比較對(duì)象相等及大小。②分別使用順序表、排序順序表存儲(chǔ)對(duì)象序列，按姓名查找，按成績排序。③在順序表類之外定義對(duì)順序表進(jìn)行特定操作的函數(shù)，順序表作為函數(shù)參數(shù)。（1）Student類publicclassStudentextendsObjectimplementsComparable<Student> //學(xué)生類（2）對(duì)象信息的分類統(tǒng)計(jì)、查找、刪除、排序等操作//分類統(tǒng)計(jì)線性表list的元素信息，分段信息存于grade數(shù)組，返回保存統(tǒng)計(jì)結(jié)果的數(shù)組int[]groupCount(SeqList<Student>list,intgrade[])voidprintCount(SeqList<Student>list,Stringtitles[],intresult[])//輸出【例2.5】使用線性表表示集合，實(shí)現(xiàn)集合運(yùn)算。目的：①線性表表示集合的特性，以集合并為例實(shí)現(xiàn)集合運(yùn)算；②泛型的繼承性。（1）（排序）線性表表示集合的特性順序表表示可重復(fù)的無序集合。因?yàn)樵亻g具有線性次序，所以，可以采用序號(hào)識(shí)別關(guān)鍵字重復(fù)的數(shù)據(jù)元素。排序順序表表示可重復(fù)的排序集合，元素按關(guān)鍵字大小排序。集合并SeqList<T>類聲明，SortedSeqList<T>類繼承。publicvoidaddAll(SeqList<?extendsT>list) //在this之后添加list的所有元素，集合并{for(inti=0;i<list.n;i++)this.insert(list.get(i));//運(yùn)行時(shí)多態(tài)，順序表尾插入；排序順序表按值插入}（2）泛型的繼承性泛型聲明[修飾符]class類<類型參數(shù)列表>[extends父類][implements接口列表][public]interface接口<類型參數(shù)列表>[extends父接口列表][public][static]<類型參數(shù)列表>

返回值類型方法([參數(shù)列表])[throws異常類列表]<類型參數(shù)列表>：類型變量

[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>]//語法錯(cuò)TextendsComparable<?superT>publicclassPerson

implementsComparable<Person>{publicintcompareTo(Person)}

//符合publicclassStudentextendsPerson[implementsComparable<Person>]{publicintcompareTo(Person)}//符合2.2.3排序順序表圖2.9SeqList<T>類與子類SortedSeqList<T>

成員方法的關(guān)系【思考題2-4】SeqList<T>類聲明以下方法，子類SortedSeqList<T>是否可用？為什么？//返回將this與list所有元素合并連接的順序表SeqList<T>

union(SeqList<?extendsT>list)習(xí)題解答{SeqList<T>result=newSeqList<T>(this);

//深拷貝this，無法創(chuàng)建子類實(shí)例result.addAll(list);//順序表合并連接，尾插入

returnresult;//只能返回SeqList<T>對(duì)象}//子類不可用SeqList<T>addAll(SeqList<?extendsT>list)

//語法錯(cuò)，參數(shù)列表相同時(shí)不能重載SortedSeqList<T>類聲明覆蓋union(list)方法SortedSeqList<T>union(SeqList<?extendsT>list)

//覆蓋，值類型不同但賦值相容。與父類實(shí)例運(yùn)算{SortedSeqList<T>result=new SortedSeqList<T>(this);//創(chuàng)建子類實(shí)例，深拷貝

result.addAll(list);//繼承父類方法，運(yùn)行時(shí)多態(tài)，//排序順序表合并，按值插入returnresult;//返回SortedSeqList<T>對(duì)象}實(shí)驗(yàn)題2-2

元素互異的（排序）順序表類publicclassDifferentSeqList<T>extendsSeqList<T> //互異順序表類publicclassDifferentSortedSeqList<TextendsComparable<?superT>>

extendsSortedSeqList<T> //互異排序順序表類（升序）2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.2單鏈表2.3.3雙鏈表第2章線性表2.3.2單鏈表單鏈表結(jié)點(diǎn)類2.單鏈表的基本操作3.帶頭結(jié)點(diǎn)的單鏈表4.單鏈表操作的效率分析5.單鏈表的淺拷貝與深拷貝6.排序單鏈表7.循環(huán)單鏈表publicclassNode<T>//單鏈表結(jié)點(diǎn)類{publicTdata;//數(shù)據(jù)域，保存數(shù)據(jù)元素

publicNode<T>next;//地址域，引用后繼結(jié)點(diǎn)

publicNode(Tdata,Node<T>next)//構(gòu)造結(jié)點(diǎn)publicNode()publicStringtoString()}//繼承析構(gòu)方法，不需要拷貝構(gòu)造方法。習(xí)題解答實(shí)驗(yàn)2.1Node<String>p,q;p=newNode<String>("A",null);q=newNode<String>("B",null);p.next=q;1.單鏈表結(jié)點(diǎn)類習(xí)題2-6寫出以下數(shù)據(jù)結(jié)構(gòu)的聲明。習(xí)題解答Node<T>table[]; //一維數(shù)組，元素為結(jié)點(diǎn)SinglyList<T>table[]; //一維數(shù)組，元素為單鏈表SeqList<Node<T>>table;//順序表，元素為結(jié)點(diǎn)SeqList<SinglyList<T>>table;//順序表，元素為單鏈表

2.單鏈表的基本操作（1）單鏈表的遍歷操作Node<T>p=head;while(p!=null){p.data.toString()//執(zhí)行訪問p結(jié)點(diǎn)的相關(guān)操作p=p.next;}【思考題2-5】如果語句p=p.next寫成p.next=pp.next=p;使p.next指向p結(jié)點(diǎn)自己，改變了結(jié)點(diǎn)間的鏈接關(guān)系。遍歷算法死循環(huán)。習(xí)題解答（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）中，如果①②兩句次序顛倒，將會(huì)怎樣？

Node<T>p=newNode<T>(x,null);front.next=p;//①p.next=front.next;//②習(xí)題解答（3）單鏈表的刪除操作頭刪除head=head.next;中間/尾刪除if(front.next!=null)

front.next=front.next.next;3.帶頭結(jié)點(diǎn)的單鏈表頭結(jié)點(diǎn)的作用是，使所有鏈表（包括空表）的頭指針非空，則對(duì)單鏈表的插入、刪除操作不需要區(qū)分操作位置。3.帶頭結(jié)點(diǎn)的單鏈表頭插入和頭刪除操作不會(huì)改變head指針。單鏈表類publicclassSinglyList<T>{publicNode<T>head;//頭指針publicSinglyList()//構(gòu)造空表publicSinglyList(T[]values)

publicbooleanisEmpty()publicTget(inti)//返回第i個(gè)元素

publicvoidset(inti,Tx)//設(shè)置第i個(gè)元素為x

publicintsize()//長度publicStringtoString()單鏈表類SinglyList<T>

publicNode<T>insert(inti,Tx)//插入x作為第i個(gè)元素publicNode<T>insert(Tx)//尾插入publicTremove(inti)//刪除第i個(gè)元素publicvoidclear()//刪除所有元素}【思考題2-7】①單鏈表成員方法voidset(inti,Tx)//設(shè)置第i個(gè)元素為xintsize()//長度Node<T>search(Tkey)//查找booleancontains(Tkey)//包含Node<T>insertDifferent(Tx)//插入不重復(fù)元素，查找不成功時(shí)尾插入Tremove(Tkey)//刪除【思考題2-7】②基于查找操作SinglyList<T>類的insertDifferent(x)和remove(key)方法能否調(diào)用search(key)方法確定操作位置？為什么？都不能。因?yàn)閱捂湵淼牟迦牒蛣h除需要修改前驅(qū)結(jié)點(diǎn)的next域，而search(key)方法返回key結(jié)點(diǎn)，無法操作。insertDifferent(x)方法要求查找不成功時(shí)，尾插入。而search(key)方法查找不成功時(shí)返回null，失去操作位置信息?！舅伎碱}2-7】③使用單鏈表例2.1，采用單鏈表求解約瑟夫環(huán)問題。

SinglyList<String>list=newSinglyList<String>();例2.4，分類統(tǒng)計(jì)學(xué)生成績。

int[]groupCount(SinglyList<Student>list,

intgrade[])分析各操作效率。修改對(duì)順序表操作的方法，使其對(duì)單鏈表操作的效率最佳?！舅伎碱}2-7】③

【例2.1】采用單鏈表求解Josephus問題?！纠?.1】求解約瑟夫環(huán)問題。newJosephus(5,0,3)4.單鏈表操作的效率分析isEmpty()方法的時(shí)間復(fù)雜度是O(1)。size()、toString()等，遍歷單鏈表，O(n)。get(i)和set(i)，遍歷部分單鏈表，O(n)，不是隨機(jī)存取結(jié)構(gòu)。insert(i,x)和remove(i)，查找i，O(n)。在front結(jié)點(diǎn)之后插入、刪除圖2.13在p結(jié)點(diǎn)之前插入q結(jié)點(diǎn)，要尋找p的前驅(qū)結(jié)點(diǎn)front圖2.13刪除p結(jié)點(diǎn)，要尋找p的前驅(qū)結(jié)點(diǎn)front

（4）提高單鏈表操作效率的措施插入操作對(duì)序號(hào)容錯(cuò)Node<T>insert(Tx) //尾插入{returninsert(this.size(),x); //需兩次遍歷單鏈表，效率較低}returninsert(Integer.MAX_VALUE,x);//遍歷一次，必須容錯(cuò)i超長②單鏈表不能調(diào)用get(i)方法遍歷。//返回?cái)?shù)值線性表的平均值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();//實(shí)數(shù)除，存在除數(shù)為0錯(cuò)誤}//順序表，O(n)；單鏈表，O(n2)③增加屬性成員變量n表示單鏈表長度，插入，n++；刪除，n--，則size()時(shí)間為O(1)。成員變量rear作為單鏈表的尾指針，則尾插入的時(shí)間是O(1)。【例2.6】單鏈表逆轉(zhuǎn)。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;//設(shè)置succ是p結(jié)點(diǎn)的后繼結(jié)點(diǎn)

p.next=front; //使p.next指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

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

}list.head.next=front;}構(gòu)造反序單鏈表//頭插入，單鏈表元素次序與數(shù)組元素次序相反<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;//返回單鏈表對(duì)象引用}5.單鏈表的淺拷貝與深拷貝SinglyList(SinglyList<T>list)//淺拷貝{this.head=list.head;//對(duì)象引用賦值//導(dǎo)致兩個(gè)引用變量指向同一個(gè)結(jié)點(diǎn)}單鏈表的深拷貝SinglyList(SinglyList<T>list)//深拷貝{this();//創(chuàng)建空單鏈表，只有頭結(jié)點(diǎn)

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單鏈表尾

}}單鏈表的深度拷貝，復(fù)制對(duì)象【思考題2-8】②單鏈表比較相等兩條單鏈表相等是指，它們各對(duì)應(yīng)元素相等并且長度相同。publicbooleanequals(Objectobj)//覆蓋【習(xí)題解答例2.1】集合并運(yùn)算，單鏈表深拷貝的應(yīng)用。理解單鏈表的深拷貝。理解對(duì)象引用參數(shù)。//在this單鏈表之后連接list單鏈表，集合并voidconcat(SinglyList<T>list)合并連接單鏈表//在this單鏈表之后連接list單鏈表；設(shè)置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;}單鏈表深拷貝//復(fù)制list單鏈表中所有結(jié)點(diǎn)插入到this單鏈表之后publicvoidaddAll(SinglyList<T>list){this.concat(newSinglyList<T>(list)); //先執(zhí)行單鏈表深拷貝，再連接復(fù)制的list}返回并集//返回復(fù)制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構(gòu)造排序單鏈表（升序）排序單鏈表類（升序），

繼承單鏈表類publicclassSortedSinglyList<TextendsComparable<?superT>>extendsSinglyList<T>//T或T的某個(gè)祖先類實(shí)現(xiàn)Comparable<T>接口{SortedSinglyList()//構(gòu)造空表SortedSinglyList(T[]values)//構(gòu)造，按值插入SortedSinglyList(SortedSinglyList<T>list)//深拷貝SortedSinglyList(SinglyList<T>list)//重載深拷貝，由單鏈表構(gòu)造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)//插入不重復(fù)元素，覆蓋

Tremove(Tkey)//刪除key元素，覆蓋voidaddAll(SinglyList<T>list)//將list中所有元素插入 到this單鏈表，不改變list，集合并。覆蓋}insertDifferent(Tx)//插入不重復(fù)元素，返回插入結(jié)點(diǎn)；覆蓋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.循環(huán)單鏈表head.next=head;rear.next=head;publicclassCirSinglyList<T>{publicNode<T>head;//頭指針

publicCirSinglyList()//構(gòu)造空表

{this.head=newNode<T>();//創(chuàng)建頭結(jié)點(diǎn)

this.head.next=this.head;//構(gòu)成環(huán)形}publicbooleanisEmpty()//判空

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

{//遍歷，循環(huán)條件改變了for(Node<T>p=this.head.next;p!=this.head;p=p.next)}}【思考題2-10】能否使用以下語句創(chuàng)建循環(huán)單鏈表的頭結(jié)點(diǎn)？為什么？publicCirSinglyList()//構(gòu)造空表{

head=newNode<T>(null,head);}習(xí)題解答【答】不能。因?yàn)樯暾?qǐng)結(jié)點(diǎn)存儲(chǔ)空間時(shí)head沒有初始化，實(shí)際語義需要的是將該結(jié)點(diǎn)地址作為其next域值，做不到。2.3.3雙鏈表雙鏈表結(jié)點(diǎn)類2.雙鏈表的特性和操作3.循環(huán)雙鏈表4.排序循環(huán)雙鏈表1.雙鏈表結(jié)點(diǎn)類publicclassDoubleNode<T>{publicTdata;

publicDoubleNode<T>prev,next;//前驅(qū)，后繼

publicDoubleNode(Tdata,DoubleNode<T>prev, DoubleNode<T>next)//構(gòu)造方法重載

publicDoubleNode(Tdata)publicDoubleNode()publicStringtoString()}//繼承析構(gòu)方法，不需要拷貝構(gòu)造方法。習(xí)題2-11DoubleNode類不能聲明如下，繼承單鏈表結(jié)點(diǎn)類。publicclassDoubleNode<T>extendsNode<T> {DoubleNode<T>prev;//前驅(qū)結(jié)點(diǎn)//Node<T>next;//數(shù)據(jù)類型錯(cuò)誤}//習(xí)題解答2.雙鏈表的特性和操作雙鏈表結(jié)構(gòu)和特性空雙鏈表，只有頭結(jié)點(diǎn)。head.next==null且head.prev==null非空雙鏈表，設(shè)p指向雙鏈表中非兩端的某個(gè)結(jié)點(diǎn)，有：

p=p.next.prev=p.prev.next（2）雙鏈表的插入操作//在p結(jié)點(diǎn)之前插入q=newDoubleNode<T>(x);q.prev=p.prev;q.next=p;①p.prev.next=q;//因有p.prev!=NULL②p.prev=q;//【思考題2-11】兩句次序顛倒，將會(huì)怎樣？【思考題2-11】在p結(jié)點(diǎn)之后插入q=newDoubleNode<T>(x);q.prev=p;q.next=p.next;if(p.next!=NULL)//中間插入p.next.prev=q;p.next=q;//與上句次序顛倒，將會(huì)怎樣？習(xí)題解答（3）雙鏈表的刪除操作p.prev.next=p.next;//有p.prev!=nullif(p.next!=null)

//中間刪除p.next.prev=p.prev;3.循環(huán)雙鏈表空循環(huán)雙鏈表有head.next==head且head.prev==head循環(huán)雙鏈表類CirDoublyListpublicclassCirDoublyList<T>//循環(huán)雙鏈表類{DoubleNode<T>head;//頭指針

CirDoublyList()//構(gòu)造空表

booleanisEmpty()//判空

DoubleNode<T>insert(inti,Tx)//插入x為第i個(gè)元素

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

//實(shí)現(xiàn)以下方法

StringtoPreviousString()//反序輸出

TremoveLast()//刪除最后一個(gè)元素}插入x為第i個(gè)元素

publicDoubleNode<T>insert(inti,Tx)

尾插入x元素，O(1)//尾插入x元素，返回x結(jié)點(diǎn)。在頭結(jié)點(diǎn)之前插入publicDoubleNode<T>insert(Tx)習(xí)題2-13循環(huán)雙鏈表類能否聲明如下，繼承單鏈表類，繼承了head成員變量？為什么？classCirDoublyList<T>extendsSinglyList<T>實(shí)現(xiàn)循環(huán)雙鏈表類的size()等其他成員函數(shù)。習(xí)題解答【答】不能。等價(jià)于以下：{Node<T>head;//繼承基類的成員變量，//數(shù)據(jù)類型錯(cuò)誤，應(yīng)該是DoubleNode<T>};刪除元素Tremove(inti)//刪除第i個(gè)元素TremoveLast()//刪除最后一個(gè)元素{DoubleNode<T>p=this.head.prev;//p指向頭結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

if(p!=head){p.prev.next=this.head;//刪除p結(jié)點(diǎn)，由JVM稍后釋放

this.head.prev=p.prev;returnp.data;//返回p結(jié)點(diǎn)元素

}returnnull;//當(dāng)i<0或i>表長時(shí)}習(xí)題解答【習(xí)2.3】

循環(huán)雙鏈表合并連接publicvoidconcat(CirDoublyList<T>list)4.排序循環(huán)雙鏈表圖2.22構(gòu)造排序循環(huán)雙鏈表（升序）排序循環(huán)雙鏈表類（升序），

繼承循環(huán)雙鏈表類publicclassSortedCirDoublyList<TextendsComparable<?superT>>extendsCirDoublyList<T>//T或T的某個(gè)祖先類實(shí)現(xiàn)Comparable<T>接口{//插入x，x!=null，根據(jù)x對(duì)象大小順序查找確定插入位置，插入在等值結(jié)點(diǎn)之前。

//返回插入結(jié)點(diǎn)。O(n)。覆蓋

publicDoubleNode<T>insert(Tx)}排序循環(huán)雙鏈表類（升序）SortedCirDoublyList()//構(gòu)造空表SortedCirDoublyList(T[]values)//構(gòu)造，數(shù)組對(duì)象按值插入SortedCirDoublyList(SortedCirDoubly