1、第第13章常見數據結構的章常見數據結構的Java實現實現l13.1鏈表鏈表l13.2棧棧l13.3樹集樹集l13.4樹映射樹映射l13.5散列集散列集l13.6散列表散列表l13.7向量向量 13.1 鏈表鏈表l鏈表是由若干個稱作節點的對象組成的一種數據結構，每個節點含有一個數據和下一個節點的引用（單鏈表），或含有一個數據并含有上一個節點的引用和下一個節點的引用（雙鏈表）。LinkedList類中的常用方法類中的常用方法 lpublic boolean add(Object element) 向鏈表末尾添加一個新的節點，該節點中的數據是參數elememt指定的對象。lpublic void a

2、dd(int index ,Object element) 向鏈表的指定位置添加一個新的節點，該節點中的數據是參數elememt指定的對象。lpublic void addFirst(Object element) 向鏈表的頭添加新節點，該節點中的數據是參數elememt指定的對象的引用。lpublic void addLast(Object element) 向鏈表的末尾添加新節點，該節點中的數據是參數elememt指定的對象。lpublic void clear() 刪除鏈表的所有節點，使當前鏈表成為空鏈表。lpublic Object remove(int index) 刪除指定位置上的

3、節點。lpublic boolean remove(Object element) 刪除首次出現含有數據elemen的節點。lpublic Object removeFirst() 刪除第一個節點，并返回這個節點中的對象。lpublic Object removeLast() 刪除最后一個節點對象，并返回這個節點中的對象。lpublic Object get(int index) 得到鏈表中指定位置處節點中的對象。lpublic Object getFirst() 得到鏈表中第一個節點中的對象。lpublic Object getLast() 得到鏈表中最后一個節點中的對象 遍歷鏈表遍歷鏈表

4、l鏈表對象可以使用iterator()方法獲取一個Iterator對象，Iterator對象中每個數據成員剛好是鏈表節點中的數據，而且這些數據成員是按順序存放在Iterator對象中的。Iterator對象使用next()方法可以得到它中的數據成員。顯然，使用Iterator對象遍歷鏈表要比鏈表使用get方法遍歷鏈表的速度快。13.2 棧棧l棧棧是一種“后進先出”的數據結構，只能在一端進行輸入或輸出數據的操作。棧把第一個放入該棧的數據放在最底下，而把后續放入的數據放在已有數據的頂上。向棧中輸入數據的操作稱為“壓棧”，從棧中輸出數據的操作稱為“彈棧”。 l棧對象可以使用 public Objec

5、t push(Object data); 輸入數據，實現壓棧操作.l使用 public Object pop(); 輸出數據，實現彈棧操作。l使用 public boolean empty(); 判斷棧是否還有數據，有數據返回false ，否則返回true。 13.3 樹集樹集l樹集是一些節點組成的數據結構，節點按著樹形一層一層的排列 .lTreeSet來創建一個樹集 ,和鏈表不同的是，用add 方法增加節點時，節點會按其存放的數據的“大小”一層一層地依次排列，在同一層中的節點從左到右遞增排列，下一層的都比上一層的小。l節點對象必須實現Comparable接口，以便樹集比較節點對象的大小關系

6、14.4 樹映射樹映射lTreeMap類實現了Map接口，稱TreeMap對象為樹映射。樹映射使用 public Object put(Object key,Object value) 方法添加節點，該節點不僅存儲著數據value，而且也存儲著和其關聯的關鍵字key，也就是說，樹映射的節點存儲“關鍵字/值”對。和樹集不同的是，樹映射保證節點是按照節點中的關鍵字升序排列。 13.5 散列集散列集 lHashSet類實現了Set接口，可以使用構造方法HashSet（）創建散列集，例如 HashSet set= HashSet(); set可以調用add(Object o)方法將對象添加到集合中，添加到集合中的數據稱做集合的元素。集合不允許有相同的元素，也就是說，如果對象b已經是集合中的元素，那么再執行set.add(b)操作是無效的。 13.6 散列表散列表 l散列表是使用相關關鍵字查找被存儲的數據項的一種數據結構，關鍵字不可以發生邏輯沖突，即不要兩個數據項使用相同的關鍵字，如果出現兩個數據項對應相同的關鍵字，那么，先前散列表中的數據項將被替換。 13.7向量向量lJava的 java.util包中的Vector類負責創建一個那么很容易就會使用向量。當我們創建一個向量時不用象數組那樣必須要給出數組