數(shù)據(jù)結(jié)構(gòu)與算法（Java語言版）課件 第6章 順序表與ArrayList類

第6章順序表與ArrayList類2024/11/916.1順序表的特點(diǎn)2024/11/92順序表也是線性表的一種具體體現(xiàn)，順序表節(jié)點(diǎn)形成的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)、節(jié)點(diǎn)的存儲結(jié)構(gòu)是順序存儲，即節(jié)點(diǎn)的物理地址是依次相鄰的。2024/11/936.1順序表的特點(diǎn)順序表使用數(shù)組來實(shí)現(xiàn)，順序表的節(jié)點(diǎn)的物理地址是依次相鄰的，因此可以隨機(jī)訪問任何一個節(jié)點(diǎn)，不必從頭節(jié)點(diǎn)計(jì)數(shù)查找其它節(jié)點(diǎn)?！癫樵児?jié)點(diǎn)

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

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

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

6.2創(chuàng)建順序表2024/11/96順序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayList<E>泛型類所實(shí)現(xiàn)。2024/11/976.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/986.2創(chuàng)建順序表順序表可以使用add(Eobj)方法向順序表依次增加節(jié)點(diǎn)。創(chuàng)建空順序表，使用ArrayList<E>泛型類聲明順序表時，必須要指定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)建一個空順序表arrlistOne，然后向空鏈表arrlistOne添加3個節(jié)點(diǎn)，隨后再用arrlistOne中的節(jié)點(diǎn)創(chuàng)建順序表arrlistTwo。修改arrlistTwo的節(jié)點(diǎn)，并不影響arrlistOne的節(jié)點(diǎn).6.3順序表常用方法2024/11/99voidadd(intindex,Ee)向順序表的index指定位置添加一個新的節(jié)點(diǎn)e（時間復(fù)雜度O(n)）。publicbooleancontains(Objectobj)判斷順序表中是否有對象obj，如果有節(jié)點(diǎn)是對象obj返回true，否則返回false(時間復(fù)雜度O(n))。

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

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

Example6_6.java

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

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

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

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

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

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

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

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

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

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

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

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

如果允許砝碼放在天秤的兩端（允許放在被稱重的物體一端），那么就把另一端（被稱重的物體一端）的砝碼拿回到放置砝碼的一端、并變成“負(fù)碼”（重量是負(fù)數(shù)），就將問題轉(zhuǎn)化為砝碼只放天秤一端的情況。6.8順序表與記錄2024/11/929有時候，需要將一維數(shù)組，比如一個記錄學(xué)生成績的一維數(shù)組，看作一個整體，稱作一條記錄（如果學(xué)過數(shù)據(jù)庫，相當(dāng)于表中的一條記錄）。借助順序表，可以批量處理記錄，比如，排序紀(jì)錄。2024/11/9306.8順序表與記錄●順序表與一維數(shù)組例子13Example6_13.javaArrays類的靜態(tài)方法：static<T>List<T>asList(T...a)返回一個順序表。該方法是可變參數(shù)，可以把若干個類型相同的對象放入一個順序表，也可以把一個數(shù)組放入一個順序表。順序表調(diào)用public<T>T[]toArray(T[]a)方法，可以把節(jié)點(diǎn)，存到一個數(shù)組中。在使用這個方法之前，要實(shí)現(xiàn)預(yù)備一個數(shù)組，長度為1即可，將這個數(shù)組傳遞給toArray(T[]a)方法的參數(shù)a，此參數(shù)僅僅是通知該方法再創(chuàng)建新的一維數(shù)組、將順序表節(jié)點(diǎn)放到新數(shù)組中，并返回這個新的數(shù)組的引用。2024/11/9316.8順序表與記錄●順序表與二維數(shù)組例子14Example6_14.java二維數(shù)組是由若干多個一維數(shù)組所構(gòu)成，即若干條記錄所構(gòu)成，例如，二維數(shù)組a:int[][]a={{90,89,77,68},{72,50,97,69},{52,50,67,79}};由3條記錄構(gòu)成。例子14的主類Example6_14把一個二維數(shù)據(jù)中的記錄放入順序表，并對順序表中記錄進(jìn)行排序.6.8Vector類2024/11/932Vector<E>泛型類實(shí)現(xiàn)了Java集合框架中的List泛型接口(和鏈表不同，沒有實(shí)現(xiàn)Queue泛型接口)。Vector<E>泛型類繼承了List泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了List泛型接口中的抽象方法。Vector<E>泛型類和ArrayList<E>泛型類的主要區(qū)別是，Vector<E>泛型類提供的方法都是同步(synchronized)方法，即是線性安全的，而ArrayList<E>泛型類不是線性安全的。當(dāng)有多個線程訪問同一個ArrayList類型的順序表時，用戶必須自己考慮多線程帶來的問題，比如一個線程修改順序表時，是否允許另一個線程訪