抽象數(shù)據(jù)類型（abstract data type,ADT）：帶有一組操作的一些隊形的集合缰儿，如：表畦粮、集合、圖以及與他們各自的操作一起形成的這些對象都可以被看做是抽象數(shù)據(jù)類型,就像整數(shù)返弹、實數(shù)锈玉、布爾數(shù)都是基本數(shù)據(jù)類型一樣；

3.3 Java collections API 中的表

collection(集合) ： 它存儲一組類型相同的對象义起。Collection 接口擴展了Iterable 接口 .

實驗Iteration 接口 的類可以擁有增強的for 循環(huán)拉背。

Iteration 接口的思路是，集合通過iterater() 方法的調用默终，每個集合均可創(chuàng)建并返回給客戶一個實現(xiàn)Iterator接口的對象椅棺，“并將當前位置的概念在對象內部存儲下來？（這里不是很懂）”齐蔽。每次對next()的調用都給出集合的（尚未出現(xiàn)的）下一項两疚。hasNext()返回是否存在下一項。

當要刪除集合中的某個元素時含滴，Iterator 的remove() 方法比Collection 集合里的remove()方法安全诱渤，所以盡量使用Iterator.remove() 方法。Iterator.remove()方法刪除由iterator.next()返回的對象谈况，所以在調用iterator.remove()方法前必須先調用iterator.next()方法勺美。其優(yōu)點在于： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1递胧、Collection的remove() 必須首先找到要被刪除的項，如果知道所要刪除的項的準備位置赡茸，那么刪除它的開銷很可能要小很多缎脾。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2、如果對正在被迭代的集合進行結構上的改變（即調用Collection的add()/remove()/clear()方法）占卧，那么迭代器就不再合法（并會拋出Concurrent-ModificationException異常）遗菠。這是為了避免迭代器準備給出的某一項作為下一項，而該項之后的后者被刪除华蜒，或者一個新的項正好插入到該項的前面的情形（這在并發(fā)中很容易出現(xiàn)）辙纬；所以在當在需要刪除某項時盡量使用Iterator.remove()方法，該點在阿里的開發(fā)文檔中也是被強調的友多；

List 接口牲平、ArrayList 類和LinkedList類

List 繼承了 Collection 接口,因此它具有包含Collection 接口的所有方法，外加其他定義的方法域滥。

ArrayList 提供了List ADT 的一種可增長數(shù)組的實現(xiàn)纵柿。其優(yōu)點在于，對get()和set()的調用花費時間是常數(shù)級的启绰，其缺點是新項的插入和已有項的刪除需要將該項后面的數(shù)全都移動（前/后）一位其開銷很大昂儒。除非是在末端新增或刪除。

LinkList t提供了 List ADT 的一種雙向鏈表實現(xiàn)委可。其優(yōu)點新的插入項和現(xiàn)有的刪除項開銷是常數(shù)級的（假設變動項的位置已知）渊跋，其缺點是不容易做索引，所以其get()方法的調用是昂貴的着倾。

最近加班多拾酝，自己時間不多······ 就記一些自己覺得重要的了

練習題：

3.6：Josephus problem:

/**

* ?Josephus problem: N個人編號從1 到N ，圍坐成一個圓圈卡者，從1號開始傳遞一個熱土豆蒿囤，進過M次傳遞之后拿著熱土豆的人被

* 清楚，圍坐繼續(xù)崇决，最后剩下的人取勝材诽，因此，如果M=0,和 N =5恒傻，則5 號游戲人獲勝脸侥，若M = 1 ，N = 5 那么背清除的人是 2盈厘， 4,1睁枕，5 則 3 號獲勝，編寫程解決M 和 N 在一般值下的問題

*/

看到這題有一點朦朧的印象，應該以前上學的時候老師講過譬重，但我估計上課睡著了拒逮，只記得老師說的是一道一群人圍成一圈自殺的題罐氨⊥喂妫看到這題我首先想到的是用雙向鏈表去實現(xiàn)。因為每次經過M次的傳遞必須減少一位數(shù)栅隐，鏈表結構的刪除比數(shù)組結構的要快塔嬉，而且游戲說的是玩家圍成一個圈，感覺鏈表結構更形象一點租悄。首先是創(chuàng)建列表谨究，游戲中就是將人先圍成一圈也就是遍歷N創(chuàng)建節(jié)點個數(shù)。其次將末尾的節(jié)點的后導.next指向首節(jié)點first,將首節(jié)點的前導.pre指向最后一個節(jié)點：先看代碼吧

之后從第一位玩家開始傳遞泣棋，傳遞了m 次后指針指向了當前要被殺死的人胶哲。將當前節(jié)點前一個人的后導.next指向當前節(jié)點的下一節(jié)點，當前的下一個節(jié)點的前導指向當前節(jié)點的前一個節(jié)點潭辈，這樣當前節(jié)點就相當于被刪除在該列表中鸯屿，然后指針指向下一個節(jié)點。直到當前節(jié)點的下一位是自己的時候把敢，表明游戲結束寄摆，當前節(jié)點是最后存活下來的人。

第四章 樹

二叉樹：其中每個節(jié)點都不能有多于兩個兒子

樹的先序遍歷：

樹的中序遍歷：

樹的后序遍歷：

二叉查找樹：

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?