數(shù)據(jù)結(jié)構(gòu)與算法（Java語言版）課件全套 耿祥義 第1-14章 數(shù)據(jù)結(jié)構(gòu)簡介-經(jīng)典算法思想

第1章數(shù)據(jù)結(jié)構(gòu)簡介2024/11/91主要內(nèi)容邏輯結(jié)構(gòu)物理結(jié)構(gòu)算法與結(jié)構(gòu)1.1邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指有限多個(gè)節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）之間的邏輯關(guān)系，不涉及節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）在計(jì)算機(jī)中的存儲位置。2024/11/92主要的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖結(jié)構(gòu)和集合這四種結(jié)構(gòu)。⒈線性結(jié)構(gòu)2024/11/93在實(shí)際生活中，經(jīng)常遇到具有線性結(jié)構(gòu)的一組數(shù)據(jù)，比如，中國農(nóng)歷的二十四節(jié)氣：立春、雨水、驚蟄、春分、清明、谷雨、立夏、小滿、芒種、夏至、小暑、大暑、立秋、處暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒2024/11/94⒈線性結(jié)構(gòu)2024/11/95⒈線性結(jié)構(gòu)2024/11/96⒈線性結(jié)構(gòu)2024/11/972024/11/982.

樹結(jié)構(gòu)

2024/11/992.

樹結(jié)構(gòu)用倒置的樹形示意一個(gè)樹2024/11/9102.

樹結(jié)構(gòu)一個(gè)樹T=(A,R)

由多個(gè)互不相交的樹構(gòu)成2024/11/9112.

樹結(jié)構(gòu)樹的每個(gè)結(jié)點(diǎn)至多有2個(gè)子結(jié)點(diǎn)，稱這樣的樹是二叉樹二叉查詢樹，特點(diǎn)是，每個(gè)結(jié)點(diǎn)上的值都大于等于它的左子樹上的結(jié)點(diǎn)里的值、小于它的右子樹上結(jié)點(diǎn)里的值。首先猜m是上面的二叉樹的根結(jié)點(diǎn)中的數(shù)，如果猜測錯(cuò)誤，反饋信息給你，你猜測的比根結(jié)點(diǎn)中的數(shù)大，那你就繼續(xù)猜測這個(gè)數(shù)是當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)，如果告知你，你猜測的數(shù)不大于根結(jié)點(diǎn)中的數(shù)，那你就繼續(xù)猜測這個(gè)數(shù)是當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)，依次類推，您可以較快的猜測到這個(gè)數(shù)。2024/11/9122.

樹結(jié)構(gòu)樹的層從上至下，從0層開始根結(jié)點(diǎn)沒有父結(jié)點(diǎn)，非根、非葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但有一個(gè)或多個(gè)子結(jié)點(diǎn)，葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但沒有子結(jié)點(diǎn)。根據(jù)樹結(jié)構(gòu)的這個(gè)特點(diǎn)，可以把樹的結(jié)點(diǎn)按層次分類：樹的結(jié)點(diǎn)按層次分類，從根開始定義，根為第0層，根的子結(jié)點(diǎn)為第1層，以此類推。每一層上的結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)有關(guān)系，但可能和下一層的0個(gè)或多個(gè)結(jié)點(diǎn)有關(guān)系。2024/11/9133.

圖結(jié)構(gòu)鋼筋焊接起來的平面架中的焊點(diǎn)：a,b,c,d,e2024/11/9143.

圖結(jié)構(gòu)鋼筋焊接起來的平面架中的焊點(diǎn)：a,b,c,d,e

這個(gè)圖結(jié)構(gòu)中，人們規(guī)定(a,b)和(b,a)是一樣的（都代表同一根鋼筋），即(a,b)和(b,a)都是沒有方向的“標(biāo)量”邊，這樣的圖結(jié)構(gòu)稱作無向圖2024/11/9153.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

2024/11/9163.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

對于G=(V,E)，如果(a,b)是邊，那么默認(rèn)(b,a)也就是邊，并規(guī)定(a,b)邊等于(b,a)邊，這樣規(guī)定的G=(V,E)是無向圖，簡稱V是無向圖，即無向圖的邊是沒有方向的。無向圖2024/11/9173.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

如果(a,b)，(b,a)都是邊，就規(guī)定(a,b)邊不等于(b,a)邊，這樣規(guī)定的G=(V,E)是有向圖，簡稱V是有向圖，即有向圖的邊是有方向的。2024/11/9184.

集合集合A中的元素除了同屬一個(gè)集合外，無其它任何關(guān)系，即關(guān)系集合是空集合，可表示為(A,?)（?是A×A的空子集）2024/11/919對于(A,R)，計(jì)算機(jī)程序在存儲空間中存放集合A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的形式，稱為A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的物理結(jié)構(gòu)，也稱為A的存儲結(jié)構(gòu)。1.2物理結(jié)構(gòu)比如，對于一個(gè)線性表，可根據(jù)需要采用順序存儲（節(jié)點(diǎn)的物理地址是依次相鄰的）或鏈?zhǔn)酱鎯Γü?jié)點(diǎn)的物理地址不必是相鄰的）。常用的存儲結(jié)構(gòu)有順序存儲、鏈?zhǔn)酱鎯凸４鎯Φ?，有關(guān)細(xì)節(jié)見后續(xù)的章節(jié)，例如，第4章至第11章2024/11/920實(shí)施于集合上的算法，在其執(zhí)行完畢后，必須保持集合的邏輯結(jié)構(gòu)不變，比如，對于線性表，實(shí)施了增加或刪除節(jié)點(diǎn)的操作后，要保證新的節(jié)點(diǎn)構(gòu)成的集合仍然是線性結(jié)構(gòu)，否則算法必須對當(dāng)前的線性表的節(jié)點(diǎn)進(jìn)行調(diào)整，使得當(dāng)前線性表在邏輯上仍然是一個(gè)線性結(jié)構(gòu)。1.3算法與結(jié)構(gòu)有關(guān)細(xì)節(jié)見后續(xù)的章節(jié)，例如，第4章至第11章。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲結(jié)構(gòu)第2章算法復(fù)雜度2024/11/921主要內(nèi)容●算法●算法的復(fù)雜度

●常見的復(fù)雜度2.1算法算法(algorithm)就是一個(gè)正確的計(jì)算過程，該過程取某個(gè)值或值的集合作為輸入并產(chǎn)生某個(gè)值或值的集合作為輸出。2024/11/9222024/11/923算法的4個(gè)主要特性：2.1算法算法的4個(gè)主要特性是：●確切性：算法由語句組成，每個(gè)語句的功能是確切的?！褫斎霐?shù)據(jù)：可以向算法輸入多個(gè)或0個(gè)數(shù)據(jù)（方法可以有參數(shù)或無參數(shù)），即算法可以接收或不接收外部數(shù)據(jù)?！褫敵鰯?shù)據(jù)：算法可以給出明確的計(jì)算結(jié)果（方法的返回值）或輸出若干數(shù)據(jù)到客戶端以反映算法產(chǎn)生的效果。●可行性：基本操作都是在有限時(shí)間內(nèi)被完成。所謂有限時(shí)間是指這個(gè)時(shí)值僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，即不會隨著n的增加而增大?！翊_切性●輸入數(shù)據(jù)●輸出數(shù)據(jù)●可行性2024/11/924一個(gè)算法不能在有限的時(shí)間內(nèi)結(jié)束，就不屬于算法復(fù)雜度的研究的范疇，比如一個(gè)算法里出現(xiàn)的無限循環(huán)，就不再屬于算法復(fù)雜度的研究的范疇了2.2復(fù)雜度算法，從執(zhí)行到結(jié)束，涉及兩個(gè)度量：一個(gè)是執(zhí)行方法所消耗的時(shí)間，一個(gè)是執(zhí)行方法所需要的內(nèi)存空間。2024/11/925方法里聲明的局部變量，包括參數(shù)都不歸類到基本操作，即不是基本操作。2.2復(fù)雜度⒈基本操作一個(gè)基本操作是一個(gè)語句或一個(gè)運(yùn)算表達(dá)式。一個(gè)基本操作是一個(gè)語句或一個(gè)運(yùn)算表達(dá)式，而且必須是在有限時(shí)間內(nèi)能被完成的計(jì)算步驟，其耗時(shí)僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，不會隨著n的增加而增大。2024/11/926在計(jì)算算法執(zhí)行的基本操作的總數(shù)時(shí)，要真對最壞的情況，即在某種條件下執(zhí)行的基本操作的總數(shù)是最多的情況2.2復(fù)雜度3時(shí)間復(fù)雜度算法執(zhí)行的基本操作的總數(shù)T(n)。算法的復(fù)雜度主要是度量隨著n的增大，T(n)值的趨勢。2024/11/927學(xué)習(xí)復(fù)雜度，記住一個(gè)通俗的道理：時(shí)間累加，空間不累加.2.2復(fù)雜度4復(fù)雜度比較2024/11/9282.3常見復(fù)雜度⒈O(jiān)(1)復(fù)雜度算法中的基本操作被執(zhí)行的總次數(shù)是一個(gè)常量，即不依賴一個(gè)正整數(shù)n、不會隨著n的增加而增大，那么將算法的時(shí)間復(fù)雜度，記作O(1)。算法中的所占用的內(nèi)存是一個(gè)常量，即所占內(nèi)存不依賴一個(gè)正整數(shù)n、不會隨著n的增加而增大，那么將算法的空間復(fù)雜度，記作O(1)。

例子1Max.javaExample2_1.java2024/11/9292.3常見復(fù)雜度1.O(1)復(fù)雜度

例子2Sum.javaExample2_2.java2024/11/9302.3常見復(fù)雜度2.O(n)復(fù)雜度

2024/11/9312.3常見復(fù)雜度2.O(n)復(fù)雜度例子3SumAndMult.java

Example2_3.java

2024/11/9322.3常見復(fù)雜度2.O(n)復(fù)雜度例子4ArrayMax.java

Example2_4.java

2024/11/9332.3常見復(fù)雜度2.O(n)復(fù)雜度例子5FindMissNumber.java

Example2_5.java

理論上知道，同一臺計(jì)算機(jī)，執(zhí)行“異或”運(yùn)算要比“加減”運(yùn)算快。所以，對于同一個(gè)算法，在復(fù)雜度相同的情況下，盡量使用速度快的基本操作。如果軟件的需求不十分介意速度，選擇的基本操作能使得的代碼更簡練、閱讀性更好，那么也可以使用這樣的基本操作。2024/11/9342.3常見復(fù)雜度3.2024/11/9352.3常見復(fù)雜度3.例子6Multi.java

Example2_6.java

2024/11/9362.3常見復(fù)雜度3.例子7BubbleSort.java

Example2_7.java

2024/11/9372.3常見復(fù)雜度4.

2024/11/9382.3常見復(fù)雜度4.例子8OutPutNumber.java

Example2_8.java

2024/11/9392.3常見復(fù)雜度5.

2024/11/9402.3常見復(fù)雜度5.例子9FindNumber.java

Example2_9.java

2024/11/9412.3常見復(fù)雜度5.例子10Euclidean.java

Example2_10.java

2024/11/9422.3常見復(fù)雜度6.

如果一個(gè)方法里又調(diào)用了其它方法，即一個(gè)算法又包含另外一個(gè)算法，那么該方法的復(fù)雜度將和它包含的方法復(fù)雜度有關(guān)，需合并考察復(fù)雜度。

2024/11/9432.3常見復(fù)雜度6.例子11DataInArray.java

Example2_11.java

2024/11/9442.3常見復(fù)雜度6.例子12GCDInArray.java

Example2_12.java

2024/11/9452.3常見復(fù)雜度7.復(fù)雜度比較

程序中大部分算法都是這些復(fù)雜度中之一，除非特別需要，后續(xù)章節(jié)不再給出每個(gè)方法的復(fù)雜度。復(fù)雜度的比較規(guī)則：第3章遞歸算法2024/11/946主要內(nèi)容● 遞歸算法● 遞歸的復(fù)雜度● 問題與子問題● 遞歸與迭代● 多重遞歸● 經(jīng)典遞歸● 優(yōu)化遞歸遞歸算法是非常最重的算法，是很多算法的基礎(chǔ)算法。遞歸算法不僅能使得代碼優(yōu)美簡練，容易理解解決問題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，而且具有很好的可讀性。和排序算法不同，許多經(jīng)典的排序算法已經(jīng)是玲瓏剔透、日臻完善，在許多應(yīng)用中只要選擇一種排序算法直接使用即可（見第4章和第12章），而對于遞歸算法，真正理解遞歸算法內(nèi)部運(yùn)作機(jī)制的細(xì)節(jié)、才能真對實(shí)際問題正確的使用遞歸算法或?qū)懗稣_的遞歸算法。3.1遞歸算法遞歸算法是指一個(gè)方法在執(zhí)行過程中又調(diào)用了自身、形成了遞歸調(diào)用，這樣的方法被稱為遞歸方法或遞歸算法。2024/11/947

2024/11/9483.1遞歸算法遞歸過程中的壓棧、彈棧方法f遞歸過程是，第k次調(diào)用f需要等待第k+1次調(diào)用f結(jié)束執(zhí)行過程后才能結(jié)束執(zhí)行過程。那么第R(n)次（最后一次）調(diào)用f結(jié)束執(zhí)行過程后，就會依次使得第k次調(diào)用結(jié)束執(zhí)行過程。方法被調(diào)用時(shí)，方法的（入口）地址會被壓入棧（棧是一種先進(jìn)后出的結(jié)構(gòu)）中，稱為壓棧操作，同時(shí)方法的局部變量被分配內(nèi)存空間。

……調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用結(jié)束

結(jié)束

結(jié)束

結(jié)束結(jié)束

圖3.1遞歸執(zhí)行過程第1次調(diào)用第R(n)次調(diào)用2024/11/9493.1遞歸算法遞歸過程中的壓棧、彈棧方法調(diào)用結(jié)束，會進(jìn)行彈棧，稱為彈棧操作，同時(shí)釋放方法的局部變量所占的內(nèi)存。遞歸過程的壓棧操作可以讓棧的長度不斷增加，而彈棧操作會讓棧的長度變小，最終使棧的長度為0?！?/p>

第1次彈棧第m次彈棧第k次彈棧第1次壓棧第m次壓棧第k次壓棧2024/11/9503.1遞歸算法時(shí)間復(fù)雜度方法調(diào)用結(jié)束，會進(jìn)行彈棧，稱為彈棧操作，同時(shí)釋放方法的局部變量所占的內(nèi)存。要針對具體的遞歸方法，來計(jì)算該遞歸方法的時(shí)間復(fù)雜度。遞歸方法是一個(gè)遞歸過程，從遞歸開始到遞歸結(jié)束，方法被調(diào)的總數(shù)R(n)是依賴于一個(gè)正整數(shù)n的函數(shù)。那么遞歸方法中基本操作被執(zhí)行的總數(shù)T(n)就依賴遞歸的總數(shù)R(n)和每次遞歸時(shí)基本操作被執(zhí)行的總數(shù)。2024/11/9513.1遞歸算法空間復(fù)雜度方法調(diào)用結(jié)束，會進(jìn)行彈棧，稱為彈棧操作，同時(shí)釋放方法的局部變量所占的內(nèi)存。遞歸會讓棧的長度不斷發(fā)生變化，如果棧的長度較大可能導(dǎo)致棧溢出，使得進(jìn)程（運(yùn)行的程序）被操作系統(tǒng)終止。遞歸過程的壓棧操作增加棧的長度、彈棧操作減小棧的長度。遞歸過程中可能交替地進(jìn)行壓棧操作和彈棧操作，直至棧的長度為0（見例子2）。計(jì)算出遞歸過程中，某一時(shí)刻（某一次遞歸）棧出現(xiàn)的最大長度和每次遞歸中方法的局部變量所占的內(nèi)存空間，即計(jì)算出棧最大長度以及局部變量所占的全部內(nèi)存空間和所依賴的正整數(shù)的關(guān)系，才可以知道空間復(fù)雜度。2024/11/9523.2線性遞歸與非線性遞歸●線性遞歸線性遞歸是指，每次遞歸時(shí)，方法調(diào)用自身一次。

如果我們忘記了今天是星期幾，就需要知道昨天是星期幾，如此這般地向前（過去）翻日歷（相當(dāng)于遞歸里的壓棧，導(dǎo)致棧的長度在增加），等到能翻到某個(gè)日歷頁上顯示了星期幾，就結(jié)束翻閱日歷（相當(dāng)于結(jié)束壓棧），然后再一頁一頁的撕掉日歷（相當(dāng)于彈棧），日歷上神奇地出現(xiàn)了星期數(shù)，即方法依次計(jì)算出自己的返回值。Week.java例子1Example3_1.java2024/11/9533.2線性遞歸與非線性遞歸●線性遞歸遞歸方法f(intn)的遞歸的總次數(shù)：R(n)=n，而每次遞歸的基本操作只有2個(gè)基本操作，因此時(shí)間復(fù)雜度是O(n)。向下方向的弧箭頭表示方法被調(diào)用，向上方向的直箭頭表示方法調(diào)用結(jié)束。例子1壓棧操作過程中得到的棧的最大長度是R(n)=n，空間復(fù)雜度是O(n)。2024/11/9543.2線性遞歸與非線性遞歸●非線性遞非線性遞歸是指，每次遞歸時(shí)方法，調(diào)用自身2次或2次以上。

Fibonacci.java例子2Example3_2.java2024/11/9553.2線性遞歸與非線性遞歸●非線性遞例子2遞歸過程中，每次遞歸時(shí)方法調(diào)用自身2次，使得每次遞歸出現(xiàn)了2個(gè)遞歸“分支”，然后選擇一個(gè)分支，繼續(xù)遞歸，直到該分支遞歸結(jié)束，再沿著下一分支繼續(xù)遞歸，當(dāng)2個(gè)分支都遞歸結(jié)束，遞歸過程才結(jié)束，而且遞歸過程交替地進(jìn)行壓棧和彈棧操作，直至棧的長度為0。

2024/11/9563.3問題與子問題將規(guī)模大的問題，使用遞歸算法逐步分解成規(guī)模小的問題，最終解決規(guī)模大的問題。一個(gè)問題的子問題就是數(shù)據(jù)規(guī)模比此問題的規(guī)模更小的問題。當(dāng)一個(gè)問題，可以分解成許多子問題時(shí)就可以考慮用遞歸算法來解決這個(gè)問題。2024/11/9573.3問題與子問題

SumMulti.java例子3Example3_3.java2024/11/9583.3問題與子問題

Reverse.java例子4Example3_4.javaMaxInArray.java2024/11/9593.4遞歸與迭代遞歸的思想是根據(jù)上一次操作的結(jié)果，確定當(dāng)前操作的結(jié)果。迭代的思想是，根據(jù)當(dāng)前操作的結(jié)果，確定下一次操作的結(jié)果。對于解決相同的問題，遞歸代碼簡練，容易理解解決問題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，具有很好的可讀性。由于迭代不涉及方法的遞歸調(diào)用，所以，通常情況下遞歸算法的空間復(fù)雜度會大于迭代的復(fù)雜度，當(dāng)遞歸過程的遞歸總數(shù)比較大時(shí)，會導(dǎo)致棧溢出。2024/11/9603.4遞歸與迭代例子5中ComputePI類中的recursionMethod(intn)方法和iterationMethod(intn)都是通過計(jì)算級數(shù)的近似值返回圓周率的近似值，recursionMethod(intn)使用的是遞歸，iterationMethod(intn)使用的是迭代。ComputePI.java例子5Example3_5.java2024/11/9613.4遞歸與迭代

SearchNumber.java例子6Example3_6.java

2024/11/9623.4遞歸與迭代Euclidean.java例子7Example3_7.java

2024/11/9633.5多重遞歸所謂多重遞歸，是指一個(gè)遞歸方法調(diào)用另一個(gè)或多個(gè)遞歸方法，稱該遞歸方法多重遞歸方法。

不要求輸出含有偶數(shù)多個(gè)6的數(shù)。

2024/11/9643.5多重遞歸

2024/11/9653.6經(jīng)典遞歸選擇三個(gè)經(jīng)典的遞歸：楊輝三角形、老鼠走迷宮和漢諾塔，進(jìn)一步體會遞歸算法不僅能使得代碼優(yōu)美簡練，容易理解解決問題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，而且具有很好的可讀性。特別是漢諾塔遞歸，通過其遞歸算法，洞悉其數(shù)據(jù)規(guī)律，給出相應(yīng)的迭代算法。經(jīng)典的遞歸：楊輝三角形，老鼠走迷宮，漢諾塔2024/11/9663.6經(jīng)典遞歸楊輝三角

最早出現(xiàn)于中國南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》中。法國數(shù)學(xué)家帕斯卡（Pascal）在1654年發(fā)現(xiàn)該三角形，所以又稱帕斯卡三角形。

2024/11/9673.6經(jīng)典遞歸楊輝三角最早出現(xiàn)于中國南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》中。法國數(shù)學(xué)家帕斯卡（Pascal）在1654年發(fā)現(xiàn)該三角形，所以又稱帕斯卡三角形。

2024/11/9683.6經(jīng)典遞歸PascalTriangle.java例子9Example3_9.java楊輝三角

YanhuiTriangle.java

2024/11/9693.6經(jīng)典遞歸老鼠走迷宮老鼠首先向東走，如果走到出口結(jié)束遞歸，否則向南…向西…向北。

2024/11/9703.6經(jīng)典遞歸老鼠走迷宮例子10的主類Example3_10使用move(int[][]a,inti,intj)方法走迷宮。其中，用int型二維數(shù)組模擬迷宮，二維數(shù)組元素值是1表示墻，0表示路，2表示出口。老鼠走過迷宮后，輸出老鼠走過的路時(shí)，用☆表示老鼠走過的路，■表示墻，★表示出口，□表示老鼠未走過的路。Mouse.java例子10Example3_10.java2024/11/9713.6經(jīng)典遞歸漢諾塔（遞歸算法）漢諾塔(HanoiTower)問題是來源于印度的一個(gè)古老問題。有名字為A，B，C的三個(gè)塔，A塔上有從小到大64個(gè)盤子，每次搬運(yùn)一個(gè)盤子，最后要把64個(gè)盤子搬運(yùn)到C塔。在搬運(yùn)盤子的過程中，可以把盤子暫時(shí)放在3個(gè)塔中的任何一個(gè)上，但不允許大盤放在小盤上面。3個(gè)盤子的漢諾塔

2024/11/9723.6經(jīng)典遞歸漢諾塔（遞歸算法）3個(gè)盤子的漢諾塔

HannoiTower.java例子11Example3_11.java2024/11/9733.6經(jīng)典遞歸漢諾塔（迭代算法）

這些規(guī)律是通過研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2024/11/9743.6經(jīng)典遞歸漢諾塔（迭代算法）

一個(gè)偶數(shù)通過不斷地右位移可計(jì)算出尾部連續(xù)的0的個(gè)數(shù)，例如：8的二進(jìn)制1000右位移3次，得到奇數(shù)，因此知道8的二進(jìn)制尾部連續(xù)0的個(gè)數(shù)是3。這些規(guī)律是通過研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2024/11/9753.6經(jīng)典遞歸漢諾塔（迭代算法）這些規(guī)律是通過研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。

HanoiTowerIterator.java例子12ZeroCount.javaExample3_12.java2024/11/976計(jì)算Fibonacci序列的遞歸過程中需要將f(n-1)分支進(jìn)行完畢，再進(jìn)行f(n-2)分支。需要注意到的是，在進(jìn)行f(n-1)分支遞歸時(shí)，會完成了f(n-2)分支遞歸，那么再進(jìn)行f(n-2)分支就是一個(gè)重復(fù)的遞歸過程。簡而言之，優(yōu)化遞歸就是避免重復(fù)子遞歸。優(yōu)化遞歸就是在每次遞歸開始前，首先到某個(gè)對象中，通常為散列表對象，也可以是數(shù)組，查找本次遞歸是否已經(jīng)被實(shí)施完畢，即是否已經(jīng)有了遞歸結(jié)果，如果散列表對象中已經(jīng)有了本次遞歸的結(jié)果，就直接使用這個(gè)結(jié)果，不再浪費(fèi)時(shí)間進(jìn)行本次遞歸，否則就進(jìn)行本次遞歸，并將遞歸結(jié)果保存到散列表對象。3.7優(yōu)化遞歸2024/11/9773.7優(yōu)化遞歸

OptimizeFibonacci.java例子13Example3_13.javaOptimizeFibonacci類的散列表是靜態(tài)成員變量，會不斷累積子遞歸的結(jié)果，盡管會浪費(fèi)內(nèi)存空間，但會使得后面的遞歸速度越來越快。2024/11/9783.7優(yōu)化遞歸

OptimizePascalTriangle.java例子14Example3_14.javaOptimizePascalTriangle類的散列表是靜態(tài)成員變量，會不斷累積子遞歸的結(jié)果，盡管會浪費(fèi)內(nèi)存空間，但會使得后面的遞歸速度越來越快。第4章數(shù)組與Arrays類2024/11/979主要內(nèi)容● 數(shù)組的引用● 數(shù)組的排序● 數(shù)組的二分查找●數(shù)組的復(fù)制● 數(shù)組的比較● 數(shù)組的匹配● 公共子數(shù)組● 數(shù)組的更新● 數(shù)組的前綴運(yùn)算● 數(shù)組的動態(tài)遍歷● 數(shù)組與洗牌● 數(shù)組與生命游戲

數(shù)組是最常用的一種線性數(shù)據(jù)結(jié)構(gòu)，數(shù)組一旦被創(chuàng)建，那么數(shù)組的長度（數(shù)組的元素的個(gè)數(shù)）就不可以再發(fā)生變化，即不可以對數(shù)組進(jìn)行刪除，添加或插入操作。關(guān)于數(shù)組的算法還是非常多的，比如排序，復(fù)制，二分查找，動態(tài)遍歷等。4.1引用與參數(shù)存值

2024/11/9802024/11/9814.1引用與參數(shù)存值1.數(shù)組的引用數(shù)組屬于引用型數(shù)據(jù)，即數(shù)組中存放著一個(gè)引用值，數(shù)組使用下標(biāo)運(yùn)算訪問自己的元素（下從0開始，每個(gè)元素的下標(biāo)等于它前面的元素的個(gè)數(shù)）?？梢宰孲ystem類調(diào)用靜態(tài)方法intidentityHashCode(Objectobject)返回（得到）數(shù)組a的引用：intaddress=System.identityHashCode(a);也可以讓數(shù)組a調(diào)用inthashCode()方法返回（得到）數(shù)組的引用：intaddress=a.hashCode();兩個(gè)類型相同的數(shù)組，一旦二者的引用相同，二者就具有相同的元素。2024/11/9824.1引用與參數(shù)存值1.數(shù)組的引用數(shù)組屬于引用型數(shù)據(jù)，即數(shù)組中存放著一個(gè)引用值，數(shù)組使用下標(biāo)運(yùn)算訪問自己的元素（下從0開始，每個(gè)元素的下標(biāo)等于它前面的元素的個(gè)數(shù)）。例子1中的主類Example4_1使用了intidentityHashCode()方法和inthashCode()方法，注意例子1的輸出結(jié)果，特別是數(shù)組b的值（b的引用）賦值給數(shù)組a之后，程序的輸出結(jié)果。例子1Example4_1.java2024/11/9834.1引用與參數(shù)存值2.參數(shù)存值使用參數(shù)存儲值就是一個(gè)方法可以將某些數(shù)據(jù)存放在參數(shù)中，如果參數(shù)是引用類型，比如數(shù)組，那么方法執(zhí)行完畢，保存在參數(shù)中的值一直還存在、不會消失。例子2Example4_2.java當(dāng)a，b，c構(gòu)成等邊三角形時(shí)返回3，將三角形面積存放在數(shù)組area的元素中，構(gòu)成等腰三角形時(shí)（不是等邊）返回2，將三角形面積存放在數(shù)組area的元素中，構(gòu)成三角形時(shí)（不是等邊，也不是等腰）返回1，將三角形面積存放在數(shù)組area的元素中，不構(gòu)成三角形時(shí)返回0，將Double.NaN（沒有值）存放在數(shù)組area的元素中。Triangle.java2024/11/9844.1引用與參數(shù)存值2.參數(shù)存值使用參數(shù)存儲值就是一個(gè)方法可以將某些數(shù)據(jù)存放在參數(shù)中，如果參數(shù)是引用類型，比如數(shù)組，那么方法執(zhí)行完畢，保存在參數(shù)中的值一直還存在、不會消失。例子3Example4_3.java例子3中char型數(shù)組的元素值是某個(gè)小寫英文字母，F(xiàn)indLetters類中的findMaxCountLetters(char[]english,int[]saveCount)方法返回char型數(shù)組中出現(xiàn)次數(shù)最多的字母之一，并將這個(gè)字母出現(xiàn)的次數(shù)存放到參數(shù)指定的int型數(shù)組的元素中。FindLetters.java4.2數(shù)組與排序2024/11/985排序算法是重要的基礎(chǔ)算法。各種排序算法都是非常成熟的算法，Arrays類封裝了快速排序和歸并排序，編寫程序時(shí)直接使用即可。2024/11/9864.2數(shù)組與排序1.快速排序

雙軸快速排序不是穩(wěn)定排序。穩(wěn)定排序是指，數(shù)組里大小一樣的數(shù)據(jù)，排序后，保持原始的先后順序不變。起泡法是穩(wěn)定排序，而選擇法是不穩(wěn)定排序。如果是給對象排序（非基本類型數(shù)據(jù)），那么創(chuàng)建對象類需要實(shí)現(xiàn)Comparable<T>泛型接口來指定對象的大小關(guān)系，否則，sort()方法將按對象的引用排序?qū)ο?，這種排序往往沒有什么實(shí)際意義（就像生活中，很少按人的身份證排序）?？焖倥判蚴且环N基于遞歸的經(jīng)典排序算法。它的思路是選定一個(gè)基準(zhǔn)元素，然后把比這個(gè)元素小的元素放在它左邊，比它大的元素放在它右邊。再分別對它左邊和右邊的元素進(jìn)行遞歸處理，直到排序完成。2024/11/9874.2數(shù)組與排序1.快速排序

例子4Example4_4.javaStudent.java

主類Example4_4分別使用Arrays類的sort(Object[]a)方法和我們自己定義的BasicSort類中的方法，按身高（height）排序Student類的對象。BasicSort.java2024/11/9884.2數(shù)組與排序2.歸并排序例子5Example4_5.javaMerge.java

例子5里，我們依然給出了歸并排序算法，其目的是體現(xiàn)遞歸算法的重要性（歸并排序使用了遞歸算法），在實(shí)際應(yīng)用中，完全沒必要這樣做，只需用Arrays類的parallelSort()方法即可，讓你的代碼更加簡練有效。歸并排序算法如下：①將待排序數(shù)組分成兩個(gè)子數(shù)組，每個(gè)子數(shù)組通過遞歸進(jìn)行排序。②將兩個(gè)排好序的子數(shù)組合并成一個(gè)有序數(shù)組。4.3數(shù)組的二分查找2024/11/989二分法可用于查找一個(gè)數(shù)據(jù)是否在一個(gè)升序數(shù)組中。我們曾在第2章的例子9，第3章的例子6介紹過二分法。因?yàn)槎址ㄊ浅墒斓慕?jīng)典算法，所以Java將其作為一個(gè)方法封裝在Arrays類中。在開發(fā)程序時(shí)，可以直接使用Arrays類即可，不必再像第2章例子9或第3章的例子6去編寫算法的具體代碼。2024/11/9904.3數(shù)組的二分查找1.二分法例子6Example4_6.java例子6的主類Example4_6，在循環(huán)10000次的循環(huán)語句的循環(huán)體中，每次使用Random對象得到1至7之間的一個(gè)數(shù)字。循環(huán)結(jié)束后輸出1至7之間的各個(gè)數(shù)字出現(xiàn)的次數(shù),該例子中使用了Arrays類中的binarySearch()方法。Arrays類中的binarySearch()方法是一個(gè)重載的方法，該方法使用二分法算法查找一個(gè)數(shù)據(jù)key是否在升序數(shù)組a中，如果在數(shù)組中，返回和key相等的數(shù)組元素的索引位置，如果不在數(shù)組中，返回一個(gè)負(fù)數(shù)（不一定是-1）2024/11/9914.3數(shù)組的二分查找1.二分法例子7Example4_7.javaFilterData.java例子7中的FilterData類的int[]filterArray(int[]arr,int[]filter)方法返回一個(gè)數(shù)組，該數(shù)組的元素值是數(shù)組arr經(jīng)過數(shù)組filter過濾后的數(shù)據(jù)。過濾過程中，使用binarySearch()方法判斷數(shù)組中哪些值不在filter中，然后通過保留不在filter中值，完成過濾過程。有時(shí)候想過濾數(shù)組arr，即想去掉數(shù)組arr中的某些值。為了過濾數(shù)組arr，可以用另外一個(gè)數(shù)組filer做過濾器，即數(shù)組filer中的元素值都是數(shù)組arr準(zhǔn)備去掉的值。4.4數(shù)組的復(fù)制2024/11/992數(shù)組屬于引用型變量，兩個(gè)類型相同的數(shù)組，比如數(shù)組a和數(shù)組b，如果將a的引用賦值給b，那么二者的元素就完全相同了（見4.1節(jié)）。如果想得到一個(gè)數(shù)組b，b的元素值和a的相同，但二者的引用不同，就需要使用復(fù)制的辦法，即把數(shù)組a的元素值賦值到數(shù)組b的元素中，而不是將a的引用賦值給b。2024/11/9934.4數(shù)組的復(fù)制1.復(fù)制數(shù)組的方法例子8Example4_8.javaGetRondomNumber.javacopyOf(int[]a,intnewLength)把數(shù)組a中從索引0開始的newLength多個(gè)元素值賦值到一個(gè)新數(shù)組中，并返回新數(shù)組的引用。如果newLength的值大于數(shù)組a的長度，新數(shù)組從newLength索引位置開始的元素值都是默認(rèn)值。比如對于int型數(shù)組，默認(rèn)是就是0。copyOfRange(int[]a,intfrom,intto)把數(shù)組a中從索引from開始的到索引位置to結(jié)束的元素值（但不包括索引位置是to的元素值）賦值到一個(gè)新數(shù)組中，并返回新數(shù)組的引用。用區(qū)間法表示就是把索引范圍是半閉半開區(qū)間[from,to)的元素值賦值到一個(gè)新數(shù)組中，并返回新數(shù)組的引用。2024/11/9944.4數(shù)組的復(fù)制1.復(fù)制數(shù)組的方法例子9Example4_9.javaLeaveOneAround.java圍圈留一是一個(gè)古老的問題（也稱約瑟夫問題）：若干個(gè)人圍成一圈，從某個(gè)人開始順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，然后繼續(xù)順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，依此類推，程序輸出圈中最后剩下的一個(gè)人。圍圈留1問題可以簡化為旋轉(zhuǎn)數(shù)組（向左或向右旋轉(zhuǎn)數(shù)組），旋轉(zhuǎn)數(shù)組2次即可確定出退出圈中的人，即此時(shí)數(shù)組首元素中的號碼就應(yīng)該是要退出圈中的人。例子9中，LeaveOneAround類的leaveOne(int[]people)方法通過旋轉(zhuǎn)數(shù)組確定數(shù)組people中出圈的元素，并用copyOfRange()方法保留剩余的元素。2024/11/9954.4數(shù)組的復(fù)制2.處理重復(fù)數(shù)據(jù)例子9Example4_10.javaHandleRecurring.java有時(shí)候需要處理數(shù)組中重復(fù)的數(shù)據(jù)，即讓重復(fù)的數(shù)據(jù)只保留一個(gè)。例子10中，HandleRecurring類的handleRecurring(int[]arr)方法處理數(shù)組arr中重復(fù)的數(shù)據(jù)，該方法返回的數(shù)組中的數(shù)據(jù)是arr中去掉重復(fù)數(shù)據(jù)后的數(shù)據(jù)（重復(fù)的數(shù)據(jù)只保留一個(gè)）。4.5數(shù)組的比較2024/11/996Arrays類中的靜態(tài)方法intcompare()和booleanequals()都是重載的方法，用于比較兩個(gè)數(shù)組，二者的區(qū)別僅僅是返回值的類型不同。2024/11/9974.5數(shù)組的比較例子11Example4_11.javaFindWord.java例子11中，F(xiàn)indWord類的findWord(Stringstr,Stringword)方法輸出str中出現(xiàn)的word并返回word出現(xiàn)的次數(shù)。例子11的主類Exmple4_11輸出一段英文中出現(xiàn)的girl和girl出現(xiàn)的次數(shù)4.6公共子數(shù)組2024/11/998如果數(shù)組a的某個(gè)子數(shù)組和數(shù)組b的某個(gè)子數(shù)組的長度相同（不要求兩個(gè)子數(shù)組的起始索引相同），所包含的元素值也依次相同，就稱二者有公共子數(shù)組。2024/11/9994.6公共子數(shù)組讓長度小的數(shù)組，比如b的首單元和數(shù)組a的未單元對齊，數(shù)組b一直向左移動，直到數(shù)組b的尾部a的首單元對齊。向左滑動法那么在左移的過程中，數(shù)組a和數(shù)組b二者的所有公共子數(shù)組一定會出現(xiàn)左對齊的情況。數(shù)組a數(shù)組b2024/11/91004.6公共子數(shù)組例子12Example4_12.javaFindZeroCount.java讓長度小的數(shù)組，比如b的首單元和數(shù)組a的未單元對齊，即b的左端和a的右端對齊，然后進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果存放到一個(gè)其它數(shù)組c中，讓數(shù)組b按一個(gè)單元（元素）為單位向左依次移動（滑動），每移動一個(gè)單元，進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果存放到數(shù)組c中。數(shù)組b一直向左移動，直到數(shù)組b的尾部，即最后一個(gè)單元和數(shù)組a的首單元對齊。向左滑動法那么在左移的過程中，數(shù)組a和數(shù)組b二者的所有公共子數(shù)組一定會出現(xiàn)左對齊的情況。由異或運(yùn)算法則可知，相同的整數(shù)異或的結(jié)果是0，那么只要根據(jù)數(shù)組c中連續(xù)出現(xiàn)的0的個(gè)數(shù)，就可以找到一個(gè)最大的公共子數(shù)組。MaxCommon.java4.7數(shù)組的更新2024/11/9101Arrays類提供了對數(shù)組整體更新的方法：fill()和setAll()。1.整體更新為單值：voidfill(int[]a,intval)該方法將參數(shù)數(shù)組a的每個(gè)元素的而值都設(shè)置為參數(shù)val指定的值。2.動態(tài)更新setAll()方法是一個(gè)重載方法，例如：publicstaticvoidsetAll(double[]a,IntToDoubleFunctiongenerator)將參數(shù)數(shù)組a的每個(gè)元素的值都設(shè)置為參數(shù)generator的計(jì)算結(jié)果。2024/11/91024.7數(shù)組的更新例子13Example4_13.javapublicstaticvoidsetAll(int[]a,IntUnaryOperatorgenerator)IntUnaryOperator是一個(gè)函數(shù)接口，其中的抽象方法的參數(shù)是int型，返回值是int型?？梢詫⒁粋€(gè)Lambda表達(dá)式傳遞給generator，該Lambda表達(dá)式必須是1個(gè)int型參數(shù)，Lambda表達(dá)式中必須有return語句，返回的值是int型數(shù)據(jù)。setAll()方法會使用Lambda表達(dá)式依次設(shè)置數(shù)組a的元素的值。例子13中，主類Example4_13使用fill()和setAll()方法整體更新數(shù)組的元素的值.4.8數(shù)組的前綴算法2024/11/9103數(shù)組a的前綴算法是：①i初始化0，進(jìn)行②。②如果i的值滿足結(jié)束條件，進(jìn)行③，否則將某個(gè)運(yùn)算結(jié)果賦值到數(shù)組的第i+1個(gè)元素中（通常是a[i]與a[i+1]參與的運(yùn)算）。i++，執(zhí)行②。③結(jié)束2024/11/91044.8數(shù)組的前綴算法例子14Example4_14.javapublicstaticvoidparallelPrefix(int[]a,IntBinaryOperatorop)IntBinaryOperator是一個(gè)函數(shù)接口，其中的抽象方法的是2個(gè)int參數(shù)，返回值是int型?？梢詫⒁粋€(gè)Lambda表達(dá)式傳遞給op，該Lambda表達(dá)式必須是2個(gè)int型參數(shù)，Lambda表達(dá)式中必須有return語句，返回的值是int型數(shù)據(jù)。例如：IntBinaryOperatorop=(i,j)->{returni+j;};Arrays.parallelPrefix(arr,op);parallelPrefix()在執(zhí)行過程中，讓i取數(shù)組的第i個(gè)元素的值，j取數(shù)組的第i+1個(gè)元素的值，將Lambda表達(dá)式中return語句的返回值設(shè)置為數(shù)組第j個(gè)元素的值后，然后i再自增，再重復(fù)前面的計(jì)算。。4.9動態(tài)遍歷2024/11/9105遍歷數(shù)組的方法（算法）在遍歷數(shù)組時(shí)，讓數(shù)組的每個(gè)元素參與某種運(yùn)算，并輸出運(yùn)算后的結(jié)果，稱這樣的遍歷方法為動態(tài)遍歷方法。①將數(shù)組a的全部元素或部分元素封裝到Spliterator.OfInt對象中。②Spliterator.OfInt對象調(diào)用voidforEachRemaining(IntConsumerconsumer)方法遍歷Spliterator.OfInt對象中封裝的數(shù)組元素。2024/11/91064.9動態(tài)遍歷例子15Example4_15.javaforEachRemaining(IntConsumerconsumer)方法遍歷Spliterator.OfInt對象中封裝的數(shù)組元素。該方法的參數(shù)intConsumer是一個(gè)函數(shù)接口，該接口中的抽象方法的參數(shù)是int型，返回類型是void型。那么在調(diào)用forEachRemaining(IntConsumerconsumer)方法時(shí)，可以將一個(gè)Lambda表達(dá)式傳遞給consumer，該Lambda表達(dá)式必須是1個(gè)int型參數(shù)，不需要return語句（如果有return，不允許返回任何值）。比如，可以將下列Lambda表達(dá)式(value)->{System.out.println(value);}傳遞給consumer，forEachRemaining(IntConsumerconsumer)方法在執(zhí)行過程中將使用這個(gè)Lambda表達(dá)式，讓Lambda表達(dá)式的參數(shù)valule依次取Spliterator.OfInt對象中封裝的數(shù)組元素1.動態(tài)方法2024/11/91074.9動態(tài)遍歷例子16Com.java

可以自己編寫簡單的遍歷數(shù)組的動態(tài)方法，即方法的參數(shù)是一個(gè)函數(shù)接口。2.編寫動態(tài)方法例子16中，Com接口有一個(gè)抽象方法compute()，是一個(gè)函數(shù)接口（除了其它方法外，有且只有一個(gè)抽象方法的接口是函數(shù)接口）。Com接口中的outPut()方法的參數(shù)是一個(gè)函數(shù)接口，因此可以向該參數(shù)傳遞Lambda表達(dá)式。Example4_16.java2024/11/91084.9動態(tài)遍歷例子172.多線程遍歷Example4_17.java可以用多線程遍歷數(shù)組。在使用多線程之前，需要將封裝數(shù)組元素的Spliterator進(jìn)行拆分，即分解成幾部分，每一部分稱作Spliterator的一個(gè)分區(qū)，然后讓一個(gè)線程負(fù)責(zé)遍歷一個(gè)分區(qū)。Spliterator對象可以調(diào)用Spliterator<T>trySplit()方法將自己一拆為二，即trySplit()方法從當(dāng)前Spliterator對象中分離出一半的數(shù)組元素構(gòu)成一個(gè)新的Spliterator對象（當(dāng)前Spliterator對象中的數(shù)組元素減少一半），并返回這個(gè)新的Spliterator對象（對于數(shù)組，按索引順序，分離出后一半元素值）。對于較大的數(shù)組，將對應(yīng)的Spliterator進(jìn)行分區(qū)，使用多線程可以加快遍歷數(shù)組的速度。4.10數(shù)組與洗牌2024/11/9109

2024/11/91104.10數(shù)組與洗牌例子18ShuffleCard.java

Example4_18.java4.11數(shù)組與生命游戲2024/11/9111生命游戲?qū)儆诙S細(xì)胞自動機(jī)的一種，是英國數(shù)學(xué)家JohnHortonConway(約翰.何頓.康威)在1970年發(fā)明的一種特殊二維細(xì)胞自動機(jī)。將二維平面上的每一個(gè)格子看成是一個(gè)細(xì)胞生命體，每個(gè)細(xì)胞生命都有“生和死”兩種狀態(tài)，每一個(gè)細(xì)胞旁邊都有鄰居細(xì)胞存在，比如把3*3的9個(gè)格子構(gòu)成的正方形看成一個(gè)基本單位的話，那么這個(gè)正方形中心的細(xì)胞的鄰居就是它旁邊的8個(gè)細(xì)胞（至多8個(gè)）。4.11數(shù)組與生命游戲2024/11/9112一個(gè)細(xì)胞的下一代的生死狀態(tài)變化遵循下面的生命游戲算法。①細(xì)胞周圍有3個(gè)細(xì)胞為生，下一代該細(xì)胞為生（當(dāng)前細(xì)胞若原先為死，則轉(zhuǎn)為生，若原先為生，則保持不變）。②細(xì)胞周圍有2個(gè)細(xì)胞為生，下一代該細(xì)胞的生死狀態(tài)保持不變。③細(xì)胞周圍是其它情況，下一代該細(xì)胞為死。（即該細(xì)胞若原先為生，則轉(zhuǎn)為死，若原先為死，則保持不變）。2024/11/91134.11數(shù)組與生命游戲例子18AggregateOperation.javaExample4_19.java例子19中，AggregateOperation類定義了一些關(guān)于二維數(shù)組的一些方法，以便LifeGame類調(diào)用使用，使得LifeGame類的代碼更加簡練，提高可讀性。主類Example4_19使用LifeGame類輸出了生命游戲中生命狀態(tài)的變化。LifeGame.java第5章鏈表與LinkedList類2024/11/91145.1鏈表的特點(diǎn)2024/11/9115鏈表是由若干個(gè)節(jié)點(diǎn)組成，這些節(jié)點(diǎn)形成的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，節(jié)點(diǎn)的存儲結(jié)構(gòu)是鏈?zhǔn)酱鎯Γ垂?jié)點(diǎn)的物理地址不必是依次相鄰的。對于單鏈表，每個(gè)結(jié)點(diǎn)含有一個(gè)數(shù)據(jù)，并含有下一個(gè)節(jié)點(diǎn)的引用。對于雙鏈表，每個(gè)節(jié)點(diǎn)含有一個(gè)數(shù)據(jù)，并含有上一個(gè)節(jié)點(diǎn)的引用和下一個(gè)結(jié)點(diǎn)的引用（Java實(shí)現(xiàn)的是雙鏈表）2024/11/91165.1鏈表的特點(diǎn)圖示意的是有5個(gè)節(jié)點(diǎn)的雙鏈表（省略了上一個(gè)節(jié)點(diǎn)的引用箭頭示意）。注意，鏈表的節(jié)點(diǎn)序號是從0開始，每個(gè)節(jié)點(diǎn)的序號等于它前面的節(jié)點(diǎn)的個(gè)數(shù)。鏈表中的節(jié)點(diǎn)的物理地址不必是相鄰的，因此，鏈表的優(yōu)點(diǎn)是不需要占用一塊連續(xù)的內(nèi)存存儲空間。圖5.12024/11/91175.1鏈表的特點(diǎn)

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

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

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

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

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

插入新節(jié)點(diǎn)后，新鏈表中的節(jié)點(diǎn)序號按新的鏈表長度從0開始排列。2024/11/91235.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/9124鏈表由Java集合框架（JavaCollectionsFramework，JCF）中的LinkedList<E>泛型類所實(shí)現(xiàn)。2024/11/91255.2創(chuàng)建鏈表LinkedList<E>泛型類實(shí)現(xiàn)了Java集合框架中的List和Queue泛型接口。LinkedLis<E>t泛型類繼承了List和Queue泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了List和Queue泛型接口中的抽象方法。2024/11/91265.2創(chuàng)建鏈表例子1Example5_1.java使用LinkedList<E>泛型類聲明鏈表時(shí)，必須要指定E的具體類型，類型是類或接口類型（不可以是基本類型，比如int、float、char等），即指定鏈表中節(jié)點(diǎn)里的對象的類型。例如，指定E是String類型：LinkedList<String>listOne=newLinkedList<>();或LinkedList<String>listOne=newLinkedList<String>();例子1中的主類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查詢與相等2024/11/9127查詢鏈表節(jié)點(diǎn)中的數(shù)據(jù)的常用方法：

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

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

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

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

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

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

使用視圖時(shí)，要注意視圖中節(jié)點(diǎn)和原鏈表節(jié)點(diǎn)的對應(yīng)關(guān)系。2024/11/91395.7鏈表的視圖List<E>subList(intfromIndex,inttoIndex)方法是AbstractList類所實(shí)現(xiàn)的List接口中的一個(gè)方法（AbstractList類是LinkedList的間接父類）。該方法返回一個(gè)當(dāng)前鏈表中節(jié)點(diǎn)序號fromIndex（含）和toIndex（不含）之間的節(jié)點(diǎn)構(gòu)成的視圖。需要特別注意的是，一旦鏈表添加或刪除節(jié)點(diǎn)，就會破壞視圖的索引，即會影響之前鏈表subList()方法返回的視圖，這個(gè)視圖將無法再繼續(xù)被使用（如果繼續(xù)使用，運(yùn)行時(shí)刻會觸發(fā)ConcurrentModificationException異常），鏈表必須用subList()方法重新返回一個(gè)新的視圖。更改視圖的節(jié)點(diǎn)（增加或刪除節(jié)點(diǎn)）或?qū)?jié)點(diǎn)的數(shù)據(jù)的修改都會使得當(dāng)前鏈表發(fā)生同步的改變。2024/11/91405.7鏈表的視圖使用視圖時(shí)，要注意視圖中節(jié)點(diǎn)和原鏈表節(jié)點(diǎn)的對應(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/91415.7鏈表的視圖使用視圖時(shí)，要注意視圖中節(jié)點(diǎn)和原鏈表節(jié)點(diǎn)的對應(yīng)關(guān)系。如果視圖listView增加一個(gè)節(jié)點(diǎn)，比如尾節(jié)點(diǎn)：鬣狗那么原鏈表list會同步更新、發(fā)生變化，獵豹節(jié)點(diǎn)和河馬節(jié)點(diǎn)之間多了一個(gè)鬣狗節(jié)點(diǎn)：2024/11/91425.7鏈表的視圖例子9Example5_9.java例子9的主類Example5_9使用鏈表的視圖更新鏈表節(jié)點(diǎn)中的天氣信息。5.8鏈表的排序2024/11/9143publicdefaultvoidsort(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/91445.8鏈表的排序Comparator是一個(gè)函數(shù)接口，因此在使用該方法時(shí)，可以向參數(shù)c傳遞一個(gè)Lambda表達(dá)式，該Lambda表達(dá)式必須是2個(gè)參數(shù)，Lambda表達(dá)式中必須有return語句，返回的值是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/91455.8鏈表的排序例子10Student.java例子10的主類Example5_10分別按學(xué)生的數(shù)學(xué)和英文成績升序排序鏈表、降序排序鏈表。Example5_10.java5.9遍歷鏈表2024/11/9146某些集合根據(jù)其數(shù)據(jù)存儲結(jié)構(gòu)和所具有的操作也會提供返回?cái)?shù)據(jù)的方法，例如LinkedList類中的get(intindex)方法將返回當(dāng)前鏈表中第index節(jié)點(diǎn)中的對象。LinkedList的存儲結(jié)構(gòu)不是順序結(jié)構(gòu)，即節(jié)點(diǎn)的物理地址不必是依次相鄰的，因此，鏈表調(diào)用get(intindex)方法的速度比順序存儲結(jié)構(gòu)的集合調(diào)用get(intindex)方法的速度慢。當(dāng)用戶需要遍歷集合中的節(jié)點(diǎn)時(shí)，應(yīng)當(dāng)使用該集合提供的迭代器，而不是讓集合本身來遍歷其中的節(jié)點(diǎn)。2024/11/91475.9遍歷鏈表單向迭代器是從鏈表的頭節(jié)點(diǎn)開始，遍歷到尾節(jié)點(diǎn)。●單向迭代器鏈表對象可以使用Iterator<E>iterator()方法獲取一個(gè)實(shí)現(xiàn)Iterator接口的對象，該對象就是針對當(dāng)前鏈表的單向迭代器。迭代器內(nèi)部使用了游標(biāo)技術(shù)，單向迭代器的游標(biāo)的初始狀態(tài)是指向鏈表的頭節(jié)點(diǎn)的前面，如果游標(biāo)可以向后移動（向鏈表的尾節(jié)點(diǎn)方向），單向迭代器調(diào)用hasNext()方法返回true，否則返回false。連續(xù)的調(diào)用next()方法會將游標(biāo)移動到尾節(jié)點(diǎn)，這時(shí)游標(biāo)將無法向后移動，再調(diào)用next()方法否則觸發(fā)運(yùn)行異常NoSuchElementException（鏈表是空鏈表，直接調(diào)用next()方法也會觸發(fā)運(yùn)行異常NoSuchElementException）。2024/11/91485.9遍歷鏈表●雙向迭代器鏈表對象可以使用ListIterator<E>listIterator()方法獲取一個(gè)實(shí)現(xiàn)ListIterator接口的對象（ListIterator接口是Iterator的子接口），該對象就是針對當(dāng)前鏈表的雙向迭代器。雙單向迭代器是雙游標(biāo)迭代器，一個(gè)向后游標(biāo)（向鏈表的尾節(jié)點(diǎn)方向），一個(gè)向前游標(biāo)（向鏈表的頭節(jié)點(diǎn)方向）。雙游標(biāo)是同時(shí)移動，向前游標(biāo)在向后游標(biāo)的后面。

初始狀態(tài)向后游標(biāo)指向頭節(jié)點(diǎn)的前面，向前游標(biāo)指向頭節(jié)點(diǎn)。2024/11/91495.9遍歷鏈表●遍歷與更新迭代器對鏈表實(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)序號從當(dāng)前節(jié)點(diǎn)開始遞增），調(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/91505.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)。

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

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

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

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

6.2創(chuàng)建順序表2024/11/9161順序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayList<E>泛型類所實(shí)現(xiàn)。2024/11/91626.2創(chuàng)建順序表ArrayList<E>泛型類的實(shí)列使用數(shù)組管理節(jié)點(diǎn)，因此節(jié)點(diǎn)就是對象，后面的敘述不再說節(jié)點(diǎn)里的對象。ArrayList<E>泛型類實(shí)現(xiàn)了Java集合框架中的List泛型接口(和鏈表不同，沒有實(shí)現(xiàn)Queue泛型接口)。ArrayList<E>泛型類繼承了List泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了List泛型接口中的抽象方法。2024/11/91636.2創(chuàng)建順序表順序表可以使用add(Eobj)方法向順序表依次增加節(jié)點(diǎn)。創(chuàng)建空順序表，使用ArrayList<E>泛型類聲明順序表時(shí)，必須要指定E的具體類型，類型是類或接口類型（不可以是基本類型，比如int、float、char等）即指定順序表中節(jié)點(diǎn)（對象）的類型。例如，指定E是String類型：ArrayList<String>arrlistOne=newArrayList<>();或ArrayList<String>arrlistOne=newArrayList<String>();例子1Example6_1.java例子1中的主類Example6_1中首先創(chuàng)建一個(gè)空順序表arrlistOne，然后向