Java語言程序設(shè)計(jì)基礎(chǔ)教程課件(第12章).ppt

《Java語言程序設(shè)計(jì)基礎(chǔ)教程課件(第12章).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第12章　常見數(shù)據(jù)結(jié)構(gòu)的Java實(shí)現(xiàn)鏈表的基本操作棧樹集樹映射散列表散列集向量12.1鏈表線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結(jié)構(gòu)簡單，便于實(shí)現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實(shí)際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列：(a1,a2,a3,…an)n為線性表的長度(n≥0)，n=0的表稱為空表。線性表按其存儲結(jié)構(gòu)可分為順序表和鏈表。用順

2、序存儲結(jié)構(gòu)存儲，也就是將線性表中的數(shù)據(jù)元素依次存放在某個存儲區(qū)域中的表稱為順序表；用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表稱為鏈表。一維數(shù)組是用順序方式存儲的線性表。單鏈表：每個節(jié)點(diǎn)含有一個數(shù)據(jù)和下一個節(jié)點(diǎn)對象的引用；雙鏈表：含有一個數(shù)據(jù)并含有上一個節(jié)點(diǎn)對象的引用和下一個節(jié)點(diǎn)對象的引用。12.1.1鏈表的創(chuàng)建使用java.util包中的LinkedList類，可以創(chuàng)建一個鏈表對象。例如：LinkedListmylist=newLinkedList();//創(chuàng)建了一個空雙鏈表也可以使用add()方法向鏈表依次增加節(jié)點(diǎn)

3、。例如增加節(jié)點(diǎn)：mylist.add(“It”);mylist.add(“is”);mylist.add(“a”);mylist.add(“door”);這樣就形成了4個節(jié)點(diǎn)的鏈表，數(shù)據(jù)依次為“It”、“is”、“a”、“door”，4個節(jié)點(diǎn)是自動鏈接的?！纠?2-1】本例構(gòu)造一個含有４個節(jié)點(diǎn)的鏈表，并輸出節(jié)點(diǎn)中的數(shù)據(jù)。importjava.util.*;publicclassLinkListOne{publicstaticvoidmain(Stringargs[]){LinkedListmylist

4、=newLinkedList();mylist.add("It");//鏈表中的第一個節(jié)點(diǎn)。mylist.add("is");//鏈表中的第二個節(jié)點(diǎn)。mylist.add("a");//鏈表中的第三個節(jié)點(diǎn)。mylist.add("door");//鏈表中的第四個節(jié)點(diǎn)。intnumber=mylist.size();//獲取鏈表的長度。for(inti=0;i

5、點(diǎn)中的數(shù)據(jù):"+temp);}}}程序運(yùn)行結(jié)果如下所示：12.1.2LinkedList類中的常用方法LinkedList的常用方法包括：publicbooleanadd(Objectelement)//向鏈表末尾添加一個新的節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對象。publicvoidadd(intindex,Objectelement)//向鏈表指定位置添加節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對象。publicvoidaddFirst(Objectelement)//向鏈表頭添

6、加新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對象。publicvoidaddLast(Objectelement)//向鏈表尾添加新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對象。publicObjectremoveFirst()//刪除第一個節(jié)點(diǎn)，并返回這個節(jié)點(diǎn)中的對象。publicObjectremoveLast()//刪除最后一個節(jié)點(diǎn)，并返回這個節(jié)點(diǎn)中的對象。publicObjectremove(intindex)//刪除指定位置的節(jié)點(diǎn)publicObjectget(intindex)

7、//得到指定位置的節(jié)點(diǎn)publicObjectgetFirst()//得到鏈表第一個節(jié)點(diǎn)的對象。publicObjectgetLast()//得到鏈表最后一個節(jié)點(diǎn)的對象。intindexOf(Objectelement)：返回節(jié)點(diǎn)對象element在鏈表中首次出現(xiàn)的位置，如果鏈表中無此節(jié)點(diǎn)對象則返回-1。publicintlastIndexOf(Objectelement)：返回節(jié)點(diǎn)對象element在鏈表中最后出現(xiàn)的位置，如果鏈表中無此節(jié)點(diǎn)對象則返回-1。publicObjectset(intind

8、ex,Objectelement)//將當(dāng)前鏈表index位置節(jié)點(diǎn)中的對象替換成參數(shù)element指定的對象，返回被替換對象。publicintsize()//返回量表的長度，即節(jié)點(diǎn)的個數(shù)。publicbooleancontains(Objectelement)：判斷鏈表節(jié)點(diǎn)對象中是否含有element?！纠?2-2】本例包含了LinkedList類中的一些常用方法。importjava.util.*;publicclassep12_2{publicst