數(shù)據(jù)結(jié)構(gòu)與算法（Java語(yǔ)言版）課件 第5、6章 鏈表與LinkedList類(lèi)、順序表與ArrayList類(lèi)

第5章鏈表與LinkedList類(lèi)2024/11/915.1鏈表的特點(diǎn)2024/11/92鏈表是由若干個(gè)節(jié)點(diǎn)組成，這些節(jié)點(diǎn)形成的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是鏈?zhǔn)酱鎯?chǔ)，即節(jié)點(diǎn)的物理地址不必是依次相鄰的。對(duì)于單鏈表，每個(gè)結(jié)點(diǎn)含有一個(gè)數(shù)據(jù)，并含有下一個(gè)節(jié)點(diǎn)的引用。對(duì)于雙鏈表，每個(gè)節(jié)點(diǎn)含有一個(gè)數(shù)據(jù)，并含有上一個(gè)節(jié)點(diǎn)的引用和下一個(gè)結(jié)點(diǎn)的引用（Java實(shí)現(xiàn)的是雙鏈表）2024/11/935.1鏈表的特點(diǎn)圖示意的是有5個(gè)節(jié)點(diǎn)的雙鏈表（省略了上一個(gè)節(jié)點(diǎn)的引用箭頭示意）。注意，鏈表的節(jié)點(diǎn)序號(hào)是從0開(kāi)始，每個(gè)節(jié)點(diǎn)的序號(hào)等于它前面的節(jié)點(diǎn)的個(gè)數(shù)。鏈表中的節(jié)點(diǎn)的物理地址不必是相鄰的，因此，鏈表的優(yōu)點(diǎn)是不需要占用一塊連續(xù)的內(nèi)存存儲(chǔ)空間。圖5.12024/11/945.1鏈表的特點(diǎn)

●刪除頭、尾節(jié)點(diǎn)的復(fù)雜度O(1)刪除前面所示意5個(gè)節(jié)點(diǎn)的的鏈表的頭節(jié)點(diǎn)(大象-節(jié)點(diǎn))后的示意圖。2024/11/955.1鏈表的特點(diǎn)

●查詢(xún)頭、尾節(jié)點(diǎn)的復(fù)雜度O(1)查詢(xún)獅子和鱷魚(yú)的時(shí)間復(fù)雜度都是O(1)。2024/11/965.1鏈表的特點(diǎn)

●添加頭尾節(jié)點(diǎn)的復(fù)雜度O(1)要給圖5.1所示意的鏈表的添加新的尾節(jié)點(diǎn)（企鵝-節(jié)點(diǎn)），根據(jù)雙鏈表保存的尾節(jié)點(diǎn)的地址，找到尾節(jié)點(diǎn)（鱷魚(yú)-節(jié)點(diǎn)），將這個(gè)尾節(jié)點(diǎn)中的下一個(gè)節(jié)點(diǎn)的引用設(shè)置成新添加的節(jié)點(diǎn)（企鵝-節(jié)點(diǎn)）的引用，將添加的新節(jié)點(diǎn)（企鵝-節(jié)點(diǎn)）中的上一個(gè)節(jié)點(diǎn)的引用設(shè)置成鱷魚(yú)-節(jié)點(diǎn)的引用，將添加的新節(jié)點(diǎn)（企鵝-節(jié)點(diǎn)）中的下一個(gè)節(jié)點(diǎn)的引用設(shè)置成null，即讓新添加的節(jié)點(diǎn)成為尾結(jié)點(diǎn)。2024/11/975.1鏈表的特點(diǎn)●查詢(xún)中間節(jié)點(diǎn)的時(shí)間復(fù)雜度O(n)鏈表的節(jié)點(diǎn)的物理地址不是相鄰的，節(jié)點(diǎn)通過(guò)互相保存引用鏈接在一起。

2024/11/985.1鏈表的特點(diǎn)●刪除中間節(jié)點(diǎn)的復(fù)雜度O(n)鏈表的節(jié)點(diǎn)的物理地址不是相鄰的，節(jié)點(diǎn)通過(guò)互相保存引用鏈接在一起。

刪除了老虎-節(jié)點(diǎn)2024/11/995.1鏈表的特點(diǎn)●插入中間節(jié)點(diǎn)的復(fù)雜度O(n)

插入新節(jié)點(diǎn)后，新鏈表中的節(jié)點(diǎn)序號(hào)按新的鏈表長(zhǎng)度從0開(kāi)始排列。2024/11/9105.1鏈表的特點(diǎn)●插入中間節(jié)點(diǎn)的復(fù)雜度O(n)圖5.1的鏈表中插入新的第2個(gè)節(jié)點(diǎn)（羚羊-節(jié)點(diǎn)）5.2創(chuàng)建鏈表2024/11/911鏈表由Java集合框架（JavaCollectionsFramework，JCF）中的LinkedList<E>泛型類(lèi)所實(shí)現(xiàn)。2024/11/9125.2創(chuàng)建鏈表LinkedList<E>泛型類(lèi)實(shí)現(xiàn)了Java集合框架中的List和Queue泛型接口。LinkedLis<E>t泛型類(lèi)繼承了List和Queue泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了List和Queue泛型接口中的抽象方法。2024/11/9135.2創(chuàng)建鏈表例子1Example5_1.java使用LinkedList<E>泛型類(lèi)聲明鏈表時(shí)，必須要指定E的具體類(lèi)型，類(lèi)型是類(lèi)或接口類(lèi)型（不可以是基本類(lèi)型，比如int、float、char等），即指定鏈表中節(jié)點(diǎn)里的對(duì)象的類(lèi)型。例如，指定E是String類(lèi)型：LinkedList<String>listOne=newLinkedList<>();或LinkedList<String>listOne=newLinkedList<String>();例子1中的主類(lèi)Example5_1中首先創(chuàng)建一個(gè)空鏈表listOne，然后向空鏈表listOne添加4個(gè)節(jié)點(diǎn)，隨后再用listOne創(chuàng)建鏈表listTwo。修改listTwo節(jié)點(diǎn)的數(shù)據(jù)，并不影響listOne節(jié)點(diǎn)中的數(shù)據(jù)。5.3查詢(xún)與相等2024/11/914查詢(xún)鏈表節(jié)點(diǎn)中的數(shù)據(jù)的常用方法：

booleanequals(Objectlist)如果此鏈表和list長(zhǎng)度相同，并且對(duì)應(yīng)的每個(gè)節(jié)點(diǎn)中的對(duì)象也相等，那么方法返回true，否則返回flase。2024/11/9155.3查詢(xún)與相等例子2People.javaExample5_2.java例子2中的主類(lèi)Example5_2中比較了get(intindex)方法和getLast()方法的運(yùn)行時(shí)間。例子2中的People類(lèi)重寫(xiě)了booleanequals(Objecto)方法.2024/11/9165.3查詢(xún)與相等例子3RandomLayMines.javaExample5_3.java

主類(lèi)Example5_3使用layMines(char[][]area,intamount)方法布雷39顆。2024/11/9175.3查詢(xún)與相等例子4TeamGame.javaExample5_4.java

5.4添加2024/11/918鏈表添加節(jié)點(diǎn)常用方法：

2024/11/9195.4添加例子5Example5_5.java例子5中的主類(lèi)Example5_5中比較了voidaddLast(Ee)方法和voidadd(intindex,Ee)方法的運(yùn)行時(shí)間。5.5刪除2024/11/920鏈表刪除節(jié)點(diǎn)常用方法：

2024/11/9215.5刪除例子6RandomNumber.java例子6中RandomNumber類(lèi)的getRandom(intnumber,intamount)方法通過(guò)隨機(jī)刪除鏈表中的節(jié)點(diǎn)來(lái)得到若干個(gè)隨機(jī)數(shù)。Example5_6.java例子6中的主類(lèi)Exmple5_6使用RandomNumber類(lèi)的getRandom(intnumber,intamount)方法模擬雙色球，同時(shí)過(guò)濾一個(gè)鏈表。2024/11/9225.5刪除例子7HandleRecurring.javaExample5_7.java有時(shí)候需要處理數(shù)組中重復(fù)的數(shù)據(jù)，即讓重復(fù)的數(shù)據(jù)只保留一個(gè)。在某些場(chǎng)景下，數(shù)據(jù)重復(fù)屬于冗余問(wèn)題。冗余可能給具體的實(shí)際問(wèn)題帶來(lái)危害，比如，你在撰寫(xiě)一篇文章時(shí)，用編輯器同時(shí)打開(kāi)了一個(gè)文檔多次，那么有時(shí)候就會(huì)引起混亂。所以，應(yīng)當(dāng)只打開(kāi)文檔一次，以免在修改，保存文檔時(shí)發(fā)生數(shù)據(jù)處理不一致的情況。例子7中，HandleRecurring類(lèi)的handleRecurring(LinkedList<E>list)方法處理鏈表list中重復(fù)的數(shù)據(jù)，該方法返回的鏈表中沒(méi)有重復(fù)的數(shù)據(jù)（對(duì)于重復(fù)的數(shù)據(jù)，保留其中一個(gè)）。5.6更新2024/11/923鏈表更新節(jié)點(diǎn)的常用方法：

Collections類(lèi)的靜態(tài)方法static<T>voidfill(List<?superT>list,Tobj)將鏈表list的每個(gè)節(jié)點(diǎn)中的對(duì)象都設(shè)置為參數(shù)obj指定的對(duì)象。2024/11/9245.6更新例子8Example5_8.java例子8的主類(lèi)Example5_8使用set(intindex,Eelement)方法和fill(List<?superT>list,Tobj)方法更新鏈表節(jié)點(diǎn)中的對(duì)象。5.7鏈表的視圖2024/11/925鏈表的視圖是由鏈表中若干個(gè)節(jié)點(diǎn)所構(gòu)成，其狀態(tài)變化和鏈表是同步的。視圖的好處是，可以將經(jīng)常需要修改的節(jié)點(diǎn)放在一個(gè)視圖中，有利于數(shù)據(jù)的一致性處理。

使用視圖時(shí)，要注意視圖中節(jié)點(diǎn)和原鏈表節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系。2024/11/9265.7鏈表的視圖List<E>subList(intfromIndex,inttoIndex)方法是AbstractList類(lèi)所實(shí)現(xiàn)的List接口中的一個(gè)方法（AbstractList類(lèi)是LinkedList的間接父類(lèi)）。該方法返回一個(gè)當(dāng)前鏈表中節(jié)點(diǎn)序號(hào)fromIndex（含）和toIndex（不含）之間的節(jié)點(diǎn)構(gòu)成的視圖。需要特別注意的是，一旦鏈表添加或刪除節(jié)點(diǎn)，就會(huì)破壞視圖的索引，即會(huì)影響之前鏈表subList()方法返回的視圖，這個(gè)視圖將無(wú)法再繼續(xù)被使用（如果繼續(xù)使用，運(yùn)行時(shí)刻會(huì)觸發(fā)ConcurrentModificationException異常），鏈表必須用subList()方法重新返回一個(gè)新的視圖。更改視圖的節(jié)點(diǎn)（增加或刪除節(jié)點(diǎn)）或?qū)?jié)點(diǎn)的數(shù)據(jù)的修改都會(huì)使得當(dāng)前鏈表發(fā)生同步的改變。2024/11/9275.7鏈表的視圖使用視圖時(shí)，要注意視圖中節(jié)點(diǎn)和原鏈表節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系。原鏈表list中獅子節(jié)點(diǎn)是第1個(gè)節(jié)點(diǎn)，但在視圖listView中獅子節(jié)點(diǎn)是第0個(gè)節(jié)點(diǎn)，原鏈表list中老虎節(jié)點(diǎn)是第2個(gè)節(jié)點(diǎn)，但在視圖listView中老虎節(jié)點(diǎn)是第1個(gè)節(jié)點(diǎn)，原鏈表list中獵豹節(jié)點(diǎn)是第3個(gè)節(jié)點(diǎn)，但在視圖listView中獵豹節(jié)點(diǎn)是第2個(gè)節(jié)點(diǎn)。2024/11/9285.7鏈表的視圖使用視圖時(shí)，要注意視圖中節(jié)點(diǎn)和原鏈表節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系。如果視圖listView增加一個(gè)節(jié)點(diǎn)，比如尾節(jié)點(diǎn)：鬣狗那么原鏈表list會(huì)同步更新、發(fā)生變化，獵豹節(jié)點(diǎn)和河馬節(jié)點(diǎn)之間多了一個(gè)鬣狗節(jié)點(diǎn)：2024/11/9295.7鏈表的視圖例子9Example5_9.java例子9的主類(lèi)Example5_9使用鏈表的視圖更新鏈表節(jié)點(diǎn)中的天氣信息。5.8鏈表的排序2024/11/930publicdefaultvoidsort(Comparator<?superE>c)方法是List接口的默認(rèn)排序方法（default關(guān)鍵字修飾的方法），LinkedList繼承了該排序方法（去掉了關(guān)鍵字default）。該排序方法的參數(shù)c是Comparator泛型接口，Comparator泛型接口是一個(gè)函數(shù)接口，即此接口中的抽象方法只有一個(gè)：intcompare(Ta,Tb)，此方法比較兩個(gè)參數(shù)a和b的順序，返回值是正數(shù)表示a大于b，返回負(fù)數(shù)表示a小于b,返回零表示a等于b。2024/11/9315.8鏈表的排序Comparator是一個(gè)函數(shù)接口，因此在使用該方法時(shí)，可以向參數(shù)c傳遞一個(gè)Lambda表達(dá)式，該Lambda表達(dá)式必須是2個(gè)參數(shù)，Lambda表達(dá)式中必須有return語(yǔ)句，返回的值是int型數(shù)據(jù)（和其代表的intcompare(Ta,Tb)方法保持一致）。例如sort((a,b)->{if(a.height>b.height)return1;elseif(a.height<b.height)return-1;elsereturn0;})

2024/11/9325.8鏈表的排序例子10Student.java例子10的主類(lèi)Example5_10分別按學(xué)生的數(shù)學(xué)和英文成績(jī)升序排序鏈表、降序排序鏈表。Example5_10.java5.9遍歷鏈表2024/11/933某些集合根據(jù)其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和所具有的操作也會(huì)提供返回?cái)?shù)據(jù)的方法，例如LinkedList類(lèi)中的get(intindex)方法將返回當(dāng)前鏈表中第index節(jié)點(diǎn)中的對(duì)象。LinkedList的存儲(chǔ)結(jié)構(gòu)不是順序結(jié)構(gòu)，即節(jié)點(diǎn)的物理地址不必是依次相鄰的，因此，鏈表調(diào)用get(intindex)方法的速度比順序存儲(chǔ)結(jié)構(gòu)的集合調(diào)用get(intindex)方法的速度慢。當(dāng)用戶(hù)需要遍歷集合中的節(jié)點(diǎn)時(shí)，應(yīng)當(dāng)使用該集合提供的迭代器，而不是讓集合本身來(lái)遍歷其中的節(jié)點(diǎn)。2024/11/9345.9遍歷鏈表單向迭代器是從鏈表的頭節(jié)點(diǎn)開(kāi)始，遍歷到尾節(jié)點(diǎn)。●單向迭代器鏈表對(duì)象可以使用Iterator<E>iterator()方法獲取一個(gè)實(shí)現(xiàn)Iterator接口的對(duì)象，該對(duì)象就是針對(duì)當(dāng)前鏈表的單向迭代器。迭代器內(nèi)部使用了游標(biāo)技術(shù)，單向迭代器的游標(biāo)的初始狀態(tài)是指向鏈表的頭節(jié)點(diǎn)的前面，如果游標(biāo)可以向后移動(dòng)（向鏈表的尾節(jié)點(diǎn)方向），單向迭代器調(diào)用hasNext()方法返回true，否則返回false。連續(xù)的調(diào)用next()方法會(huì)將游標(biāo)移動(dòng)到尾節(jié)點(diǎn)，這時(shí)游標(biāo)將無(wú)法向后移動(dòng)，再調(diào)用next()方法否則觸發(fā)運(yùn)行異常NoSuchElementException（鏈表是空鏈表，直接調(diào)用next()方法也會(huì)觸發(fā)運(yùn)行異常NoSuchElementException）。2024/11/9355.9遍歷鏈表●雙向迭代器鏈表對(duì)象可以使用ListIterator<E>listIterator()方法獲取一個(gè)實(shí)現(xiàn)ListIterator接口的對(duì)象（ListIterator接口是Iterator的子接口），該對(duì)象就是針對(duì)當(dāng)前鏈表的雙向迭代器。雙單向迭代器是雙游標(biāo)迭代器，一個(gè)向后游標(biāo)（向鏈表的尾節(jié)點(diǎn)方向），一個(gè)向前游標(biāo)（向鏈表的頭節(jié)點(diǎn)方向）。雙游標(biāo)是同時(shí)移動(dòng)，向前游標(biāo)在向后游標(biāo)的后面。

初始狀態(tài)向后游標(biāo)指向頭節(jié)點(diǎn)的前面，向前游標(biāo)指向頭節(jié)點(diǎn)。2024/11/9365.9遍歷鏈表●遍歷與更新迭代器對(duì)鏈表實(shí)施的添加、刪除、更新節(jié)點(diǎn)等操作一直等到迭代器遍歷鏈表完畢再生效。雙向迭代器調(diào)用next()或previous()方法返回節(jié)點(diǎn)中的數(shù)據(jù)后，迭代器緊接著調(diào)用add(Eobj)方法，可以在該節(jié)點(diǎn)后插入一個(gè)節(jié)點(diǎn)（新節(jié)點(diǎn)序號(hào)從當(dāng)前節(jié)點(diǎn)開(kāi)始遞增），調(diào)用set(Eobj)方法可以更新該節(jié)點(diǎn)中的數(shù)據(jù)，調(diào)用remove()方法可以刪除該節(jié)點(diǎn)。單向迭代器在遍歷鏈表時(shí)也可以同時(shí)更新鏈表，但只能刪除節(jié)點(diǎn)。單向迭代器調(diào)用next()方法返回節(jié)點(diǎn)中的數(shù)據(jù)后，迭代器緊接著調(diào)用remove()方法可以刪除該節(jié)點(diǎn)。2024/11/9375.9遍歷鏈表●遍歷與鎖定單向或雙向迭代器在遍歷鏈表時(shí)，將不允許鏈表本身調(diào)用方法更改鏈表節(jié)點(diǎn)的結(jié)構(gòu)。單向或雙向迭代器在遍歷鏈表時(shí)，將不允許鏈表本身調(diào)用方法更改鏈表節(jié)點(diǎn)的結(jié)構(gòu)，即不允許鏈表調(diào)用方法增加節(jié)點(diǎn)、刪除節(jié)點(diǎn)、排序鏈表，但允許鏈表調(diào)用set(intindex，Eobj)方法更新節(jié)點(diǎn)中的數(shù)據(jù)，因?yàn)楦鹿?jié)點(diǎn)只是更新鏈表的節(jié)點(diǎn)中的數(shù)據(jù)，不屬于更改鏈表的節(jié)點(diǎn)的結(jié)構(gòu)。

在迭代器沒(méi)有結(jié)束遍歷之前，如果鏈表進(jìn)行增加節(jié)點(diǎn)、刪除節(jié)點(diǎn)、排序鏈表這些操作，程序運(yùn)行時(shí)（無(wú)編譯錯(cuò)誤）將觸發(fā)java.util.ConcurrentModificationException異常。程序必須等到迭代器被使用完畢，才允許鏈表調(diào)用add()、remove()方法添加、刪除節(jié)點(diǎn)或排序鏈表。2024/11/9385.9遍歷鏈表●for-each語(yǔ)句鏈表獲得迭代器后，在使用迭代器之前又對(duì)鏈表進(jìn)行了更新，比如添加、刪除或排序鏈表，那么就無(wú)法再使用該迭代器遍歷鏈表。如果想使用迭代器，就必須讓鏈表重新返回一個(gè)新的迭代器。使用for-each語(yǔ)句遍歷一個(gè)鏈表時(shí)，禁止當(dāng)前鏈表調(diào)用add()、remove()方法添加、刪除節(jié)點(diǎn)或排序鏈表，其原因是，for-each算法的內(nèi)部中啟用了迭代器。2024/11/9395.9遍歷鏈表例子11例子11的主類(lèi)Example5_11分別使用單向迭代器和雙向迭代器遍歷了鏈表，在遍歷的過(guò)程中也更新了鏈表。Example5_11.java2024/11/9405.9遍歷鏈表例子12約瑟夫問(wèn)題（也稱(chēng)圍圈留一問(wèn)題）：若干個(gè)人圍成一圈，從某個(gè)人開(kāi)始順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，然后繼續(xù)順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，依此類(lèi)推，程序輸出圈中最后剩下的一個(gè)人。Example5_12.javaLeaveOneAround.java這里例子12中的LeaveOneAround類(lèi)的leaveOne(LinkedList<Integer>people)方法通過(guò)遍歷鏈表，解決約瑟夫問(wèn)題：在遍歷鏈表的過(guò)程中刪除相應(yīng)的節(jié)點(diǎn)模擬出圈的人。2024/11/9415.9遍歷鏈表例子13一個(gè)遍歷鏈表的方法（算法）在遍歷鏈表時(shí)，讓鏈表的每個(gè)節(jié)點(diǎn)中的對(duì)象參與某種運(yùn)算，并輸出運(yùn)算后的結(jié)果，稱(chēng)這樣的遍歷方法為動(dòng)態(tài)遍歷方法。Example5_13.java●動(dòng)態(tài)遍歷publicdefaultvoidforEachRemaining(Consumer<?superE>action)方法是Iterator接口中的默認(rèn)方法，鏈表返回的迭代器（單向或雙向）可以使用該方法動(dòng)態(tài)的遍歷鏈表。此方法的參數(shù)類(lèi)型是Consumer函數(shù)接口，該接口中的抽象方法voidaccept(Tt)的返回類(lèi)型是void型。那么在調(diào)用此方法時(shí)，可以將一個(gè)Lambda表達(dá)式傳遞給action。2024/11/9425.9遍歷鏈表例子14Example5_14.java●動(dòng)態(tài)遍歷例子14的主類(lèi)Example5_14動(dòng)態(tài)遍歷節(jié)點(diǎn)中是數(shù)組的一個(gè)鏈表，在遍歷這個(gè)鏈表時(shí)，讓節(jié)點(diǎn)中的數(shù)組參與運(yùn)算，計(jì)算數(shù)組的元素值之和.鏈表的節(jié)點(diǎn)中可以是任何引用型的數(shù)據(jù)，例如類(lèi)，數(shù)組，接口等類(lèi)型的數(shù)據(jù)。第6章順序表與ArrayList類(lèi)2024/11/9436.1順序表的特點(diǎn)2024/11/944順序表也是線性表的一種具體體現(xiàn)，順序表節(jié)點(diǎn)形成的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)、節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)，即節(jié)點(diǎn)的物理地址是依次相鄰的。2024/11/9456.1順序表的特點(diǎn)順序表使用數(shù)組來(lái)實(shí)現(xiàn)，順序表的節(jié)點(diǎn)的物理地址是依次相鄰的，因此可以隨機(jī)訪問(wèn)任何一個(gè)節(jié)點(diǎn)，不必從頭節(jié)點(diǎn)計(jì)數(shù)查找其它節(jié)點(diǎn)?！癫樵?xún)節(jié)點(diǎn)

2024/11/9466.1順序表的特點(diǎn)和鏈表不同，順序表沒(méi)有單獨(dú)添加頭節(jié)點(diǎn)的操作，但是有添加尾節(jié)點(diǎn)的操作?！裉砑庸?jié)點(diǎn)

2024/11/9476.1順序表的特點(diǎn)

●刪除節(jié)點(diǎn)

6.2創(chuàng)建順序表2024/11/948順序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayList<E>泛型類(lèi)所實(shí)現(xiàn)。2024/11/9496.2創(chuàng)建順序表ArrayList<E>泛型類(lèi)的實(shí)列使用數(shù)組管理節(jié)點(diǎn)，因此節(jié)點(diǎn)就是對(duì)象，后面的敘述不再說(shuō)節(jié)點(diǎn)里的對(duì)象。ArrayList<E>泛型類(lèi)實(shí)現(xiàn)了Java集合框架中的List泛型接口(和鏈表不同，沒(méi)有實(shí)現(xiàn)Queue泛型接口)。ArrayList<E>泛型類(lèi)繼承了List泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了List泛型接口中的抽象方法。2024/11/9506.2創(chuàng)建順序表順序表可以使用add(Eobj)方法向順序表依次增加節(jié)點(diǎn)。創(chuàng)建空順序表，使用ArrayList<E>泛型類(lèi)聲明順序表時(shí)，必須要指定E的具體類(lèi)型，類(lèi)型是類(lèi)或接口類(lèi)型（不可以是基本類(lèi)型，比如int、float、char等）即指定順序表中節(jié)點(diǎn)（對(duì)象）的類(lèi)型。例如，指定E是String類(lèi)型：ArrayList<String>arrlistOne=newArrayList<>();或ArrayList<String>arrlistOne=newArrayList<String>();例子1Example6_1.java例子1中的主類(lèi)Example6_1中首先創(chuàng)建一個(gè)空順序表arrlistOne，然后向空鏈表arrlistOne添加3個(gè)節(jié)點(diǎn)，隨后再用arrlistOne中的節(jié)點(diǎn)創(chuàng)建順序表arrlistTwo。修改arrlistTwo的節(jié)點(diǎn)，并不影響arrlistOne的節(jié)點(diǎn).6.3順序表常用方法2024/11/951voidadd(intindex,Ee)向順序表的index指定位置添加一個(gè)新的節(jié)點(diǎn)e（時(shí)間復(fù)雜度O(n)）。publicbooleancontains(Objectobj)判斷順序表中是否有對(duì)象obj，如果有節(jié)點(diǎn)是對(duì)象obj返回true，否則返回false(時(shí)間復(fù)雜度O(n))。

Eremove(intindex)返回順序表的第index節(jié)點(diǎn)，并刪除順序表的第index節(jié)點(diǎn)（時(shí)間復(fù)雜度O(n)）。booleanremove(Objecto)刪除順序表中首次出現(xiàn)是obj的節(jié)點(diǎn)，刪除成功返回true，否則返回false（時(shí)間復(fù)雜度O(n)）。2024/11/9526.3

順序表常用方法例子2Example6_2.java例子2中的主類(lèi)Example6_2中比較了順序表的get(intindex)方法和鏈表的get(intindex)方法的運(yùn)行耗時(shí)，可以看出順序表的耗時(shí)明顯小于鏈表的耗時(shí)。2024/11/9536.3順序表常用方法例子3Example6_3.java例子3的主類(lèi)Example6_3使用了順序表的一些常用方法.booleanremoveIf(Predicate<?superE>filter)刪除滿(mǎn)足filter給出的條件的全部節(jié)點(diǎn)（時(shí)間復(fù)雜度O(n)）。Predicate是一個(gè)函數(shù)接口，其中唯一的抽象方法是booleantest(Tt)，在使用removeIf(Predicate<?superE>filter)方法時(shí)，可以將一個(gè)Lambda表達(dá)式傳遞給參數(shù)filter，該Lambda表達(dá)式的有一個(gè)參數(shù)，類(lèi)型和節(jié)點(diǎn)類(lèi)型一致，Lambda表達(dá)式的返回值類(lèi)型是boolean型。6.4遍歷順序表2024/11/954ArrayList的存儲(chǔ)結(jié)構(gòu)是順序結(jié)構(gòu)，即節(jié)點(diǎn)的物理地址是依次相鄰的，因此，順序表完全可以調(diào)用get(intindex)方法來(lái)遍歷節(jié)點(diǎn)。迭代器分單向迭代器和雙向迭代器，對(duì)于線性表，單向迭代器只能向尾節(jié)點(diǎn)方向依次遍歷節(jié)點(diǎn)（稱(chēng)向后遍歷），雙向迭代器可以向尾節(jié)點(diǎn)方向依次遍歷節(jié)點(diǎn)，也可以向頭節(jié)點(diǎn)方向依次遍歷節(jié)點(diǎn)（稱(chēng)向前遍歷）。有關(guān)向迭代器和雙向迭代器的詳細(xì)知識(shí)點(diǎn)參看第5章的5.9節(jié)。2024/11/9556.4遍歷順序表例子4Example6_4.java例子4中的主類(lèi)Example6_4中使用雙向迭代器遍歷一個(gè)順序表，該順序表的每個(gè)節(jié)點(diǎn)是一個(gè)小寫(xiě)英文字母。雙向迭代器在遍歷節(jié)點(diǎn)的過(guò)程中，動(dòng)態(tài)添加新的節(jié)點(diǎn)，當(dāng)向后遍歷時(shí)（尾部節(jié)點(diǎn)方向），在當(dāng)節(jié)點(diǎn)的遍歷方向的前面（尾節(jié)點(diǎn)方向）依次插入2個(gè)新節(jié)點(diǎn)，一個(gè)新節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)的ASCII的值（即在UNICODE表中的順序位置），另一個(gè)新節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)的大寫(xiě)字母。2024/11/9566.4遍歷順序表例子5Example6_5.javaArrayList類(lèi)提供的publicvoidforEach(Consumer<?superE>action)方法的參數(shù)類(lèi)型是Consumer函數(shù)接口，該接口中的抽象方法voidaccept(Tt)的返回類(lèi)型是void型。那么在調(diào)用forEach(Consumer<?superE>action)方法時(shí)，可以將一個(gè)Lambda表達(dá)式傳遞給action例子5的主類(lèi)Example6_5動(dòng)態(tài)遍歷節(jié)點(diǎn)是Integer對(duì)象的一個(gè)順序表，在遍歷這個(gè)順序表時(shí)，讓節(jié)點(diǎn)Integer對(duì)象參與運(yùn)算，輸出Integer對(duì)象的二進(jìn)制、八進(jìn)制和十六進(jìn)制。6.5順序表與篩選法2024/11/957篩法的算法從2開(kāi)始：2是素?cái)?shù)，把素?cái)?shù)2保存，然后把2后面所有能被2整除的數(shù)都劃去。數(shù)字2后面第1個(gè)沒(méi)劃去的數(shù)是素?cái)?shù)3，把素?cái)?shù)3保存，然后再把3后面所有能被3整除的數(shù)都劃去。3后面第1個(gè)沒(méi)劃去的數(shù)是素?cái)?shù)5，把素?cái)?shù)5保存，然后再把5后面所有能被5整除的數(shù)都劃去?！凑蘸Y法，每次留下的數(shù)字中的第1個(gè)數(shù)字一定是素?cái)?shù)，如此繼續(xù)進(jìn)行，就會(huì)把不超過(guò)N的全部合數(shù)都篩掉，保存的就是不超過(guò)N的全部素?cái)?shù)。2024/11/9586.5順序表與篩選法例子6PrimeFilter.java

Example6_6.java

例子6主類(lèi)Example6_6使用ArrayList<Integer>primeFilter(intn)方法輸出200內(nèi)的全部素?cái)?shù)，以及200以?xún)?nèi)孿生素?cái)?shù)。6.6順序表與全排列2024/11/959

2024/11/9606.6順序表與全排列例子7FullPermutatio.javaExample6_7.java

●遞歸法求全排列2024/11/9616.6順序表與全排列例子8Example6_8.java●數(shù)字填空

例子8中的主類(lèi)Example6_8，使用全排列的辦法給出了所有滿(mǎn)足九宮格填數(shù)字要求的8種方案。如果考慮旋轉(zhuǎn)、鏡像相同的屬于同一種，那么這8種方案都是一樣的。

2024/11/9626.6順序表與全排列●迭代法求全排列對(duì)于字符1，2，3，5，6，7，8組成的全排列，按字典序，最小的是12345678，最大的是87654321。從最小的全排列（或最大的全排列）開(kāi)始，按著字典序依次尋找下一個(gè)全排列，一直到找到最大的（最小的）全排列為止，就可以給出全部的全排列。這里，我們通過(guò)找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。①尋找正序相鄰對(duì)在全排列的相鄰對(duì)中找到最后一對(duì)“正序相鄰對(duì)”（小的在前、大的在后）。2024/11/9636.6順序表與全排列●迭代法求全排列這里，我們通過(guò)找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。②尋找最小字符

對(duì)于：58，找到的字符是6。字符6以后的字符（假如有的話(huà)）都比字符5小2024/11/9646.6順序表與全排列這里，我們通過(guò)找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。③最小字符與pairLast的首字符互換

2024/11/9656.6順序表與全排列34587621的下一個(gè)全排列：34612578。④反轉(zhuǎn)子序列

例子9DictionaryPermutatio.javaExample6_9.java6.7順序表與組合2024/11/966

2024/11/9676.7順序表與組合●迭代求組合和排列不同，[1,2,3]和[1,3,2]是不同的排列，是相同的組合。因此，表示組合時(shí)可以讓組合里的數(shù)字都是升序的。

該組合中的每個(gè)數(shù)，按順序存放到一個(gè)順序表list中。

得到下一個(gè)組合[1,4,5]2024/11/9686.7順序表與組合●迭代求組合例子10Combination.javaExample6_10.java例子10中Combination類(lèi)的方法C(intn,intr,List<Integer>start)返回組合start的下一個(gè)組合.例子10中的主類(lèi)Example6_10使用Combination類(lèi)的方法輸出從7個(gè)數(shù)中取5個(gè)數(shù)的全部組合.2024/11/9696.7順序表與組合●遞歸求組合例子11RecurrenceCom.javaExample6_11.java參考遞歸求楊輝三角形（見(jiàn)第3章例子9），可以寫(xiě)出遞歸求組合的算法（作者反復(fù)畫(huà)遞歸圖，找出了遞歸的規(guī)律，見(jiàn)RecurrenceCom類(lèi).

2024/11/9706.7順序表與組合●組合與砝碼稱(chēng)重例子12Weight.javaExample6_12.java有n多個(gè)重量不同的砝碼各一枚，比如，4個(gè)重量不同的砝碼：1克，3克，5克和8克。能稱(chēng)出多少種重量。有些組合可能稱(chēng)出相同的重量，比如用一個(gè)5克的砝碼可以稱(chēng)出5克重量，用1個(gè)2克砝碼和1個(gè)3克砝碼，同樣也可以稱(chēng)出5克重量。遍歷全部的組合，發(fā)現(xiàn)能稱(chēng)出相同的重量的組合（即方案）時(shí)，保留一個(gè)即可。

如果允許砝碼放在天秤的兩端（允許放在被稱(chēng)重的物體一端），那么就把另一端（被稱(chēng)重的物體一端）的砝碼拿回到放置砝碼的一端、并變成“負(fù)碼”（重量是負(fù)數(shù)），就將問(wèn)題轉(zhuǎn)化為砝碼只放天秤一端的情況。6.8順序表與記錄2024/11/971有時(shí)候，需要將一維數(shù)組，比如一個(gè)記錄學(xué)生成績(jī)的一維數(shù)組，看作一個(gè)整體，稱(chēng)作一條記錄（如果學(xué)過(guò)數(shù)據(jù)庫(kù)，相當(dāng)于表中的一條記錄）。借助順序表，可以批量處理記錄，比如，排序紀(jì)錄。2024/11/9726.8順序表與記錄●順序表與一維數(shù)組例子13Example6_13.javaArrays類(lèi)的靜態(tài)方法：static<T>List<T>asList(T...a)返回一個(gè)順序表。該方法是可變參數(shù)，可以把若干個(gè)類(lèi)型相同的對(duì)象放入一個(gè)順序表，也可以把一個(gè)數(shù)組放入一個(gè)順序表。順序表調(diào)用public<T>T[]toArray(T