數(shù)據(jù)結(jié)構(gòu)與算法（Java語(yǔ)言版）課件 第4章 數(shù)組與Arrays類

第4章數(shù)組與Arrays類2024/11/91主要內(nèi)容● 數(shù)組的引用● 數(shù)組的排序● 數(shù)組的二分查找●數(shù)組的復(fù)制● 數(shù)組的比較● 數(shù)組的匹配● 公共子數(shù)組● 數(shù)組的更新● 數(shù)組的前綴運(yùn)算● 數(shù)組的動(dòng)態(tài)遍歷● 數(shù)組與洗牌● 數(shù)組與生命游戲

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

2024/11/922024/11/934.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/944.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/954.1引用與參數(shù)存值2.參數(shù)存值使用參數(shù)存儲(chǔ)值就是一個(gè)方法可以將某些數(shù)據(jù)存放在參數(shù)中，如果參數(shù)是引用類型，比如數(shù)組，那么方法執(zhí)行完畢，保存在參數(shù)中的值一直還存在、不會(huì)消失。例子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/964.1引用與參數(shù)存值2.參數(shù)存值使用參數(shù)存儲(chǔ)值就是一個(gè)方法可以將某些數(shù)據(jù)存放在參數(shù)中，如果參數(shù)是引用類型，比如數(shù)組，那么方法執(zhí)行完畢，保存在參數(shù)中的值一直還存在、不會(huì)消失。例子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/97排序算法是重要的基礎(chǔ)算法。各種排序算法都是非常成熟的算法，Arrays類封裝了快速排序和歸并排序，編寫程序時(shí)直接使用即可。2024/11/984.2數(shù)組與排序1.快速排序

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

例子4Example4_4.javaStudent.java

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

例子5里，我們依然給出了歸并排序算法，其目的是體現(xiàn)遞歸算法的重要性（歸并排序使用了遞歸算法），在實(shí)際應(yīng)用中，完全沒必要這樣做，只需用Arrays類的parallelSort()方法即可，讓你的代碼更加簡(jiǎn)練有效。歸并排序算法如下：①將待排序數(shù)組分成兩個(gè)子數(shù)組，每個(gè)子數(shù)組通過遞歸進(jìn)行排序。②將兩個(gè)排好序的子數(shù)組合并成一個(gè)有序數(shù)組。4.3數(shù)組的二分查找2024/11/911二分法可用于查找一個(gè)數(shù)據(jù)是否在一個(gè)升序數(shù)組中。我們?cè)诘?章的例子9，第3章的例子6介紹過二分法。因?yàn)槎址ㄊ浅墒斓慕?jīng)典算法，所以Java將其作為一個(gè)方法封裝在Arrays類中。在開發(fā)程序時(shí)，可以直接使用Arrays類即可，不必再像第2章例子9或第3章的例子6去編寫算法的具體代碼。2024/11/9124.3數(shù)組的二分查找1.二分法例子6Example4_6.java例子6的主類Example4_6，在循環(huán)10000次的循環(huán)語(yǔ)句的循環(huán)體中，每次使用Random對(duì)象得到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/9134.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/914數(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/9154.4數(shù)組的復(fù)制1.復(fù)制數(shù)組的方法例子8Example4_8.javaGetRondomNumber.javacopyOf(int[]a,intnewLength)把數(shù)組a中從索引0開始的newLength多個(gè)元素值賦值到一個(gè)新數(shù)組中，并返回新數(shù)組的引用。如果newLength的值大于數(shù)組a的長(zhǎng)度，新數(shù)組從newLength索引位置開始的元素值都是默認(rèn)值。比如對(duì)于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/9164.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問題可以簡(jiǎn)化為旋轉(zhuǎn)數(shù)組（向左或向右旋轉(zhuǎn)數(shù)組），旋轉(zhuǎn)數(shù)組2次即可確定出退出圈中的人，即此時(shí)數(shù)組首元素中的號(hào)碼就應(yīng)該是要退出圈中的人。例子9中，LeaveOneAround類的leaveOne(int[]people)方法通過旋轉(zhuǎn)數(shù)組確定數(shù)組people中出圈的元素，并用copyOfRange()方法保留剩余的元素。2024/11/9174.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/918Arrays類中的靜態(tài)方法intcompare()和booleanequals()都是重載的方法，用于比較兩個(gè)數(shù)組，二者的區(qū)別僅僅是返回值的類型不同。2024/11/9194.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/920如果數(shù)組a的某個(gè)子數(shù)組和數(shù)組b的某個(gè)子數(shù)組的長(zhǎng)度相同（不要求兩個(gè)子數(shù)組的起始索引相同），所包含的元素值也依次相同，就稱二者有公共子數(shù)組。2024/11/9214.6公共子數(shù)組讓長(zhǎng)度小的數(shù)組，比如b的首單元和數(shù)組a的未單元對(duì)齊，數(shù)組b一直向左移動(dòng)，直到數(shù)組b的尾部a的首單元對(duì)齊。向左滑動(dòng)法那么在左移的過程中，數(shù)組a和數(shù)組b二者的所有公共子數(shù)組一定會(huì)出現(xiàn)左對(duì)齊的情況。數(shù)組a數(shù)組b2024/11/9224.6公共子數(shù)組例子12Example4_12.javaFindZeroCount.java讓長(zhǎng)度小的數(shù)組，比如b的首單元和數(shù)組a的未單元對(duì)齊，即b的左端和a的右端對(duì)齊，然后進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果存放到一個(gè)其它數(shù)組c中，讓數(shù)組b按一個(gè)單元（元素）為單位向左依次移動(dòng)（滑動(dòng)），每移動(dòng)一個(gè)單元，進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果存放到數(shù)組c中。數(shù)組b一直向左移動(dòng)，直到數(shù)組b的尾部，即最后一個(gè)單元和數(shù)組a的首單元對(duì)齊。向左滑動(dòng)法那么在左移的過程中，數(shù)組a和數(shù)組b二者的所有公共子數(shù)組一定會(huì)出現(xiàn)左對(duì)齊的情況。由異或運(yùn)算法則可知，相同的整數(shù)異或的結(jié)果是0，那么只要根據(jù)數(shù)組c中連續(xù)出現(xiàn)的0的個(gè)數(shù)，就可以找到一個(gè)最大的公共子數(shù)組。MaxCommon.java4.7數(shù)組的更新2024/11/923Arrays類提供了對(duì)數(shù)組整體更新的方法：fill()和setAll()。1.整體更新為單值：voidfill(int[]a,intval)該方法將參數(shù)數(shù)組a的每個(gè)元素的而值都設(shè)置為參數(shù)val指定的值。2.動(dòng)態(tài)更新setAll()方法是一個(gè)重載方法，例如：publicstaticvoidsetAll(double[]a,IntToDoubleFunctiongenerator)將參數(shù)數(shù)組a的每個(gè)元素的值都設(shè)置為參數(shù)generator的計(jì)算結(jié)果。2024/11/9244.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語(yǔ)句，返回的值是int型數(shù)據(jù)。setAll()方法會(huì)使用Lambda表達(dá)式依次設(shè)置數(shù)組a的元素的值。例子13中，主類Example4_13使用fill()和setAll()方法整體更新數(shù)組的元素的值.4.8數(shù)組的前綴算法2024/11/925數(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/9264.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語(yǔ)句，返回的值是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語(yǔ)句的返回值設(shè)置為數(shù)組第j個(gè)元素的值后，然后i再自增，再重復(fù)前面的計(jì)算。。4.9動(dòng)態(tài)遍歷2024/11/927遍歷數(shù)組的方法（算法）在遍歷數(shù)組時(shí)，讓數(shù)組的每個(gè)元素參與某種運(yùn)算，并輸出運(yùn)算后的結(jié)果，稱這樣的遍歷方法為動(dòng)態(tài)遍歷方法。①將數(shù)組a的全部元素或部分元素封裝到Spliterator.OfInt對(duì)象中。②Spliterator.OfInt對(duì)象調(diào)用voidforEachRemaining(IntConsumerconsumer)方法遍歷Spliterator.OfInt對(duì)象中封裝的數(shù)組元素。2024/11/9284.9動(dòng)態(tài)遍歷例子15Example4_15.javaforEachRemaining(IntConsumerconsumer)方法遍歷Spliterator.OfInt對(duì)象中封裝的數(shù)組元素。該方法的參數(shù)intConsumer是一個(gè)函數(shù)接口，該接口中的抽象方法的參數(shù)是int型，返回類型是void型。那么在調(diào)用forEachRemaining(IntConsumerconsumer)方法時(shí)，可以將一個(gè)Lambda表達(dá)式傳遞給consumer，該Lambda表達(dá)式必須是1個(gè)int型參數(shù)，不需要return語(yǔ)句（如果有return，不允許返回任何值）。比如，可以將下列Lambda表達(dá)式(value)->{System.out.println(value);}傳遞給consumer，forEachRemaining(IntConsumerconsumer)方法在執(zhí)行過程中將使用這個(gè)Lambda表達(dá)式，讓Lambda表達(dá)式的參數(shù)valule依次取Spliterator.OfInt對(duì)象中封裝的數(shù)組元素1.動(dòng)態(tài)方法2024/11/9294.9動(dòng)態(tài)遍歷例子16Com.java

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