常見數(shù)據(jù)結(jié)構(gòu)的Java實現(xiàn)

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

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

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

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

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

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