數(shù)據(jù)結(jié)構(gòu)與算法（Java語(yǔ)言版）課件 第11-13章 集合HashSet類(lèi)、常用算法與Collections類(lèi)、圖論

第10章散列表與HashMap類(lèi)2024/11/9110.1散列結(jié)構(gòu)的特點(diǎn)2024/11/92生活中有些數(shù)據(jù)之間可能是密切相關(guān)的一對(duì)，例如，一副手套，一雙鞋子，一對(duì)夫妻等，即數(shù)據(jù)的邏輯結(jié)構(gòu)是成對(duì)的，即不是線(xiàn)性也不是樹(shù)形結(jié)構(gòu)，一對(duì)數(shù)據(jù)與另一對(duì)數(shù)據(jù)之間也無(wú)須有必然的關(guān)系。如何存儲(chǔ)這樣的數(shù)據(jù)對(duì)，也是數(shù)據(jù)結(jié)構(gòu)非常關(guān)心的，以下要介紹的散列結(jié)構(gòu)，就是存儲(chǔ)“數(shù)據(jù)對(duì)”的最重用的手段之一.2024/11/9310.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表數(shù)據(jù)對(duì)，也稱(chēng)作"鍵-值"對(duì)，鍵和值都是某種類(lèi)的實(shí)例，即對(duì)象。敘述時(shí)可以把這"鍵-值"對(duì)記作(key,value)，稱(chēng)key是關(guān)鍵字、value是鍵值或值。散列結(jié)構(gòu)使用兩個(gè)集合存儲(chǔ)對(duì)象，一個(gè)集合稱(chēng)作關(guān)鍵字集合，記作Key。另一個(gè)是值的集合，記作Value。Key集合中的節(jié)點(diǎn)（或稱(chēng)元素）負(fù)責(zé)存儲(chǔ)關(guān)鍵字，所有關(guān)鍵字對(duì)應(yīng)的全部值稱(chēng)作散列結(jié)構(gòu)的值集合，記作Value，即Value中的節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)值。稱(chēng)Value為散列結(jié)構(gòu)中的散列表（hash表，也常常被音譯稱(chēng)作哈希表）。簡(jiǎn)單說(shuō)，散列結(jié)構(gòu)是根據(jù)關(guān)鍵字直接進(jìn)行訪問(wèn)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，其核心思想是使用散列函數(shù)（hash()函數(shù)）把關(guān)鍵字映射到散列表中一個(gè)位置，即映射到散列表中的某個(gè)節(jié)點(diǎn)。2024/11/9410.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表hash()函數(shù)本質(zhì)上就是集合Key到整數(shù)集合

2024/11/9510.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表對(duì)于一個(gè)關(guān)鍵字，比如key1，如果hash(key1)=98，那么key1關(guān)鍵字對(duì)應(yīng)的節(jié)點(diǎn)就是數(shù)組hashValue第98個(gè)元素，即hashValue[98]。2024/11/9610.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表一個(gè)散列函數(shù)，即hash()函數(shù)需保證下列兩點(diǎn)：①

對(duì)于不同的關(guān)鍵字，比如，key1，key2是Key中兩個(gè)節(jié)點(diǎn)，即兩個(gè)關(guān)鍵字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是兩個(gè)不同的節(jié)點(diǎn)。但節(jié)點(diǎn)中的對(duì)象可能是相同的（數(shù)組的兩個(gè)不同的元素中的值可能是相同的）。②為了保證第①點(diǎn)，讓hash()函數(shù)映射出的全部節(jié)點(diǎn)，分散地分布在一塊連續(xù)的內(nèi)存中，這也是人們把Value稱(chēng)作一個(gè)散列表的原因。由于散列表中的節(jié)點(diǎn)是隨機(jī)、分散分布的，所以我們不在散列表上定義任何關(guān)系（見(jiàn)第1章）。散列表或散列二字不是指數(shù)據(jù)之間的關(guān)系，而是形容存儲(chǔ)形式的特點(diǎn)（hash()函數(shù)映射存儲(chǔ)位置）。如果出現(xiàn)hash(key1)和hash(key2)相同，就稱(chēng)關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少?zèng)_突的可能性，以及在沖突不可避免時(shí)能給出解決的問(wèn)題的算法。2024/11/9710.1散列結(jié)構(gòu)的特點(diǎn)●散列結(jié)構(gòu)與散列表如果出現(xiàn)hash(key1)和hash(key2)相同，就稱(chēng)關(guān)鍵字有沖突。散列算法就是研究如何避免沖突或減少?zèng)_突的可能性，以及在沖突不可避免時(shí)能給出解決的問(wèn)題的算法?？梢杂面溄臃ń鉀Q沖突，散列函數(shù)把和關(guān)鍵字key有相同對(duì)應(yīng)的值的那些關(guān)鍵字所對(duì)應(yīng)的存儲(chǔ)位置依次設(shè)置為一個(gè)鏈表的中不同的節(jié)點(diǎn)（鏈表頭節(jié)點(diǎn)是key對(duì)應(yīng)的存儲(chǔ)位置），這樣一來(lái)，就會(huì)增大查詢(xún)Value中值的時(shí)間復(fù)雜度。如果散列函數(shù)設(shè)計(jì)的合理，那么一般不會(huì)發(fā)生關(guān)鍵字沖突或發(fā)生關(guān)鍵字沖突的概率非常小，因此也就不需要使用鏈?zhǔn)椒椒ń鉀Q沖突或使用鏈?zhǔn)椒椒ń鉀Q沖突的概率很小。鏈接法是最后保證不同關(guān)鍵字對(duì)應(yīng)的不同節(jié)點(diǎn)（不同的存儲(chǔ)位置）的最后辦法。2024/11/9810.1散列結(jié)構(gòu)的特點(diǎn)●查找、添加、刪除的特點(diǎn)由散列結(jié)構(gòu)的特點(diǎn)可以知道，使用關(guān)鍵字查找、刪除、添加Value中的節(jié)點(diǎn)，時(shí)間復(fù)雜度通常都是

（如果關(guān)鍵字沖突，使用了鏈接法）散列結(jié)構(gòu)具有數(shù)組的優(yōu)點(diǎn)，即非?？斓牟樵?xún)速度，同時(shí)又將查詢(xún)數(shù)據(jù)（Value）的索引分離到另一個(gè)獨(dú)立的集合中（Key）。數(shù)組最大的缺點(diǎn)就是將索引（下標(biāo)）和數(shù)組元素綁定，因此，一旦創(chuàng)建數(shù)組，就無(wú)法更改索引，即無(wú)法再改變數(shù)組的長(zhǎng)度。而散列結(jié)構(gòu)可以隨時(shí)添加一個(gè)“鍵-值”對(duì)（一個(gè)關(guān)鍵字，一個(gè)相應(yīng)的值），或刪除一個(gè)“鍵-值”對(duì)。10.2簡(jiǎn)單的散列函數(shù)2024/11/99通過(guò)簡(jiǎn)單的例子：停車(chē)場(chǎng)，進(jìn)一步理解散列結(jié)構(gòu)，后面我們將使用Java的HashMap類(lèi)實(shí)現(xiàn)的散列結(jié)構(gòu)。2024/11/91010.2簡(jiǎn)單的散列函數(shù)●順序擴(kuò)建停車(chē)位當(dāng)Value中節(jié)點(diǎn)的數(shù)目越來(lái)越多時(shí)，比如達(dá)到總內(nèi)存大小的一半時(shí)，就要重新調(diào)整內(nèi)存，即分配新的數(shù)組，并把原數(shù)組hashValue[]的值復(fù)制到新的數(shù)組中，新的數(shù)組成為Value的新的一塊連續(xù)內(nèi)存。汽車(chē)停車(chē)場(chǎng)（模擬散列表）初始狀態(tài)有10個(gè)連續(xù)的車(chē)位，相當(dāng)于散列結(jié)構(gòu)中分配給散列表Value的一塊連續(xù)的內(nèi)存空間（數(shù)組的長(zhǎng)度是10）。假設(shè)汽車(chē)的車(chē)牌號(hào)是3位數(shù)的正整數(shù)，相當(dāng)于散列結(jié)構(gòu)中的Key集合中節(jié)點(diǎn)里的關(guān)鍵字。停車(chē)場(chǎng)可以根據(jù)需要，隨時(shí)順序地?cái)U(kuò)大停車(chē)場(chǎng)，即連續(xù)地?cái)U(kuò)建停車(chē)位。

2024/11/91110.2簡(jiǎn)單的散列函數(shù)●順序擴(kuò)建停車(chē)位

2024/11/91210.2簡(jiǎn)單的散列函數(shù)●順序擴(kuò)建停車(chē)位每當(dāng)一輛車(chē)來(lái)到停車(chē)場(chǎng)，如果用散列函數(shù)計(jì)算了若干次，得到的車(chē)位號(hào)對(duì)應(yīng)的車(chē)位上都是已經(jīng)停放了車(chē)輛，這個(gè)時(shí)候，就擴(kuò)建停車(chē)場(chǎng)、讓其容量增加2倍，然后再用散列函數(shù)計(jì)算車(chē)位號(hào)……，如此這般，只要內(nèi)存足夠大，總能找到停車(chē)位，如圖所示意。由于用散列函數(shù)的算法是隨機(jī)的，所以，某個(gè)時(shí)刻以后，擴(kuò)建停車(chē)場(chǎng)的概率就很小了。2024/11/91310.2簡(jiǎn)單的散列函數(shù)●鏈?zhǔn)綌U(kuò)展停車(chē)位當(dāng)用散列函數(shù)計(jì)算出同樣的車(chē)位數(shù)時(shí)，比如都是9，就把二者的停車(chē)位分別指定為同一個(gè)鏈表中的不同的兩個(gè)節(jié)點(diǎn)，鏈表的頭節(jié)點(diǎn)是數(shù)組的第9個(gè)元素。2024/11/91410.2簡(jiǎn)單的散列函數(shù)例子1Key.javaExample10_1.java例子1中的ParkingOne類(lèi)使用順序辦法增加停車(chē)場(chǎng)的車(chē)位，ParkingTwo類(lèi)使用鏈?zhǔn)睫k法增加停車(chē)場(chǎng)的車(chē)位。Car.javaParkingOne.javaParkingTwo.java例子1中的主類(lèi)Example10_1模擬了兩個(gè)停車(chē)場(chǎng)的停車(chē)情況。10.3HashMap類(lèi)2024/11/915HashMap<K,V>泛型類(lèi)繼承Map泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了Map泛型接口中的抽象方法。HashMap<K,V>泛型類(lèi)的對(duì)象為散列表,散列表的Key集合是實(shí)現(xiàn)Set接口的一個(gè)實(shí)例，Key集合中不允許有兩個(gè)結(jié)點(diǎn)中的對(duì)象相同，即大小一樣的兩個(gè)結(jié)點(diǎn)，Key中不同的key對(duì)應(yīng)的Value中的節(jié)點(diǎn)是不同的，但Value中的節(jié)點(diǎn)中的對(duì)象，即數(shù)據(jù)可以是相同的，就像數(shù)組的不同元素（節(jié)點(diǎn)）里可以存放相同的數(shù)據(jù)。HashMap<K,V>泛型類(lèi)提供的添加、刪除、查找等操作的時(shí)間復(fù)雜度都是O(1).2024/11/91610.3HasMap類(lèi)HashMap<K,V>泛型類(lèi)直接實(shí)現(xiàn)了Map接口，注意，沒(méi)有實(shí)現(xiàn)SortedMap接口。2024/11/91710.3HasMap類(lèi)例子2Example10_2.java聲明一個(gè)HashMap<K,V>泛型類(lèi)的對(duì)象，即散列表，必須要指定Key和Value的具體類(lèi)型，類(lèi)型是類(lèi)或接口類(lèi)型（不可以是基本類(lèi)型，比如int、float、char等）即指定Key中節(jié)點(diǎn)里的對(duì)象的類(lèi)型和Value中節(jié)點(diǎn)里的對(duì)象的類(lèi)型。例如，指定K是String類(lèi)型、V是Car類(lèi)型，例如：HashMap<String,Car>hashMap=newHashMap<>();或HashMap<String,Car>hashMap=newHashMap<String,Car>();Car.java例子2中的主類(lèi)Example10_2中首先創(chuàng)建一個(gè)空散列表hashMapOne，然后向散列表hashMapOne添加4個(gè)”鍵-值”對(duì)，隨后再用hashMapOne創(chuàng)建另一個(gè)散列表hashMapTwo。10.4散列表的基本操作2024/11/918publicVput(Kkey,Vvalue)向散列表添加”鍵-值”對(duì)，即將key存儲(chǔ)在Key中，把value放置在Value中，如果添加成功返回null。需要注意的是，如果散列表Key中已經(jīng)有了鍵key，那么當(dāng)前添加的”鍵-值”對(duì)將替換已存在的”鍵-值”對(duì)，并返回舊”鍵-值”對(duì)中的value值，即返回被替換的”鍵-值”對(duì)的值。publicVputIfAbsent(Kkey,Vvalue)如果散列表Key中沒(méi)有key，則添加該鍵值對(duì)(key,value)到散列表，并返回null，如果散列表Key中已經(jīng)有鍵key，則返回舊key對(duì)應(yīng)的value(不做添加操作)。10.4散列表的基本操作2024/11/919publicVget(Objectkey)返回”鍵-值”對(duì)(key,value)中的value，如果key不在集合Key中，方法返回null。publicbooleancontainsKey(Objectkey)判斷Key中是否有關(guān)鍵字key，有返回true，否則返回false。publicbooleancontainsValue(Objectvalue)判斷Value中是否有value，有返回true，否則返回false。publicbooleanisEmpty()如果散列表中沒(méi)有任何"鍵-值"對(duì)，則返回true，否則返回false。10.4散列表的基本操作2024/11/920publicVremove(Objectkey)刪除關(guān)鍵字key組合的”鍵-值”對(duì)(key,value)，并返回value。publicVreplace(Kkey,Vvalue)如果散列表Key已有key，就用(key,value)替換已有的key組合的”鍵-值”對(duì)，并返回替換后的value，如果Key中沒(méi)有關(guān)鍵字key，不進(jìn)行替換操作，并返回null。publicvoidclear()刪除散列表的全部”鍵-值”對(duì)。2024/11/92110.4散列表的基本操作例子3Example10_3.java例子3的主類(lèi)Example10_3使用了HashMap<K,V>泛型類(lèi)的一些常用方法。10.5遍歷散列表2024/11/922publicvoidforEach(BiConsumer<?superK,?superV>action)對(duì)散列表中的所有(key,value)執(zhí)行給定的action操作，直到所有(key,value)對(duì)都被處理或操作引發(fā)異常。BiConsumer是一個(gè)函數(shù)接口，該接口里的抽象方法是voidaccept(Kk,Vv)。使用forEach()方法時(shí)將一個(gè)Lambda表達(dá)式傳遞給action，例如：（k,v）->{System.out.println(v);}。forEach()方法將Lambda表達(dá)式中的k,v，依次取散列表中的(key,value)。2024/11/92310.5遍歷散列表例子4Example10_4.java例子4的主類(lèi)Example10_4將正整數(shù)和正整數(shù)的平方根（最多保留3位小數(shù)）作為(key,value)存放在一個(gè)散列表中，然后遍歷散列表。10.6散列表與字符、單詞頻率2024/11/924●每次讀取文件的一個(gè)字符，如果是字母，并且散列表中還沒(méi)有(key,value)：(字母,次數(shù))，散列表就添加(key,value)：(字母，次數(shù))，如果散列表中已經(jīng)有(key,value)：(字母，次數(shù))，就更新該(key,value)：(字母，次數(shù))，將其次數(shù)增加1?！衩看巫x取文件的一個(gè)單詞，如果散列表中還沒(méi)有(key,value)：(單詞，次數(shù))，散列表就添加(key,value)：(單詞，次數(shù))，如果散列表中已經(jīng)有(key,value)：(單詞，次數(shù))，就更新該(key,value)：(單詞，次數(shù))，將其次數(shù)增加1。2024/11/92510.6散列表與字符、單詞頻率例子5LettersFrequency.java例子5中的LettersFrequency類(lèi)負(fù)責(zé)統(tǒng)計(jì)文本文件中字符出現(xiàn)的次數(shù)和頻率，WordsFrequency負(fù)責(zé)統(tǒng)計(jì)文本文件中單詞出現(xiàn)的次數(shù)和頻率。WordsFrequency.javaExample10_5.java例子5中Example10_5.java中的主類(lèi)Example10_5使用LettersFrequency類(lèi)統(tǒng)計(jì)了Example10_5.java里字母出現(xiàn)的次數(shù)和頻率，另外一個(gè)主類(lèi)MainClass使用WordsFrequency統(tǒng)計(jì)了Example10_5.java里單詞出現(xiàn)的次數(shù)和頻率。10.7散列表與單件模式2024/11/926●單件模式

保證一個(gè)類(lèi)僅有一個(gè)實(shí)例，并提供一個(gè)訪問(wèn)它的全局訪問(wèn)點(diǎn)。散列表可以用來(lái)存儲(chǔ)已知的數(shù)據(jù)，在后續(xù)的操作中，通過(guò)散列表查找是否已經(jīng)存在，從而實(shí)現(xiàn)唯一性驗(yàn)證的功能。因此在實(shí)現(xiàn)的具體代碼中可以借助散列表來(lái)實(shí)現(xiàn)單件模式。2024/11/92710.7散列表與單件模式例子6SingletonSun.javaExample10_6.java例子6中的SingletonSun類(lèi)實(shí)現(xiàn)了單件模式，SingletonSun類(lèi)只能創(chuàng)建一個(gè)“太陽(yáng)”。在例子6中，SingletonSun類(lèi)中的getInstance()方法檢查散列表中是否已經(jīng)存在當(dāng)前類(lèi)的實(shí)例對(duì)象，如果不存在則創(chuàng)建一個(gè)新的，然后將其存儲(chǔ)到散列表中，并返回該實(shí)例。這樣就保證了SingletonSun類(lèi)在整個(gè)程序中只能創(chuàng)建它的一個(gè)對(duì)象。10.8散列表與數(shù)據(jù)緩存2024/11/928

2024/11/92910.8散列表與數(shù)據(jù)緩存例子7Hash.javaExample10_7.java例子7中的Hash類(lèi)將頻繁使用的階乘放在散列表中(用到第3章例子3中的SumMulti類(lèi))10.9TreeMap類(lèi)2024/11/93010.9TreeMap類(lèi)2024/11/931在類(lèi)的層次上，TreeMap<K,V>泛型類(lèi)HashMap<K,V>泛型類(lèi)不同，HashMap<K,V>泛型類(lèi)直接實(shí)現(xiàn)Map接口，TreeMap<K,V>泛型類(lèi)不是直接實(shí)現(xiàn)Map接口，而是實(shí)現(xiàn)NavigableMap接口，該接口又是SortedMap的子接口，SortedMap接口又是Map的子接口，如圖前圖。稱(chēng)TreeMap<K,V>泛型類(lèi)的實(shí)例或創(chuàng)建的對(duì)象是一個(gè)映射樹(shù)。10.9TreeMap類(lèi)2024/11/932在存儲(chǔ)數(shù)據(jù)上，TreeMap<K,V>泛型類(lèi)和HashMap<K,V>泛型類(lèi)似，映射樹(shù)也是存儲(chǔ)"鍵-值"對(duì)，但映射樹(shù)不是散列結(jié)構(gòu)。映射樹(shù)也是使用兩個(gè)集合存儲(chǔ)對(duì)象，一個(gè)集合稱(chēng)作關(guān)鍵字集合，記作Key。另一個(gè)是值的集合，記作Value。TreeMap<K,V>的Key集合也是實(shí)現(xiàn)Set接口的一個(gè)實(shí)例，映射樹(shù)中按著Key集合中的關(guān)鍵字的大小關(guān)系，將關(guān)鍵字key對(duì)應(yīng)的value，存放在一個(gè)紅黑樹(shù)（平衡二叉搜索樹(shù)，見(jiàn)第9章）上，即映射樹(shù)的Value是一棵紅黑樹(shù)，這也是TreeMap<K,V>類(lèi)名的來(lái)歷。10.9TreeMap類(lèi)2024/11/933

2024/11/93410.9TreeMap類(lèi)TreeMap中的Value是紅黑樹(shù)，是按著Key中的關(guān)鍵字的大小關(guān)系排序的，這就意味著Value紅黑樹(shù)上可以有相同的對(duì)象，即可以有兩個(gè)結(jié)點(diǎn)中的對(duì)象是相同的，甚至，所有結(jié)點(diǎn)中的對(duì)象都可以是相同的。

2024/11/93510.9TreeMap類(lèi)例子8Example10_8.java例子8中，主類(lèi)Example10_8使用了TreeMap的一些常用方法。2024/11/93610.9TreeMap類(lèi)例子9Example10_9.java例子9的主類(lèi)Example10_9獲取的映射樹(shù)的視圖，查詢(xún)了視圖中的”鍵-值”對(duì)，并對(duì)視圖進(jìn)行更新操作。2024/11/93710.9TreeMap類(lèi)例子10Example10_10.javaStudent.javaKeyStudent.java數(shù)映射中的Value，是按著Key中的關(guān)鍵字大小來(lái)排序的，那么，相對(duì)TreeSet（見(jiàn)第9章），使用映射樹(shù)對(duì)Value進(jìn)行排序的方便之處就是，可以隨時(shí)更改Key中關(guān)鍵字的大小關(guān)系。例子10中的KeyStudent類(lèi)實(shí)現(xiàn)了Comparable接口，給出了樹(shù)映射的Key的大小關(guān)系。例子10中的主類(lèi)Example10_10使用映射樹(shù)分別按數(shù)學(xué)成績(jī)和英語(yǔ)成績(jī)排序?qū)W生.10.10Hashtable類(lèi)2024/11/938Hashtable<K,V>泛型類(lèi)也實(shí)現(xiàn)了Java集合框架中的Map接口。Hashtable<K,V>泛型類(lèi)和HashMap<K,V>泛型類(lèi)的主要區(qū)別是，Hashtable<K,V>泛型類(lèi)提供的方法都是同步(synchronized)方法，即是線(xiàn)性安全的，而HashMap<K,V>泛型類(lèi)不是線(xiàn)性安全的。2024/11/93910.10Hashtable類(lèi)例子11Example10_11.javaTarget.java例子11中的主類(lèi)Example10_11里的f()方法使用兩個(gè)線(xiàn)程訪問(wèn)HashMap散列表，由于HashMap散列表不是線(xiàn)程安全的，一個(gè)線(xiàn)程遍歷HashMap散列表的過(guò)程中，另一個(gè)線(xiàn)程也可以遍歷HashMap散列表。例子11中另一個(gè)主類(lèi)MainCalss里的f()方法使用兩個(gè)線(xiàn)程訪問(wèn)Hashtable散列表，兩個(gè)線(xiàn)程各自遍歷Hashtable散列表，由于Hashtable散列表是線(xiàn)程安全的，一個(gè)線(xiàn)程遍歷Hashtable散列表的過(guò)程中，另一個(gè)線(xiàn)程無(wú)法遍歷Hashtable散列表。訪問(wèn)線(xiàn)程不安全的散列表訪問(wèn)線(xiàn)程安全的散列表第12章常用算法與Collections類(lèi)2024/11/9402024/11/9412024/11/942Collections類(lèi)是Object類(lèi)的一個(gè)直接子類(lèi)（注意Collections比Collection多了一個(gè)字母s），該類(lèi)封裝了一系列算法，例如，二分查找，排序、洗牌等算法，這些算法可用于List，Queue、Set。需要注意的是Collections是類(lèi)，Collection是接口，Collections類(lèi)沒(méi)有實(shí)現(xiàn)Collection接口.12.1排序2024/11/943

2024/11/94412.1排序例子1Score.java例子1中的主類(lèi)Example12_1使用Collections類(lèi)的sort()方法排序（升序）一個(gè)鏈表，首先按鏈表中的對(duì)象實(shí)現(xiàn)的Comparable接口給出的比較器排序鏈表，然后再指定新的比較器排序鏈表。Example12_1.java12.2二分查找2024/11/945publicstaticintbinarySearch(List<?extendsT>list,Tkey)查找對(duì)象key是否在升序的list中（list中的對(duì)象按自然序排序），如果key在list中，方法返回key在list中的索引位置（索引位置從0開(kāi)始），否則返回一個(gè)負(fù)數(shù)。publicstaticintbinarySearch(List<?extendsT>list,Tkey,Comparator<?superT>c)查找對(duì)象key是否在升序的list中（list的元素按比較器c排序），如果key在list中，方法返回key在list中的索引位置（索引位置從0開(kāi)始），否則返回一個(gè)負(fù)數(shù)。注意，排序使用的比較器的算法需要和該方法使用的比較器c的算法相同。2024/11/94612.2二分查找例子2FindWords.java例子2中的FindWords類(lèi)的booleanfindWords(Stringstr,Stringkey)方法使用二分法判斷單詞key是否在str中。Example12_2.java12.3反轉(zhuǎn)與旋轉(zhuǎn)2024/11/947publicstaticvoidreverse(List<?>list)反轉(zhuǎn)list中元素的順序.publicstaticvoidrotate(List<?>list,intdistance)把list向右(distance是正整數(shù))或向左(distance是負(fù)整數(shù))旋轉(zhuǎn)distance個(gè)索引位置。例如，list節(jié)點(diǎn)中的對(duì)象依次是[a,b,c,d,e]，如果執(zhí)行Colections.rotate(list,1)，那么list節(jié)點(diǎn)中的對(duì)象依次是[e,a,b,c,d]，如果執(zhí)行Colections.rotate(list,-2)，那么list節(jié)點(diǎn)中的對(duì)象依次是[cdeab]。2024/11/94812.3反轉(zhuǎn)與旋轉(zhuǎn)例子3LeaveOne.javaWordReverse.java例子3中的LeaveOne類(lèi)的leaveByRotate(LinkedList<Integer>list)方法通過(guò)旋轉(zhuǎn)鏈表，解決約瑟夫問(wèn)題：把list向左旋轉(zhuǎn)2個(gè)索引位置，即可確定出退出圈中的人，理由是，此刻鏈表頭節(jié)點(diǎn)就是數(shù)到的第3個(gè)人，即要出圈的人。例子3的WordRevers類(lèi)的isReverse(Stringword)方法判斷word是否是回文單詞（回文單詞和它的反轉(zhuǎn)相同）。建議讀者把這里的例子3和第4章的例子9做一個(gè)比較，體會(huì)使用旋轉(zhuǎn)list解決約瑟夫問(wèn)題，能讓代碼更加簡(jiǎn)練。Example12_3.java12.4洗牌2024/11/949我們?cè)诘?章的4.10節(jié)，講解過(guò)洗牌算法，即Fisher-Yates洗牌算法。Collections類(lèi)將Fisher-Yates洗牌算法封裝在下列方法中：publicstaticvoidshuffle(List<?>list)使用Fisher-Yates洗牌算法排列l(wèi)ist。2024/11/95012.4洗牌例子4例子4的主類(lèi)Example12_4使用Collectiones類(lèi)提供的Fisher-Yates洗牌算法演示洗牌過(guò)程。Example12_4.java12.5最大與最小2024/11/951publicstaticTmax(Collection<?extendsT>coll)按coll元素的自然序（元素實(shí)現(xiàn)Comparable接口中的比較器給出的大小順序），返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll)按coll元素的自然序，返回coll中的最小值。publicstaticTmax(Collection<?extendsT>coll,Comparator<?superT>comp)

按comp比較器，返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll,,Comparator<?superT>comp)按comp比較器，返回coll中的最小值。2024/11/95212.5最大與最小例子5Example12_5.java例子5中的主類(lèi)Example12_5求集合中的最大值和最小值。12.6頻率2024/11/953publicstaticintfrequency(Collection<?>c,Objectobj)返回c中與指定對(duì)象obj相等的元素的數(shù)量。我們?cè)诘?0章的例子5中，使用散列表統(tǒng)計(jì)文本文件中單詞出現(xiàn)的次數(shù)和頻率。下面的例子6使用intfrequency(Collection<?>c,Objectobj)方法統(tǒng)計(jì)文本文件中單詞或漢字出現(xiàn)的次數(shù)和頻率。2024/11/95412.5最大與最小例子6Example12_6.java例子6中的FrequencyEnglish類(lèi)將英文組成的文本文件中的單詞存放在一個(gè)集合中，便于統(tǒng)計(jì)出不相同的單詞的總數(shù)，把單詞存放在一個(gè)鏈表中，便于統(tǒng)計(jì)每個(gè)單詞出現(xiàn)的次數(shù)，并計(jì)算出單詞出現(xiàn)的頻率。FrequencyChinese類(lèi)將中文組成的文本文件中的漢字存放在一個(gè)集合中，便于統(tǒng)計(jì)出不相同的漢字的總數(shù)，把漢字存放在一個(gè)鏈表中，便于統(tǒng)計(jì)每個(gè)漢字出現(xiàn)的次數(shù)，并計(jì)算出漢字出現(xiàn)的頻率。FrequencyEnglish.javaFrequencyChinese.java第13章圖論2024/11/9552024/11/956

13.1無(wú)向圖2024/11/957

⒈無(wú)向圖的定義2024/11/95813.1無(wú)向圖

⒈無(wú)向圖的定義2024/11/95913.1無(wú)向圖

2鄰接點(diǎn)

2024/11/96013.1無(wú)向圖3.路徑

2024/11/96113.1無(wú)向圖4.連通圖

13.2有向圖2024/11/962⒈有向圖的定義

2024/11/96313.2有向圖

⒈有向圖的定義

2024/11/96413.2有向圖2鄰接點(diǎn)

2024/11/96513.2無(wú)向圖3.路徑

2024/11/96613.2有向圖4.強(qiáng)連通圖

13.3網(wǎng)絡(luò)2024/11/967

2024/11/96813.3網(wǎng)絡(luò)刻畫(huà)北京，廣州，成都和上海四個(gè)城市之間的民航航線(xiàn)，航線(xiàn)之間的權(quán)重是航線(xiàn)距離。2024/11/96913.3網(wǎng)絡(luò)刻畫(huà)北京，廣州，成都和上海四個(gè)城市之間的民航航線(xiàn)，航線(xiàn)之間的權(quán)重是航線(xiàn)的票價(jià)（往返的票價(jià)不盡相同）。13.4圖的存儲(chǔ)2024/11/9701.鄰接矩陣

13.4圖的存儲(chǔ)2024/11/9711.鄰接矩陣

2024/11/97213.4圖的存儲(chǔ)例子1Example13_1.javaGraphByMatrix.java例子1中的GraphByMatrix類(lèi)使用鄰接矩陣存儲(chǔ)圖或網(wǎng)絡(luò)的邊。例子1的主類(lèi)Example13_1使用GraphByMatrix類(lèi)演示了無(wú)向圖、有向圖和有向網(wǎng)絡(luò)使用鄰接矩陣存儲(chǔ)邊.13.4圖的存儲(chǔ)2024/11/9731.鄰接表

2024/11/97413.4圖的存儲(chǔ)例子2Example13_2.javaGraphByLinkedList.java例子2中的GraphByLinkedList類(lèi)使用鄰接鏈表存儲(chǔ)圖或網(wǎng)絡(luò)的邊。例子2的主類(lèi)Example13_2使用GraphByLinkedList類(lèi)演示了無(wú)向圖、有向圖和有向網(wǎng)絡(luò)使用鄰接鏈表存儲(chǔ)邊.13.4圖的遍歷2024/11/975

13.4圖的遍歷2024/11/976廣度搜索（BFS）則是從起點(diǎn)開(kāi)始，逐層訪問(wèn)所有路徑可達(dá)到的頂點(diǎn)，一層一層地往外擴(kuò)展（廣度優(yōu)先），直到所有路徑可達(dá)到的頂點(diǎn)都被訪問(wèn)到，就結(jié)束此次遍歷過(guò)程。如果圖中仍然有沒(méi)訪問(wèn)過(guò)的頂點(diǎn)，就在沒(méi)訪問(wèn)過(guò)的頂點(diǎn)中，選擇一個(gè)頂點(diǎn)重新開(kāi)始遍歷。廣度優(yōu)先搜索一直到圖中再也沒(méi)有可訪問(wèn)的頂點(diǎn)，就結(jié)束搜索過(guò)程。廣度優(yōu)先搜索的算法中可以用隊(duì)列（Deque）這種數(shù)據(jù)結(jié)構(gòu)體現(xiàn)廣度優(yōu)先.2024/11/97713.5圖的遍歷例子3Example13_3.javaGraphDFS.java1.深度優(yōu)先搜索（DFS）算法DFS算法描述如下。①檢查是否已經(jīng)訪問(wèn)了全部的頂點(diǎn)，如果已經(jīng)訪問(wèn)了全部的頂點(diǎn)，進(jìn)行③，否則，將一個(gè)不曾訪問(wèn)的頂點(diǎn)壓入棧，進(jìn)行②。②如果棧是空，進(jìn)行①，否則進(jìn)行彈棧，把彈出的頂點(diǎn)標(biāo)記為訪問(wèn)過(guò)的頂點(diǎn)，然后把彈出的頂點(diǎn)的鄰接頂點(diǎn)壓入棧（體現(xiàn)深度優(yōu)先），但不再對(duì)訪問(wèn)過(guò)的頂點(diǎn)進(jìn)行壓棧操作，再進(jìn)行②。③算法結(jié)束。例子3中的GraphDFS類(lèi)封裝了DFS算法。Vertex.java2024/11/97813.5圖的遍歷例子4Example13_4.javaGraphBFS.java2.廣度優(yōu)先搜索（BFS）算法例子4中的GraphBFS類(lèi)封裝了BFS算法。Vertex.javaBFS算法描述如下：①檢查是否已經(jīng)訪問(wèn)了全部的頂點(diǎn)，如果已經(jīng)訪問(wèn)了全部的頂點(diǎn)，進(jìn)行③，否則，將一個(gè)不曾訪問(wèn)的頂點(diǎn)入列，進(jìn)行②。②如果隊(duì)列是空，進(jìn)行①，否則進(jìn)行出列操作，把出列的頂點(diǎn)標(biāo)記