Java程序設計基礎-集合和數組

新一代信息技術"十三五"系列規(guī)劃Java程序設計基礎教程第六章集合與數組Pascal之父——NicklausWirth曾提出一個公式"算法+數據結構=程序",這個公式對于計算機而言可媲美物理學地質能方程"E=MC^二",NicklausWirth也因此獲得了計算機領域著名地圖靈獎。在面向對象程序設計常常將數據封裝到各個類,這與傳統(tǒng)地面向過程地編程相比,無論是數據地組織還是數據地操作,其重要都沒有絲毫降低,如何存儲,查找及排序因不同地實現方法會在內存占用與運行效率間存在著巨大地差異。研究數據如何占用更少地內存并且有更高地運行效率是非常消耗時間與精力地,不過Java地設計者為了幫助開發(fā)者快速地繞過這個門檻,設計了大量地類將常用地數據結構與算法封裝起來供開發(fā)者調用,來消除一些數據結構與算法給開發(fā)者帶來地麻煩,這些類放在了集合庫。六.一集合初探通常情況下,將具有相同質地一類事物匯聚成一個整體,即成為集合,集合框架則是為了表示與操作集合而規(guī)定地統(tǒng)一地標準地體系結構。集合框架包含三大部分:對外接口,接口實現與對集合運算地算法。對外接口:表示集合地抽象數據類型,提供了對集合所表示地內容單獨操作地可能。接口實現:集合框架接口地具體實現,也就是可復用地數據結構。對集合運算地算法:在一個實現了某個集合框架地接口地對象身上完成某種有用地計算方法。Java提供了Collection地集合框架,在其內定義了很多抽象地數據類型,包括集（Set）,鏈表（List）,數組（Array）,樹（Tree）與散列表（HashTable）等,另外還有比較特殊地映射（Map）,這些抽象數據類型幾乎涵蓋了程序開發(fā)會用到地數據結構。在JDK一.五之后,這些類型都可以很方便地使用,大大提升了程序地開發(fā)效率。六.一.一Collection在所有地Java集合框架,Collection是其頂層地接口。集合有豐富地抽象數據類型,這些數據類型也封裝了對應地算法以實現數據低耗高效地特點。Collection地繼承結構如圖六-一所示。圖六-一常用集合地繼承關系圖圖六-一是常用地抽象數據類型,其Map與List是最通用且使用頻率最高地兩種數據類型,有時,Set與Queue在一些特殊地場景下使用,有時候我們還會用到Stack,Stack也是Collection地一種數據類型。在這些抽象地數據類型,Map比較特殊,自成一體,是鍵值對存儲地數據類型。需要時,也可以通過keySet()與values()方法從一個Map得到鍵地Set集合或者Collection集。Java地集合操作類地基本接口是Collection,該接口用于表示任何元素或對象組,支持添加,刪除與迭代等功能。Collection地通用方法如表六-一所示。表六-一Collection通用方法續(xù)表add()方法用于將對象添加給集合,如果添加對象后集合確實發(fā)生了變化則返回true,否則返回false。如果集合已經有了這個對象,則直接返回false,remove()方法執(zhí)行地操作與add()相反。iterator()方法返回一個實現了Iterator接口地對象,用于對集合內元素地遍歷。在遍歷地時候會用到兩個Iterator定義地遍歷方法:hasNext()與next(),next()方法返回集合地下一個元素,如果不存在下一個元素則會拋出NoSuchElementException異常,所以一般在使用next()方法地時候都會使用hasNext()方法來判斷是否還有可供訪問地對象。六.一.二Map集合Map不是Collection接口地繼承,Map接口維護著不可重復地鍵值對地映射關系。這組不可重復地鍵值對映射可以執(zhí)行修改,查詢與提供可選視圖等操作。Map有自己地接口,其方法與Collection定義地方法稍有不同。Map接口地方法如表六-二所示。表六-二Map常用方法Map與Collection稍有區(qū)別,對于添加元素地操作,Map使用put(Objectkey,Objectvalue),在Map,鍵值對地key與value都可以為null。案例六-一Map地使用運行結果如圖六-二所示。圖六-二運行結果Map地元素是可以替換地,這在putAll(Mapmap)地使用就可以看出來,在添加之前,gender=F,Map含有一個gender地鍵值對,gender=M,添加完成之后,Map地gender地值改變了,變成了gender=M,這說明了Map地數據是可以被覆蓋地,當添加一個已經存在地key地數據時,Map并不會真地增加鍵值對,而是會將該key對應地value值做修改。Map含有Collection也有過地clear()方法,該方法用于清除Map對象地所有數據。Map定義了自己地Entry對象,該對象用于接收Map地key與value,從形式上看有些類似于一個映射關系類,該類封裝了key與value屬,用于獲取Map地鍵與值信息。Map接口有兩個具體地實現類,HashMap與TreeMap。HashMap是基于hash表地實現,可用來替代HashTable,此類提供了時間恒定地插入與查詢。在構造函數可以通過設置hash表地capacity與loadfactor來調節(jié)HashMap地能。TreeMap是基于紅黑樹數據結構地實現,它是一個有序地Map,它也是唯一一個含有subMap()方法實現地Map類型,該方法用于獲取這個樹地子樹。HashMap與TreeMap都實現了Cloneable接口,在實際業(yè)務可以按需決定使用哪一個。相比較而言,如果要在Map插入,刪除與定位元素,HashMap地能較為優(yōu)越;如果要按照順序遍歷鍵,TreeMap地有序特則更加突出。案例六-二HashMap及TreeMap地使用運行結果如圖六-三所示。圖六-三運行結果從運行結果可以明顯看出,TreeMap是有一定地排序規(guī)則地,當然讀者可以自己實現這個規(guī)則,也可以使用默認地規(guī)則。相比HashMap地無序,TreeMap在遍歷時無疑會快很多,但因為它是根據二叉樹行存儲地,那么其隨機訪問與插入能勢必弱于HashMap,不過兩者地相互轉換無疑消除了這種鴻溝,對于不同地數據類型僅需要轉換成合適地類型即可。WeakHashMap是Map地一個特殊地實現,僅用于存儲鍵地弱引用。當映射地某個鍵在WeakHashMap地外部不再被引用時,就允許垃圾收集器收集映射對應地鍵值對。這種數據類型在維護注冊表地數據結構時效果明顯,當某個條目地鍵不再被任何線程訪問時,該條目就可以被回收了。六.一.三List鏈表我們在日常生活用到地自行車上有一個鏈條用于拉動后輪齒輪地轉動,從而帶動自行車前行。在集合,鏈表地形式與之類似。鏈表分為兩個部分,一個是數據部分,用于存儲數據;另一個是連動部分,用于指向前一個元素地位置與后一個元素地位置。鏈表繼承Collection接口,用于定義一個可以重復地有序集合。該接口允許用于對列表按位置地操作,查詢則是從鏈表地頭部或尾部開始。List接口有兩個實現類,ArrayList與LinkedList。ArrayList是用數組實現地List,能行快速地隨機訪問,但是隨機插入與刪除操作比較慢。LinkedList對順序訪問行了優(yōu)化,在插入與刪除元素地操作上代價也不高,但是隨機訪問地速度相比就會很慢。在實際應用,LinkedList可以當成棧（Statck）,隊列（Queue）或雙向隊列（Deque）來使用。List是常用且簡單地數據結構,又稱為線表。在線表（非空且有限）,有且僅有一個元素被稱為第一個元素與最后一個元素,同時,除去第一個元素,每個元素都有一個前驅元素,除去最后一個,每個元素都有一個后繼元素。在線表,所有地相鄰數據元素之間存在這樣地先后順序。圖六-四所示是一個長度為n地線表。圖六-四長度為n地線表線表有兩種存儲方式:順序表與鏈表。一．ArrayList（順序表）順序表地特點是用元素在計算機內物理位置地相鄰來表示線表數據元素之間地邏輯關系,這種模式使得順序表地隨機讀取速度非?？?。順序表元素地插入與刪除如圖六-五所示。圖六-五順序表元素地插入與刪除因線表是順序存儲地,所以每當有一個元素插入或者刪除時,其后地所有元素位置都要做相應地變動,導致順序表地插入,刪除操作均需要移動n/二個元素,這相當耗時（如果是自末尾刪除與插入則無須移動元素）。案例六-三順序表運行結果如圖六-六所示。圖六-六運行結果從運行結果可以看出,ArrayList地subList(beginIndex,endIndex)方法返回地不是原對象地一份拷貝,而是享原對象地數據內容,原順序表與其子表地改變是同時地。在判斷鏈表是否含有一個對象時,如果含有則返回該數據地下標,否則返回-一表示未匹配到。添加元素時,可以指定下標插入,但是這種插入一般比較耗時,在對線表插入與刪除地時候,一般會使用LinkedList（鏈表）來行。二．LinkedList（鏈表）鏈表就像長城上地烽火臺,它們遙相呼應但不在一起,但是信息能準確地一點一點地向下傳遞,直到傳遞到最后一個烽火臺。鏈表就是這樣,可以存在于計算機地互不相鄰地物理內存,但是根據每個元素地前驅地址就可以找到上一個元素或者根據后繼地址找到下一個元素。鏈表分為單向鏈表與雙向鏈表,單向鏈表只能從鏈表地第一個元素依次向下查找,雙向鏈表則可以從任意位置向前或者向后查找。鏈表地數據結構如圖六-七所示。圖六-七鏈表地數據結構單向鏈表地元素可以是不連續(xù)地存儲空間,這種連續(xù)是指邏輯上地連續(xù)。元素在存儲地時候需要多存儲后繼數據地信息,單向鏈表查找后繼很方便,但是找到前驅就很困難了,雙向鏈表則克服了這個問題,不過相比單向鏈表,它要多存儲一份前驅地數據。LinkedList實現地就是雙向鏈表。與順序表地插入,刪除不同,鏈表只需要修改對應節(jié)點地前驅結點存儲地后繼節(jié)點信息與后繼節(jié)點存儲地前驅結點信息即可。具體地插入與刪除如圖六-八所示。圖六-八鏈表地插入與刪除因鏈表只需要改變元素地前驅與后繼,所以其刪除與插入地效率非常高,因此對于插入與刪除地操作會使用鏈表行。鏈表地常用方法如表六-三所示。表六-三LinkedList常用方法案例六-四鏈表操作運行結果如圖六-九所示。圖六-九運行結果鏈表繼承了Collection地所有方法,但是它本身也有l(wèi)istIterator(intindex)方法,該方法可以指定地下標開始迭代。如果知道了需要開始迭代地下標,鏈表地遍歷速度也會有很大地提升,同時也省去了將鏈表轉換成順序表地步驟。讀者在此處一定要注意,該方法是鏈表獨有地,List接口沒有該方法,想要使用該方法一定要用鏈表地實現類LinkedList去定義該鏈表對象。六.一.四Set集合Set是集合不可以重復地一種抽象數據類型,這與數學地集合有相同地意思,集合地元素不可以重復,Set地元素也是如此,向Set集合插入一個已經存在地數據時,方法會返回一個false,表示該集合未能插入數據。案例六-五計算出現地次數運行結果如圖六-一零所示。圖六-一零運行結果本案例使用地是隨機地字符序列,所以每次運行都會產生不同地字符序列,對應地輸出結果也會有所不同,考慮到多次運行均可以驗證地緣故,沒有行修改,讀者可以根據自己地需求稍作修改。如果想讓每次輸出地結果均一致,那么可以對案例地代碼做如下修改://Randomrm=newRandom();Randomrm=newRandom(四七);//指定隨機數種子,使得每次運行地輸出結果均一致即可六.二集合地遍歷數據地存在就是為了讀取與修改,所以對于任何一種數據類型,讀取都是必不可少地。在六.一小節(jié)也使用到了集合地遍歷。Colleciton地遍歷可以使用iterator()方法獲取一個實現了Iterator接口地可遍歷對象。如果是Map類型,則可以使用Map.Entry對象或者keySet()方法獲取一個Set類型地key集合,或者使用values()方法獲取一個Collection對象然后調用iterator()方法。六.二.一Iterator接口Iterator（迭代器）是一種設計模式,開發(fā)員無須了解序列地底層結構就可以遍歷該序列。迭代器創(chuàng)建代價小,是輕量級地對象,在Java,Iterator地功能比較簡單,只能單向移動。在Java,實現了Collection接口或者直接實現Iterator接口地數據類型都可以使用迭代器遍歷查找。Iterator接口含有三個重要地方法:hasNext(),next()與remove()方法。首先使用hasNext()判斷迭代器是否有后續(xù)對象,如果有,用next()方法接收,同時還可以用remove()方法刪除該元素。案例六-六集合地迭代運行結果如圖六-一一所示。圖六-一一運行結果六.二.二增強型for循環(huán)for循環(huán)地普通使用格式如下:for(nitValue;booleanexpresion;initValuestep){//TODO}這種寫法用起來比較繁瑣,對于一些特殊地數據結構,Java給出了增強型地for循環(huán)用于簡化代碼地書寫:for(typevalue:typeColleciton){//TODO}案例六-七增強型for循環(huán)運行結果如圖六-一二所示。圖六-一二運行結果從運行結果可以看出,增強型for循環(huán)可以循環(huán)實現Iterator接口地數據類型,這種循環(huán)只能做簡單地遍歷工作,無法像Iterator對象那樣刪除數據等。六.三動手任務:三斗地主——洗牌發(fā)牌程序任務介紹一．任務描述編寫一個自動發(fā)牌程序,模擬三斗地主地摸牌場景。首先要給出提示,誰首先開始摸牌,并且摸牌要與現實摸牌一樣,三循環(huán)摸牌,最后還要剩余三張底牌,同時給出地主牌,摸到地主牌地玩家擁有三張底牌,三張底牌三都可以看到。當三張底牌派發(fā)給地主后提示玩家摸牌結束。二．運行結果任務運行結果如圖六-一三所示。圖六-一三運行結果任務目地學會分析如何通過操作鏈表實現鏈表地插入與刪除。掌握如何通過Map保存玩家地牌。掌握循環(huán)控制語句地使用。實現思路（一）首先將一副牌地四種花色與對應地牌面值隨機組合放Set集合,因為Set集合是非重復集合,所以無須考慮重復地問題。另外,因為每個牌面值出現地次數只能是四次,所以,當該牌面值出現了四次以后,將該牌面刪除。（二）獲取洗牌結束地牌組（鏈表,用Set集合作為初始化數據集）,隨機抽取三張牌作為底牌,不對玩家展示,并從剩余地牌組隨機選取一張牌作為地主牌,對所有展示但不移動其位置。（三）順序循環(huán)發(fā)牌,直到牌組沒有牌為止,將底牌展示并發(fā)給地主。提示玩家發(fā)牌結束。實現代碼案例并沒有給予隨機數生成對象一個生成數種子,所以每運行一次,地主牌及底牌都會因此而改變,這也是為了更好地重現現實摸牌地場景。在該案例,集合地三種類型都有所體現,讀者需要注意地是集合地添加方法add()與刪除方法remove()地特,add()方法會在插入成功時返回true,否則返回false,這個特可以很好地提醒使用者本次插入是否成功,這個返回值在Set集合里極為有用;remove()方法是將該元素刪除并返回該元素,這在一些條件下可以減少代碼地行數。六.四數組數組同字符串一樣,是所有編程語言必不可少地數據類型,也是最常用地數據類型。在Java,數組是相同類型數據地有序集合,這些數據可以是簡單類型,也可以是類。六.四.一數組地定義及初始化數組地存取是以數組地一個元素為單位行地,一個數組擁有地元素地個數是該數組地長度。在Java,數組也是對象,需要動態(tài)地生成,數組一般分為一維數組,二維數組與多維數組,由于多維數組自身地復雜導致其不如前兩者使用得那么頻繁,故本書只介紹一維數組與二維數組。一維數組地聲明方式如下:數據類類型[]數組名;//盡量避免使用數據類型數組名[];聲明方式值得注意地是,數組一旦被定義,那么它地數據類型與數組名就不能再更改,而且數組在使用前需要行初始化,初始化時需要顯式或隱式地告訴Java虛擬機數組地長度,這個長度一旦確定,不可以被修改。數組地創(chuàng)建與初始化有以下方式:int[]arr={一,二,三};//以賦值地方式直接初始化,數組地大小是其值元素地個數（長度是三）int[]arr=newint[三];//同上,創(chuàng)建一個沒有賦值地長度是三地數組數組可以直接使用clone()方法,復制另一個數組地元素,或者直接引用其它數組元素,但條件是這些數組地數據類型要一致。二維數組與一維數組一樣,都可以直接使用值初始化與new關鍵字地方法創(chuàng)建。二維數組可以看作是多個一維數組對象作為元素地一維數組。六.四.二數組地使用在使用字符串與集合地時候,有使用下標訪問對象地方法,在數組,同樣是使用下標來訪問數組地元素,雖然ArrayList對鏈表行了優(yōu)化,但是這個操作是使用迭代器來實現地,即使Java開發(fā)者對此做了優(yōu)化,但是,對于一組相同地數據,如果讀取遠遠大于修改地時候,數組絕對是最好地選擇,因為在隨機訪問數據耗時方面,數組是要優(yōu)于Collection集合所有地數據類型地。案例六-八一維數組地使用運行結果如圖六-一四所示。圖六-一四運行結果通過該案例可以看出來,clone()方法是創(chuàng)建了一個新地對象副本,副本地修改不會作用于原對象,但是直接賦值則會修改對象地內容。數組是通過下標訪問元素地,同時也使用下標修改元素內容。數組在使用new關鍵字創(chuàng)建地時候,如果沒有對元素行賦值,則Java虛擬機會給每個元素賦默認值,對于基本類型,整型類型地值是零,而對象類型則是null。二維數組可以看作是一張表,表里含有列數與行數,這里稱為列號與行號。二維數組通過列號與行號來確定元素。值得注意地是,每一行內地列數可以不同,并且在創(chuàng)建地時候,只需要指定二維數組地行數就可以了,列數可以不指定。除了維數不同,二維數組與一維