第2章 線性表電子課件

第2章線性表

本章講解線性表。要求理解線性表概念、基本操作；掌握線性表的存儲(chǔ)結(jié)構(gòu)；掌握順序表的基本操作；掌握鏈表的基本操作；靈活應(yīng)用線性表。北京有冰糖葫蘆，咱們成都有糖油果子。老遠(yuǎn)處看還真難以區(qū)分，在成都的北京人以為要吃到家鄉(xiāng)的冰糖葫蘆了；在北京的成都人以為要吃到家鄉(xiāng)的糖油果子了。哈哈，原來它們盡管味道霄壤之別，卻長得相像，皆是線性結(jié)構(gòu)。提綱2.1線性表基本概念2.2順序表2.3單鏈表2.4雙鏈表2.5循環(huán)鏈表2.6線性表應(yīng)用2.7線性表學(xué)習(xí)總結(jié)2.1線性表基本概念

2.1線性表基本概念如圖2.1所示，太陽公公和小朋友們手拉手，他的直接前驅(qū)是2號(hào)小朋友，直接后繼是4號(hào)小朋友；1號(hào)和5號(hào)小朋友分別是太陽公公的間接前驅(qū)和間接后繼。2.1線性表基本概念線性表的抽象數(shù)據(jù)接口描述如下：publicinterfaceIList{

publicvoidclear(); //將線性表置成空表

publicbooleanisEmpty(); //判斷線性表是否為空表

publicintlength(); //返回線性表的長度

publicObjectget(inti)throwsException;//獲取第i個(gè)元素

publicvoidinsert(inti,Objectx)throwsException;//i位置插入x

publicvoidremove(inti)throwsException;//刪除位置i的元素

publicintindexOf(Objectx); //返回元素x首次出現(xiàn)的位序號(hào)

publicvoiddisplay(); //輸出線性表所有元素

}

根據(jù)存儲(chǔ)結(jié)構(gòu)不同，線性表分為順序表和鏈表2大類。2.2順序表以順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的線性表稱為順序表。2.2.1順序表存儲(chǔ)結(jié)構(gòu)順序表存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)方式，邏輯上相鄰的元素物理存儲(chǔ)位置也相鄰，元素存儲(chǔ)都是連續(xù)的。由這種結(jié)構(gòu)特點(diǎn)可知，順序表可以隨機(jī)訪問快速定位某個(gè)元素，查找效率高，但刪除和插入元素時(shí)，需要移動(dòng)大量元素，效率低。舉例：老師在教室里選擇1列或1行無空位連續(xù)坐著n個(gè)學(xué)生的區(qū)域，假設(shè)有座位編號(hào)，老師可以迅速定位某個(gè)學(xué)生，如3號(hào)學(xué)生玩手機(jī)優(yōu)先回答問題吧；若把3號(hào)學(xué)生請出教室后仍保持這個(gè)區(qū)域順序存儲(chǔ)，則4號(hào)坐到3號(hào)處，5號(hào)坐到4號(hào)處，依此類推n號(hào)坐到n-1號(hào)處；若3號(hào)學(xué)生在教室外呆了一會(huì)兒反省了，老師又讓他坐回原來位置，則n-1號(hào)先坐回n號(hào)處。。。。。。此時(shí)的3號(hào)坐回4號(hào)處，原3號(hào)學(xué)生坐回3號(hào)處。在這個(gè)例子中，n個(gè)學(xué)生的區(qū)域是順序表存儲(chǔ)結(jié)構(gòu)，對順序表的查找較容易而對其刪除和插入較麻煩。2.2.2順序表基本操作順序表類的描述如下：publicclassSeqListimplementsIList{

publicObject[]listItem;//順序表用一維數(shù)組作為存儲(chǔ)空間

publicintcurLen;//順序表當(dāng)前長度

publicintmaxSize;//最大分配空間

publicSeqList(intmaxSize){//構(gòu)造存儲(chǔ)空間為maxsize的順序表

curLen=0;

maxSize=maxSize;

listItem=newObject[maxSize];

}

//順序表基本操作（略）

}

2.2.2順序表基本操作

2.2.2順序表基本操作初始化創(chuàng)建初始化創(chuàng)建是為順序表分配一段預(yù)定義大小的連續(xù)空間，用listItem記錄首地址。初始化元素個(gè)數(shù)不超過最大分配空間即可，如算法2.1和圖2.2所示。2.2.2順序表基本操作

2.2.2順序表基本操作

2.2.2順序表基本操作查找順序表查找元素是指在順序表中查找與指定關(guān)鍵字key是否有相等的元素。如圖2.3所示查找與關(guān)鍵字相同的元素8，若找到則返回其位置，否則返回最后的-1。倘若查找的是3則返回1，查找的是5則返回3。那么如何實(shí)現(xiàn)的呢？我們來看看算法2.2。2.2.2順序表基本操作【算法2.2】在順序表中查找首次出現(xiàn)的元素8，若找到則返回其位置；若沒找到則返回-1。思路:（1）從第1個(gè)元素開始順序查找，依次比較每一個(gè)元素值。（2）若相等則找到，可返回元素位置。

（3）若遍歷完順序表都沒找到，則查找失敗，可返回-1。代碼見算法2_22.2.2順序表基本操作

2.2.2順序表基本操作【算法2.3】在順序表的i=2處插入元素7。思路：（1）如果順序表已滿，拋出異常；

（2）如果插入的位置超出[0,curLen]范圍，則拋出異常；

（3）如果i=curLen，則直接插入，否則執(zhí)行（4）；

（4）從順序表最后1個(gè)元素開始依次往后移動(dòng)，直到位置i上的元素移動(dòng)；

（5）將元素elem插入到位置i處；

（6）將curLen加1，插入成功返回ture，否則返回false。代碼見算法2_32.2.2順序表基本操作刪除順序表刪除元素是指在順序表中若找到要?jiǎng)h除的元素elem則將其刪除，若沒找到則刪除失敗。如圖2.5所示刪除元素7前后的對比。若要?jiǎng)h除元素7，又如何實(shí)現(xiàn)的呢？我們來看看算法2.4。2.2.2順序表基本操作

2.3單鏈表由于鏈表的存儲(chǔ)在物理上元素之間可以連續(xù)也可以不連續(xù)，體現(xiàn)元素之間的關(guān)聯(lián)就需要附加1個(gè)指針域next，除了數(shù)據(jù)與data外。只有1個(gè)指針域指向其后繼的鏈表叫單鏈表，如圖2.6所示，其中指針域next也是單鏈表節(jié)點(diǎn)類型，這種結(jié)構(gòu)稱為遞歸結(jié)構(gòu)定義；符號(hào)“∧”表示空。2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)單鏈表存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)方式，邏輯上相鄰的元素物理存儲(chǔ)位置不一定相鄰，元素存儲(chǔ)是離散的。由這種結(jié)構(gòu)特點(diǎn)可知，單鏈表不能隨機(jī)存取，查找效率低，但刪除和插入元素時(shí)，不需要移動(dòng)大量元素，效率高。舉例：教室里的學(xué)生并沒有按照學(xué)號(hào)順序依次坐，中間空位也多，不必連續(xù)，這叫入座自由！老師考勤，讓學(xué)生從小到大自報(bào)學(xué)號(hào)后2位，你看看“遍地開花”！為什么亂坐現(xiàn)象能夠順序點(diǎn)名？因?yàn)槊總€(gè)學(xué)生的學(xué)號(hào)（加1）可以看作指向下一個(gè)學(xué)生的指針，上一個(gè)學(xué)生找到了那么下一個(gè)學(xué)生也就找到了，與他們之間所坐的物理位置無關(guān)！在這個(gè)例子中，教室里的學(xué)生可以看作構(gòu)成單鏈表的節(jié)點(diǎn)元素，所有學(xué)生構(gòu)成單鏈表。2.3.2單鏈表基本操作單鏈表節(jié)點(diǎn)類Node描述單鏈表類LinkList描述2.3.2單鏈表基本操作1.初始化單鏈表初始化操作是指創(chuàng)建一個(gè)空表?？毡硗挥蓄^節(jié)點(diǎn)head，不存儲(chǔ)數(shù)據(jù)，頭節(jié)點(diǎn)的指針域?yàn)榭?，如下圖所示。頭節(jié)點(diǎn)的作用：（1）找到相應(yīng)的單鏈表，好比穿衣服抓到衣領(lǐng)；（2）方便一些從頭節(jié)點(diǎn)開始的操作如遍歷查找。2.3.2單鏈表基本操作【算法2.5】單鏈表初始化。publicvoidalgorithm2_5(Objectelem)throwsException{

LinkList=newLinkList(); //創(chuàng)建單鏈表

System.out.println(linkList.head.data);//驗(yàn)證單鏈表頭節(jié)點(diǎn)數(shù)據(jù)域空

System.out.println(linkList.head.next);//驗(yàn)證單鏈表頭節(jié)點(diǎn)指針域空

}

算法2.5，用單鏈表類的不帶參數(shù)的構(gòu)造方法創(chuàng)建了只有頭節(jié)點(diǎn)的單鏈表空表，且頭節(jié)點(diǎn)不包含任何內(nèi)容。2.3.2單鏈表基本操作2.插入單鏈表插入操作是指將節(jié)點(diǎn)s插入節(jié)點(diǎn)p的后面。如圖2.8所示的插入過程又如何實(shí)現(xiàn)的呢？我們來看看算法2.6。2.3.2單鏈表基本操作【算法2.6】在帶頭節(jié)點(diǎn)的單鏈表中將節(jié)點(diǎn)s插入到節(jié)點(diǎn)p之后。思路：（1）從單鏈表頭節(jié)點(diǎn)開始遍歷，尋找節(jié)點(diǎn)p；（2）若遍歷完之后沒找到，則返回false，否則執(zhí)行（3）；（3）若節(jié)點(diǎn)p是尾節(jié)點(diǎn)，則將p的next指向s，s的next置為null，返回true；（4）若節(jié)點(diǎn)p不是尾節(jié)點(diǎn)，則將節(jié)點(diǎn)s的next指向節(jié)點(diǎn)p原來的后繼；將節(jié)點(diǎn)p的next指向節(jié)點(diǎn)s，返回true。代碼見算法2_6（）2.3.2單鏈表基本操作【思考與練習(xí)2.1】在圖2.8中，2個(gè)新增的指針（見①②），賦值的先后順序可否改變，即s.next=p.next;與p.next=s;這2條語句可否交換順序，為什么？答：不能！如果交換順序，p.next=s;沒問題，節(jié)點(diǎn)p指向了插入后的節(jié)點(diǎn)s，但s.next=p.next;就是s指向自己，因?yàn)榇藭r(shí)的p指向的是s，而非原來的后繼。所以只能按照順序進(jìn)行操作。2.3.2單鏈表基本操作3.整表創(chuàng)建單鏈表整表創(chuàng)建操作是指一次性創(chuàng)建并初始化單鏈表一些元素，它可由尾插法和頭插法進(jìn)行整表創(chuàng)建。顧名思義，尾插法是將插入元素始終在單鏈表的尾部插入；頭插法是將插入元素始終在單鏈表的頭部插入。舉例：請1到5學(xué)號(hào)的同學(xué)依次上講臺(tái)來，從左到右的面向方向：1號(hào)上來，2號(hào)在1號(hào)后面，3號(hào)在2號(hào)后面，依次類推，最后排列的順序與上來的順序一樣；再來一遍，上來的順序不變，1號(hào)上來，2號(hào)在1號(hào)的前面，3號(hào)在2號(hào)的前面，依次類推，最后排列的順序與上來的順序相反。通過這個(gè)例子，顯然我們得知：尾插法的結(jié)果是順序/正序，頭插法的結(jié)果是逆序/倒序。2.3.2單鏈表基本操作如圖2.9所示，每產(chǎn)生1個(gè)新節(jié)點(diǎn)s，始終將其插入單鏈表的尾部或頭部（頭節(jié)點(diǎn)head之后）。那么又如何實(shí)現(xiàn)尾插法和頭插法整體建表的呢？我們來看看算法2.7和算法2.8。2.3.2單鏈表基本操作【算法2.7】用尾插法創(chuàng)建單鏈表。思路：（1）移動(dòng)指針t指向頭節(jié)點(diǎn)head；（2）在t的后面插入單鏈表新節(jié)點(diǎn)s；（3）t移動(dòng)到s；（4）重復(fù)執(zhí)行（2）、（3），直到數(shù)組a遍歷完；（5）置t的指針域?yàn)閚ull。代碼見算法2_7()2.3.2單鏈表基本操作【算法2.8】用頭插法創(chuàng)建單鏈表。思路：（1）遍歷數(shù)組a，每次產(chǎn)生1個(gè)單鏈表新節(jié)點(diǎn)s；（2）在單鏈表的頭節(jié)點(diǎn)head之后插入s；（3）重復(fù)執(zhí)行（1）、（2），直到數(shù)組a遍歷完。代碼見算法2_8()（備注：游戲視頻演示細(xì)節(jié)有問題，請同學(xué)指出）2.3.2單鏈表基本操作【思考與練習(xí)2.2】可否利用算法2.6實(shí)現(xiàn)單鏈表的尾插法和頭插法？答：可以的。在尾插法中，始終將節(jié)點(diǎn)p置為尾節(jié)點(diǎn)，遍歷數(shù)組a時(shí)調(diào)用算法2.6進(jìn)行插入；在頭插法中，始終將節(jié)點(diǎn)p置為頭節(jié)點(diǎn)head，遍歷數(shù)組a時(shí)調(diào)用算法2.6進(jìn)行插入。如thinkpad2_2算法。2.3.2單鏈表基本操作4.取值單鏈表取值操作是指取到第i個(gè)元素的值，將其值返回；若沒取到則返回-1。舉例：我要找到教室里學(xué)號(hào)為18的學(xué)生，我可以讓學(xué)生從1號(hào)開始報(bào)號(hào)，直到報(bào)到18號(hào)。倘若要找學(xué)號(hào)為88的學(xué)生，報(bào)完了也找不到！因?yàn)槌鋈≈捣秶恕?.3.2單鏈表基本操作如圖2.10所示，要取到單鏈表中第i個(gè)元素的值ai，又如何實(shí)現(xiàn)的呢？我們來看看算法2.9。2.3.2單鏈表基本操作【算法2.9】單鏈表中取第i個(gè)元素的值。思路：（1）節(jié)點(diǎn)p設(shè)為從首節(jié)點(diǎn)開始遍歷單鏈表的指針，計(jì)數(shù)變量j初值為1；（2）每遍歷到1個(gè)節(jié)點(diǎn)時(shí)，判斷j是否等于i：若相當(dāng)則返回p指向節(jié)點(diǎn)的值；若不等則p繼續(xù)移動(dòng)，j加1；（3）重復(fù)（2），直到找到而返回，或遍歷完而沒找到返回-1。代碼見算法2_9()2.3.2單鏈表基本操作5.查找單鏈表查找操作是指在單鏈表中查找與指定關(guān)鍵字key是否相同的元素。單鏈表不能像順序表那樣隨機(jī)存取，所以查找過程是從頭節(jié)點(diǎn)或首節(jié)點(diǎn)開始依次遍歷比較的過程。如圖2.11所示，查找單鏈表中是否有key=“FanFan”的節(jié)點(diǎn)，若找到第1個(gè)這樣的節(jié)點(diǎn)則查找成功返回true；若沒找到則返回false。又如何實(shí)現(xiàn)的呢？我們來看看算法2.10。2.3.2單鏈表基本操作【算法2.10】單鏈表中查找key=“FanFan”的第1個(gè)節(jié)點(diǎn)。思路：（1）節(jié)點(diǎn)p設(shè)為從首節(jié)點(diǎn)開始遍歷單鏈表的指針；（2）取出p的數(shù)據(jù)域值，與指定關(guān)鍵字key比較：若相等則找到，返回true；若不相等則繼續(xù)找下一個(gè)元素，執(zhí)行（3）；（3）重復(fù)（2），直到找到而返回true，或遍歷完而沒找到返回false。代碼見算法2_10()2.3.2單鏈表基本操作6.刪除單鏈表刪除操作是指將單鏈表中位置為i的節(jié)點(diǎn)從單鏈表中刪除。單鏈表刪除操作有點(diǎn)像“跳過”要?jiǎng)h除的節(jié)點(diǎn)，好比a、b、c三人手拉手，ac牽手則b出去了，如圖2.12所示，要?jiǎng)h除i位置處的b節(jié)點(diǎn)，只需（i-1）位置處的a節(jié)點(diǎn)的指針域指向節(jié)點(diǎn)b的后繼c即可。那么代碼又如何實(shí)現(xiàn)的呢？我們來看看算法2.11。2.3.2單鏈表基本操作【算法2.11】單鏈表中刪除位置為i的b節(jié)點(diǎn)。思路：（1）設(shè)置1個(gè)移動(dòng)指針p，初始指向頭節(jié)點(diǎn)head；（2）將p移動(dòng)到（i-1）位置處；（3）將p指向的節(jié)點(diǎn)的指針域修改為該節(jié)點(diǎn)的后繼的后繼。代碼見算法2_11()2.4雙鏈表雙鏈表雙鏈表有2個(gè)指針域，顧名思義。比單鏈表在節(jié)點(diǎn)結(jié)構(gòu)上多了1個(gè)指針域prior：指向前驅(qū)的指針域，它解決了單鏈表只能向后操作的問題。雙鏈表的頭節(jié)點(diǎn)也有2個(gè)指針域，如圖2.13所示帶頭節(jié)點(diǎn)的雙鏈表邏輯結(jié)構(gòu)。2.4.1雙鏈表存儲(chǔ)結(jié)構(gòu)雙鏈表存儲(chǔ)結(jié)構(gòu)類同單鏈表，也是采用鏈?zhǔn)酱鎯?chǔ)方式，也有與單鏈表共同的特性如增刪節(jié)點(diǎn)高效。由于有2個(gè)指針域，所以雙鏈表既可以利用next指針域向后操作，也可以利用prior指針域向前操作。這一特性又可以改變一些單鏈表算法思路。2.4.1雙鏈表存儲(chǔ)結(jié)構(gòu)舉例：請5個(gè)同學(xué)上講臺(tái)，從左到右1到5編號(hào)。（1）單鏈表游戲表演：5個(gè)同學(xué)向左轉(zhuǎn)，雙手搭在下一個(gè)同學(xué)肩膀上（最后1個(gè)同學(xué)除外）；從1號(hào)開始，雙手使勁搖下2號(hào)肩膀，表示2號(hào)存活，2號(hào)再使勁去搖3號(hào)肩膀，3號(hào)存活，依此類推。其實(shí)我們要出局3號(hào)，2號(hào)一不小心搖了他，他又搖了4號(hào)，4號(hào)沒有對3號(hào)的生死權(quán)，游戲只得從頭再來。（2）雙鏈表游戲表演：5個(gè)同學(xué)面向教室手拉手，1號(hào)搖搖左手，2號(hào)存活，2號(hào)搖搖左手3號(hào)存活，3號(hào)搖搖左手，4號(hào)存活；4號(hào)或者此時(shí)的觀眾想起來了，3號(hào)要出局！莫慌，4號(hào)懶得搖搖右手了，直接去牽2號(hào)的左手，3號(hào)出局！倘若到5號(hào)才想起3號(hào)要出局，5號(hào)搖搖右手，4號(hào)冰雪聰明：牽2號(hào)左手！2.4.2雙鏈表基本操作雙鏈表節(jié)點(diǎn)類DuLNode描述雙鏈表類DuLinkList描述2.4.2雙鏈表基本操作1.初始化雙鏈表的初始化操作是指構(gòu)建1個(gè)空表，建頭節(jié)點(diǎn)而不存儲(chǔ)數(shù)據(jù)，頭節(jié)點(diǎn)的2個(gè)指針域皆為空，如圖2.14所示。

2.4.2雙鏈表基本操作【算法2.12】雙鏈表初始化。publicvoidalgorithm2_12(Objectelem)throwsException{

DuLinkListduLinkList=newDuLinkList();//創(chuàng)建雙鏈表

System.out.println(duLinkList.head.prior);//驗(yàn)證頭節(jié)點(diǎn)前驅(qū)域?yàn)榭?/p>

System.out.println(duLinkList.head.data);//驗(yàn)證頭節(jié)點(diǎn)數(shù)據(jù)域?yàn)榭?/p>

System.out.println(duLinkList.head.next);//驗(yàn)證頭節(jié)點(diǎn)后繼域?yàn)榭?/p>

}

算法2.12，用雙鏈表類的不帶參數(shù)的構(gòu)造方法創(chuàng)建了只有頭節(jié)點(diǎn)的雙鏈表空表，且頭節(jié)點(diǎn)不包含任何內(nèi)容。2.4.2雙鏈表基本操作2.插入雙鏈表插入操作同單鏈表插入操作，不同的是在插入過程中單鏈表改變的是2個(gè)指針，雙鏈表改變的是4個(gè)指針，除非是尾部插入和不帶頭節(jié)點(diǎn)的頭部插入。不妨仍將節(jié)點(diǎn)s插入節(jié)點(diǎn)p的后面，如圖2.15所示的插入過程又如何實(shí)現(xiàn)的呢？我們來看看算法2.13。2.4.2雙鏈表基本操作【算法2.13】在帶頭節(jié)點(diǎn)的雙鏈表中將節(jié)點(diǎn)s插入到節(jié)點(diǎn)p之后。思路：（1）從雙鏈表頭節(jié)點(diǎn)開始遍歷，尋找節(jié)點(diǎn)p；（2）若遍歷完之后沒找到，則返回false，否則執(zhí)行（3）；（3）若節(jié)點(diǎn)p是尾節(jié)點(diǎn)，則將p的next指向s；將s的prior指向p；將s的next置為null，返回true；（4）若節(jié)點(diǎn)p不是尾節(jié)點(diǎn)，則將節(jié)點(diǎn)s的next指向節(jié)點(diǎn)p原來的后繼；將節(jié)點(diǎn)p原來的后繼的prior指向s；將節(jié)點(diǎn)s的prior指向p；將節(jié)點(diǎn)p的next指向s；返回true。代碼見算法2.132.4.2雙鏈表基本操作【思考與練習(xí)2.3】在雙鏈表的插入操作中，若節(jié)點(diǎn)p是節(jié)點(diǎn)s的后繼，能否實(shí)現(xiàn)插入，若不能為什么；若可以又如何實(shí)現(xiàn)？答：可以！如圖2.16所示，從左到右4個(gè)指針分別執(zhí)行①②④③，也可以是①③④②。如下面的算法：publicvoidthinkPad2_3()throwsException{

//雙鏈表，由后繼或者在當(dāng)前節(jié)點(diǎn)處插入操作的主要代碼：

/*

s.prior=p.prior;

p.prior.next=s;

s.next=p;

p.prior=s;

*/

}

在雙鏈表的插入操作中，可以隨便改變4個(gè)指針更新的順序嗎？答：不能！同單鏈表，見【思考與練習(xí)2.1】解答。2.4.2雙鏈表基本操作3.整表創(chuàng)建雙鏈表整表創(chuàng)建操作同單鏈表整表創(chuàng)建操作，也可由尾插法和頭插法進(jìn)行整表創(chuàng)建。不同的是，它更新的指針更多。那么又如何實(shí)現(xiàn)的呢？我們來看看算法2.14和2.15?！舅惴?.14】用尾插法創(chuàng)建雙鏈表。思路：（1）移動(dòng)指針t指向頭節(jié)點(diǎn)head；（2）在t的后面插入雙鏈表新節(jié)點(diǎn)s；（3）t移動(dòng)到s；（4）重復(fù)執(zhí)行（2）、（3），直到數(shù)組a遍歷完；（5）置t的指針域?yàn)閚ull。代碼見算法2.142.4.2雙鏈表基本操作【算法2.15】用頭插法創(chuàng)建雙鏈表。思路：（1）遍歷數(shù)組a，每次產(chǎn)生1個(gè)雙鏈表新節(jié)點(diǎn)s；（2）在雙鏈表的頭節(jié)點(diǎn)head之后插入s；（3）重復(fù)執(zhí)行（1）、（2），直到數(shù)組a遍歷完。代碼見算法2.15同單鏈表整表創(chuàng)建一樣，雙鏈表整表創(chuàng)建也可以多次調(diào)用其“插入”函數(shù)高級(jí)編程實(shí)現(xiàn)。2.4.2雙鏈表基本操作4.取值雙鏈表取值操作同單鏈表取值操作，不同的是雙鏈表取值可以從前開始，也可以從后開始取值，由于雙鏈表雙向操作特點(diǎn)?！舅惴?.16】雙鏈表中取第i個(gè)元素的值。思路：（1）節(jié)點(diǎn)p設(shè)為從首節(jié)點(diǎn)開始遍歷雙鏈表的指針，計(jì)數(shù)變量j初值為1；（2）每遍歷到1個(gè)節(jié)點(diǎn)時(shí)，判斷j是否等于i：若相當(dāng)則返回p指向節(jié)點(diǎn)的值；若不等則p繼續(xù)移動(dòng)，j加1；（3）重復(fù)（2），直到找到而返回，或遍歷完而沒找到返回-1。代碼見算法2.162.4.2雙鏈表基本操作【思考與練習(xí)2.4】在雙鏈表的取值操作中，如果當(dāng)前節(jié)點(diǎn)p為尾節(jié)點(diǎn)，取值節(jié)點(diǎn)的位置i靠近尾節(jié)點(diǎn)，顯然這種情況從“尾”開始比從“頭”開始好！那么如何實(shí)現(xiàn)從尾節(jié)點(diǎn)開始逆向遍歷取到節(jié)點(diǎn)值呢？答：如下面的算法：publicObjectthinkPad2_4(inti)throwsException{

DuLinkListduLinkList=newDuLinkList();//創(chuàng)建空雙鏈表

//假設(shè)雙鏈表中初始化了一些元素（略）

intlength=0;//雙鏈表長度

DuLNodep=duLinkList.head;//p為移動(dòng)指針，初始指向頭節(jié)點(diǎn)

while(p.next!=null){

length++;

p=p.next;

}//置p為尾節(jié)點(diǎn)，并計(jì)算出雙鏈表長度

intj=length;

while(p!=null){//未遍歷完單鏈表

if(j==i)//找到

returnp.data;

else{//還沒找到

p=p.prior;//繼續(xù)往前找

j--;//計(jì)數(shù)變量減1，逆向遍歷

}

}

return-1;//沒找到返回-1

}

2.4.2雙鏈表基本操作留意：遍歷鏈表時(shí)注意循環(huán)條件，如p.next！=null和p！=null兩個(gè)條件，在最后遍歷完鏈表后，當(dāng)前指針p位置是不同的，前者最后指向尾節(jié)點(diǎn)，后者最后為null（指向尾節(jié)點(diǎn)之后）。2.4.2雙鏈表基本操作5.查找雙鏈表查找操作同單鏈表查找操作，不同的是雙鏈表可以雙向查找。如圖2.17所示，查找雙鏈表中是否有key=“Vivian”的元素，假設(shè)這個(gè)元素若存在則是唯一的，且在中間位置偏左一點(diǎn)；若找到則返回true，否則返回false。那么又如何實(shí)現(xiàn)的呢？我們來看看算法2.17。2.4.2雙鏈表基本操作【算法2.17】雙鏈表中查找中間位置偏左一點(diǎn)且key=“Vivian”的節(jié)點(diǎn)。思路：（1）準(zhǔn)備1個(gè)帶節(jié)點(diǎn)編號(hào)的雙鏈表，并初始化一些數(shù)據(jù)；（2）假設(shè)當(dāng)前指針p已經(jīng)走到雙鏈表的中間位置；（3）取出p的數(shù)據(jù)域值，與指定關(guān)鍵字key比較：若相等則找到，返回true；若不相等則向前移動(dòng)1個(gè)位置，執(zhí)行（4）；（4）重復(fù)（3），直到找到而返回true。代碼見算法2.172.4.2雙鏈表基本操作6.刪除雙鏈表刪除操作同單鏈表同單鏈表刪除操作，不同的是雙鏈表刪除操作可以從被刪除節(jié)點(diǎn)的前驅(qū)進(jìn)行，也可以從其后繼進(jìn)行。如圖2.18所示通過被刪除節(jié)點(diǎn)的前驅(qū)或后繼p進(jìn)行刪除，那么代碼又如何實(shí)現(xiàn)的呢？我們來看看算法2.18。2.4.2雙鏈表基本操作【算法2.18】雙鏈表中刪除位置為i的b節(jié)點(diǎn)。思路：（1）設(shè)置1個(gè)移動(dòng)指針p，初始指向頭節(jié)點(diǎn)head；（2）將p移動(dòng)到（i-1）或（i+1）位置處；（3）p為被刪節(jié)點(diǎn)的前驅(qū)時(shí)：a.p后繼的后繼的prior指向p；b.p的next指向后繼的后繼。p為被刪節(jié)點(diǎn)的后繼時(shí)：a.p的前驅(qū)的前驅(qū)的next指向p；b.p的prior指向前驅(qū)的前驅(qū)。代碼見算法2.182.4.2雙鏈表基本操作【思考與練習(xí)2.5】在圖2.18中，①和②的操作順序是否可以交換，為什么？答：可以，因?yàn)橹羔樣蜃兓皇苡绊?。不過建議先操作離當(dāng)前節(jié)點(diǎn)p較遠(yuǎn)的操作，即遵循“遠(yuǎn)端優(yōu)先操作”原則。如下面的算法：publicvoidthinkPad2_5()throwsException{

//p為被刪節(jié)點(diǎn)前驅(qū)，①和②交換：

/*

p.next=p.next.next;//p的next指向后繼的后繼

p.next.next.prior=p;//p后繼的后繼的prior指向p

*/

//p為被刪節(jié)點(diǎn)后繼，①和②交換：

/*

p.prior=p.prior.prior;//p的prior指向前驅(qū)的前驅(qū)

p.prior.prior.next=p;//p的前驅(qū)的前驅(qū)的next指向p

*/

}2.5循環(huán)鏈表循環(huán)鏈表是在之前所講的單鏈表、雙鏈表的基礎(chǔ)上改進(jìn)而得的鏈表。由單鏈表改進(jìn)得到循環(huán)單鏈表，由雙鏈表改進(jìn)得到循環(huán)雙鏈表。它們的改進(jìn)有個(gè)共同特點(diǎn)：首尾相連，形成環(huán)。為了更好區(qū)分這4種鏈表，見下面的例子。舉例：請5個(gè)同學(xué)自告奮勇上臺(tái)。第1個(gè)動(dòng)作：站成一排，除最后1個(gè)同學(xué)外，其他同學(xué)的左手搭在左旁同學(xué)肩上。第2個(gè)動(dòng)作：站成一排，手拉手吧！第3個(gè)動(dòng)作：圍成圈，左手搭在左旁同學(xué)肩上。第4個(gè)動(dòng)作：圍成圈，手拉手。通過這個(gè)例子我們可以很形象而生動(dòng)地認(rèn)識(shí)到，4個(gè)動(dòng)作分別說的就是單鏈表、雙鏈表、循環(huán)單鏈表、循環(huán)雙鏈表，大概括?。?.5循環(huán)鏈表循環(huán)單鏈表和循環(huán)雙鏈表的存儲(chǔ)結(jié)構(gòu)與單鏈表和雙鏈表的存儲(chǔ)結(jié)構(gòu)相同。2.5.1循環(huán)單鏈表循環(huán)單鏈表的尾節(jié)點(diǎn)的next不再為空，是指向頭節(jié)點(diǎn)，這樣使整個(gè)單鏈表形成環(huán)；若只有頭節(jié)點(diǎn)的空表，頭節(jié)點(diǎn)的next也指向頭節(jié)點(diǎn)自身。如圖2.19所示。2.5.1循環(huán)單鏈表循環(huán)單鏈表的節(jié)點(diǎn)類與單鏈表的節(jié)點(diǎn)類相同，鏈表類和基本操作相似，主要不同在于：循環(huán)單鏈表需通過head.next=head;語句置空表；判斷尾節(jié)點(diǎn)時(shí)不再是單鏈表的p.next==null;而是p.next==head;語句。2.5.1循環(huán)單鏈表循環(huán)單鏈表類CLinkList的描述2.5.2循環(huán)雙鏈表循環(huán)雙鏈表的尾節(jié)點(diǎn)的next也指向頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的prior不再為空，是指向尾節(jié)點(diǎn)，這樣使整個(gè)雙鏈表形成環(huán)；若只有頭節(jié)點(diǎn)的空表，頭節(jié)點(diǎn)的next和prior皆指向頭節(jié)點(diǎn)自身。如圖2.20所示。2.5.2循環(huán)雙鏈表循環(huán)雙鏈表與雙鏈表的節(jié)點(diǎn)類相同，鏈表類和基本操作相似，主要不同在于：循環(huán)雙鏈表需通過head.next=head;和head.prior=head;語句置空表；判斷尾節(jié)點(diǎn)時(shí)不再是雙鏈表的p.next==null;而是p.next==head;語句。，2.5.2循環(huán)雙鏈表循環(huán)雙鏈表類CDuLinkList的描述2.6線性表應(yīng)用2.6.1順序表應(yīng)用【例2.1】將含有n個(gè)元素的有序順序表S中的所有元素逆置。如S=（1,2,3,4,5），逆置后S=（5,4,3,2,1），并分析算法的時(shí)空復(fù)雜度。思路：（1）雙指針設(shè)置：頭指針i和尾指針j；（2）交換它們所指向的元素后；（3）i++且j--，若i<j則執(zhí)行（2），否則結(jié)束。代碼見例2.1算法2.6.1順序表應(yīng)用【進(jìn)一步思考】請寫出實(shí)現(xiàn)例2.1算法的其他思路。答：（1）逆序遍歷思路（2）入棧和出棧思路。等等。2.6.1順序表應(yīng)用【例2.2】將含有n個(gè)整數(shù)元素的順序表S中相鄰重復(fù)元素刪掉，只保留1個(gè)。如S=（1,3,3,4,1），刪除后S=（1,3,4,1），并分析算法的時(shí)空復(fù)雜度。思路：（1）新建一個(gè)順序表，將原順序表第1個(gè)元素插入；（2）從原順序表第2個(gè)元素開始遍歷，比較新順序表中尾元素：若相等則繼續(xù)遍歷，若不相等則將其插入到新表中；（3）直到原順序表遍歷完成。代碼見例2.2算法2.6.1順序表應(yīng)用【進(jìn)一步思考】請寫出實(shí)現(xiàn)例2.2算法的其他思路。答：第1次遍歷找到相鄰相同的元素，第2次遍歷相鄰不相同的元素與之合并。等等。2.6.2單鏈表應(yīng)用【例2.3】將含有n個(gè)元素的有序單鏈表L中的所有元素逆置。如L=（1,2,3,4,5），逆置后L=（5,4,3,2,1），并分析算法的時(shí)空復(fù)雜度。思路：（1）p指向單鏈表首節(jié)點(diǎn)；（2）置L為空單鏈表；（3）遍歷L，將p插入到L的頭部。代碼見例2.3算法2.6.2單鏈表應(yīng)用【進(jìn)一步思考】請寫出實(shí)現(xiàn)例2.3算法的其他思路。答：（1）頭尾雙指針交換，同例2.1算法思路(雙鏈表而言)（2）順序遍歷入棧，再出棧尾插法成單鏈表思路。等等。2.6.2單鏈表應(yīng)用【例2.4】將2個(gè)遞增有序整數(shù)單鏈表A和B合并為C，C也是遞增有序單鏈表，并分析算法的時(shí)空復(fù)雜度。思路：（1）采用二路歸并和尾插法思想，在同時(shí)遍歷A和B時(shí)，比較元素大??；（2）將